1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [Vika 6, Áframhaldandi]

2
00:00:02,520 --> 00:00:04,160
[David J. Malan] [Harvard University]

3
00:00:04,160 --> 00:00:08,720
[Þetta er CS50.] [CS50.TV]

4
00:00:08,720 --> 00:00:12,970
Þetta er CS50 og þetta er í lok 6. viku.

5
00:00:12,970 --> 00:00:17,970
Svo CS50x, eitt af fyrstu námskeið Harvard er þátt í EDX frumkvæði

6
00:00:17,970 --> 00:00:20,590
reyndar frumraun síðasta mánudag.

7
00:00:20,590 --> 00:00:23,460
Ef þú vildi eins og til að fá innsýn í það sem aðrir á Netinu

8
00:00:23,460 --> 00:00:27,180
eru nú eftir með, getur þú höfuð á x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
Það verður sent þig til viðeigandi stað á edx.org,

10
00:00:30,350 --> 00:00:34,160
sem var þar sem þetta og önnur námskeið frá MIT og Berkeley nú lifa.

11
00:00:34,160 --> 00:00:38,140
Þú þarft að skrá þig sem notanda, þú munt komast að því að efnið er að mestu leyti sama

12
00:00:38,140 --> 00:00:42,170
eins og þú hafir fengið þessa önn, að vísu nokkurra vikna seinkun, eins og við fá allt tilbúið.

13
00:00:42,170 --> 00:00:46,930
En hvað nemendur í CS50x mun nú sjá er tengi alveg eins og þessi.

14
00:00:46,930 --> 00:00:50,040
Þetta til dæmis, er Zamyla leiða walkthrough fyrir setja vandamál 0.

15
00:00:50,040 --> 00:00:54,230
Við innskráningu í edx.org, a CS50x nemandi sér tegund af hlutur

16
00:00:54,230 --> 00:00:57,170
þú vildi búast við að sjá í námskeiði: á fyrirlestur í Monday,

17
00:00:57,170 --> 00:01:01,650
fyrirlestur í Wednesday, ýmsar stuttbuxur, vandamálið setur á, walkthroughs, PDFs.

18
00:01:01,650 --> 00:01:04,459
Auk, eins og þú sérð hér, vél þýðingar

19
00:01:04,459 --> 00:01:08,390
á ensku afrit í kínversku, japönsku, spænsku, ítölsku,

20
00:01:08,390 --> 00:01:12,810
og a heild búnt af öðrum tungumálum sem verður örugglega ófullkomin

21
00:01:12,810 --> 00:01:15,840
eins og við rúlla þá út kerfisbundið að nota eitthvað sem heitir API,

22
00:01:15,840 --> 00:01:18,360
eða umsókn forritun tengi, frá Google

23
00:01:18,360 --> 00:01:21,360
sem gerir okkur kleift að umbreyta ensku þessum tungumálum.

24
00:01:21,360 --> 00:01:24,100
En takk fyrir frábæra anda nokkrum hundrað plús sjálfboðaliðum,

25
00:01:24,100 --> 00:01:26,940
handahófi fólk á Netinu, sem hafa boðið boðið að taka þátt

26
00:01:26,940 --> 00:01:30,180
í þessu verkefni, munum við smám saman að bæta gæði þeirra þýðingar

27
00:01:30,180 --> 00:01:35,790
með því að hafa menn leiðrétta mistök sem tölvur okkar hafa gert.

28
00:01:35,790 --> 00:01:42,330
>> Svo kemur í ljós að við höfðum nokkur nemendur mæta á mánudaginn en við reiknuðum upphaflega.

29
00:01:42,330 --> 00:01:48,980
Í staðreynd, nú hefur CS50x 100.000 manns eftirfarandi eftir heima.

30
00:01:48,980 --> 00:01:54,430
Svo grein fyrir að þú ert öll hluti þessa vígslu flokki að þessu námskeiði í tölvunarfræði

31
00:01:54,430 --> 00:01:57,370
menntun almennt, í víðara samhengi, aðgengileg.

32
00:01:57,370 --> 00:02:00,130
Og raunin er nú, með nokkrum af þessum stórfellda online námskeið,

33
00:02:00,130 --> 00:02:04,070
þeir byrja allir með þessum mjög miklu magni, eins og við virðast hafa gert hér.

34
00:02:04,070 --> 00:02:08,759
En markmiðið, að lokum, að CS50x er í raun að fá eins og margir að ljúka við lína eins og kostur er.

35
00:02:08,759 --> 00:02:12,000
Með hönnun, CS50x er að fara að vera í boði frá þessu síðasta Mánudagur

36
00:02:12,000 --> 00:02:17,430
alla leið í gegnum 15 Apr, 2013, þannig að fólk sem hefur skóla skuldbindingar annars staðar,

37
00:02:17,430 --> 00:02:20,990
vinna, fjölskylda, önnur átök og eins, hafa aðeins meiri sveigjanleika

38
00:02:20,990 --> 00:02:23,640
sem að kafa í þessu námskeiði, sem nægja að segja,

39
00:02:23,640 --> 00:02:30,540
er alveg ambitiously gert ef aðeins á meðan aðeins þrjá mánuði á venjulegum önn.

40
00:02:30,540 --> 00:02:34,190
En þessir nemendur verða að takast á við sömu setur vandamál, skoða sama efni,

41
00:02:34,190 --> 00:02:36,350
hafa aðgang að sömu stuttbuxur og þess háttar.

42
00:02:36,350 --> 00:02:38,990
Svo grein fyrir því að við erum öll í raun í þessu saman.

43
00:02:38,990 --> 00:02:42,360
Og einn af the endir markmiðum CS50x er ekki bara til að fá sem margir gott fólk

44
00:02:42,360 --> 00:02:45,720
til að ljúka við lína og gefa þeim þessa nýfundinni skilning á tölvunarfræði

45
00:02:45,720 --> 00:02:49,000
og forritun, en einnig að hafa þá með þessa hluti reynslu.

46
00:02:49,000 --> 00:02:52,010
Eitt af skilgreina eiginleika 50 á háskólasvæðinu, við vonum,

47
00:02:52,010 --> 00:02:56,260
hefur verið svona samfélagsleg reynslu, fyrir betri eða verri, stundum,

48
00:02:56,260 --> 00:02:59,480
en hafa þetta fólk að snúa sér að vinstri og hægri,

49
00:02:59,480 --> 00:03:01,830
og skrifstofa klukkustundir og hackathon og sanngjarnt.

50
00:03:01,830 --> 00:03:04,560
Það er svolítið erfiðara að gera það í eigin persónu með fólkinu á netinu,

51
00:03:04,560 --> 00:03:10,580
en CS50x lýkur í apríl með fyrsta sinn CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
sem verður að vera á netinu í aðlögun hugmynd okkar um sanngjörn

53
00:03:13,630 --> 00:03:18,250
þar sem þessar þúsundir nemenda allt verður boðið að senda inn 1 - til 2-mínútna vídeó,

54
00:03:18,250 --> 00:03:22,480
annaðhvort screencast um lokaverkefni þeirra eða vídeó af þeim veifa halló

55
00:03:22,480 --> 00:03:24,490
og tala um verkefni þeirra og demoing það,

56
00:03:24,490 --> 00:03:27,610
mikið eins og forveri þinn hefur gert hér á háskólasvæðinu á gangvirði,

57
00:03:27,610 --> 00:03:31,400
þannig að í lok hverrar annar, er ætlunin að hafa alþjóðlegt sýningu

58
00:03:31,400 --> 00:03:37,080
endanlega verkefni CS50x nemenda, eins og það sem bíður þér þetta desember hér á háskólasvæðinu.

59
00:03:37,080 --> 00:03:39,680
Svo meira um það á næstu mánuðum.

60
00:03:39,680 --> 00:03:43,640
>> Með 100.000 nemendur, þó kemur, þörf fyrir nokkra CAS.

61
00:03:43,640 --> 00:03:47,590
Í ljósi þess að þú krakkar eru að ryðja brautina hér og taka CS50

62
00:03:47,590 --> 00:03:51,630
nokkrar vikur áður en gefa út þetta efni er til gott fólk á EDX,

63
00:03:51,630 --> 00:03:55,330
grein við myndum elska að taka eins og margir af eigin nemendum okkar og hægt er í þessu verkefni,

64
00:03:55,330 --> 00:03:58,720
bæði á önn auk vetur og þetta kemur vor.

65
00:03:58,720 --> 00:04:01,620
Svo ef þú vilt taka þátt í CS50x,

66
00:04:01,620 --> 00:04:07,450
sérstaklega að taka þátt í á CS50x ræða, þá EDX útgáfa af CS50 ræða,

67
00:04:07,450 --> 00:04:10,140
sem margir ykkar hafa verið að nota á háskólasvæðinu, the online bulletin borð,

68
00:04:10,140 --> 00:04:13,040
skaltu ekki höfuð til að vefslóð, láttu okkur vita hver þú ert,

69
00:04:13,040 --> 00:04:16,450
vegna þess að við myndum elska að byggja upp lið af nemendum og starfsfólki og kenndu jafnt

70
00:04:16,450 --> 00:04:19,630
á háskólasvæðinu, sem eru einfaldlega að spila með og hjálpa út.

71
00:04:19,630 --> 00:04:21,720
Og þegar þeir sjá spurningu sem er kunnuglegt við þá,

72
00:04:21,720 --> 00:04:25,320
þú heyrir nemandi skýrslur sumir padda einhvers staðar þarna úti í einhverju landi á Netinu,

73
00:04:25,320 --> 00:04:27,450
Og það hringir bjöllu vegna þess að þú hafði líka þessi sömu mál

74
00:04:27,450 --> 00:04:32,620
í þínu d-sal fyrir nokkru, vonandi þá getur Chime í og ​​deila eigin reynslu.

75
00:04:32,620 --> 00:04:37,300
Svo skaltu ekki taka þátt ef þú vilt.

76
00:04:37,300 --> 00:04:39,360
>> Tölvunarfræði námskeið við Harvard hafa a hluti af hefð,

77
00:04:39,360 --> 00:04:44,730
CS50 meðal þeirra, af því að hafa nokkur fatnaður, föt, sem hægt er að klæðast með stolti

78
00:04:44,730 --> 00:04:49,090
í lok hverrar annar og sagði alveg stoltur að þú lokið CS50

79
00:04:49,090 --> 00:04:51,830
og tók CS50 og þess háttar, og við reynum alltaf að taka nemendur

80
00:04:51,830 --> 00:04:54,540
í þessu ferli eins mikið og mögulegt er, þar sem við bjóðum,

81
00:04:54,540 --> 00:04:56,900
í kringum þennan tíma önn, nemendur að skila hönnun

82
00:04:56,900 --> 00:04:59,330
nota Photoshop eða hvað tól sem þú velur þú vilt nota

83
00:04:59,330 --> 00:05:02,330
Ef þú ert hönnuður, til að leggja hönnun fyrir T-skyrta og sweatshirts

84
00:05:02,330 --> 00:05:06,100
og regnhlífar og lítil bandanas fyrir hunda sem við höfum nú og þess háttar.

85
00:05:06,100 --> 00:05:09,370
Og allt er svo - sigurvegari á hverju ári er þá sýnd

86
00:05:09,370 --> 00:05:12,700
á heimasíðu Námskeiðið er á store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Allt er selt á kostnaðarverði þar, en website bara rekur sig

88
00:05:15,790 --> 00:05:18,330
og leyfa fólki að velja liti og hönnun, sem þeir vilja.

89
00:05:18,330 --> 00:05:20,420
Þannig að ég hélt að við myndum bara deila sumir af hönnun á síðasta ári

90
00:05:20,420 --> 00:05:25,130
sem voru á vefsíðu auk þessa hér, sem er árleg hefð.

91
00:05:25,130 --> 00:05:29,410
"Á hverjum degi Ég Seg Faultn" var eitt af uppgjöf á síðasta ári,

92
00:05:29,410 --> 00:05:32,290
sem er enn til staðar þarna fyrir Alumni.

93
00:05:32,290 --> 00:05:35,820
Við höfðum þetta einn, "CS50, Stofnað 1989."

94
00:05:35,820 --> 00:05:39,010
Einn af Bowdens okkar, Rob, var mjög vinsæl í fyrra.

95
00:05:39,010 --> 00:05:43,480
"Team Bowden" fæddist, var þessi hönnun lögð meðal efstu seljendur.

96
00:05:43,480 --> 00:05:49,040
Eins var þetta hérna. Margir höfðu "Bowden Fever" í samræmi við sölu logs.

97
00:05:49,040 --> 00:05:52,650
Gera sér grein fyrir að það gæti nú verið hönnun þar, upp á Netinu.

98
00:05:52,650 --> 00:05:57,510
Nánari upplýsingar um þetta í næsta vandamál setur að koma.

99
00:05:57,510 --> 00:06:00,330
>> Einn fleiri tól: þú hefur haft nokkur áhrif og vonandi er

100
00:06:00,330 --> 00:06:02,350
sumir snertið ekki-á reynsla með GDB,

101
00:06:02,350 --> 00:06:04,570
sem er, auðvitað, a aflúsara og gerir þér kleift að stjórna

102
00:06:04,570 --> 00:06:09,500
program á tiltölulega lágu stigi, að gera hvers konar hluti?

103
00:06:09,500 --> 00:06:13,030
Hvað er GDB láta þig gera?

104
00:06:13,030 --> 00:06:15,030
Já? Gefðu mér eitthvað. [Námsmaður svar, óskiljanlegur]

105
00:06:15,030 --> 00:06:18,120
Gott. Skref í aðgerð, þannig að þú ert ekki bara að slá hlaupa

106
00:06:18,120 --> 00:06:22,310
og hafa forritið blása gegnum heild sinni, prenta út það við hefðbundna framleiðslu.

107
00:06:22,310 --> 00:06:25,190
Frekar er hægt að stíga í gegnum hann línu fyrir línu, annaðhvort skrifa næst

108
00:06:25,190 --> 00:06:30,300
að fara línu fyrir línu eða skref til að kafa í aðgerð, venjulega einn sem þú skrifaðir.

109
00:06:30,300 --> 00:06:35,240
Hvað annað er GDB láta þig gera? Já? [Námsmaður svar, óskiljanlegur]

110
00:06:35,240 --> 00:06:38,100
Prenta breytur. Svo ef þú vilt gera smá sjálfsskoðun inni í forritinu

111
00:06:38,100 --> 00:06:41,500
án þess að þurfa að grípa til að skrifa printf yfirlýsingar um allt,

112
00:06:41,500 --> 00:06:44,600
þú getur bara prentað breytu eða birta breytu.

113
00:06:44,600 --> 00:06:46,710
Hvað annað er hægt að gera með aflúsara eins gdb?

114
00:06:46,710 --> 00:06:49,170
[Námsmaður svar, óskiljanlegur]

115
00:06:49,170 --> 00:06:52,080
Einmitt. Þú getur stillt Rofstaðir, þú getur sagt brjóta framkvæmd

116
00:06:52,080 --> 00:06:54,020
á meginvirkni eða foo virka.

117
00:06:54,020 --> 00:06:56,800
Það má segja að brjóta framkvæmd í línu 123.

118
00:06:56,800 --> 00:06:58,950
Og breakpoints eru mjög öflug tækni

119
00:06:58,950 --> 00:07:01,110
því ef þú ert með almenna tilfinningu um hvar vandamálið

120
00:07:01,110 --> 00:07:05,360
líklega er, þú þarft ekki að eyða tíma stepping í heild áætlunarinnar.

121
00:07:05,360 --> 00:07:08,250
Þú getur í raun hoppa þarna og þá byrja að slá -

122
00:07:08,250 --> 00:07:10,970
stepping í gegnum það með skref eða næsta eða eins.

123
00:07:10,970 --> 00:07:14,340
En aflinn með eitthvað eins og gdb er að það hjálpar þér, manna,

124
00:07:14,340 --> 00:07:16,940
finna vandamál og finna galla þínum.

125
00:07:16,940 --> 00:07:19,470
Það þýðir ekki endilega að finna þá svo mikið fyrir þig.

126
00:07:19,470 --> 00:07:23,070
>> Þannig að við kynntum um daginn style50, sem er stutt stjórn lína tól

127
00:07:23,070 --> 00:07:27,500
sem reynir að stylize númerið þitt svolítið meira eðlilega en þú,, manna gæti hafa gert.

128
00:07:27,500 --> 00:07:29,530
En það líka er í raun bara fagurfræði hlutur.

129
00:07:29,530 --> 00:07:34,110
En það kemur í ljós að það er þetta önnur tól gestur Valgrind sem er lítið meira Bogagöng að nota.

130
00:07:34,110 --> 00:07:36,860
Framleiðsla hennar er atrociously Cryptic við fyrstu sýn.

131
00:07:36,860 --> 00:07:39,420
En það er frábærlega vel, sérstaklega núna þegar við erum á hluta tíma

132
00:07:39,420 --> 00:07:43,080
þar sem þú ert að byrja að nota malloc og dynamic minni úthlutun.

133
00:07:43,080 --> 00:07:45,420
Hlutur getur farið mjög, mjög rangt fljótt.

134
00:07:45,420 --> 00:07:49,320
Vegna þess að ef þú gleymir að losa minni þitt, eða þú dereference sumir NULL músina,

135
00:07:49,320 --> 00:07:55,770
eða þú dereference sumir sorp músina, það er yfirleitt einkenni sem niðurstöður?

136
00:07:55,770 --> 00:07:59,470
Seg kenna. Og þú færð þessa algerlega skrá einhvers fjölda kílóbæti eða megabæti

137
00:07:59,470 --> 00:08:02,990
sem sýnir stöðu minni program þegar það hrundi,

138
00:08:02,990 --> 00:08:05,730
en program seg lokum galla, skiptingu kenna,

139
00:08:05,730 --> 00:08:08,450
sem þýðir eitthvað slæmt gerðist nánast alltaf tengd

140
00:08:08,450 --> 00:08:11,750
á minni sem tengist mistök sem þú gerðir eitthvað.

141
00:08:11,750 --> 00:08:14,100
Svo hjálpar Valgrind að finna hluti eins og þetta.

142
00:08:14,100 --> 00:08:17,720
Það er tól sem þú keyrir, eins gdb, eftir að þú hefur safnað saman program,

143
00:08:17,720 --> 00:08:20,330
heldur en að keyra forrit beint, hlaupa þú Valgrind

144
00:08:20,330 --> 00:08:23,960
og þú fara að því program, rétt eins og þú gerir við GDB.

145
00:08:23,960 --> 00:08:26,220
Nú, notkun, til að fá bestu konar framleiðsla,

146
00:08:26,220 --> 00:08:30,410
er svolítið langur, svo þarna efst á skjánum sem þú munt sjá Valgrind-v.

147
00:08:30,410 --> 00:08:35,350
"-V" nánast almennt þýðir fjölorður þegar þú ert að nota forrit á Linux tölvu.

148
00:08:35,350 --> 00:08:38,770
Svo þýðir það spýta út fleiri upplýsingar en þú gætir sjálfgefið.

149
00:08:38,770 --> 00:08:45,510
"- Leka-stöðva = fullur." Þetta er bara að segja stöðva fyrir öllum mögulegum leka minni,

150
00:08:45,510 --> 00:08:49,430
mistök sem gætu hafa ég gerði. Þetta líka, er sameiginlegt mynstur með Linux forrit.

151
00:08:49,430 --> 00:08:52,710
Almennt, ef þú hafa a lína rifrildi sem er "rofi",

152
00:08:52,710 --> 00:08:55,830
sem er ætlað að breyta hegðun forritsins, og það er eitt bréf,

153
00:08:55,830 --> 00:09:00,310
það er-V, en ef það er kveikt, bara með hönnun forritari,

154
00:09:00,310 --> 00:09:05,150
er fullt orð eða röð af orðum, stjórn lína rifrildi byrjar -.

155
00:09:05,150 --> 00:09:08,190
Þetta eru bara menn samninga, en þú munt sjá þá í auknum mæli.

156
00:09:08,190 --> 00:09:12,410
Og svo, að lokum, "a.out" er handahófskennt nafn fyrir the program í þessu tiltekna dæmi.

157
00:09:12,410 --> 00:09:14,640
Og hér er einhver fulltrúi framleiðsla.

158
00:09:14,640 --> 00:09:22,890
>> Áður en við lítum á það sem gæti þýtt, láta mig fara yfir í kóða hérna.

159
00:09:22,890 --> 00:09:26,390
Og láta mig færa þetta út af the vegur, kemur bráðum,

160
00:09:26,390 --> 00:09:32,120
og við skulum kíkja á memory.c, sem er þessi stutta dæmi hér.

161
00:09:32,120 --> 00:09:36,290
Svo í þessari áætlun, að láta mig stækka aðgerðir og spurningar.

162
00:09:36,290 --> 00:09:39,430
Við höfum fall helstu sem kallar fall, F,

163
00:09:39,430 --> 00:09:45,590
og þá hvað er f halda áfram að gera, í aðeins tæknilega ensku?

164
00:09:45,590 --> 00:09:49,760
Hvað f halda áfram að gera?

165
00:09:49,760 --> 00:09:53,680
Hvernig væri að ég ætla að byrja með línu 20, og staðsetningu stjarnan er ekki máli,

166
00:09:53,680 --> 00:09:56,720
en ég ætla bara að vera í samræmi hér við síðasta fyrirlestur.

167
00:09:56,720 --> 00:09:59,910
Hvað er lína 20 gera fyrir okkur? Á vinstri hönd. Við munum brjóta niður frekar.

168
00:09:59,910 --> 00:10:02,410
Int * x: hvað þýðir það að gera?

169
00:10:02,410 --> 00:10:04,940
Allt í lagi. Það að lýsa yfir með músina, og nú skulum vera enn meira tæknilega.

170
00:10:04,940 --> 00:10:10,230
Hvað þýðir það, mjög concretely, að lýsa yfir músina? Einhver annar?

171
00:10:10,230 --> 00:10:15,050
Já? [Námsmaður svar, óskiljanlegur] of langt.

172
00:10:15,050 --> 00:10:17,060
Svo þú ert að lesa á the réttur-hönd hlið af the jafna tákn.

173
00:10:17,060 --> 00:10:20,290
Við skulum einblína bara á vinstri, bara á int * x.

174
00:10:20,290 --> 00:10:24,700
Þetta er "lýsa" bendi, en nú skulum kafa í dýpra í þeirri skilgreiningu.

175
00:10:24,700 --> 00:10:28,330
Hvað þýðir að concretely, tæknilega meina? Já?

176
00:10:28,330 --> 00:10:31,940
[Námsmaður svar, óskiljanlegur]

177
00:10:31,940 --> 00:10:35,090
Allt í lagi. Það er að undirbúa að vista veffang í minni.

178
00:10:35,090 --> 00:10:40,680
Gott. Og við skulum taka þetta einu skrefi lengra, það er að lýsa yfir breytu, x, sem er 32 bita.

179
00:10:40,680 --> 00:10:44,440
Og ég veit að það er 32 bita vegna þess að -?

180
00:10:44,440 --> 00:10:47,390
Það er ekki vegna þess að það er int, því það er bendi í þessu tilfelli.

181
00:10:47,390 --> 00:10:49,650
Tilviljun að það er eitt og hið sama með int,

182
00:10:49,650 --> 00:10:51,970
en sú staðreynd að það er stjarna þarna þýðir þetta er bendillinn

183
00:10:51,970 --> 00:10:57,300
og í tækinu, eins og með margar tölvur, en ekki allir, eru ábendingum 32 bits.

184
00:10:57,300 --> 00:11:01,850
Á fleiri nútíma vélbúnaði eins nýjustu Macs, nýjustu tölvur, þú might hafa 64-bita punkta,

185
00:11:01,850 --> 00:11:04,160
en í tækinu eru þetta 32 bita.

186
00:11:04,160 --> 00:11:08,380
Svo munum við staðla á því. Meira concretely, sagan fer sem hér segir:

187
00:11:08,380 --> 00:11:10,820
Við "lýsa" bendi, hvað þýðir það?

188
00:11:10,820 --> 00:11:12,810
Við undirbúning að geyma minni heimilisfang.

189
00:11:12,810 --> 00:11:15,530
Hvað þýðir það?

190
00:11:15,530 --> 00:11:19,810
Við að búa til breytu kallað X sem tekur upp 32 bita

191
00:11:19,810 --> 00:11:23,810
sem mun brátt geyma veffang heiltala.

192
00:11:23,810 --> 00:11:26,470
Og það er líklega um eins nákvæm og við getum fengið.

193
00:11:26,470 --> 00:11:31,810
Það er í lagi að færa fram til að einfalda heiminn og segja bara lýsa bendi heitir x.

194
00:11:31,810 --> 00:11:35,380
Kunngjörið bendi, en átta sig og skilja hvað er í raun að gerast

195
00:11:35,380 --> 00:11:38,490
jafnvel í aðeins þeim nokkrum stöfum.

196
00:11:38,490 --> 00:11:42,040
>> Nú, þetta er nánast svolítið auðveldara, jafnvel þótt það sé lengri tjáningu.

197
00:11:42,040 --> 00:11:48,160
Svo hvað er þetta að gera, það er lögð áhersla á núna: "malloc (10 * sizeof (int));" Já?

198
00:11:48,160 --> 00:11:52,350
[Námsmaður svar, óskiljanlegur]

199
00:11:52,350 --> 00:11:58,250
Gott. Og ég tek það þar. Það er úthlutun klumpur af minni fyrir tíu heiltölur.

200
00:11:58,250 --> 00:12:02,190
Og nú skulum kafa örlítið dýpra, það er úthlutun klumpur af minni fyrir tíu heiltölur.

201
00:12:02,190 --> 00:12:05,390
Hvað er malloc aftur þá?

202
00:12:05,390 --> 00:12:10,390
Heimilisfang þess klumpur, eða fleiri concretely, heimilisfang fyrstu bæti þess klumpur.

203
00:12:10,390 --> 00:12:14,080
Hvernig þá er ég forritari, að vita hvar þessi klumpur af endum minni?

204
00:12:14,080 --> 00:12:18,340
Ég veit að það er samliggjandi. Malloc, samkvæmt skilgreiningu, mun gefa þér samfelldu klumpur af minni.

205
00:12:18,340 --> 00:12:21,240
Engar eyður í henni. Þú hefur aðgang að öllum bæti í því klumpur,

206
00:12:21,240 --> 00:12:26,760
aftur til baka til baka, en hvernig veit ég hvar í lok þessa klumpur af minni er?

207
00:12:26,760 --> 00:12:28,850
Þegar þú notar malloc? [Námsmaður svar, óskiljanlegur] Good.

208
00:12:28,850 --> 00:12:30,670
Þú gerir það ekki. Þú þarft að muna.

209
00:12:30,670 --> 00:12:35,960
Ég verð að muna að ég notaði verðmæti 10, og ég er ekki einu sinni virðist hafa gert það hér.

210
00:12:35,960 --> 00:12:41,000
En kvöð er algjörlega á mig. Strlen, sem við höfum orðið örlítið reiðir sig á fyrir strengi,

211
00:12:41,000 --> 00:12:45,860
virkar einungis vegna þessa samnings að hafa \ 0

212
00:12:45,860 --> 00:12:48,840
eða þetta sérstaka NUL karakter, NUL, í lok streng.

213
00:12:48,840 --> 00:12:51,740
Það þýðir ekki að halda að aðeins handahófi klumpur af minni.

214
00:12:51,740 --> 00:12:58,590
Það er komið að þér. Svo línu 20, þá úthlutar, klumpur af minni

215
00:12:58,590 --> 00:13:02,590
sem getur geymt tíu heiltölur, og það geymir veffang fyrstu bæti

216
00:13:02,590 --> 00:13:05,610
þess klumpur af minni í breytu sem heitir x.

217
00:13:05,610 --> 00:13:11,140
Ergo, sem er stiga. Svo línu 21, því miður, voru mistök.

218
00:13:11,140 --> 00:13:16,110
En fyrst, hvað er það að gera? Það er að segja verslun á stað 10, 0 verðtryggð,

219
00:13:16,110 --> 00:13:19,480
á klumpur af minni kallast x gildi 0.

220
00:13:19,480 --> 00:13:21,510
>> Svo taka a par af hlutur að fara á.

221
00:13:21,510 --> 00:13:25,420
Jafnvel þó að x er bendillinn, muna frá fáeinum vikum

222
00:13:25,420 --> 00:13:29,440
að þú getur samt notað array-stíl ferningur krappi tákn.

223
00:13:29,440 --> 00:13:36,180
Vegna þess að það er í raun stutt-hönd tákn fyrir meira Cryptic-útlit músina tölur.

224
00:13:36,180 --> 00:13:40,320
þar sem við myndum gera eitthvað eins og this: Taktu heimilisfang x, færa 10 blettur yfir,

225
00:13:40,320 --> 00:13:44,550
þá fara þar til hvað netfang er geymd á þeim stað.

226
00:13:44,550 --> 00:13:48,090
En hreinskilnislega, þetta er bara grimmilegur að lesa og fá þægilegri með.

227
00:13:48,090 --> 00:13:52,900
Svo notar heimurinn vanalega hornklofum bara vegna þess að það er svo miklu fleiri manna-vingjarnlegur að lesa.

228
00:13:52,900 --> 00:13:55,140
En það er það sem er raunverulega að gerast undir hetta,

229
00:13:55,140 --> 00:13:58,190
x er heimilisfang, ekki fylki, í sjálfu sér.

230
00:13:58,190 --> 00:14:02,410
Þannig að þetta er að geyma 0 í stað 10 í x.

231
00:14:02,410 --> 00:14:06,120
Af hverju er þetta slæmt? Já?

232
00:14:06,120 --> 00:14:17,370
[Námsmaður svar, óskiljanlegur] Einmitt.

233
00:14:17,370 --> 00:14:21,100
Við úthlutað aðeins tíu ints, en við telja frá 0 þegar forritun í C,

234
00:14:21,100 --> 00:14:25,690
þannig að þú hefur aðgang að 0 1 2 3 4 5 6 7 8 9 en ekki 10.

235
00:14:25,690 --> 00:14:30,270
Svo annað hvort forritið er að fara að seg kenna eða það er ekki.

236
00:14:30,270 --> 00:14:32,900
En við í raun ekki vita, þetta er tegund af nondeterministic hegðun.

237
00:14:32,900 --> 00:14:35,600
Það fer alveg eftir hvort við heppinn.

238
00:14:35,600 --> 00:14:40,650
Ef það kemur í ljós að stýrikerfið er ekki sama hvort ég nota þessi auka bæti,

239
00:14:40,650 --> 00:14:43,360
jafnvel þótt það hafi ekki gefið mér það, program minn gæti ekki hrun.

240
00:14:43,360 --> 00:14:46,780
Það er hrár, það er þrjótur, en þú might ekki sjá þessi einkenni,

241
00:14:46,780 --> 00:14:48,960
eða þú gætir séð hana aðeins einu sinni í a á meðan.

242
00:14:48,960 --> 00:14:51,230
En raunin er að villan sé í raun.

243
00:14:51,230 --> 00:14:54,320
Og það er mjög erfitt ef þú hefur skrifað forrit sem þú vilt vera rétt,

244
00:14:54,320 --> 00:14:58,840
að þú hefur selt forrit sem fólk notar að sérhver einu sinni í a á meðan hrun

245
00:14:58,840 --> 00:15:02,450
vegna þess, að sjálfsögðu, þetta er ekki gott. Í staðreynd, ef þú ert með Android símann eða iPhone

246
00:15:02,450 --> 00:15:05,550
og þú sækir forrit þessa dagana, ef þú hefur einhvern tímann fengið app bara hætta,

247
00:15:05,550 --> 00:15:10,040
allt í einu að það hverfur, það er nánast alltaf afleiðing af minni sem tengist mál,

248
00:15:10,040 --> 00:15:12,830
þar sem forritari ruglaður upp og dereferenced bendi

249
00:15:12,830 --> 00:15:18,670
að hann ætti ekki að hafa, og afleiðing af IOS eða Android er bara að drepa forrit öllu

250
00:15:18,670 --> 00:15:23,080
frekar en áhættu óskilgreindu hegðun eða einhvers konar málamiðlun öryggi.

251
00:15:23,080 --> 00:15:25,950
>> Það er einn annar galla í þessu forriti nema þessu.

252
00:15:25,950 --> 00:15:30,180
Hvað annað hef ég ruglaður upp í þessu forriti?

253
00:15:30,180 --> 00:15:32,740
Ég hef ekki æft það sem ég hef boðað. Já?

254
00:15:32,740 --> 00:15:34,760
[Námsmaður svar, óskiljanlegur] Good.

255
00:15:34,760 --> 00:15:36,880
Ég hef ekki frelsi minni. Svo þumalputtaregla nú

256
00:15:36,880 --> 00:15:43,150
þarf að vera hvenær sem þú kalla malloc, þú verður að hringja frítt þegar þú ert búinn að nota þessi minni.

257
00:15:43,150 --> 00:15:45,610
Nú, þegar ég myndi vilja til að losa þetta minni?

258
00:15:45,610 --> 00:15:49,780
Sennilega, miðað þessi fyrsta lína var rétt, myndi ég vilja til að gera það hér.

259
00:15:49,780 --> 00:15:55,710
Þar sem ég gat ekki, til dæmis, gera það hérna. Hvers vegna?

260
00:15:55,710 --> 00:15:57,860
Bara út af umfangi. Svo jafnvel þó að við erum að tala um ábendingum,

261
00:15:57,860 --> 00:16:04,830
þetta er viku 2 eða 3 mál, þar sem x er aðeins í umfangi inni á hrokkið axlabönd þar var lýst.

262
00:16:04,830 --> 00:16:11,000
Svo þú ákveðið getur ekki losa það þar. Eina von mín til losa það er um það bil eftir línu 21.

263
00:16:11,000 --> 00:16:15,170
Þetta er frekar einfalt forrit, það var nokkuð auðvelt þegar þú vafði konar hugann

264
00:16:15,170 --> 00:16:17,870
um hvaða forrit er að gera, þar sem mistök voru.

265
00:16:17,870 --> 00:16:20,500
Og jafnvel ef þú hefur ekki séð hann í fyrstu, vonandi er það svolítið augljóst nú

266
00:16:20,500 --> 00:16:23,870
að þessi mistök eru nokkuð auðvelt að leysa og auðveldlega gert.

267
00:16:23,870 --> 00:16:28,720
En þegar forrit er meira en 12 línur lengi, það er 50 línur lengi, 100 línur lengi,

268
00:16:28,720 --> 00:16:31,150
ganga í gegnum línu númer með því að línu, hugsa um það rökrétt,

269
00:16:31,150 --> 00:16:35,110
er mögulegt en ekki sérstaklega gaman að gera, stöðugt að leita að galla,

270
00:16:35,110 --> 00:16:38,340
og það er líka erfitt að gera, og það er ástæðan fyrir tól eins Valgrind til.

271
00:16:38,340 --> 00:16:40,900
Leyfðu mér að fara á undan og gera þetta: láta mig opna Terminal gluggann minn,

272
00:16:40,900 --> 00:16:45,400
og láta mig ekki bara að keyra minni, því minni virðist vera fínn.

273
00:16:45,400 --> 00:16:49,180
Ég ætla að fá heppinn. Fara til að auka bæti í lok fylkisins

274
00:16:49,180 --> 00:16:51,060
virðist ekki vera of erfið.

275
00:16:51,060 --> 00:16:56,370
En láta mig, engu að síður, gera geðheilsu stöðva, sem þýðir bara að athuga

276
00:16:56,370 --> 00:16:58,320
hvort þetta er í raun rétt.

277
00:16:58,320 --> 00:17:04,690
>> Svo skulum gera valgrind-v - leka-stöðva = fullur,

278
00:17:04,690 --> 00:17:07,520
og þá er nafn af the program í þessu tilfelli minni, ekki a.out.

279
00:17:07,520 --> 00:17:10,760
Svo láta mig fara á undan og gera það. Hit inn.

280
00:17:10,760 --> 00:17:14,109
Kæri Guð. Þetta er afrakstur hennar, og þetta er það sem ég benti á áðan.

281
00:17:14,109 --> 00:17:17,550
En ef þú lærir að lesa í gegnum allt bull hér,

282
00:17:17,550 --> 00:17:20,760
flest af þessu er bara sjúkdómsgreiningar framleiðsla sem er ekki áhugavert.

283
00:17:20,760 --> 00:17:24,829
Hvaða auga þitt raunverulega vill að leita að er minnst á villur eða öryrki.

284
00:17:24,829 --> 00:17:26,800
Orð sem stinga vandamál.

285
00:17:26,800 --> 00:17:29,340
Og reyndar, við skulum sjá hvað er að gerast rangt hérna.

286
00:17:29,340 --> 00:17:35,230
Ég er með yfirlit af einhverju tagi, "í notkun á brottför:. 40 bæti í 1 blokkum"

287
00:17:35,230 --> 00:17:38,750
Ég er ekki alveg viss hvað blokk er enn, en 40 bæti

288
00:17:38,750 --> 00:17:41,260
raunverulega líður eins og ég gæti fundið út hvar það kemur frá.

289
00:17:41,260 --> 00:17:45,030
40 bæti. Hvers vegna er 40 bæti í notkun á hætta?

290
00:17:45,030 --> 00:17:48,780
Og sérstaklega, ef við skruna niður hér,

291
00:17:48,780 --> 00:17:54,520
Hvers vegna hef ég misst örugglega 40 bæti? Já?

292
00:17:54,520 --> 00:17:59,520
[Námsmaður svar, óskiljanlegur] Perfect. Já, nákvæmlega.

293
00:17:59,520 --> 00:18:03,540
Það voru tíu heiltölur, og hver þeirra er stærð 4, eða 32 bita,

294
00:18:03,540 --> 00:18:08,300
þannig að ég hef misst nákvæmlega 40 bæti, því eins og þú lagt, ég hef ekki kallað frjáls.

295
00:18:08,300 --> 00:18:13,460
Það er ein villa, og nú skulum líta niður aðeins lengra og sjá við hliðina á þessu,

296
00:18:13,460 --> 00:18:16,900
"Ógilt skrifa af stærð 4." Nú hvað er þetta?

297
00:18:16,900 --> 00:18:21,150
Þetta netfang er lýst hvaða stöð tákn, virðist?

298
00:18:21,150 --> 00:18:23,640
Þetta er sextánskur, og hvenær þú sérð númer byrjar á 0x,

299
00:18:23,640 --> 00:18:29,410
það þýðir sextánskur, sem við gerðum leið aftur í, ég held, kafla pset 0 um spurningum,

300
00:18:29,410 --> 00:18:34,090
sem var bara að gera warmup æfa, umbreyta aukastaf að álög til tvöfaldur og svo framvegis.

301
00:18:34,090 --> 00:18:39,220
Sextánskt, bara með því að mönnum venju, er oftast notuð til að tákna punkta

302
00:18:39,220 --> 00:18:41,570
eða, almennt, fjallar um. Það er bara venju,

303
00:18:41,570 --> 00:18:45,340
því það er svolítið auðveldara að lesa, það er a lítill fleiri samningur en eitthvað eins og tugabrot,

304
00:18:45,340 --> 00:18:47,720
og tvöfaldur er gagnslaus fyrir flest menn að nota.

305
00:18:47,720 --> 00:18:50,840
Svo nú hvað þýðir þetta? Jæja, það lítur út eins og það er ógilt skrifa

306
00:18:50,840 --> 00:18:54,480
stærð 4 á línu 21 í memory.c.

307
00:18:54,480 --> 00:18:59,180
Svo við skulum fara aftur á línu 21, og reyndar, hér er það ógilt skrifa.

308
00:18:59,180 --> 00:19:02,640
Svo Valgrind er ekki að fara að alveg að halda í hendina á mér og segja mér hvað festa er,

309
00:19:02,640 --> 00:19:05,520
en það er að finna að ég er að gera ógilt skrifa.

310
00:19:05,520 --> 00:19:08,800
Ég er snerta 4 bæti sem ég ætti ekki að vera, og greinilega er það vegna þess,

311
00:19:08,800 --> 00:19:13,960
eins og þú bent á, ég er að gera [10] í stað [9] hámarks

312
00:19:13,960 --> 00:19:16,660
eða [0] eða eitthvað þar á milli.

313
00:19:16,660 --> 00:19:19,690
Með Valgrind, átta sig hvenær sem þú ert nú að skrifa forrit

314
00:19:19,690 --> 00:19:24,190
sem notar ábendingum og notar minni og malloc nánar tiltekið,

315
00:19:24,190 --> 00:19:27,080
ákveðið að fá inn í vana að keyra þetta lengi

316
00:19:27,080 --> 00:19:30,890
en mjög auðvelt að afrita og líma stjórn Valgrind

317
00:19:30,890 --> 00:19:32,650
til að sjá hvort það er einhver villa þar.

318
00:19:32,650 --> 00:19:34,820
Og það verður yfirþyrmandi hvert skipti sem þú sérð framleiðsla,

319
00:19:34,820 --> 00:19:39,430
en bara flokka í gegnum sjónrænt öll framleiðsla og sjá hvort þú sérð nefnir villur

320
00:19:39,430 --> 00:19:43,190
eða varnaðarorð eða ógilt eða glataður.

321
00:19:43,190 --> 00:19:46,200
Hvaða orð sem hljóma eins og þú ruglaður upp einhvers staðar.

322
00:19:46,200 --> 00:19:48,580
Svo átta sig á að það er nýtt tæki í tól þitt.

323
00:19:48,580 --> 00:19:51,270
>> Nú á mánudaginn, við höfðum a heild búnt af fólkinu komið upp hér

324
00:19:51,270 --> 00:19:53,150
og tákna hugmynd um tengda lista.

325
00:19:53,150 --> 00:20:00,970
Og við kynntum tengda listanum sem lausn á því vandamál?

326
00:20:00,970 --> 00:20:04,590
Já? [Námsmaður svar, óskiljanlegur] Good.

327
00:20:04,590 --> 00:20:06,530
Fylki er ekki minni við þá.

328
00:20:06,530 --> 00:20:09,440
Ef úthluta á fjölbreytta stærð 10, það er allt sem þú færð.

329
00:20:09,440 --> 00:20:13,690
Þú getur hringt í virka eins realloc ef þú kallaðir upphaflega malloc,

330
00:20:13,690 --> 00:20:17,580
og að geta reynt að vaxa array ef það er pláss undir lok þess

331
00:20:17,580 --> 00:20:21,610
sem enginn annar er að nota, og ef það er ekki, það verður bara að finna þér stærri klumpur annars staðar.

332
00:20:21,610 --> 00:20:25,040
En þá er það mun afrita allar þessar bæti í nýju fylki.

333
00:20:25,040 --> 00:20:28,310
Þetta hljómar eins og mjög réttri lausn.

334
00:20:28,310 --> 00:20:34,790
Hvers vegna er þetta óaðlaðandi?

335
00:20:34,790 --> 00:20:36,940
Ég meina það virkar, hafa menn leyst þetta vandamál.

336
00:20:36,940 --> 00:20:40,710
Af hverju gerði við þurfum að leysa það á mánudaginn með tengd listum? Já?

337
00:20:40,710 --> 00:20:44,060
[Námsmaður svar, óskiljanlegur] Það gæti tekið langan tíma.

338
00:20:44,060 --> 00:20:49,260
Í raun, á meðan þú ert að hringja malloc eða realloc eða calloc, sem er enn einn,

339
00:20:49,260 --> 00:20:52,470
hvenær sem þú, the program, eru að tala um stýrikerfi,

340
00:20:52,470 --> 00:20:54,310
þú hættir að hægja forritið niður.

341
00:20:54,310 --> 00:20:57,470
Og ef þú ert að gera þessar tegundir af hlutum í lykkjur, þú ert virkilega hægur hlutur dúnn.

342
00:20:57,470 --> 00:21:00,740
Þú ert ekki að fara að taka þetta fyrir einföldustu "Halló heimur" tegund programs,

343
00:21:00,740 --> 00:21:04,300
en í miklu stærri verkefnum, spyrja stýrikerfið aftur og aftur fyrir minni

344
00:21:04,300 --> 00:21:07,520
eða gefa það aftur og aftur hefur tilhneigingu til að vera gott.

345
00:21:07,520 --> 00:21:11,210
Auk, það er bara svoleiðis intellectually - það er alger tímasóun.

346
00:21:11,210 --> 00:21:16,490
Hvers vegna skiptir meira og meira minni, hætta að afrita allt í nýju fylki,

347
00:21:16,490 --> 00:21:21,980
Ef þú ert með val sem gerir þér kleift að úthluta aðeins eins mikið minni og þú þarft í raun og veru?

348
00:21:21,980 --> 00:21:24,130
Svo er það plús og mínus hér.

349
00:21:24,130 --> 00:21:26,730
Eitt af plús-merkjum nú að við höfum kraft.

350
00:21:26,730 --> 00:21:29,100
Skiptir ekki máli hvar klumpur af minni eru sem eru ókeypis,

351
00:21:29,100 --> 00:21:32,070
Ég get bara svona að búa til þessar brauð mola með ábendingum

352
00:21:32,070 --> 00:21:34,470
til band alla tengda listanum mínum saman.

353
00:21:34,470 --> 00:21:36,470
En ég borga amk eitt verð.

354
00:21:36,470 --> 00:21:40,060
>> Hvað þarf ég að gefa upp á að ná tengd listum?

355
00:21:40,060 --> 00:21:42,470
Já? [Námsmaður svar, óskiljanlegur] Good.

356
00:21:42,470 --> 00:21:45,650
Þú þarft meira minni. Nú þarf ég pláss fyrir þessum ábendingum,

357
00:21:45,650 --> 00:21:47,900
og í tilfelli þessarar frábær einfalt tengd lista

358
00:21:47,900 --> 00:21:51,410
sem er aðeins að reyna að geyma heiltölur, sem eru 4 bytes, halda við að segja

359
00:21:51,410 --> 00:21:54,240
Jæja, er bendillinn er 4 bæti, svo nú hef ég bókstaflega tvöfaldast

360
00:21:54,240 --> 00:21:57,290
magn af minni sem ég þarf bara að geyma þennan lista.

361
00:21:57,290 --> 00:21:59,680
En aftur, þetta er stöðug tradeoff í tölvunarfræði

362
00:21:59,680 --> 00:22:03,440
milli tíma og rúmi og þróun, fyrirhöfn og öðrum auðlindum.

363
00:22:03,440 --> 00:22:06,630
Hvað er annar ókostur við að nota tengda listanum? Já?

364
00:22:06,630 --> 00:22:10,150
[Námsmaður svar, óskiljanlegur]

365
00:22:10,150 --> 00:22:12,600
Gott. Ekki eins auðvelt að nálgast. Við getum ekki lengur skiptimynt

366
00:22:12,600 --> 00:22:15,530
viku 0 meginreglur eins og skipta og sigra.

367
00:22:15,530 --> 00:22:18,220
Og nánar tiltekið, tvöfaldur leit. Því jafnvel þó að við mennirnir

368
00:22:18,220 --> 00:22:20,400
getur séð um það bil þar sem miðja þessum lista er

369
00:22:20,400 --> 00:22:25,840
tölvan veit bara að þetta tengist listinn byrjar á netfangið heitir fyrst.

370
00:22:25,840 --> 00:22:28,250
Og það er 0x123 eða eitthvað svoleiðis.

371
00:22:28,250 --> 00:22:30,990
Og eina leiðin sem forritið finnur miðju þáttur

372
00:22:30,990 --> 00:22:33,350
er að í raun að leita á alla lista.

373
00:22:33,350 --> 00:22:35,500
Og jafnvel þá, það hefur bókstaflega að leita á alla lista þar

374
00:22:35,500 --> 00:22:38,950
jafnvel þegar þú nærð miðju þáttur með því að fylgja ábendingar,

375
00:22:38,950 --> 00:22:42,380
þú, the program, hafa ekki hugmynd um hversu lengi þessi listi er, hugsanlega,

376
00:22:42,380 --> 00:22:45,250
þar til þú högg í lok þess, og hvernig veistu kerfisbundið

377
00:22:45,250 --> 00:22:48,600
að þú ert á the endir af a tengda listanum?

378
00:22:48,600 --> 00:22:51,120
Það er sérstakt NULL músina, svo aftur, samningur.

379
00:22:51,120 --> 00:22:53,870
Frekar en að nota þetta bendi, ákveðið að við viljum ekki að það sé einhver sorp gildi

380
00:22:53,870 --> 00:22:57,750
bendir á stig einhvers staðar, við viljum það til að vera hönd niður, NULL,

381
00:22:57,750 --> 00:23:01,530
þannig að við höfum þetta Terminus í þessum gögnum uppbyggingu svo við vitum hvar það endar.

382
00:23:01,530 --> 00:23:03,410
>> Hvað ef við viljum vinna þetta?

383
00:23:03,410 --> 00:23:05,980
Við gerðum mest af þessu sjónrænt og með mönnum,

384
00:23:05,980 --> 00:23:07,630
En hvað ef við viljum gera á innsetningu?

385
00:23:07,630 --> 00:23:12,360
Svo upprunalega lista var 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
Hvað ef við vildum þá malloc pláss fyrir fjölda 55, tengipunktur fyrir það,

387
00:23:16,730 --> 00:23:20,730
og þá viljum við að setja 55 inn á listann eins og við gerðum á mánudaginn?

388
00:23:20,730 --> 00:23:23,690
Hvernig gerum við þetta? Jæja, Anita kom upp og hún gekk í meginatriðum á listanum.

389
00:23:23,690 --> 00:23:27,500
Hún byrjaði á fyrstu frumefni, þá næst, næst, næst, næst, næst.

390
00:23:27,500 --> 00:23:29,500
Lokum högg the vinstri-hönd alla leið niður

391
00:23:29,500 --> 00:23:34,480
og áttaði ó, þetta er NULL. Svo hvað bendillinn meðferð þarf að gera?

392
00:23:34,480 --> 00:23:37,980
Sá sem var á enda, númer 34, þurfti vinstri hönd hans upp

393
00:23:37,980 --> 00:23:46,220
að benda á 55, 55 þarf vinstri handlegg sínum vísar niður til að vera nýr NULL Terminator. Lokið.

394
00:23:46,220 --> 00:23:49,540
Pretty auðvelt að setja 55 í raðaða lista.

395
00:23:49,540 --> 00:23:51,800
Og hvernig getur þetta útlit?

396
00:23:51,800 --> 00:23:55,690
>> Leyfðu mér að fara á undan og opna upp smá kóða dæmi hér.

397
00:23:55,690 --> 00:23:58,120
Ég opna gedit, og láta mig opna tveir skrá fyrst.

398
00:23:58,120 --> 00:24:02,050
Einn er list1.h, og láta mig minna bara að þetta var klumpur af kóða

399
00:24:02,050 --> 00:24:04,920
sem við notuðum til að tákna hnút.

400
00:24:04,920 --> 00:24:13,040
A hnútur er með bæði int sem heitir N og bendilinn heitir næst að bara benda á næsta hlutur í listanum.

401
00:24:13,040 --> 00:24:15,450
Það er nú í. Klst skrá. Hvers vegna?

402
00:24:15,450 --> 00:24:19,090
Það er þetta venju, og við höfum ekki nýtt sér þetta mikið sjálf,

403
00:24:19,090 --> 00:24:22,220
en sá sem skrifaði printf og aðrar aðgerðir

404
00:24:22,220 --> 00:24:27,150
gaf sem gjöf til heimsins allar þessar aðgerðir með því að skrifa til skrá sem kallast stdio.h.

405
00:24:27,150 --> 00:24:30,950
Og þá er það string.h, og þá er map.h, og það er öll þessi h skrár

406
00:24:30,950 --> 00:24:34,410
sem þú gætir hafa séð eða notuð á tíma skrifuð af öðru fólki.

407
00:24:34,410 --> 00:24:38,470
Venjulega á þeim. H skrár eru aðeins hluti eins typedefs

408
00:24:38,470 --> 00:24:42,310
eða yfirlýsingar af sérsniðnum gerðum eða yfirlýsingum um Fastar.

409
00:24:42,310 --> 00:24:47,890
Þú setur ekki gerð virka 'í skrá haus.

410
00:24:47,890 --> 00:24:50,570
Þú setur í staðinn, bara frumútgáfur þeirra.

411
00:24:50,570 --> 00:24:53,050
Þú setur það sem þú vilt til að deila með heiminum hvað þeir þurfa

412
00:24:53,050 --> 00:24:55,640
í því skyni að safna saman kóðann. Svo bara til að komast inn í þennan vana,

413
00:24:55,640 --> 00:24:59,110
ákváðum við að gera það sama. Það er ekki mikið í list1.h,

414
00:24:59,110 --> 00:25:02,070
en við höfum sett eitthvað sem gæti haft áhuga á fólki í heiminum

415
00:25:02,070 --> 00:25:05,030
sem vilja nota tengda listanum framkvæmd okkar.

416
00:25:05,030 --> 00:25:08,040
Nú, í list1.c, ég mun ekki fara í gegnum þetta allt hlutur

417
00:25:08,040 --> 00:25:11,390
vegna þess að það er dálítið langur, þetta forrit, en við skulum hlaupa það raunverulegur fljótt við áminningu.

418
00:25:11,390 --> 00:25:15,720
Leyfðu mér að taka saman List1, láttu mig hlaupa þá List1, og það sem þú munt sjá er

419
00:25:15,720 --> 00:25:18,070
við höfum herma einfalt lítið forrit hér

420
00:25:18,070 --> 00:25:20,990
sem er að fara að leyfa mér að bæta við og fjarlægja númer til lista.

421
00:25:20,990 --> 00:25:24,310
Svo láta mig fara á undan og gerð 3 fyrir valkostina 3.

422
00:25:24,310 --> 00:25:27,880
Mig langar að setja inn númerið - við skulum gera fyrstu töluna, sem var 9,

423
00:25:27,880 --> 00:25:30,550
og nú er ég sagði listinn er nú 9.

424
00:25:30,550 --> 00:25:33,760
Leyfðu mér að fara á undan og gera aðra innsetningu, svo ég högg matseðill valkostur 3.

425
00:25:33,760 --> 00:25:36,760
Hvaða númer ég vil að setja? 17.

426
00:25:36,760 --> 00:25:39,220
Enter. Og ég geri bara eitt.

427
00:25:39,220 --> 00:25:41,720
Leyfðu mér að setja númer 22.

428
00:25:41,720 --> 00:25:45,850
Þannig að við höfum upphaf tengda listanum sem við höfðum í formi renna í smá stund síðan.

429
00:25:45,850 --> 00:25:48,740
Hvernig er þetta innsetning gerast í raun?

430
00:25:48,740 --> 00:25:52,000
Reyndar, 22 er nú í lok listanum.

431
00:25:52,000 --> 00:25:55,050
Sagan við sagt á sviðinu á mánudaginn og recapped bara núna

432
00:25:55,050 --> 00:25:57,460
verður í raun að vera að gerast í kóða.

433
00:25:57,460 --> 00:25:59,700
Við skulum taka a líta. Leyfðu mér að fletta ofan í þessari skrá.

434
00:25:59,700 --> 00:26:01,720
Við munum gljái yfir nokkrar af þeim aðgerðum,

435
00:26:01,720 --> 00:26:05,630
en við förum niður, segja, setja virka.

436
00:26:05,630 --> 00:26:11,720
>> Við skulum sjá hvernig við förum um að setja nýjan hnút í þessu tengda lista.

437
00:26:11,720 --> 00:26:14,550
Hvar er listinn lýst? Jæja, við skulum fletta alla leið upp á toppinn,

438
00:26:14,550 --> 00:26:19,970
og taka eftir því að tengjast minn listi er í raun lýst sem einu bendill sem er upphaflega NULL.

439
00:26:19,970 --> 00:26:23,180
Þannig að ég er að nota alþjóðlegt breytu hér, sem almennt við höfum boðað gegn

440
00:26:23,180 --> 00:26:25,280
vegna þess að það gerir númerið þitt smá sóðalegur til að viðhalda,

441
00:26:25,280 --> 00:26:29,080
það er tegund af latur, venjulega, en það er ekki latur og það er ekki rangt og það er ekki slæmt

442
00:26:29,080 --> 00:26:33,660
ef eini tilgangur program í lífinu er að gera sér einn tengda listanum.

443
00:26:33,660 --> 00:26:35,460
Sem er einmitt það sem við erum að gera.

444
00:26:35,460 --> 00:26:39,100
Svo frekar en að lýsa þessu í aðal og þá þarf að gefa það til allra virka

445
00:26:39,100 --> 00:26:42,640
við höfum skrifað í þessari áætlun, við skiljum í stað ó, við skulum bara gera það alþjóðlegt

446
00:26:42,640 --> 00:26:47,060
vegna þess að allt tilgangur þessarar áætlunar er að sýna fram á eitt og aðeins eitt tengda listanum.

447
00:26:47,060 --> 00:26:50,700
Svo finnst það í lagi. Hér eru frumgerðir mín, og við munum ekki fara í gegnum allar þessar,

448
00:26:50,700 --> 00:26:55,800
en ég skrifaði eyða stjórna, finna fallið, að setja inn virka og fara virka.

449
00:26:55,800 --> 00:26:59,080
En við skulum nú fara til baka niður í snertingu við virka

450
00:26:59,080 --> 00:27:01,490
og sjá hvernig þetta virkar hérna.

451
00:27:01,490 --> 00:27:09,940
Setja er á línu - hér við fara.

452
00:27:09,940 --> 00:27:12,850
Setja. Þannig að það tekur ekki neina rök, vegna þess að við erum að fara að spyrja

453
00:27:12,850 --> 00:27:15,930
notandi inni á þessum möguleika fyrir fjölda sem þeir vilja til að setja inn.

454
00:27:15,930 --> 00:27:19,410
En fyrst, búa við að gefa þeim pláss.

455
00:27:19,410 --> 00:27:22,050
Þetta er tegund af afrita og líma úr öðrum dæmi.

456
00:27:22,050 --> 00:27:25,110
Í því tilfelli, við vorum að úthluta við int, í þetta sinn við erum að úthluta í hnút.

457
00:27:25,110 --> 00:27:27,910
Ég er ekki alveg að muna hversu margir bæti hnút er, en það er allt í lagi.

458
00:27:27,910 --> 00:27:30,460
Sizeof geta tala það út fyrir mig.

459
00:27:30,460 --> 00:27:33,340
Og hvers vegna er ég að athuga for null í línu 120?

460
00:27:33,340 --> 00:27:37,530
Hvað gæti farið úrskeiðis í línu 119? Já?

461
00:27:37,530 --> 00:27:40,530
[Námsmaður svar, óskiljanlegur]

462
00:27:40,530 --> 00:27:43,440
Gott. Bara gæti verið raunin að ég hef beðið um of mikið minni

463
00:27:43,440 --> 00:27:47,020
eða eitthvað er rangt og stýrikerfi er ekki nóg bæti til að gefa mér,

464
00:27:47,020 --> 00:27:50,640
þannig merki það eins mikið með aftur núll, og ef ég stöðva ekki fyrir að

465
00:27:50,640 --> 00:27:54,710
og ég að halda áfram bara í blindni að nota heimilisfangið aftur, gæti það verið tómt.

466
00:27:54,710 --> 00:27:58,400
Það gæti verið einhver óþekkt gildi, ekki gott nema ég -

467
00:27:58,400 --> 00:28:00,590
í raun mun ekki vera óþekkt gildi. Það gæti verið NULL, svo ég vil ekki

468
00:28:00,590 --> 00:28:02,550
að misnota það og hætta dereferencing það.

469
00:28:02,550 --> 00:28:07,410
Ef það gerist, aftur ég bara og við munum láta eins og ég vissi ekki að fá aftur allir minni yfirleitt.

470
00:28:07,410 --> 00:28:12,270
>> Annars, ég segi notandi gefið mér númer til að setja inn, ég kalla gamla vini GetInt okkar,

471
00:28:12,270 --> 00:28:15,530
og þá var nýja setningafræði við kynnt á mánudag.

472
00:28:15,530 --> 00:28:20,320
'Newptr-> n "þýðir að taka á það heimilisfang sem þú varst gefið malloc

473
00:28:20,320 --> 00:28:23,490
sem táknar fyrsta bæti nýs hnút hlut,

474
00:28:23,490 --> 00:28:26,860
og þá fara að því sviði sem kallast n.

475
00:28:26,860 --> 00:28:35,270
Smá fróðleiksmoli spurning: Þetta jafngildir hvað meira dulinn línu af kóða?

476
00:28:35,270 --> 00:28:38,110
Hvernig annars gæti ég skrifað þetta? Viltu taka stunga?

477
00:28:38,110 --> 00:28:41,480
[Námsmaður svar, óskiljanlegur]

478
00:28:41,480 --> 00:28:44,870
Gott. Notkun. N, en það er ekki alveg eins einfalt og þetta.

479
00:28:44,870 --> 00:28:47,090
Hvað þarf ég fyrst að gera? [Námsmaður svar, óskiljanlegur]

480
00:28:47,090 --> 00:28:52,730
Gott. Ég þarf að gera * newptr.n.

481
00:28:52,730 --> 00:28:55,610
Þannig að þetta er að segja nýja bendillinn er augljóslega netfang. Hvers vegna?

482
00:28:55,610 --> 00:28:59,520
Vegna þess að hún var aftur með malloc. Á * newptr segja "fara þangað,"

483
00:28:59,520 --> 00:29:02,970
og svo þegar þú ert þarna, þá er hægt að nota fleiri kunnugleg. N,

484
00:29:02,970 --> 00:29:05,730
en þetta lítur bara svolítið ljót, sérstaklega ef við mennirnir eru að fara að

485
00:29:05,730 --> 00:29:10,360
draga ábendingum með örvum alla tíma, heimurinn hefur staðlað á þessum ör merki,

486
00:29:10,360 --> 00:29:12,320
sem gerir nákvæmlega það sama.

487
00:29:12,320 --> 00:29:16,070
Svo þú notar aðeins -> tákn þegar hlutur vinstri er músina.

488
00:29:16,070 --> 00:29:18,790
Annars, ef það er í raun strúktúr, nota. N.

489
00:29:18,790 --> 00:29:25,800
Og þá er þetta: Hvers vegna frumstilla ég newptr-> hliðina á NÚLL?

490
00:29:25,800 --> 00:29:28,610
Við viljum ekki hangandi vinstri hönd burt í lok áfanga.

491
00:29:28,610 --> 00:29:31,630
Við viljum því benda beint niður, sem þýðir í lok þessa lista

492
00:29:31,630 --> 00:29:34,980
gæti hugsanlega verið á þessum hnút, þannig að við gert betur úr skugga um það er NULL.

493
00:29:34,980 --> 00:29:38,460
Og almennt, Frumstilli breytur eða gögn meðlimir og structs

494
00:29:38,460 --> 00:29:40,470
að eitthvað er bara gott starf.

495
00:29:40,470 --> 00:29:45,170
Bara að láta sorp hendi og halda áfram að vera yfirleitt fær þér í vandræði

496
00:29:45,170 --> 00:29:48,650
Ef þú gleymir að gera eitthvað síðar.

497
00:29:48,650 --> 00:29:51,590
>> Hér er nokkur dæmi. Þetta aftur er að setja virka,

498
00:29:51,590 --> 00:29:54,930
og það fyrsta sem ég athuga er hvort breyta heitir fyrst,

499
00:29:54,930 --> 00:29:58,240
sem alþjóðlegt breytu er NULL, sem þýðir að það er ekkert tengt lista.

500
00:29:58,240 --> 00:30:02,460
Við höfum ekki sett neinar tölur, þannig að það er léttvæg til að setja þennan núverandi fjölda

501
00:30:02,460 --> 00:30:05,240
í listanum, því það tilheyrir bara á the byrjun af the listi.

502
00:30:05,240 --> 00:30:08,100
Þannig að þetta var þegar Anita var bara að standa upp hér einn, þykjast

503
00:30:08,100 --> 00:30:11,390
enginn annar var upp hér á sviðinu þar til við úthlutað hnút,

504
00:30:11,390 --> 00:30:13,940
svo hún gæti aukið hönd hennar í fyrsta sinn,

505
00:30:13,940 --> 00:30:17,420
Ef allir aðrir voru komnir upp á svið á eftir henni á mánudaginn.

506
00:30:17,420 --> 00:30:22,900
Nú hér, þetta er smá athuga þar sem ég verð að segja ef nýjan hnút á gildi á n

507
00:30:22,900 --> 00:30:27,370
er <verðmæti n í núverandi fyrstu hnút,

508
00:30:27,370 --> 00:30:29,930
sem þýðir að það er tengda listanum sem er hafin.

509
00:30:29,930 --> 00:30:32,330
Það er að minnsta kosti einn hnút á listanum, en þetta nýja strákur

510
00:30:32,330 --> 00:30:37,230
tilheyrir áður en það, þannig að við þurfum að færa hlutina í kring.

511
00:30:37,230 --> 00:30:43,450
Með öðrum orðum, ef listinn er hafin við bara, við skulum segja,

512
00:30:43,450 --> 00:30:48,100
bara númer 17, það er - í raun, við getum gert þetta betur.

513
00:30:48,100 --> 00:30:56,010
Ef við byrjum sögu okkar með músina hér heitir fyrst,

514
00:30:56,010 --> 00:30:59,870
og fyrst það er NULL, og við setja númer 9,

515
00:30:59,870 --> 00:31:02,510
númer 9 tilheyrir greinilega í upphafi listanum.

516
00:31:02,510 --> 00:31:07,400
Svo skulum láta okkur malloced bara heimilisfang eða númer 9 og setja það hér.

517
00:31:07,400 --> 00:31:13,170
Ef fyrsta er 9 sjálfgefið, fyrsta atburðarás við ræddum þýðir bara benda skulum þessi strákur hér,

518
00:31:13,170 --> 00:31:15,790
hafðu þetta eins NULL, nú höfum við númer 9.

519
00:31:15,790 --> 00:31:18,280
Næsta tala við viljum að setja er 17.

520
00:31:18,280 --> 00:31:22,420
17 tilheyrir hérna, þannig að við erum að fara að gera sumir rökrétt stíga í gegnum þetta.

521
00:31:22,420 --> 00:31:26,060
Svo skulum í staðinn, áður en við gerum það, við skulum láta sem við vildum að setja númer 8.

522
00:31:26,060 --> 00:31:28,650
>> Svo bara fyrir sakir þægindi er, ég ætla að draga hér.

523
00:31:28,650 --> 00:31:30,760
En mundu, malloc getur sett það mest hvar sem er.

524
00:31:30,760 --> 00:31:33,460
En fyrir sakir teikningu er, mun ég setja það hér.

525
00:31:33,460 --> 00:31:38,440
Svo þykjast Ég hef bara úthlutað hnút fyrir fjölda 8, þetta er NULL sjálfgefið.

526
00:31:38,440 --> 00:31:42,800
Hvað þarf nú að gerast? A par af hlutum.

527
00:31:42,800 --> 00:31:47,090
Við gerðum þetta mistök á sviðinu á mánudaginn þar sem við uppfært bendi svona,

528
00:31:47,090 --> 00:31:51,890
þá var þetta, og þá erum við krafa - við munaðarlaus allir aðrir á sviðinu.

529
00:31:51,890 --> 00:31:54,350
Þar sem þú skóf - röð aðgerða hér er mikilvægt,

530
00:31:54,350 --> 00:31:58,760
því að nú höfum við misst þennan hnút 9 sem er bara svona fljótandi í geimnum.

531
00:31:58,760 --> 00:32:01,150
Svo þetta var ekki rétt nálgun á mánudaginn.

532
00:32:01,150 --> 00:32:03,330
Við höfum fyrst að gera eitthvað annað.

533
00:32:03,330 --> 00:32:06,280
Ástandið í heiminum lítur svona út. Upphaflega hefur 8 verið úthlutað.

534
00:32:06,280 --> 00:32:10,550
Hvað væri betri leið til að setja 8?

535
00:32:10,550 --> 00:32:14,720
Í stað þess að uppfæra þessa músina fyrst, bara uppfæra þetta einn hér í staðinn.

536
00:32:14,720 --> 00:32:17,720
Þannig að við þurfum línu af kóða sem er að fara að snúa þessu NÚLL staf

537
00:32:17,720 --> 00:32:22,020
í raunveruleg músina sem er að benda á hnútinn 9,

538
00:32:22,020 --> 00:32:27,970
og þá getum við örugglega breytt fyrstur til að benda á þennan gaur hérna.

539
00:32:27,970 --> 00:32:31,330
Nú höfum við lista, sem tengist lista, af tveimur þáttum.

540
00:32:31,330 --> 00:32:33,580
Og hvað þýðir það líta út í raun eins og hér?

541
00:32:33,580 --> 00:32:36,900
Ef við lítum á kóðann, eftir að ég hef gert nákvæmlega það.

542
00:32:36,900 --> 00:32:41,970
Ég hef sagt newptr, og í þessari sögu, newptr var að benda á þennan mann.

543
00:32:41,970 --> 00:32:45,520
>> Svo láta mig draga eitt í viðbót, og ég ætti að hafa skilið smá meira pláss fyrir þetta.

544
00:32:45,520 --> 00:32:48,540
Svo fyrirgefið litla teikningu.

545
00:32:48,540 --> 00:32:52,140
Þessi strákur heitir newptr.

546
00:32:52,140 --> 00:32:57,940
Það er breyta sem við lýst nokkrum línum áður í takt - bara yfir 25.

547
00:32:57,940 --> 00:33:03,430
Og það er að benda á 8. Svo þegar ég segi newptr-> næsta, sem þýðir að fara á strúktúr

548
00:33:03,430 --> 00:33:07,910
sem er verið að benda á með newptr, svo hér erum við, fara þangað.

549
00:33:07,910 --> 00:33:13,990
Þá örin er að segja að fá næsta sviði, og þá = er að segja setja það gildi þar?

550
00:33:13,990 --> 00:33:17,280
Gildið sem var í fyrstu, hvaða gildi var í fyrsta?

551
00:33:17,280 --> 00:33:21,930
Fyrst var að benda á þennan hnút, svo það þýðir að þetta ætti nú að benda á þennan hnút.

552
00:33:21,930 --> 00:33:25,660
Með öðrum orðum, það sem lítur að vísu fáránlega vandræðum með rithönd mína,

553
00:33:25,660 --> 00:33:28,620
það er einföld hugmynd um bara að færa þessar örvarnar í kringum

554
00:33:28,620 --> 00:33:31,560
þýðir að kóða með aðeins þetta eina Ferja.

555
00:33:31,560 --> 00:33:38,110
Geymið það í fyrst í næsta reit og síðan uppfæra það fyrst raunverulega er.

556
00:33:38,110 --> 00:33:40,900
Við skulum fara á undan og fljótur-áfram í gegnum eitthvað af þessu,

557
00:33:40,900 --> 00:33:44,220
og líta aðeins á þessu hali sett í bili.

558
00:33:44,220 --> 00:33:51,210
Segjum að ég fá til the benda hvar ég finn að næsta sviði einhverjum hnút er NULL.

559
00:33:51,210 --> 00:33:53,410
Og á þessum tímapunkti í sögunni, er smáatriði sem ég glossing yfir

560
00:33:53,410 --> 00:33:58,170
er að ég hef kynnt aðra músina upp hér í línu 142, forvera músina.

561
00:33:58,170 --> 00:34:01,320
Í meginatriðum, á þessum tímapunkti í sögunni, þegar fær listinn langur,

562
00:34:01,320 --> 00:34:04,800
Ég þarf svona að ganga hann með tveimur fingrum því ef ég fer of langt,

563
00:34:04,800 --> 00:34:08,219
muna í einum lengd lista, getur þú ekki farið aftur á bak.

564
00:34:08,219 --> 00:34:13,659
Svo er þessi hugmynd um predptr vinstri fingur minn, og newptr - ekki newptr.

565
00:34:13,659 --> 00:34:17,199
Annar músina sem er hér er annar fingur minn, og ég er bara svona að ganga á listanum.

566
00:34:17,199 --> 00:34:22,179
Það er hvers vegna það er. En við skulum aðeins íhuga eitt af einfaldari málum hér.

567
00:34:22,179 --> 00:34:26,620
Ef næsta sviði sem bendillinn er NULL, hvað er rökrétt vísbendingu?

568
00:34:26,620 --> 00:34:30,840
Ef þú ert að fara yfir þennan lista og þú högg NULL músina?

569
00:34:30,840 --> 00:34:35,780
Þú ert í lok listanum og svo númerið að þá bæta þetta einn til viðbótar þáttur

570
00:34:35,780 --> 00:34:41,230
er tegund af leiðandi tekur þessi hnút lét næsta bendillinn er NULL,

571
00:34:41,230 --> 00:34:46,120
þannig að þetta er nú NULL, og breyta því, þó að heimilisfang nýja hnút.

572
00:34:46,120 --> 00:34:52,260
Þannig að við erum bara að teikna í kóða á örina sem við brá á sviðinu með því að hækka vinstri hönd einhvers.

573
00:34:52,260 --> 00:34:54,070
>> Og ef að ég veifa höndum í bili,

574
00:34:54,070 --> 00:34:58,020
bara vegna þess að ég held að það er auðvelt að villast þegar við gerum það í þessa tegund af umhverfi,

575
00:34:58,020 --> 00:35:00,600
er að leita að innsetningu á miðjum lista er.

576
00:35:00,600 --> 00:35:03,220
En bara innsæi, hvað þarf að gerast ef þú vilt að reikna út

577
00:35:03,220 --> 00:35:06,600
þar sem sumir tala tilheyrir í miðjunni er að þú þarft að ganga hana

578
00:35:06,600 --> 00:35:09,510
með fleiri en einum fingri, meira en einn músina,

579
00:35:09,510 --> 00:35:12,920
reikna út þar sem það tilheyrir með því að haka er þáttur <núverandi einn,

580
00:35:12,920 --> 00:35:15,450
> Núverandi einn, og þegar þú kemst að því að stað,

581
00:35:15,450 --> 00:35:20,400
þá verður þú að gera þessa tegund af leiknum skel þar sem þú færir ábendingum um mjög vel.

582
00:35:20,400 --> 00:35:23,850
Og það svar, ef þú vilt ástæðu gegnum þetta heima á eigin spýtur,

583
00:35:23,850 --> 00:35:28,340
snýst um bara að þessum tveimur línum af kóða, en röð af þessum línum er frábær mikilvægt.

584
00:35:28,340 --> 00:35:31,390
Vegna þess að ef þú missir hönd einhvers og hækka einhver annar er í rangri röð,

585
00:35:31,390 --> 00:35:34,580
aftur, gætir þú endað orphaning lista.

586
00:35:34,580 --> 00:35:39,500
Til að draga fleiri hugtök, innsetningu á hali er tiltölulega einfalt.

587
00:35:39,500 --> 00:35:42,940
Ísetningu á höfði er líka tiltölulega einfalt,

588
00:35:42,940 --> 00:35:45,580
en þú þarft að uppfæra til viðbótar bendi þessum tíma

589
00:35:45,580 --> 00:35:47,930
að kreista númer 5 í listanum hér

590
00:35:47,930 --> 00:35:51,560
og felur í sér innsetningu í miðju enn meira átak,

591
00:35:51,560 --> 00:35:56,130
að mjög vel að setja númer 20 í réttan stað,

592
00:35:56,130 --> 00:35:58,350
sem er á milli 17 og 22.

593
00:35:58,350 --> 00:36:02,700
Svo þú þarft að gera eitthvað eins og að hafa nýja hnút 20 benda til 22,

594
00:36:02,700 --> 00:36:08,470
og þá músina sem tengipunktur er þarf að vera uppfærð síðast?

595
00:36:08,470 --> 00:36:10,630
Það er 17, að í raun setja það.

596
00:36:10,630 --> 00:36:14,080
Svo aftur, ég fresta raunverulegri kóða fyrir viðkomandi framkvæmd.

597
00:36:14,080 --> 00:36:17,280
>> Við fyrstu sýn, það er svolítið yfirþyrmandi, en það er í raun bara óendanlegur lykkja

598
00:36:17,280 --> 00:36:21,770
sem er lykkja, lykkja, lykkja, lykkja, og brjóta um leið og þú högg the NULL músina,

599
00:36:21,770 --> 00:36:24,590
á hver benda þú getur gert nauðsynlegar innsetningu.

600
00:36:24,590 --> 00:36:30,960
Þetta, þá er fulltrúi tengda listanum innsetningu kóða.

601
00:36:30,960 --> 00:36:34,590
Það var góður af a einhver fjöldi, og mér finnst eins og við höfum leyst eitt vandamál,

602
00:36:34,590 --> 00:36:36,940
en við höfum kynnt í heild hitt. Frankly, höfum við eytt öllum þessum tíma

603
00:36:36,940 --> 00:36:40,540
á stóra O og Ω og hlaupandi tíma, að reyna að leysa vandamál hraðar,

604
00:36:40,540 --> 00:36:43,270
og hér erum við að taka stórt skref aftur á bak, það líður.

605
00:36:43,270 --> 00:36:45,380
Og enn, ef markmiðið er að geyma gögn,

606
00:36:45,380 --> 00:36:48,010
mér finnst eins og Gral, eins og ég sagði á mánudag, myndi virkilega vera

607
00:36:48,010 --> 00:36:50,470
að geyma það þegar í stað.

608
00:36:50,470 --> 00:36:53,930
>> Í staðreynd, gera ráð fyrir að við fengum að setja til hliðar tengist lista fyrir smá stund

609
00:36:53,930 --> 00:36:56,000
og við kynntum í staðinn hugmyndina um borð.

610
00:36:56,000 --> 00:36:59,110
Og við skulum bara hugsa um borð í smástund sem fylki.

611
00:36:59,110 --> 00:37:03,790
Þessi fylki og þetta mál hefur hér nokkrar 26 þætti, 0 í 25,

612
00:37:03,790 --> 00:37:07,940
og geri ráð fyrir að þú þurfti klumpur af geymslu fyrir nöfn:

613
00:37:07,940 --> 00:37:10,350
Alice og Bob og Charlie og eins.

614
00:37:10,350 --> 00:37:12,880
Og þú þarft sumir gögn uppbygging til að geyma þau nöfn.

615
00:37:12,880 --> 00:37:15,000
Jæja, getur þú notað eitthvað eins og tengda lista

616
00:37:15,000 --> 00:37:20,260
og þú gætir gengið lista innsetning Alice fyrir Bob og Charlie eftir Bob og svo framvegis.

617
00:37:20,260 --> 00:37:23,850
Og í raun, ef þú vilt sjá kóðann svona sem innskot,

618
00:37:23,850 --> 00:37:27,230
vita að í list2.h við gera nákvæmlega það.

619
00:37:27,230 --> 00:37:30,610
Við munum ekki fara í gegnum þennan kóða, en það er afbrigði af fyrstu dæmi

620
00:37:30,610 --> 00:37:34,640
sem kynnir eitt annað strúktúr sem við höfum séð áður kallað nemanda,

621
00:37:34,640 --> 00:37:40,330
og þá hvað það geymir í raun í tengda listanum er bendi á nemandi uppbyggingu

622
00:37:40,330 --> 00:37:44,520
fremur en a einfaldur lítill heiltala, n.

623
00:37:44,520 --> 00:37:46,900
Svo átta sig á það er númerið þar sem felur raunverulegt strengi,

624
00:37:46,900 --> 00:37:49,940
en ef markmiðið fyrir hendi í raun nú er að takast á við skilvirkni vandamál,

625
00:37:49,940 --> 00:37:53,380
myndi það ekki vera gott ef við erum gefið hlut sem heitir Alice,

626
00:37:53,380 --> 00:37:56,020
við viljum að setja hana inn á réttum stað í gögn uppbygging,

627
00:37:56,020 --> 00:37:58,860
mér finnst eins og það væri mjög gaman að bara setja Alice,

628
00:37:58,860 --> 00:38:01,180
hét byrjar með, í fyrsta stað.

629
00:38:01,180 --> 00:38:05,270
Og Bob, sem nafn byrjar með B, á öðrum stað.

630
00:38:05,270 --> 00:38:09,580
Með fjölda, eða við skulum byrja að kalla það töflu, kjötkássa borð í það,

631
00:38:09,580 --> 00:38:13,650
getum við gert nákvæmlega það. Ef við erum að fá nafn eins og Alice,

632
00:38:13,650 --> 00:38:16,700
a band eins og Alice, hvar þú setja A-l-i-c-e?

633
00:38:16,700 --> 00:38:20,540
Við þurfum hueristic. Við þurfum að virka til að taka inntak eins Alice

634
00:38:20,540 --> 00:38:24,610
og aftur svar, "Put Alice á þessum stað."

635
00:38:24,610 --> 00:38:28,720
Og þetta virka, þetta svartur kassi, er að fara að vera kölluð kjötkássa virka.

636
00:38:28,720 --> 00:38:32,330
>> A kjötkássa virka er eitthvað sem tekur inntak, eins og "Alice",

637
00:38:32,330 --> 00:38:38,080
og aftur til þín, yfirleitt, tölugildi stað í nokkur gögn uppbygging þar sem Alice tilheyrir.

638
00:38:38,080 --> 00:38:40,830
Í þessu tilfelli, kjötkássa virka okkar ætti að vera tiltölulega einfalt.

639
00:38:40,830 --> 00:38:47,510
Kjötkássa virka okkar ætti að segja, ef þú ert að fá "Alice", sem staf að hugsa um?

640
00:38:47,510 --> 00:38:55,660
Sú fyrsta. Svo ég horfi á [0], og þá segi ég ef [0] eðli er A, skila fjölda 0.

641
00:38:55,660 --> 00:39:01,130
Ef það er B, aftur 1. Ef C það er, aftur 2, og svo framvegis.

642
00:39:01,130 --> 00:39:05,940
Allir 0 vísitölu, og sem myndi leyfa mér að setja Alice og þá Bob og þá Charlie og svo framvegis

643
00:39:05,940 --> 00:39:10,960
í þessum gögnum uppbyggingu. En það er vandamál.

644
00:39:10,960 --> 00:39:13,060
Hvað ef Anita kemur með aftur?

645
00:39:13,060 --> 00:39:17,510
Hvar setjum Anita? Nafn hennar, líka byrjar með stafinn A,

646
00:39:17,510 --> 00:39:20,330
og mér finnst eins og við höfum gert enn stærri óreiðu á þessu vandamáli.

647
00:39:20,330 --> 00:39:24,380
Við höfum nú strax innsetningu, stöðug tími ísetningar, í gögn uppbygging

648
00:39:24,380 --> 00:39:27,100
en verr ef línuleg,

649
00:39:27,100 --> 00:39:29,510
En hvað getum við gert við Anita í þessu tilviki?

650
00:39:29,510 --> 00:39:34,110
Hvað eru tveir valkostir, virkilega? Já?

651
00:39:34,110 --> 00:39:37,410
[Námsmaður svar, óskiljanlegur] Jæja, svo að við gætum hafa aðra vídd.

652
00:39:37,410 --> 00:39:42,320
Það er gott. Þannig að við getum byggt það út í 3D eins og við ræddum um munnlega á mánudaginn.

653
00:39:42,320 --> 00:39:46,700
Við gætum bætt annan aðgang hérna, en geri ráð fyrir að enginn, ég er að reyna að halda þetta einfalt.

654
00:39:46,700 --> 00:39:50,160
Í heild Markmið hér er að hafa strax föstu-tíma aðgang,

655
00:39:50,160 --> 00:39:52,170
Svo að bæta of mikið flókið.

656
00:39:52,170 --> 00:39:55,970
Hvað eru aðrir kostir við að reyna að setja Anita í þessum gögnum uppbyggingu? Já?

657
00:39:55,970 --> 00:39:58,610
[Námsmaður svar, óskiljanlegur] Good. Þannig að við gætum flutt allir aðrir niður

658
00:39:58,610 --> 00:40:03,040
eins og Charlie nudges niður Bob og Alice, og þá erum við að setja Anita þar sem hún vill í raun að vera.

659
00:40:03,040 --> 00:40:05,660
>> Auðvitað, nú, það er aukaverkun af þessu.

660
00:40:05,660 --> 00:40:09,000
Þessi gögn uppbygging er sennilega gagnlegur ekki vegna þess að við viljum að setja fólk þegar

661
00:40:09,000 --> 00:40:11,250
en vegna þess að við viljum athuga hvort þeir eru það síðar

662
00:40:11,250 --> 00:40:13,600
Ef við viljum prenta út allar nöfn í gögn uppbygging.

663
00:40:13,600 --> 00:40:15,850
Við erum að fara að gera eitthvað við þessum gögnum endanum.

664
00:40:15,850 --> 00:40:20,810
Svo nú höfum við svona ruglaður yfir Alice, sem er ekki lengur þar sem hún á að vera.

665
00:40:20,810 --> 00:40:23,880
Né er Bob, né er Charlie.

666
00:40:23,880 --> 00:40:26,060
Svo kannski er þetta ekki svo góð hugmynd.

667
00:40:26,060 --> 00:40:28,830
En reyndar, þetta er einn kosturinn. Við gætum skipta öllum niður,

668
00:40:28,830 --> 00:40:32,240
eða Heck, Anita kom seint til leiks, hví ekki að við setjum bara Anita

669
00:40:32,240 --> 00:40:35,870
ekki hér, ekki hér, ekki hér, við skulum bara setja hana aðeins lægri á listanum.

670
00:40:35,870 --> 00:40:38,680
En þá byrjar þetta vandamál að flytjast aftur.

671
00:40:38,680 --> 00:40:41,630
Þú might vera fær til finna Alice stað, byggt á fyrsta nafnið hennar.

672
00:40:41,630 --> 00:40:44,320
Og Bob stað, og Charlie. En þá að leita að Anita,

673
00:40:44,320 --> 00:40:46,360
og þú sérð, Hmm, Alice er í leiðinni.

674
00:40:46,360 --> 00:40:48,770
Jæja, láttu mig athuga neðan Alice. Bubbi er ekki Anita.

675
00:40:48,770 --> 00:40:51,850
Charlie er ekki Anita. Oh, það er Anita.

676
00:40:51,850 --> 00:40:54,720
Og ef þú heldur áfram að lest rökfræði alla leið,

677
00:40:54,720 --> 00:41:00,690
hvað er versta hlaupandi tíma að finna eða setja Anita í þessari nýju gögn uppbygging?

678
00:41:00,690 --> 00:41:03,280
Það er O (n), ekki satt?

679
00:41:03,280 --> 00:41:06,280
Vegna þess að í versta falli, það er Alice, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
alla leið niður til að einhver sem heitir "Y", þannig að það er aðeins einn blettur eftir.

681
00:41:10,150 --> 00:41:13,950
Sem betur fer, höfum við engan sem heitir "Z", þannig að við setjum Anita á mjög botn.

682
00:41:13,950 --> 00:41:16,040
>> Við höfum í raun ekki að leysa þessi vandamál.

683
00:41:16,040 --> 00:41:19,890
Svo kannski að við þurfum að kynna þetta þriðja vídd.

684
00:41:19,890 --> 00:41:22,230
Og það kemur í ljós, ef við kynna þetta þriðja vídd,

685
00:41:22,230 --> 00:41:25,240
við getum ekki gert þetta fullkomlega, en Gral sé að fara að fá

686
00:41:25,240 --> 00:41:28,370
föstu-tíma innsetningu og dynamic ísetningar þannig að

687
00:41:28,370 --> 00:41:30,960
við þurfum ekki að harða kóða fylki af stærð 26.

688
00:41:30,960 --> 00:41:34,400
Við getum sett inn eins mörg nöfn eins og við viljum, en við skulum taka 5-mínútna hlé okkar hér

689
00:41:34,400 --> 00:41:38,790
og þá gera það almennilega.

690
00:41:38,790 --> 00:41:46,020
Allt í lagi. Ég setti söguna upp nokkuð tilbúnar þarna

691
00:41:46,020 --> 00:41:48,670
með því að velja Alice og þá Bob og þá Charlie og svo Anita,

692
00:41:48,670 --> 00:41:51,000
hét augljóslega að fara að rekast á við Alice.

693
00:41:51,000 --> 00:41:54,120
En spurningin sem við lauk á mánudag með er bara hversu líklegt er það

694
00:41:54,120 --> 00:41:56,370
sem þú vilt fá þessar tegundir af árekstrum? Með öðrum orðum,

695
00:41:56,370 --> 00:42:00,490
Ef við byrjum að nota þessa töflu uppbyggingu, sem er í raun bara fylki,

696
00:42:00,490 --> 00:42:02,460
í þessu tilviki 26 stöðum,

697
00:42:02,460 --> 00:42:05,740
hvað ef aðföng eru í staðinn jafnt dreift?

698
00:42:05,740 --> 00:42:09,620
Það er ekki tilbúnar Alice og Bob og Charlie og Davíð og svo framvegis í stafrófsröð,

699
00:42:09,620 --> 00:42:12,380
það er jafnt dreift yfir með Z.

700
00:42:12,380 --> 00:42:15,220
>> Kannski við verðum bara að fá heppinn og við ætlum ekki að hafa tvö A-eða tveir er B

701
00:42:15,220 --> 00:42:17,640
með mjög miklar líkur, en eins og einhver benti á,

702
00:42:17,640 --> 00:42:20,730
ef við almenn þetta vandamál og ekki 0-25

703
00:42:20,730 --> 00:42:26,060
en, segjum, 0 í 364 eða 65, oft fjölda daga í a dæmigerður ári,

704
00:42:26,060 --> 00:42:31,170
og spurði, "Hvað er að líkurnar á því að tveir af okkur í þessu herbergi hafa sama afmæli?"

705
00:42:31,170 --> 00:42:34,600
Setja það annar vegur, hvað er líkurnar á því að tveir af okkur hafa nafn sem byrjar á A?

706
00:42:34,600 --> 00:42:37,190
Eins konar spurning er það sama, en það heimilisfang rúm,

707
00:42:37,190 --> 00:42:39,940
þessari leit rúm, er stærri um er að ræða afmæli,

708
00:42:39,940 --> 00:42:42,820
vegna þess að við höfum svo marga fleiri daga á ári en bréf í stafrófinu.

709
00:42:42,820 --> 00:42:44,910
Hver er líkur á árekstri?

710
00:42:44,910 --> 00:42:48,410
Jæja, við getum hugsað um þetta með því að vangaveltur út stærðfræðina gagnstæða leið.

711
00:42:48,410 --> 00:42:50,580
Hvað er líkurnar á engum árekstrum?

712
00:42:50,580 --> 00:42:53,970
Jæja, þetta mál hér segir að það er líkur

713
00:42:53,970 --> 00:42:58,770
ef það er bara einn maður í þessu herbergi, sem þeir hafa einstakt afmæli?

714
00:42:58,770 --> 00:43:01,190
Það er 100%. Vegna þess að ef það er aðeins einn maður í herberginu,

715
00:43:01,190 --> 00:43:03,940
hans eða afmæli hennar getur verið af 365 daga úr árinu.

716
00:43:03,940 --> 00:43:08,650
Svo gefur 365/365 valkostir mér gildi 1.

717
00:43:08,650 --> 00:43:11,250
Svo eru líkurnar á að ræða í augnablikinu bara 1.

718
00:43:11,250 --> 00:43:13,270
En ef það er annað maður í herberginu,

719
00:43:13,270 --> 00:43:16,490
hvað er líkurnar á því að afmælið þeirra er öðruvísi?

720
00:43:16,490 --> 00:43:20,680
Það er aðeins 364 mögulegar daga og hunsa stökk ár,

721
00:43:20,680 --> 00:43:23,580
fyrir afmæli þeirra ekki rekast með öðrum einstaklingum.

722
00:43:23,580 --> 00:43:31,920
Svo 364/365. Ef þriðji maður kemur í, það er 363/365 og svo framvegis.

723
00:43:31,920 --> 00:43:35,790
Svo við höldum margfalda saman þessum brotum, sem eru að fá minni og minni,

724
00:43:35,790 --> 00:43:40,720
til að reikna út hvað eru líkurnar á að öll okkar hafa einstakt afmæli?

725
00:43:40,720 --> 00:43:43,570
En þá getum við að sjálfsögðu bara taka það svar og flettir því í kring

726
00:43:43,570 --> 00:43:47,210
og gera 1 mínus öll þessi, tjáning munum loksins fá

727
00:43:47,210 --> 00:43:51,250
Ef þú manst aftan á bækur stærðfræði, það lítur svolítið eitthvað eins og þetta,

728
00:43:51,250 --> 00:43:54,590
sem er mun auðveldara að túlka myndrænt.

729
00:43:54,590 --> 00:43:57,820
Og þetta grafík hér hefur á x ásnum fjölda afmæli,

730
00:43:57,820 --> 00:44:02,030
eða fjöldi fólks með afmæli, og á y ás er líkurnar á leik.

731
00:44:02,030 --> 00:44:06,060
Og hvað þetta er að segja er að ef þú ert með, við skulum segja, jafnvel,

732
00:44:06,060 --> 00:44:10,860
skulum velja eitthvað eins og 22, 23.

733
00:44:10,860 --> 00:44:13,160
Ef það er 22 eða 23 manns í herbergi,

734
00:44:13,160 --> 00:44:17,100
líkurnar á því að tveir af þeim mjög fáir eru að fara að hafa sama afmæli

735
00:44:17,100 --> 00:44:19,560
er í raun frábær hár, combinatorially.

736
00:44:19,560 --> 00:44:23,450
50% líkur að í flokki aðeins 22 manns, námskeið, nánast,

737
00:44:23,450 --> 00:44:25,790
2 af þeim eru að fara að hafa sama afmæli.

738
00:44:25,790 --> 00:44:28,520
Vegna þess að það er svo margar leiðir sem hægt er að hafa sama afmælisdag.

739
00:44:28,520 --> 00:44:31,110
Jafnvel verra, ef þú horfir á the réttur-hönd hlið af the sjókort,

740
00:44:31,110 --> 00:44:34,040
þann tíma sem þú ert með bekk og 58 nemendur í það,

741
00:44:34,040 --> 00:44:39,270
líkurnar á 2 menn sem hafa afmæli er frábær, frábær hár, næstum 100%.

742
00:44:39,270 --> 00:44:41,880
Nú, það er eins konar skemmtileg staðreynd um raunveruleikanum.

743
00:44:41,880 --> 00:44:45,850
>> En afleiðingarnar, nú, fyrir mannvirki gögn og geyma upplýsingar

744
00:44:45,850 --> 00:44:51,100
þýðir að bara hrokafullur þú hafa a ágætur, hreinan og samræmda dreifingu gagna

745
00:44:51,100 --> 00:44:53,650
og þú ert nógu stór fylking að passa fullt af hlutum

746
00:44:53,650 --> 00:44:59,360
þýðir ekki að þú ert að fara að fá fólk í einstaka stöðum.

747
00:44:59,360 --> 00:45:03,810
Þú ert að fara að hafa fyrir árekstra. Svo þessi hugmynd um hakkast, eins og það er kallað,

748
00:45:03,810 --> 00:45:07,450
taka inntak eins og "Alice" og nudda það á einhvern hátt

749
00:45:07,450 --> 00:45:10,190
og þá fá aftur svar eins 0 eða 1 eða 2.

750
00:45:10,190 --> 00:45:17,500
Getting bak sumir framleiðsla frá því aðgerð er plága þessi líkur á árekstri.

751
00:45:17,500 --> 00:45:19,530
Og hvernig getum við séð þá árekstra?

752
00:45:19,530 --> 00:45:21,940
Jæja, á einu máli, getum við tekið þá hugmynd sem var leiðbeinandi.

753
00:45:21,940 --> 00:45:25,100
Við getum bara vakt alla niður, eða kannski, svolítið meira einfaldlega,

754
00:45:25,100 --> 00:45:29,870
frekar en allir færa annað, við skulum bara fara Anita til the botn af the laus blettur.

755
00:45:29,870 --> 00:45:32,810
Svo ef Alice er í 0, Bob er í 1, Charlie er í 2,

756
00:45:32,810 --> 00:45:35,260
við verðum bara að setja Anita í stað 3.

757
00:45:35,260 --> 00:45:38,860
Og þetta er tækni í gagnauppbyggingu kallast línuleg leit.

758
00:45:38,860 --> 00:45:41,310
Línuleg vegna þess að þú ert bara að ganga þessa línu, og þú ert svona leit

759
00:45:41,310 --> 00:45:43,640
að tiltækum stöðum í gögn uppbygging.

760
00:45:43,640 --> 00:45:46,210
Auðvitað, þetta devolves í O (n).

761
00:45:46,210 --> 00:45:49,590
Ef gögn uppbygging er mjög fullur, það er 25 manns í það nú þegar,

762
00:45:49,590 --> 00:45:54,120
og þá kemur Anita eftir, endar hún upp á hvað væri staðsetning Z, og það er allt í lagi.

763
00:45:54,120 --> 00:45:56,540
Hún passar ennþá, og við getum fundið hana seinna.

764
00:45:56,540 --> 00:46:00,100
>> En þetta var þvert á markmið hraðakstur það upp.

765
00:46:00,100 --> 00:46:02,530
Og hvað ef við kynna staðinn þetta þriðja vídd?

766
00:46:02,530 --> 00:46:06,400
Þessi tækni er almennt kallað sérstakt chaining, eða hafa keðjur.

767
00:46:06,400 --> 00:46:10,030
Og hvað kjötkássa borð er nú þetta tabular uppbyggingu,

768
00:46:10,030 --> 00:46:13,450
taflan er bara fylki af ábendingum.

769
00:46:13,450 --> 00:46:18,230
En hvað þessir ábendingum benda á er giska hvað?

770
00:46:18,230 --> 00:46:21,970
A tengda listanum. Og hvað ef við tökum það besta af báðum þessum heimum?

771
00:46:21,970 --> 00:46:26,500
Við notum fylki fyrir fyrstu vísitölur

772
00:46:26,500 --> 00:46:32,070
í gögn uppbygging svo við getum þegar í stað að fara til [0] [1], [30] eða svo framvegis,

773
00:46:32,070 --> 00:46:36,480
en svo að við höfum sumir sveigjanleika og við getum passa Anita og Alice og Adam

774
00:46:36,480 --> 00:46:38,630
og önnur heiti,

775
00:46:38,630 --> 00:46:43,470
Við skulum þess í stað öðrum ás vaxa geðþótta.

776
00:46:43,470 --> 00:46:47,340
Og við að lokum, eins og með mánudagur, hafa þessi tjáningu getu með tengda listanum.

777
00:46:47,340 --> 00:46:49,530
Við getum vaxa gögn uppbygging geðþótta.

778
00:46:49,530 --> 00:46:52,450
Einnig gætum við bara gert mikið 2-víddar array,

779
00:46:52,450 --> 00:46:57,190
en það er að fara að vera ansi ástand ef einn af línum í 2-víddar array

780
00:46:57,190 --> 00:47:01,280
er ekki nógu stórt til viðbótar mann, hvers nafn kemur til að byrja með A.

781
00:47:01,280 --> 00:47:04,200
Guð forði okkur að reallocate mikið 2-víddar uppbygging

782
00:47:04,200 --> 00:47:06,600
bara vegna þess að það er svo margir sem heita A,

783
00:47:06,600 --> 00:47:09,480
sérstaklega þegar það er svo fáir sem heitir Z eitthvað.

784
00:47:09,480 --> 00:47:12,170
Það er bara að fara að vera mjög dreifður gögn uppbygging.

785
00:47:12,170 --> 00:47:15,400
Svo það er ekki fullkominn með öllum tiltækum ráðum, en nú erum við að hafa að minnsta kosti möguleika

786
00:47:15,400 --> 00:47:19,090
að þegar í stað að finna þar sem Alice eða Anita tilheyrir,

787
00:47:19,090 --> 00:47:21,090
að minnsta kosti hvað varðar lóðrétta ásnum,

788
00:47:21,090 --> 00:47:25,850
og þá erum við bara að ákveða hvar á að setja Anita eða Lísa í tengda listanum.

789
00:47:25,850 --> 00:47:32,480
Ef við gerum sama um flokka hluti, hversu fljótt gætum við setja Alice í uppbyggingu eins og þetta?

790
00:47:32,480 --> 00:47:35,370
Það er stöðug skipti. Við vísitölu í [0], og ef enginn er,

791
00:47:35,370 --> 00:47:37,550
Alice fer í byrjun að tengja lista.

792
00:47:37,550 --> 00:47:40,000
En það er ekki a gríðarstór samningur. Vegna þess að ef Anita kemur þá með

793
00:47:40,000 --> 00:47:42,160
sumir tala af skrefum síðar, þar er Anita tilheyra?

794
00:47:42,160 --> 00:47:45,140
Jæja, [0]. OOP. Alice er nú þegar í að tengja lista.

795
00:47:45,140 --> 00:47:47,760
>> En ef við gerum sama um flokkun þessum nöfnum,

796
00:47:47,760 --> 00:47:53,580
við getum bara flutt Alice yfir, setja Anita, en jafnvel það er stöðug skipti.

797
00:47:53,580 --> 00:47:57,010
Jafnvel ef það er Alice og Adam og öll þessi hinn nöfn,

798
00:47:57,010 --> 00:47:59,410
það er í raun ekki að breytast þá líkamlega. Hvers vegna?

799
00:47:59,410 --> 00:48:04,090
Þar sem við gerðum bara hér með tengda listanum, hver veit voru þessi hnútar eru samt?

800
00:48:04,090 --> 00:48:06,550
Allt sem þú þarft að gera er að flytja brauð mola.

801
00:48:06,550 --> 00:48:10,930
Færa örvarnar í kring, þú þarft ekki að líkamlega færa nein gögn um.

802
00:48:10,930 --> 00:48:14,610
Þannig að við getum sett Anita, í því tilfelli, þegar í stað. Constant tíma.

803
00:48:14,610 --> 00:48:20,250
Þannig að við höfum stöðugt-tími útlit og föstu-tíma Ísetning einhvern eins Anita.

804
00:48:20,250 --> 00:48:22,740
En svona oversimplifying heiminn.

805
00:48:22,740 --> 00:48:28,510
Hvað ef við viljum síðar að finna Alice?

806
00:48:28,510 --> 00:48:31,050
Hvað ef við viljum síðar að finna Alice?

807
00:48:31,050 --> 00:48:35,690
Hversu mörg skref er að fara að taka?

808
00:48:35,690 --> 00:48:37,850
[Námsmaður svar, óskiljanlegur]

809
00:48:37,850 --> 00:48:40,950
Einmitt. Fjölda fólks fyrir Lísa í tengda listanum.

810
00:48:40,950 --> 00:48:45,420
Svo það er ekki alveg fullkominn, vegna þess að gögn uppbygging okkar, aftur hefur þetta lóðrétt aðgang

811
00:48:45,420 --> 00:48:50,240
og þá hefur það þessi tengd lista hangandi - reyndar, við skulum ekki draga það sem fylki.

812
00:48:50,240 --> 00:48:56,020
Það hefur þessi tengd listum hangandi burt af því sem lítur svolítið eitthvað eins og this.

813
00:48:56,020 --> 00:48:59,110
En vandamálið er ef Alice og Adam og öll þessi hinn nöfn

814
00:48:59,110 --> 00:49:01,720
enda fleiri og fleiri þarna,

815
00:49:01,720 --> 00:49:04,810
finna einhver gæti endað að taka fullt af skrefum,

816
00:49:04,810 --> 00:49:06,670
bcause þú þarft að fara yfir tengda lista,

817
00:49:06,670 --> 00:49:08,090
sem er línuleg aðgerð.

818
00:49:08,090 --> 00:49:14,270
Svo í raun, þá er innsetning tími er endanlega O (n), þar sem n er fjöldi staka í listanum.

819
00:49:14,270 --> 00:49:21,780
Skipt eftir, skulum geðþótta kalla það m, þar sem m er fjöldi tengdra lista

820
00:49:21,780 --> 00:49:24,500
sem við höfum í þessum lóðrétta ásinn.

821
00:49:24,500 --> 00:49:27,180
Með öðrum orðum, ef við gerum ráð fyrir sannarlega samræmda dreifingu nöfn,

822
00:49:27,180 --> 00:49:30,150
algerlega óraunhæft. Það er augljóslega meira af sumum stöfum en aðrir.

823
00:49:30,150 --> 00:49:32,580
>> En ef við gerum ráð fyrir stundu a samræmdu dreifingu,

824
00:49:32,580 --> 00:49:37,350
og við höfum n alls fólk og m alls keðjur

825
00:49:37,350 --> 00:49:40,630
í boði fyrir okkur, þá er lengd hvers af þessum fjötrum

826
00:49:40,630 --> 00:49:44,380
nokkuð einfaldlega er að fara að vera alls, N deilt með fjölda keðjur.

827
00:49:44,380 --> 00:49:48,900
Svo N / m. En hér er þar sem við getum verið allt stærðfræðilega snjallt.

828
00:49:48,900 --> 00:49:53,030
m er stöðug, því að það er fastur fjöldi þeirra.

829
00:49:53,030 --> 00:49:54,620
Þú ert að fara að lýsa array þinn í upphafi,

830
00:49:54,620 --> 00:49:58,450
og við erum ekki að breyta stærð á lóðrétta ásinn. Samkvæmt skilgreiningu sem helst fastur.

831
00:49:58,450 --> 00:50:01,220
Það er aðeins lárétt ás, svo að segja, sem er að breytast.

832
00:50:01,220 --> 00:50:04,760
Svo tæknilega, það er stöðug. Svo nú er innsetning tíma

833
00:50:04,760 --> 00:50:09,700
er ansi mikið O (n).

834
00:50:09,700 --> 00:50:12,410
Svo að ekki finnst öllum það mikið betur.

835
00:50:12,410 --> 00:50:14,940
En hvað er sannleikurinn hér? Jæja, allt að þessu sinni, í margar vikur,

836
00:50:14,940 --> 00:50:20,640
við höfum verið að segja O (n ²). O (n), 2 x N ², - n, deilt með 2. . . ECH.

837
00:50:20,640 --> 00:50:23,580
Það er bara N ². En nú, í þessum hluta misseris,

838
00:50:23,580 --> 00:50:25,560
getum við byrjað að tala um raunverulega heimi aftur.

839
00:50:25,560 --> 00:50:31,520
Og N / m er algerlega hraðar en bara n einn.

840
00:50:31,520 --> 00:50:35,170
Ef þú ert með þúsund nöfn, og þú brýtur þau upp í mörgum fötunum

841
00:50:35,170 --> 00:50:37,820
þannig að þú hefur aðeins tíu nöfn á öllum þessum fjötrum,

842
00:50:37,820 --> 00:50:41,670
algerlega að leita tíu hluti er að fara að vera hraðari en þúsund hlutum.

843
00:50:41,670 --> 00:50:43,740
Og svo einn af the komandi setur vandamál er að fara að skora á þig

844
00:50:43,740 --> 00:50:46,100
að hugsa um einmitt að jafnvel þó, já,

845
00:50:46,100 --> 00:50:49,520
aðfellu og stærðfræðilega, þetta er samt bara línuleg,

846
00:50:49,520 --> 00:50:51,700
sem sýgur í almennt þegar að reyna að finna það.

847
00:50:51,700 --> 00:50:54,530
Í raun og veru, það er að fara að vera hraðari en

848
00:50:54,530 --> 00:50:56,520
vegna þessa divisor.

849
00:50:56,520 --> 00:50:58,310
Og þannig að það er aftur að fara að vera svona málamiðlun

850
00:50:58,310 --> 00:51:01,390
og þetta átök milli kenningar og veruleika,

851
00:51:01,390 --> 00:51:03,550
og einn af hnappa byrja beygja á þessum tímapunkti í önn

852
00:51:03,550 --> 00:51:07,510
er meira um raunveruleika eitt eins og við að undirbúa eins konar fyrir lok semster er,

853
00:51:07,510 --> 00:51:09,280
eins og við kynna the veröld af forritun vefur,

854
00:51:09,280 --> 00:51:11,530
þar raunverulega, árangur er að fara að telja vegna þess að notendur þínir eru að fara til

855
00:51:11,530 --> 00:51:14,880
byrja að finna og þakka fátækum ákvarðanir hönnun.

856
00:51:14,880 --> 00:51:19,950
>> Svo hvernig gera þú fara óður í framkvæmd tengd - kjötkássa borð með 31 þætti?

857
00:51:19,950 --> 00:51:22,600
Og dæmið var geðþótta um afmæli.

858
00:51:22,600 --> 00:51:26,190
Ef einhver á afmæli 1. janúar eða 1. febrúar munum við setja þá í fötu.

859
00:51:26,190 --> 00:51:28,960
Ef það er 2. janúar 2. febrúar 2. mars munum við setja þá í fötu.

860
00:51:28,960 --> 00:51:32,220
Það er hvers vegna það var 31. Hvernig lýsa þér kjötkássa borð?

861
00:51:32,220 --> 00:51:37,480
Það getur verið frekar einfalt, hnút Tafla er handahófskennt nafn mitt fyrir það, [31].

862
00:51:37,480 --> 00:51:42,400
Þetta gefur mér 31 ábendingum til hnúður,

863
00:51:42,400 --> 00:51:45,370
og að leyfa mér að hafa 31 ábendingar til að tengjast listum

864
00:51:45,370 --> 00:51:48,800
jafnvel þótt þær keðjur eru upphaflega NULL.

865
00:51:48,800 --> 00:51:54,860
Hvað vil ég setja ef ég vil geyma "Alice", "Bob", "Charlie"?

866
00:51:54,860 --> 00:51:57,010
Jæja, þurfum við að vefja þá hluti í uppbyggingu

867
00:51:57,010 --> 00:52:00,530
vegna þess að við þurfum Alice að benda á Bob, að benda á Charlie, og svo framvegis.

868
00:52:00,530 --> 00:52:04,940
Við getum ekki bara nöfnin ein, þannig að ég gæti búið til nýtt skipulag kallast hnút hér.

869
00:52:04,940 --> 00:52:08,310
>> Hvað er raunverulegt hnút? Hvað er hnúturinn í þessu nýja tengda listanum?

870
00:52:08,310 --> 00:52:11,840
The fyrstur hlutur sem kallast orð, er fyrir nafn viðkomandi.

871
00:52:11,840 --> 00:52:14,340
Lengd, væntanlega til, að hámarks lengd nafni manna er,

872
00:52:14,340 --> 00:52:18,210
hvað það er, 20, 30, 40 stafir í brjálaður tilvikum horn,

873
00:52:18,210 --> 00:52:22,680
og 1 er fyrir hvað? Það er bara auka NULL karakter, \ 0.

874
00:52:22,680 --> 00:52:27,410
Svo þessi hnútur er umbúðir "eitthvað" inni í sig,

875
00:52:27,410 --> 00:52:29,640
en það lýsir líka bendi heitir næsta

876
00:52:29,640 --> 00:52:32,580
svo að við getum keðja Alice til Bob til Charlie og svo framvegis.

877
00:52:32,580 --> 00:52:36,700
Getur verið NULL en ekki endilega að vera.

878
00:52:36,700 --> 00:52:40,110
Einhverjar spurningar um þessi kjötkássa matskeið? Já?

879
00:52:40,110 --> 00:52:46,190
[Námsmaður spyrja spurningu, óskiljanlegur] An array - góð spurning.

880
00:52:46,190 --> 00:52:50,120
Hvers vegna er þetta bleikja orð í fjölda frekar en bara char *?

881
00:52:50,120 --> 00:52:53,830
Í þessu nokkuð handahófskennt dæmi, gerði ég ekki vilja til að grípa

882
00:52:53,830 --> 00:52:56,190
að malloc fyrir hvert upphaflegu nöfnum.

883
00:52:56,190 --> 00:52:59,530
Mig langaði til að lýsa hámarks magn af minni fyrir streng

884
00:52:59,530 --> 00:53:06,020
svo að ég gæti afrita í uppbyggingu Alice \ 0 og ekki þurfa að takast á við malloc og frjáls og þess háttar.

885
00:53:06,020 --> 00:53:11,710
En ég gæti gert það ef ég vildi vera meira meðvitaður um notkun rúm. Góð spurning.

886
00:53:11,710 --> 00:53:14,780
Svo skulum reyna að alhæfa frá þessu

887
00:53:14,780 --> 00:53:18,350
og einbeita sér afganginn í dag á gagnauppbyggingu almennt

888
00:53:18,350 --> 00:53:21,170
og önnur vandamál sem við getum leyst með sömu grundvallaratriði

889
00:53:21,170 --> 00:53:24,590
jafnvel þótt gögn uppbygging sjálfir getur verið mismunandi í einstökum atriðum þeirra.

890
00:53:24,590 --> 00:53:27,910
>> Svo kemur í ljós í tölvunarfræði, eru tré mjög algeng.

891
00:53:27,910 --> 00:53:29,760
Og hægt er að hugsa um tré konar eins og ættartré,

892
00:53:29,760 --> 00:53:31,830
þar er sumir rætur, sumir matriarch eða patriarcha,

893
00:53:31,830 --> 00:53:34,540
amma eða afi eða fyrr til baka,

894
00:53:34,540 --> 00:53:38,880
undir sem eru mamma og pabbi og ýmsir systkini eða þess háttar.

895
00:53:38,880 --> 00:53:42,500
Svo hefur tré uppbyggingu hnúður og það hefur börn,

896
00:53:42,500 --> 00:53:45,260
yfirleitt 0 eða fleiri börn fyrir hvern hnút.

897
00:53:45,260 --> 00:53:47,320
Og sumir af the hrognamál sem þú sérð á þessari mynd hér

898
00:53:47,320 --> 00:53:50,630
er einhver af litlu krökkunum eða grandkids á brúnir

899
00:53:50,630 --> 00:53:52,330
sem hafa ekki örvarnar berast frá þeim,

900
00:53:52,330 --> 00:53:55,070
þeir eru svokölluð lauf, og einhver á inni

901
00:53:55,070 --> 00:53:58,790
er innri hnút, þú getur hringt í það neitt meðfram þeim línum.

902
00:53:58,790 --> 00:54:01,430
En þessi uppbygging er ansi algengt. Þessi er svolítið handahófskennt.

903
00:54:01,430 --> 00:54:04,930
Við höfum eitt barn til vinstri, höfum við þrjú börn á hægri,

904
00:54:04,930 --> 00:54:06,830
tvö börn á the botn vinstri.

905
00:54:06,830 --> 00:54:10,740
Þannig að við getum haft mismunandi-stór tré, en ef við byrjum að staðla hlutina,

906
00:54:10,740 --> 00:54:15,330
og þú gætir muna þetta frá vídeó Patrick um tvöfaldur leit frá fyrri stutt

907
00:54:15,330 --> 00:54:19,490
netinu, tvöfaldur leita þarf ekki að koma til framkvæmda með fjölda

908
00:54:19,490 --> 00:54:21,410
eða stykki af pappír á karta.

909
00:54:21,410 --> 00:54:25,490
Segjum að þú vildir geyma númer þitt í flóknari gögn uppbygging.

910
00:54:25,490 --> 00:54:27,680
Þú getur búið til tré eins og this.

911
00:54:27,680 --> 00:54:35,290
Þú gætir hafa hnút lýst í C, og að hnúturinn getur haft að minnsta kosti tvo þætti innan þess.

912
00:54:35,290 --> 00:54:39,470
Einn er númerið sem þú vilt geyma, og hitt er - ja, við þurfum eitt.

913
00:54:39,470 --> 00:54:41,540
Hin er börn þess.

914
00:54:41,540 --> 00:54:45,150
Svo er hér önnur gögn uppbygging. This tími, er hnút skilgreind sem geyma númer N

915
00:54:45,150 --> 00:54:49,060
og þá tveir ábendingum, vinstri barn og hægri barn.

916
00:54:49,060 --> 00:54:52,100
Og þeir eru ekki handahófskennt. Hvað er áhugavert um þetta tré?

917
00:54:52,100 --> 00:55:00,550
>> Hvað er mynstur í því hvernig við höfum sett þetta út eða hvernig Patrick lagði fram í myndbandinu hans?

918
00:55:00,550 --> 00:55:02,790
Það er góður af augljóst að það er einhver flokkun gerast hér,

919
00:55:02,790 --> 00:55:04,460
en það er einföld regla? Já?

920
00:55:04,460 --> 00:55:08,350
[Námsmaður svar, óskiljanlegur]

921
00:55:08,350 --> 00:55:12,040
Perfect. Ef þú litið á þetta, þú sérð litla tölur til vinstri,

922
00:55:12,040 --> 00:55:14,690
stór númer á vinstri, en það er satt fyrir hvern hnút.

923
00:55:14,690 --> 00:55:20,370
Fyrir hvern hnút, vinstri barn hennar minna en það, og hægri barn hennar meira en það.

924
00:55:20,370 --> 00:55:25,210
Hvað þýðir þetta er nú ef ég vil leita þessi gögn uppbygging fyrir, segjum, fjölda 44,

925
00:55:25,210 --> 00:55:29,320
Ég verð að byrja á rót, því eins og við öll þessi flóknari gögn uppbygging nú,

926
00:55:29,320 --> 00:55:31,910
við höfum bara bendi á eitt, í byrjun.

927
00:55:31,910 --> 00:55:35,010
Og í þessu tilfelli, upphafið er rót. Það er ekki vinstri enda,

928
00:55:35,010 --> 00:55:39,530
það er rót þessa uppbyggingu. Svo sé ég hérna er 55, og ég er að leita að 44.

929
00:55:39,530 --> 00:55:41,430
Hvaða átt ég vil fara?

930
00:55:41,430 --> 00:55:45,680
Jæja, ég vil fara til vinstri, því augljóslega, til hægri er að fara að vera of stór.

931
00:55:45,680 --> 00:55:49,050
Svo taka hér, þú ert konar eðli chopping gegnum tréð í helmingur

932
00:55:49,050 --> 00:55:51,700
vegna þess að þú ert aldrei að fara niður á hægra megin.

933
00:55:51,700 --> 00:55:55,410
Svo nú er ég að fara frá 55 til 33. Það er of lítið af mörgum.

934
00:55:55,410 --> 00:56:01,590
Ég er að leita að 44, en nú veit ég hvort 44 er í þessu tré, ég get farið augljóslega til hægri.

935
00:56:01,590 --> 00:56:04,460
Svo aftur, ég pruning trénu í tvennt.

936
00:56:04,460 --> 00:56:06,780
Það er ansi mikið eðli eins símaskránni.

937
00:56:06,780 --> 00:56:09,510
Það er eins og það sem við gerðum með pappíra á töfluna,

938
00:56:09,510 --> 00:56:13,940
en það er flóknari mannvirki sem gerir okkur kleift að í raun að gera

939
00:56:13,940 --> 00:56:16,880
þetta skipta og sigra með hönnun reiknirit,

940
00:56:16,880 --> 00:56:19,420
og í raun fara yfir skipulag eins og þetta - Úpps.

941
00:56:19,420 --> 00:56:22,870
Fara yfir skipulag eins og þetta, þar sem það er bara "fara þessa leið eða fara þessa leið,"

942
00:56:22,870 --> 00:56:26,870
þýðir öll þessi númer sem beygði hug þinn í fyrstu þegar útfæra hana í kafla

943
00:56:26,870 --> 00:56:31,270
eða ganga í gegnum það heima, að tvöfaldur leit með endurkvæmni eða endurtekning,

944
00:56:31,270 --> 00:56:35,060
það er sársauki í hálsinum. Finndu miðju frumefni, þá gera lokið máli mínu upp eða niður.

945
00:56:35,060 --> 00:56:39,230
>> Það er fegurð í þessu vegna þess að við getum nú notað endurkvæmni aftur

946
00:56:39,230 --> 00:56:43,760
en miklu meira eðlilega. Reyndar, ef þú ert á númer 55 og þú vilt að finna 44,

947
00:56:43,760 --> 00:56:48,450
þú ferð eftir í þessu tilfelli, þá hvað gerir þú? Þú keyra nákvæmlega sama reiknirit.

948
00:56:48,450 --> 00:56:51,560
Þú athuga gildi hnút, þá fara til vinstri eða hægri.

949
00:56:51,560 --> 00:56:53,670
Síðan sem þú athuga gildi hnút, fara til vinstri eða hægri.

950
00:56:53,670 --> 00:56:56,710
Þetta er fullkomlega til þess fallin að endurkvæmni.

951
00:56:56,710 --> 00:57:00,920
Svo jafnvel þó í fortíðinni sem við höfum gert nokkrar nokkuð handahófskennt dæmi felur endurkvæmni

952
00:57:00,920 --> 00:57:03,430
það þarf ekki að vera endurkvæma með stuctures gögn,

953
00:57:03,430 --> 00:57:07,820
einkum tré, það er fullkominn umsókn um þessa hugmynd um að taka vandamál,

954
00:57:07,820 --> 00:57:12,920
skar það, og þá leysa sömu tegund, en minni, program.

955
00:57:12,920 --> 00:57:14,590
>> Svo er það önnur gögn uppbygging sem við getum kynna.

956
00:57:14,590 --> 00:57:18,760
Þessi er hönnuð við fyrstu sýn að líta dulinn, en þetta er ótrúlegt.

957
00:57:18,760 --> 00:57:25,090
Þannig að þetta er gögn uppbygging kallast trie, trie, sem er arfur af orðinu sókn,

958
00:57:25,090 --> 00:57:30,210
sem er ekki áberandi aftur TRY-Val, en það er það sem heimurinn kallar þetta. Reynir. T-r-i-e.

959
00:57:30,210 --> 00:57:35,190
Það er tré uppbyggingu einhvers konar, en hver af hnúður í trie

960
00:57:35,190 --> 00:57:41,280
virðist vera það? Og þetta er svolítið villandi vegna þess að það er eins konar styttur.

961
00:57:41,280 --> 00:57:45,960
En það lítur út eins og hver hnútur í trie er í raun fylki.

962
00:57:45,960 --> 00:57:48,840
Og jafnvel þó að höfundur þessarar myndinni hefur ekki sýnt það,

963
00:57:48,840 --> 00:57:54,130
í þessu tilfelli, þetta trie er gögn uppbygging sem tilgangur í lífinu er að geyma orð

964
00:57:54,130 --> 00:57:57,330
eins og A-l-i-c-e eða B-o-B.

965
00:57:57,330 --> 00:58:02,480
Og með hvaða hætti þessi gögn birgðir Alice og Bob og Charlie og Anita og svo framvegis

966
00:58:02,480 --> 00:58:06,970
það notar fylki þar á að geyma Lísa í trie,

967
00:58:06,970 --> 00:58:09,820
við byrjum á rót hnút, sem lítur út eins og fylki,

968
00:58:09,820 --> 00:58:12,080
og það hefur verið skrifað í merki shorthand.

969
00:58:12,080 --> 00:58:15,070
Höfundur sleppt ABCDEFG því það voru engin nöfn með því.

970
00:58:15,070 --> 00:58:19,150
Þeir sýndu bara M og P og T, en í þessu tilviki,

971
00:58:19,150 --> 00:58:22,780
við skulum fara burtu frá Alice og Bob og Charlie að sumir nöfn sem eru hérna.

972
00:58:22,780 --> 00:58:25,670
Maxwell er í raun í þessari mynd.

973
00:58:25,670 --> 00:58:29,570
Svo hvernig did höfundur verslun M-a-x-W-E-L-L?

974
00:58:29,570 --> 00:58:36,990
Hann byrjaði á rót hnút, og fór til [M], svo u.þ.b. 13, 13. stað í fylkinu.

975
00:58:36,990 --> 00:58:40,750
Þaðan, það er bendir.

976
00:58:40,750 --> 00:58:42,760
Bendi leiðir til annað fylki.

977
00:58:42,760 --> 00:58:47,880
Þaðan höfundur verðtryggð í þessi fylki á stað A, eins og sjá má þar efst til vinstri,

978
00:58:47,880 --> 00:58:52,250
og þá er hann eða hún eftir að bendi til annars fylking,

979
00:58:52,250 --> 00:58:55,460
og fór í músina á staðsetningu X.

980
00:58:55,460 --> 00:58:59,840
Síðan í næsta array staðsetningu W, E, L, L, og svo framvegis,

981
00:58:59,840 --> 00:59:03,090
og að lokum, við skulum í raun að reyna að setja mynd í þetta.

982
00:59:03,090 --> 00:59:05,380
Hvað hnút líta út í kóða?

983
00:59:05,380 --> 00:59:11,820
A hnútur í trie inniheldur fjölbreytta ábendingum til fleiri hnúta.

984
00:59:11,820 --> 00:59:16,090
En það er einnig fengið að vera einhvers konar Boolean gildi, að minnsta kosti í þessari framkvæmd.

985
00:59:16,090 --> 00:59:18,770
Ég gerst að kalla það is_word. Hvers vegna?

986
00:59:18,770 --> 00:59:22,670
Því þegar þú ert að setja Maxwell, þú ert ekki að setja

987
00:59:22,670 --> 00:59:25,300
eitthvað í þessum gögnum uppbyggingu.

988
00:59:25,300 --> 00:59:27,480
Þú ert ekki að skrifa M. Þú ert ekki að skrifa X.

989
00:59:27,480 --> 00:59:30,240
Allt sem þú ert að gera er að fylgja ábendingum.

990
00:59:30,240 --> 00:59:33,360
Músina sem sýnir m, síðan á músina sem sýnir A,

991
00:59:33,360 --> 00:59:36,310
þá bendillinn sem táknar X, þá W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
en það sem þú þarft að gera í lok er tegund af að fara, skoða, náði ég þessa staðsetningu.

993
00:59:41,950 --> 00:59:45,560
Það var orð sem endar hér í gögn uppbygging.

994
00:59:45,560 --> 00:59:48,190
>> Svo hvað trie er mjög fyllt með og höfundur valdi til að tákna

995
00:59:48,190 --> 00:59:51,880
þessi terminuses með lítið þríhyrninga.

996
00:59:51,880 --> 00:59:56,470
Þetta bara þýðir að sú staðreynd Þessi þríhyrningur er hér, þetta Boole gildi satt

997
00:59:56,470 --> 00:59:59,200
þýðir að ef þú ferð aftur í trénu,

998
00:59:59,200 --> 01:00:02,420
sem þýðir orð heitir Maxwell er í þessu.

999
01:00:02,420 --> 01:00:04,870
En orð foo, til dæmis,

1000
01:00:04,870 --> 01:00:07,970
er ekki í trénu, því að ef ég byrja á rót hnút hérna efst,

1001
01:00:07,970 --> 01:00:14,030
Það er engin f músina, ekki o músina, ekki o músina. Foo er ekki nafn á þessari orðabók.

1002
01:00:14,030 --> 01:00:22,460
En með því móti, Turing, T-U-r-i-n-g. Aftur, var ég ekki að geyma t eða u eða r eða ég eða n eða g.

1003
01:00:22,460 --> 01:00:29,820
En ég gerði verslun í þessum gögnum uppbyggingu gildið satt vegur niður í hnút - í trénu

1004
01:00:29,820 --> 01:00:33,030
með því að setja þetta Boolean gildi is_word satt.

1005
01:00:33,030 --> 01:00:35,740
Svo er trie konar þetta mjög áhugavert meta uppbyggingu,

1006
01:00:35,740 --> 01:00:39,810
þar sem þú ert í raun ekki að geyma orðin sig af þessu tagi orðabók.

1007
01:00:39,810 --> 01:00:45,100
Til að vera skýr, þú ert bara að geyma já eða nei, það er orð sem endar hér.

1008
01:00:45,100 --> 01:00:46,430
>> Nú hvað er óbeint?

1009
01:00:46,430 --> 01:00:51,120
Ef þú ert með 150.000 orð í orðabók sem þú ert að reyna að geyma í minni

1010
01:00:51,120 --> 01:00:53,400
að nota eitthvað eins og tengda listanum,

1011
01:00:53,400 --> 01:00:56,870
þú ert að fara að hafa 150.000 hnúta í tengda listanum þínum.

1012
01:00:56,870 --> 01:01:00,250
Og finna einn af þessum orðum í stafrófsröð gæti tekið O (n) tíma.

1013
01:01:00,250 --> 01:01:04,370
Línulegum tíma. En í tilviki hér á trie,

1014
01:01:04,370 --> 01:01:09,210
hvað er í gangi þegar að finna orð?

1015
01:01:09,210 --> 01:01:17,390
Það kemur í ljós fegurð hér er að jafnvel ef þú hefur 149.999 orð þegar í þessari orðabók,

1016
01:01:17,390 --> 01:01:20,170
sem útfærð með þessum gögnum uppbyggingu,

1017
01:01:20,170 --> 01:01:25,560
hversu mikinn tíma tekur það að finna eða setja eina í viðbót í það, eins og Alice, Alice?

1018
01:01:25,560 --> 01:01:30,640
Jæja, það er bara 5, kannski 6 skref fyrir slóð staf.

1019
01:01:30,640 --> 01:01:32,880
Þar sem presense annarra nöfn í uppbyggingu

1020
01:01:32,880 --> 01:01:35,340
ekki að komast í the vegur af að setja Alice.

1021
01:01:35,340 --> 01:01:39,640
Þar að auki, finna Alice þegar það eru 150.000 orð í þessari orðabók

1022
01:01:39,640 --> 01:01:41,960
ekki fá í leiðinni að finna Alice yfirleitt,

1023
01:01:41,960 --> 01:01:46,880
því Alice er. . . . . hér, vegna þess að ég fann Boolean gildi.

1024
01:01:46,880 --> 01:01:50,920
Og ef það er engin Boolean satt, þá Alice er ekki í þessum gögnum uppbyggingu orða.

1025
01:01:50,920 --> 01:01:56,220
Með öðrum orðum, að keyra tíma að finna hluti og setja hluti í þessu nýja

1026
01:01:56,220 --> 01:02:01,920
gögn uppbyggingu trie er O - það er ekki n.

1027
01:02:01,920 --> 01:02:05,730
Þar sem presense af 150.000 manns hefur ekki áhrif á Alice, virðist.

1028
01:02:05,730 --> 01:02:11,560
Svo við skulum kalla það k, þar sem k er Hámarkslengd orð í ensku

1029
01:02:11,560 --> 01:02:14,050
sem er yfirleitt ekki meira en 20-eitthvað stafir.

1030
01:02:14,050 --> 01:02:17,940
Svo er k fasti. Svo Gral við virðast hafa fundið nú

1031
01:02:17,940 --> 01:02:26,000
er þessi af a trie, stöðug tíma fyrir sett inn, í leit fyrir úrfellingum.

1032
01:02:26,000 --> 01:02:29,170
Vegna þess að fjöldi af hlutur þegar í uppbyggingu,

1033
01:02:29,170 --> 01:02:32,600
sem eru ekki einu sinni líkamlega þar. Aftur, þeir raða bara af köflóttur út, já eða nei,

1034
01:02:32,600 --> 01:02:35,050
hefur engin áhrif á framtíð í gangi á sínum tíma.

1035
01:02:35,050 --> 01:02:37,940
>> En það hlýtur að vera a grípa, annars myndum við ekki sóa svo miklum tíma

1036
01:02:37,940 --> 01:02:41,460
á öllum þessum gagnauppbyggingu bara að lokum fá til the leyndarmál einn sem er ótrúlegt.

1037
01:02:41,460 --> 01:02:46,410
Svo hvaða verð erum við að borga til að ná þessu hátignar hér? Space.

1038
01:02:46,410 --> 01:02:49,010
Þessi hlutur er gegnheill. Og ástæða þess að höfundur

1039
01:02:49,010 --> 01:02:52,400
ekki kynna það hér, eftir að allir þessir hlutir sem líta út eins og fylki,

1040
01:02:52,400 --> 01:02:55,400
hann ekki draga restina af trénu, en afgangurinn af trie,

1041
01:02:55,400 --> 01:02:58,060
vegna þess að þeir eru bara ekki viðeigandi að sögunni.

1042
01:02:58,060 --> 01:03:01,870
En öll þessi hnúður er frábær breiður, og sérhver hnútur í trénu tekur upp

1043
01:03:01,870 --> 01:03:07,780
26 eða í raun, gæti verið 27 stafir því í þessu tilfelli var ég þar pláss fyrir úrfellingarmerki

1044
01:03:07,780 --> 01:03:09,980
svo að við gætum hafa apostrophized orð.

1045
01:03:09,980 --> 01:03:14,450
Í þessu tilfelli er þetta breiður fylki. Svo jafnvel þótt þeir séu ekki picutured,

1046
01:03:14,450 --> 01:03:18,190
þetta tekur allt gríðarlegt magn af vinnsluminni.

1047
01:03:18,190 --> 01:03:20,670
Sem gæti verið fínn, especilly í nútíma vélbúnaði,

1048
01:03:20,670 --> 01:03:25,650
en það er tradeoff. Við fáum minni tíma með því að eyða meira pláss.

1049
01:03:25,650 --> 01:03:28,580
Hvar er þetta að fara allt?

1050
01:03:28,580 --> 01:03:32,640
Jæja, við skulum gera - við skulum sjá hér.

1051
01:03:32,640 --> 01:03:39,510
Við skulum gera stökk til þetta strákur hér.

1052
01:03:39,510 --> 01:03:43,450
>> Trúa það eða ekki, eins skemmtilegt og C hefur verið um nokkurt skeið,

1053
01:03:43,450 --> 01:03:48,130
við erum að ná að benda á önn þar sem það er kominn tími til að skipta yfir í það meira nútíma.

1054
01:03:48,130 --> 01:03:50,950
Hlutina á hærra stig. Og jafnvel þó að á næstu vikum

1055
01:03:50,950 --> 01:03:54,580
við munum samt halda áfram að sökkva okkur í heimi ábendingum og minni stjórnun

1056
01:03:54,580 --> 01:03:57,210
að fá þessi þægindi sem við getum þá byggja á,

1057
01:03:57,210 --> 01:04:01,270
enda leikur er að lokum að kynna, kaldhæðni, ekki þetta tungumál.

1058
01:04:01,270 --> 01:04:03,330
Við munum eyða, eins og 10 mínútur að tala um HTML.

1059
01:04:03,330 --> 01:04:05,950
Allt HTML er er Markup Language, og hvað Markup Language er

1060
01:04:05,950 --> 01:04:10,220
er þessi röð af opnum sviga og loka sviga sem segja 'gera þetta feitletrað'

1061
01:04:10,220 --> 01:04:12,000
"Gera þetta skáletrun 'gera þessa miðju."

1062
01:04:12,000 --> 01:04:14,250
Það er ekki allt sem vitsmunalega áhugavert, en það er frábær gagnlegt.

1063
01:04:14,250 --> 01:04:16,650
Og það er vissulega omnipresent þessa dagana.

1064
01:04:16,650 --> 01:04:19,450
En hvað er öflugur um heim HTML og vefur forritun almennt,

1065
01:04:19,450 --> 01:04:25,910
er að byggja dynamic hluti, skrifa kóða í tungumálum eins og PHP eða Python eða Ruby eða Java eða C #.

1066
01:04:25,910 --> 01:04:30,360
Raunverulega, hvað tungumál þitt val er, og búa til HTML virk.

1067
01:04:30,360 --> 01:04:32,960
Búa eitthvað sem kallast CSS virk.

1068
01:04:32,960 --> 01:04:35,810
Cascading Style Sheets, sem er einnig um fagurfræði.

1069
01:04:35,810 --> 01:04:41,360
Og svo jafnvel þó, í dag, ef ég fer til einhvers website eins kunnuglega Google.com,

1070
01:04:41,360 --> 01:04:46,100
og ég fer að skoða, verktaki, skoða uppspretta, sem kannski þú hefur gert áður,

1071
01:04:46,100 --> 01:04:49,800
en að fara að skoða uppspretta, þetta efni lítur sennilega nokkuð dulinn.

1072
01:04:49,800 --> 01:04:55,320
En þetta er undirliggjandi kóða sem útfærir Google.com.

1073
01:04:55,320 --> 01:04:57,940
Á framenda. Og í raun er þetta allt Fluffy fagurfræði efni.

1074
01:04:57,940 --> 01:05:01,740
Þetta er CSS upp hér. Ef ég halda að fletta niður fáum við lit-dulmáli efni.

1075
01:05:01,740 --> 01:05:06,890
Þetta er HTML. Kóða Google lítur út eins og óreiðu, en ef ég opna reyndar upp aðra glugga,

1076
01:05:06,890 --> 01:05:09,380
getum við séð nokkur uppbygging að þessu.

1077
01:05:09,380 --> 01:05:12,640
Ef ég opna þetta upp, taka hér, það er svolítið læsilegri.

1078
01:05:12,640 --> 01:05:16,850
Við ætlum að sjá áður en langt þetta merki, [orðið] er tag,

1079
01:05:16,850 --> 01:05:23,520
HTML, höfuð, líkama, div, handrit, texta svæði, span, miðju, div.

1080
01:05:23,520 --> 01:05:26,770
Og þetta er líka svona Cryptic-útlit á fyrstu sýn,

1081
01:05:26,770 --> 01:05:30,890
en alla þessa óreiðu fylgir ákveðin mynstur og repeatable mynstur,

1082
01:05:30,890 --> 01:05:33,850
þannig að þegar við fá grunnatriði niður, munt þú vera fær um að skrifa kóða svona

1083
01:05:33,850 --> 01:05:37,550
og þá vinna númer svona með enn öðru tungumáli, sem heitir JavaScript.

1084
01:05:37,550 --> 01:05:40,440
Og JavaScript er tungumál sem keyrir inni í vafra

1085
01:05:40,440 --> 01:05:44,380
dag sem við notum á Harvard námskeiðum, til að versla auðvitað tól sem Google Maps notar

1086
01:05:44,380 --> 01:05:48,660
til að gefa þér allt fullt af krafti, Facebook gefur þér til að sýna augnablik stöðu uppfærslur,

1087
01:05:48,660 --> 01:05:51,430
Twitter notar það til að sýna þér kvak stað.

1088
01:05:51,430 --> 01:05:53,820
Allt þetta munum við byrja að sökkva okkur inn

1089
01:05:53,820 --> 01:05:57,190
En til að fá það þurfum við að skilja lítið eitthvað um internetið.

1090
01:05:57,190 --> 01:06:01,130
Þetta myndband hér er bara mínútu löng, og við skulum gera ráð fyrir því að nú er þetta í raun,

1091
01:06:01,130 --> 01:06:08,380
hvernig Netið virkar sem beitu fyrir hvað er um að koma. Ég gefa þér "Warriors á Netinu."

1092
01:06:08,380 --> 01:06:14,720
>> [♫ Slow kór tónlist ♫]

1093
01:06:14,720 --> 01:06:20,450
[Male sögumaður] Hann kom með skilaboð.

1094
01:06:20,450 --> 01:06:23,770
Með siðareglur allt sitt.

1095
01:06:23,770 --> 01:06:37,270
[♫ Festa Raftónlist ♫]

1096
01:06:37,270 --> 01:06:41,330
Hann kom í heiminn á flottum eldveggir, uncaring leið,

1097
01:06:41,330 --> 01:06:45,690
og hættum miklu verra en dauðinn.

1098
01:06:45,690 --> 01:06:55,400
Hann er fljótur. Hann er sterkur. Hann er TCP / IP, og hann er með netfangið þitt.

1099
01:06:55,400 --> 01:06:59,250
Warriors á Netinu.

1100
01:06:59,250 --> 01:07:05,290
[Malan] Næsta vika, þá. The Internet. Vefur forritun. Þetta er CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]