1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [6. hét, folytatás]

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

3
00:00:04,160 --> 00:00:08,720
[Ez a CS50.] [CS50.TV]

4
00:00:08,720 --> 00:00:12,970
Ez a CS50 és ez a hét végén 6.

5
00:00:12,970 --> 00:00:17,970
Szóval CS50x, az egyik Harvard első tanfolyamok bevont EDX kezdeményezés

6
00:00:17,970 --> 00:00:20,590
Valóban debütált az elmúlt hétfőn.

7
00:00:20,590 --> 00:00:23,460
Ha azt szeretné, hogy egy pillantást, amit mások az interneten

8
00:00:23,460 --> 00:00:27,180
most következő együtt, akkor irány x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
Ez majd átirányítja a megfelelő hely edx.org,

10
00:00:30,350 --> 00:00:34,160
ami volt, ahol ezt és egyéb tanfolyamok az MIT és a Berkeley él.

11
00:00:34,160 --> 00:00:38,140
Neked kell regisztrálj egy fiókot, akkor rájössz, hogy az anyag nagyrészt ugyanaz

12
00:00:38,140 --> 00:00:42,170
ahogy már volt ebben a félévben, de néhány héttel késik, mert kapunk mindent készen.

13
00:00:42,170 --> 00:00:46,930
De mi a diákok CS50x most lát, az egy interfész egészen olyan, mint ez.

14
00:00:46,930 --> 00:00:50,040
Ez például, Zamyla vezető walkthrough a probléma set 0.

15
00:00:50,040 --> 00:00:54,230
Amikor bejelentkezik edx.org, a CS50x diák látja a dolgot

16
00:00:54,230 --> 00:00:57,170
elvárható, hogy egy tanfolyam: az előadás Hétfő,

17
00:00:57,170 --> 00:01:01,650
előadás, szerda különböző rövidnadrág, a probléma készletek, a walkthroughs, PDF formátumban.

18
00:01:01,650 --> 00:01:04,459
Ráadásul, mivel itt látsz, gépi fordítás

19
00:01:04,459 --> 00:01:08,390
Az angol nyelvű átirata a kínai, japán, spanyol, olasz,

20
00:01:08,390 --> 00:01:12,810
és egy csomó más nyelveken, hogy minden bizonnyal nem tökéletes

21
00:01:12,810 --> 00:01:15,840
ahogy gördül őket algoritmikusan használ valami úgynevezett API,

22
00:01:15,840 --> 00:01:18,360
vagy alkalmazás programozási felület, a Google-tól

23
00:01:18,360 --> 00:01:21,360
, amely lehetővé teszi számunkra, hogy megtérít angol e más nyelveken.

24
00:01:21,360 --> 00:01:24,100
De hála a csodálatos szellemét néhány száz-plus önkéntesek,

25
00:01:24,100 --> 00:01:26,940
random emberek az interneten, akik kedvesen felajánlotta, hogy vegyenek részt

26
00:01:26,940 --> 00:01:30,180
ebben a projektben, akkor fokozatosan minőségének javítása e fordítások

27
00:01:30,180 --> 00:01:35,790
azáltal, hogy az emberek javítani a hibákat, hogy a számítógépek tettek.

28
00:01:35,790 --> 00:01:42,330
>> Így kiderül, mi volt még néhány diák jelenik meg hétfőn, mint azt eredetileg várták.

29
00:01:42,330 --> 00:01:48,980
Sőt, most már CS50x 100.000 ember követően végig otthon.

30
00:01:48,980 --> 00:01:54,430
Így kiderül, mind része ennek alakuló osztály, hogy ezt az utat a számítástechnikában

31
00:01:54,430 --> 00:01:57,370
oktatás általában szélesebb körben hozzáférhető.

32
00:01:57,370 --> 00:02:00,130
És a valóság most, néhány ilyen masszív online kurzusok,

33
00:02:00,130 --> 00:02:04,070
mindannyian kezdeni ezekkel a nagyon nagy számokat, hiszen úgy tűnik, hogy volna itt.

34
00:02:04,070 --> 00:02:08,759
De a cél, végül pedig az CS50x igazán, hogy minél több ember bevonása a célvonalon, mint lehetséges.

35
00:02:08,759 --> 00:02:12,000
By design, CS50x fog felajánlani a múlt hétfő

36
00:02:12,000 --> 00:02:17,430
végig április 15, 2013, hogy emberek, akik iskolai kötelezettségek mailt,

37
00:02:17,430 --> 00:02:20,990
munka, család, egyéb konfliktusok és hasonlók, egy kicsit több rugalmasságot

38
00:02:20,990 --> 00:02:23,640
amellyel merülni ebbe a tanfolyam, amely elegendő annyit mondani,

39
00:02:23,640 --> 00:02:30,540
meglehetősen ambiciózus történik, ha csak folyamán mindössze három hónap alatt szokásos félévben.

40
00:02:30,540 --> 00:02:34,190
De ezek a diákok is ugyanaz a probléma kezelése készletek, megtekintők ugyanaz a tartalom,

41
00:02:34,190 --> 00:02:36,350
hozzáféréssel rendelkező azonos rövidnadrág és a hasonlók.

42
00:02:36,350 --> 00:02:38,990
Így rájönnek, hogy mindannyian valóban az e együtt.

43
00:02:38,990 --> 00:02:42,360
És az egyik végét céljainak CS50x nem csak azért, hogy a sok ember

44
00:02:42,360 --> 00:02:45,720
a célvonalon, és adjon nekik ez újdonsült megértése számítástechnika

45
00:02:45,720 --> 00:02:49,000
és programozási hanem azokat ezt közös élményt.

46
00:02:49,000 --> 00:02:52,010
Az egyik meghatározó tulajdonsága az 50 az egyetemen, reméljük,

47
00:02:52,010 --> 00:02:56,260
már ez a fajta közösségi élmény, a jobb vagy rosszabb, néha,

48
00:02:56,260 --> 00:02:59,480
de mivel ezek az emberek, hogy forduljon balra és jobbra,

49
00:02:59,480 --> 00:03:01,830
és irodai óra, hackathon és a valós.

50
00:03:01,830 --> 00:03:04,560
Ez egy kicsit nehezebb csinálni, hogy személy emberek online,

51
00:03:04,560 --> 00:03:10,580
de CS50x zárul áprilisban az első CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
melyik lesz egy online adaptációja a mi elképzelésünk a valós

53
00:03:13,630 --> 00:03:18,250
ha ezek a diákok ezrei mind felkérik, hogy nyújtson be egy 1 - 2-perces videó,

54
00:03:18,250 --> 00:03:22,480
vagy egy screencast azok végleges projekt vagy video azok hullámzó helló

55
00:03:22,480 --> 00:03:24,490
és beszél a projektről és demoing azt,

56
00:03:24,490 --> 00:03:27,610
ugyanúgy, mint az elődei volna itt az egyetemen, a tisztességes,

57
00:03:27,610 --> 00:03:31,400
annak érdekében, hogy a félév végére, a remény, hogy egy átfogó kiállítás

58
00:03:31,400 --> 00:03:37,080
A CS50x tanulók végső projektek, ugyanúgy, mint az, ami vár rád decemberben itt az egyetemen.

59
00:03:37,080 --> 00:03:39,680
Tehát többet, hogy az elkövetkező hónapokban.

60
00:03:39,680 --> 00:03:43,640
>> A 100.000 diák, bár, jön a szükség van egy néhány CA.

61
00:03:43,640 --> 00:03:47,590
Tekintettel arra, hogy ti is lángoló a nyomvonalat ide, és figyelembe CS50

62
00:03:47,590 --> 00:03:51,630
néhány héttel ez az anyag szabadon bocsátását, hogy az emberek, az EDX,

63
00:03:51,630 --> 00:03:55,330
észre, mi lenne szeretni bevonni minél több saját diákok lehetséges ezt a kezdeményezést,

64
00:03:55,330 --> 00:03:58,720
mind a félév során, valamint az ezen a télen, és a jövő tavasszal.

65
00:03:58,720 --> 00:04:01,620
Tehát, ha szeretnének részt CS50x,

66
00:04:01,620 --> 00:04:07,450
különösen csatlakozott részt CS50x Fórum, az EDX változata CS50 Fórum,

67
00:04:07,450 --> 00:04:10,140
amelyet sokan közületek korábban már használta az egyetemen, az online hirdetőtábla,

68
00:04:10,140 --> 00:04:13,040
tegye fejét, hogy az URL-t, tudassa velünk, hogy ki vagy,

69
00:04:13,040 --> 00:04:16,450
mert szeretnék felépíteni egy csapatot a hallgatók és oktatók és a tanárok egyaránt

70
00:04:16,450 --> 00:04:19,630
az egyetemen, akik egyszerűen csak játszani végig, és segítettem.

71
00:04:19,630 --> 00:04:21,720
És ha látják a kérdést, ami ismerős számukra,

72
00:04:21,720 --> 00:04:25,320
hallasz egy diák jelentéstételi néhány hiba valahol néhány országban az interneten,

73
00:04:25,320 --> 00:04:27,450
és hogy a gyűrűk egy harang, mert túl volt, hogy ugyanabban a kérdésben

74
00:04:27,450 --> 00:04:32,620
a d-terem néhány évvel ezelőtt, remélhetőleg akkor hangjelzés, és ossza meg saját tapasztalatai.

75
00:04:32,620 --> 00:04:37,300
Ezért kérjük, ne vegyen, ha szeretné.

76
00:04:37,300 --> 00:04:39,360
>> Számítástechnika tanfolyamok Harvard egy kicsit a hagyomány,

77
00:04:39,360 --> 00:04:44,730
CS50 köztük annak, egyes ruházati cikkek, néhány ruhát, amit viselni büszkén

78
00:04:44,730 --> 00:04:49,090
A félév végén, mondván, elég büszkén, hogy befejezte CS50

79
00:04:49,090 --> 00:04:51,830
és elvette CS50 és hasonlók, és igyekszünk bevonni a diákok

80
00:04:51,830 --> 00:04:54,540
ebben a folyamatban, amennyire csak lehetségesek, ahol meghívjuk,

81
00:04:54,540 --> 00:04:56,900
ez idő tájt a félév, a hallgatók, hogy nyújtson be terveket

82
00:04:56,900 --> 00:04:59,330
a Photoshop, vagy bármi más eszköz a választás szeretné használni

83
00:04:59,330 --> 00:05:02,330
ha a tervező, hogy nyújtson be formatervezési pólók és pulóverek

84
00:05:02,330 --> 00:05:06,100
és napernyőkkel és kis tarka selyemkendők kutyák most van, és hasonlók.

85
00:05:06,100 --> 00:05:09,370
És minden ezután - a nyertesek minden évben, majd kiállításra

86
00:05:09,370 --> 00:05:12,700
A kurzus honlapján store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Minden eladott Olcsó ott, de a honlapon csak saját magát működteti

88
00:05:15,790 --> 00:05:18,330
és lehetővé teszi, hogy válassza ki a színek és minták, hogy tetszik.

89
00:05:18,330 --> 00:05:20,420
Szóval azt hittük, csak megosztani a tavalyi tervek

90
00:05:20,420 --> 00:05:25,130
voltak a honlapon kívül ez itt, ami egy éves hagyomány.

91
00:05:25,130 --> 00:05:29,410
"Minden nap vagyok Seg Faultn" egyike volt a beadványok tavaly

92
00:05:29,410 --> 00:05:32,290
amely még mindig rendelkezésre áll ott öregdiák.

93
00:05:32,290 --> 00:05:35,820
Mi volt ez, "CS50, alapították 1989-ben."

94
00:05:35,820 --> 00:05:39,010
Az egyik Bowdens, Rob, nagyon népszerű volt az elmúlt évben.

95
00:05:39,010 --> 00:05:43,480
"Team Bowden" született, ez a kialakítás nyújtottak be, többek között a legjobb eladók.

96
00:05:43,480 --> 00:05:49,040
Mivel ez volt itt. Sok ember volt "Bowden Fever" szerint az eladási naplókat.

97
00:05:49,040 --> 00:05:52,650
Ismerd fel, hogy ami most a design ott fel az interneten.

98
00:05:52,650 --> 00:05:57,510
További részletek erről a következő probléma, állítja, hogy jöjjön.

99
00:05:57,510 --> 00:06:00,330
>> Még egy szerszám: már volt néhány expozíció, és remélhetőleg most

100
00:06:00,330 --> 00:06:02,350
Néhány gyakorlati tapasztalatok GDB,

101
00:06:02,350 --> 00:06:04,570
ami, természetesen, a hibakereső és lehetővé teszi, hogy manipulálják

102
00:06:04,570 --> 00:06:09,500
a program egy viszonylag alacsony szintről, mit csinál dolgokat?

103
00:06:09,500 --> 00:06:13,030
Mit jelent a GDB engedi csinálni?

104
00:06:13,030 --> 00:06:15,030
Igen? Adj valamit. [Student válasz, érthetetlen]

105
00:06:15,030 --> 00:06:18,120
Jó. Lépjen be funkciót, így nem csak azt írja futtatni

106
00:06:18,120 --> 00:06:22,310
és a programot csapást keresztül teljes egészében kinyomtatott dolgokat szabványos kimenetre.

107
00:06:22,310 --> 00:06:25,190
Inkább, akkor lehet lépni rajta soronként, akár gépelés következő

108
00:06:25,190 --> 00:06:30,300
menni soronként sorra vagy lépcső belevetik magukat egy funkciót, általában az egyik, hogy írtál.

109
00:06:30,300 --> 00:06:35,240
Mi mást jelent GDB engedi csinálni? Igen? [Student válasz, érthetetlen]

110
00:06:35,240 --> 00:06:38,100
Nyomtatás változókat. Tehát, ha szeretné, hogy egy kis önvizsgálat belül a program

111
00:06:38,100 --> 00:06:41,500
anélkül, hogy igénybe írásban printf kimutatások az egész hely,

112
00:06:41,500 --> 00:06:44,600
ha csak nyomtatni egy változó, vagy megjelenik egy változó.

113
00:06:44,600 --> 00:06:46,710
Mi mást lehet csinálni egy debugger, mint a GDB?

114
00:06:46,710 --> 00:06:49,170
[Student válasz, érthetetlen]

115
00:06:49,170 --> 00:06:52,080
Pontosan. Beállíthatjuk töréspont, akkor lehet mondani, szünet végrehajtás

116
00:06:52,080 --> 00:06:54,020
a fő funkciója, vagy a foo függvényt.

117
00:06:54,020 --> 00:06:56,800
Azt lehet mondani, szünet végrehajtás sorban 123.

118
00:06:56,800 --> 00:06:58,950
És töréspont egy igazán erős technika

119
00:06:58,950 --> 00:07:01,110
mert ha van egy általános értelemben, ahol a probléma

120
00:07:01,110 --> 00:07:05,360
talán az, hogy nem kell időt vesztegetni fokozása révén a program egészét.

121
00:07:05,360 --> 00:07:08,250
Akkor lényegében ugrani ott majd kezdjen gépelni -

122
00:07:08,250 --> 00:07:10,970
átlépve azt lépéssel vagy mellette vagy a hasonló.

123
00:07:10,970 --> 00:07:14,340
De a fogási valami hasonló GDB, hogy ez segít, az emberi,

124
00:07:14,340 --> 00:07:16,940
találni a problémákra, és keresd meg a hibákat.

125
00:07:16,940 --> 00:07:19,470
Ez nem feltétlenül találja őket annyira neked.

126
00:07:19,470 --> 00:07:23,070
>> Így vezette be a minap style50, ami egy rövid parancssori eszköz

127
00:07:23,070 --> 00:07:27,500
hogy megpróbálja stilizál a kód egy kicsit tisztábban, mint te, az ember, lehet, kész.

128
00:07:27,500 --> 00:07:29,530
De ez is tényleg csak egy esztétikai dolog.

129
00:07:29,530 --> 00:07:34,110
De kiderült, hogy itt van ez a másik eszköz az úgynevezett Valgrind ez egy kicsit misztikus használni.

130
00:07:34,110 --> 00:07:36,860
A kimenet atrociously rejtélyes első pillantásra.

131
00:07:36,860 --> 00:07:39,420
De ez csodálatosan hasznos, különösen most, hogy mi vagyunk a része, a kifejezés

132
00:07:39,420 --> 00:07:43,080
hol kezded használni malloc és dinamikus memória kiosztás.

133
00:07:43,080 --> 00:07:45,420
A dolgok lehet menni nagyon, nagyon rossz gyorsan.

134
00:07:45,420 --> 00:07:49,320
Mert ha elfelejtette, hogy szabad a memóriát, vagy ha valamilyen dereference NULL pointer,

135
00:07:49,320 --> 00:07:55,770
vagy dereference valami szemetet pointer, ami tipikusan a jelenség, hogy az eredmények?

136
00:07:55,770 --> 00:07:59,470
Seg hiba. És hogy ezt a core fájl egyes hány kilobájtot vagy megabyte

137
00:07:59,470 --> 00:08:02,990
amely képviseli az állam a program memóriájában, amikor lezuhant,

138
00:08:02,990 --> 00:08:05,730
de a program végül seg hibák, szegmentálási hiba,

139
00:08:05,730 --> 00:08:08,450
ami azt jelenti, hogy valami rossz történt, szinte mindig kapcsolódik

140
00:08:08,450 --> 00:08:11,750
a memóriával kapcsolatos hibát, amit tett valahol.

141
00:08:11,750 --> 00:08:14,100
Szóval Valgrind segít megtalálni az ilyesmit.

142
00:08:14,100 --> 00:08:17,720
Ez egy eszköz, hogy fut, mint a GDB, miután összeállítani a programot,

143
00:08:17,720 --> 00:08:20,330
hanem mint a program futtatásával közvetlenül futtatni Valgrind

144
00:08:20,330 --> 00:08:23,960
, és adja át neki a program, mint te a GDB.

145
00:08:23,960 --> 00:08:26,220
Most, a használat, hogy a legjobb fajta teljesítmény,

146
00:08:26,220 --> 00:08:30,410
egy kicsit hosszú, így ott a képernyő tetején látni fogod Valgrind-v.

147
00:08:30,410 --> 00:08:35,350
"-V" szinte az egész világon olyan bőbeszédű, ha éppen használ programok Linux számítógépen.

148
00:08:35,350 --> 00:08:38,770
Tehát ez azt jelenti, kiköp több adatot, mint talán alapértelmezés szerint.

149
00:08:38,770 --> 00:08:45,510
"- Szivárgás-ellenőrzés = teljes." Ez csak azt mondom csekket minden lehetséges memóriavesztés,

150
00:08:45,510 --> 00:08:49,430
hibákat, hogy talán volna. Ez is egy közös paradigma Linux programokat.

151
00:08:49,430 --> 00:08:52,710
Általában, ha egy parancssori argumentum, hogy ez a "kapcsoló",

152
00:08:52,710 --> 00:08:55,830
hogy kéne változtatni a program viselkedését, és ez egy levél,

153
00:08:55,830 --> 00:09:00,310
ez-v, de ha ez kapcsolva, csak a design a programozó,

154
00:09:00,310 --> 00:09:05,150
van egy teljes szót vagy sorozat szavakkal, a parancssori argumentum kezdődik -.

155
00:09:05,150 --> 00:09:08,190
Ezek csak emberi egyezményeket, de akkor látni őket egyre.

156
00:09:08,190 --> 00:09:12,410
És aztán, végül "a.out" a önkényes nevet a program az adott példában.

157
00:09:12,410 --> 00:09:14,640
És itt van néhány reprezentatív kimenet.

158
00:09:14,640 --> 00:09:22,890
>> Mielőtt megnézzük, hogy ez mit is jelent, hadd menjen át a kódrészletet ide.

159
00:09:22,890 --> 00:09:26,390
És hadd mozgatni ezt az útból, jön hamarosan,

160
00:09:26,390 --> 00:09:32,120
és vessünk egy pillantást memory.c, amely e rövid példa itt.

161
00:09:32,120 --> 00:09:36,290
Tehát ebben a programban, hadd nagyításához funkciók és kérdéseket.

162
00:09:36,290 --> 00:09:39,430
Van egy fontos funkciója, hogy meghív egy függvényt, f,

163
00:09:39,430 --> 00:09:45,590
és akkor mit jelent f folytassa csinálni, kissé műszaki angolul?

164
00:09:45,590 --> 00:09:49,760
Mit f folytassa csinálni?

165
00:09:49,760 --> 00:09:53,680
Mi lenne, kezdjük a 20 vezetéken, és a csillag helyét nem számít,

166
00:09:53,680 --> 00:09:56,720
de én csak itt kell lenniük utolsó előadás.

167
00:09:56,720 --> 00:09:59,910
Mi van a 20 vezetéken nem nekünk? A bal oldalon. Fogjuk lebontani tovább.

168
00:09:59,910 --> 00:10:02,410
Int * x: mit tegyek?

169
00:10:02,410 --> 00:10:04,940
Oké. Ez nyilvánító mutató, és most legyünk még inkább technikai jellegű.

170
00:10:04,940 --> 00:10:10,230
Mit jelent ez, nagyon konkrétan, hogy állapítsa meg a mutató? Valaki más?

171
00:10:10,230 --> 00:10:15,050
Igen? [Student válasz, érthetetlen] Túl messzire.

172
00:10:15,050 --> 00:10:17,060
Szóval olvasni a jobb oldali az egyenlőségjel.

173
00:10:17,060 --> 00:10:20,290
Nézzük összpontosít csak a bal oldalon, csak az int * x.

174
00:10:20,290 --> 00:10:24,700
Ez nem "nyilvánítja" a mutató, de most hadd merüljön mélyebbre e meghatározás.

175
00:10:24,700 --> 00:10:28,330
Mit jelent ez konkrétan, technikailag jelent? Igen?

176
00:10:28,330 --> 00:10:31,940
[Student válasz, érthetetlen]

177
00:10:31,940 --> 00:10:35,090
Oké. Úgy készül, hogy megmentse egy címet a memóriában.

178
00:10:35,090 --> 00:10:40,680
Jó. És vegyük ezt egy lépéssel tovább, ez nyilvánító változó, x, ez 32 bites.

179
00:10:40,680 --> 00:10:44,440
És tudom, hogy ez 32 bit, mert -?

180
00:10:44,440 --> 00:10:47,390
Nem azért, mert ez egy int, mert ez a mutató ebben az esetben.

181
00:10:47,390 --> 00:10:49,650
Véletlen egybeesés, hogy ez egy és ugyanazon egy int,

182
00:10:49,650 --> 00:10:51,970
de az a tény, hogy ott van a csillag van jelent ez a mutató

183
00:10:51,970 --> 00:10:57,300
és a készülék, mint sok számítógép, de nem az összes mutató 32 bit.

184
00:10:57,300 --> 00:11:01,850
A több modern hardvert, mint a legújabb Mac, a legújabb PC-k, lehet, hogy 64-bites mutatók,

185
00:11:01,850 --> 00:11:04,160
de a készülék, ezek a dolgok 32 bit.

186
00:11:04,160 --> 00:11:08,380
Így fogjuk egységesíteni rajta. Konkrétabban, a történet a következő:

187
00:11:08,380 --> 00:11:10,820
Mi "nyilvánítja" a mutató, ez mit jelent?

188
00:11:10,820 --> 00:11:12,810
Készítünk tárolja a memória címet.

189
00:11:12,810 --> 00:11:15,530
Mit jelent ez?

190
00:11:15,530 --> 00:11:19,810
Készítünk egy változó un x, hogy vesz fel 32 bites

191
00:11:19,810 --> 00:11:23,810
hogy hamarosan tárolja címét egy egész szám.

192
00:11:23,810 --> 00:11:26,470
És ez valószínűleg a legpontosabb juthatunk.

193
00:11:26,470 --> 00:11:31,810
Ez rendben halad előre, hogy egyszerűsítse a világ és csak annyit nyilvánítja mutató úgynevezett x.

194
00:11:31,810 --> 00:11:35,380
Állapítsa meg a mutató, de a megvalósítása, és megérteni, hogy mi folyik itt valójában

195
00:11:35,380 --> 00:11:38,490
még csak a néhány karakter.

196
00:11:38,490 --> 00:11:42,040
>> Nos, ez már majdnem egy kicsit könnyebb, bár ez egy hosszabb kifejezés.

197
00:11:42,040 --> 00:11:48,160
Szóval, mit keres ez, ez most kiemelte: "malloc (10 * sizeof (int));" Igen?

198
00:11:48,160 --> 00:11:52,350
[Student válasz, érthetetlen]

199
00:11:52,350 --> 00:11:58,250
Jó. És én viszem oda. Ez kiosztása egy darab memória 10 egészek.

200
00:11:58,250 --> 00:12:02,190
És most hadd merüljön kissé mélyebbre, ez kiosztása egy darab memória 10 egészek.

201
00:12:02,190 --> 00:12:05,390
Mi malloc akkor visszatér?

202
00:12:05,390 --> 00:12:10,390
A címét darabos, vagy konkrétabban a címe az első bájt adott darab.

203
00:12:10,390 --> 00:12:14,080
Hogy akkor vagyok, a programozó, hogy hol, hogy a darab végén a memória?

204
00:12:14,080 --> 00:12:18,340
Tudom, hogy ez folytonos. Malloc, definíció szerint, kapsz egy folytonos darab memória.

205
00:12:18,340 --> 00:12:21,240
Nem hiányosságok benne. Hozzá tud férni minden byte e darab,

206
00:12:21,240 --> 00:12:26,760
háttal hátra, de hogyan tudom, hol a vége ennek a darab memória?

207
00:12:26,760 --> 00:12:28,850
Amikor malloc? [Student válasz, érthetetlen] Jó.

208
00:12:28,850 --> 00:12:30,670
Tényleg nem. Meg kell emlékezni.

209
00:12:30,670 --> 00:12:35,960
Meg kell emlékezni, hogy én használt a 10 értéket, és nem is úgy tűnik, hogy kellett volna ide.

210
00:12:35,960 --> 00:12:41,000
De a felelősség teljes mértékben rám. Strlen, amit lettél kissé függ a húrok,

211
00:12:41,000 --> 00:12:45,860
működik, csak azért, mert az egyezmény annak, \ 0

212
00:12:45,860 --> 00:12:48,840
vagy a speciális NULL karakter, NUL végén egy string.

213
00:12:48,840 --> 00:12:51,740
Ez nem tart mindössze tetszőleges darabokat memória.

214
00:12:51,740 --> 00:12:58,590
Ez rajtad múlik. Szóval a 20 vezetéken, majd lefoglal egy darab memória

215
00:12:58,590 --> 00:13:02,590
, amely képes tárolni 10 egész számok, és tárolja a címét az első bájt

216
00:13:02,590 --> 00:13:05,610
E darab memória a nevű változó x.

217
00:13:05,610 --> 00:13:11,140
Ergo, ami a mutató. Szóval vonal 21, sajnos, hiba volt.

218
00:13:11,140 --> 00:13:16,110
De először is, mit csinál? Ez mondja áruház a helyszínen 10, 0 indexelt,

219
00:13:16,110 --> 00:13:19,480
A darab az úgynevezett memória x értéke 0-ra.

220
00:13:19,480 --> 00:13:21,510
>> Tehát észre egy pár dolog folyik.

221
00:13:21,510 --> 00:13:25,420
Annak ellenére, hogy x egy mutatót, visszahívja a pár héttel ezelőtt

222
00:13:25,420 --> 00:13:29,440
hogy továbbra is használhatja a tömb stílusú szögletes zárójel jelöléssel.

223
00:13:29,440 --> 00:13:36,180
Mert ez tényleg rövid oldali jelölést a több rejtélyes kinézetű mutató számtani.

224
00:13:36,180 --> 00:13:40,320
ha tennénk valami ilyesmit: Fogd a cím x, mozgás 10 foltok felett,

225
00:13:40,320 --> 00:13:44,550
akkor megy oda, hogy bármilyen címen tárolják az adott helyen.

226
00:13:44,550 --> 00:13:48,090
De őszintén szólva, ez csak szörnyű, hogy olvassa el, és kap kényelmes.

227
00:13:48,090 --> 00:13:52,900
Így a világ általában használja a szögletes zárójelek csak azért, mert sokkal több ember-barát olvasni.

228
00:13:52,900 --> 00:13:55,140
De ez az, amit igazán folyik a motorháztető alatt;

229
00:13:55,140 --> 00:13:58,190
x egy cím, nem egy tömb, per se.

230
00:13:58,190 --> 00:14:02,410
Szóval ez tárolja a 0 helyen a 10 x.

231
00:14:02,410 --> 00:14:06,120
Miért van ez rossz? Igen?

232
00:14:06,120 --> 00:14:17,370
[Student válasz, érthetetlen] Pontosan.

233
00:14:17,370 --> 00:14:21,100
Csak kiosztott 10 ints, de számolni 0-tól, amikor programozás C,

234
00:14:21,100 --> 00:14:25,690
így hozzáférhet 0 1 2 3 4 5 6 7 8 9, de nem 10-ig.

235
00:14:25,690 --> 00:14:30,270
Szóval vagy a program fog seg hibája vagy nem.

236
00:14:30,270 --> 00:14:32,900
De nem igazán tudom, ez egyfajta nemdeterminisztikus viselkedés.

237
00:14:32,900 --> 00:14:35,600
Ez tényleg attól függ, hogy mi szerencsénk.

238
00:14:35,600 --> 00:14:40,650
Ha kiderül, hogy az operációs rendszer nem bánja, ha használni, hogy extra byte,

239
00:14:40,650 --> 00:14:43,360
annak ellenére, hogy nem adott el nekem, a program esetleg nem összeomolhat.

240
00:14:43,360 --> 00:14:46,780
Ez a nyers, ez hibás, de lehet, hogy nem látja, hogy tünet,

241
00:14:46,780 --> 00:14:48,960
vagy lehet, hogy látni csak egyszer egy darabig.

242
00:14:48,960 --> 00:14:51,230
De a valóság az, hogy a hiba, sőt, ott.

243
00:14:51,230 --> 00:14:54,320
És ez nagyon problematikus, ha már írt egy programot, amely azt szeretné, hogy helyes,

244
00:14:54,320 --> 00:14:58,840
hogy már eladta a programot, hogy az emberek használják, hogy hébe-hóba összeomlik

245
00:14:58,840 --> 00:15:02,450
mert természetesen, ez nem jó. Sőt, ha van egy Android telefont vagy egy iPhone

246
00:15:02,450 --> 00:15:05,550
és letölteni apps ezekben a napokban, ha valaha is volt egy app csak kilép,

247
00:15:05,550 --> 00:15:10,040
hirtelen eltűnik, ez szinte mindig az eredménye néhány memóriával kapcsolatos kérdés,

248
00:15:10,040 --> 00:15:12,830
ahol a programozó elszúrta, és másolunk egy mutató

249
00:15:12,830 --> 00:15:18,670
arról, hogy nem kellett volna, és az eredmény a iOS vagy Android, hogy csak megölni a program összesen

250
00:15:18,670 --> 00:15:23,080
kockázat helyett meghatározatlan viselkedést vagy valamilyen biztonsági kompromisszumot.

251
00:15:23,080 --> 00:15:25,950
>> Van egy másik hiba az e program mellett ezt.

252
00:15:25,950 --> 00:15:30,180
Mi mást is elcsesztem ebben a programban?

253
00:15:30,180 --> 00:15:32,740
Már nem gyakorolják, azt, amit prédikált. Igen?

254
00:15:32,740 --> 00:15:34,760
[Student válasz, érthetetlen] Jó.

255
00:15:34,760 --> 00:15:36,880
Még nem szabadult a memóriát. Tehát a szabály most

256
00:15:36,880 --> 00:15:43,150
kell, hogy legyen, amikor csak hívja malloc, fel kell hívnia ingyenes, ha végezzük, hogy a memóriát.

257
00:15:43,150 --> 00:15:45,610
Most, amikor azt akarom, hogy kiszabadítsa a memória?

258
00:15:45,610 --> 00:15:49,780
Valószínűleg, feltételezve, hogy ez az első sor helyes volt, azt akarom csinálni itt.

259
00:15:49,780 --> 00:15:55,710
Mert nem tudtam például, tedd le ide. Miért?

260
00:15:55,710 --> 00:15:57,860
Csak ki a hatálya alól. Így annak ellenére, hogy beszélünk mutatók,

261
00:15:57,860 --> 00:16:04,830
ez egy héten 2 vagy 3 kérdés, ahol az x csak a hatálya alá belsejében kapcsos zárójelek, ahol megadták.

262
00:16:04,830 --> 00:16:11,000
Így biztosan nem lehet kiszabadítani ott. Az egyetlen esély, hogy kiszabadítsa az hozzávetőleg után sor 21.

263
00:16:11,000 --> 00:16:15,170
Ez egy viszonylag egyszerű program, ez meglehetősen egyszerű, ha egyszer ilyen becsomagolt fejedben

264
00:16:15,170 --> 00:16:17,870
körül, amit a program csinál, ahol a hibák voltak.

265
00:16:17,870 --> 00:16:20,500
És akkor is, ha nem látod az első, remélhetőleg ez egy kicsit most már nyilvánvaló,

266
00:16:20,500 --> 00:16:23,870
hogy ezek a hibák elég könnyen megoldható, és könnyen sor.

267
00:16:23,870 --> 00:16:28,720
De ha a program több mint 12 sor hosszú, ez 50 sor hosszú, 100 sor hosszú,

268
00:16:28,720 --> 00:16:31,150
séta a kódot sorról sorra, és arra gondolt át logikusan,

269
00:16:31,150 --> 00:16:35,110
lehetséges, de nem különösebben szórakoztató csinálni, folyamatosan keresi a hibákat,

270
00:16:35,110 --> 00:16:38,340
és ez is nehéz csinálni, és ezért egy olyan eszköz, mint a Valgrind létezik.

271
00:16:38,340 --> 00:16:40,900
Hadd menjek előre, és ezt: hadd kinyitom a terminál ablak,

272
00:16:40,900 --> 00:16:45,400
és hadd ne csak fuss memóriában, mert a memória úgy tűnik, hogy rendben van.

273
00:16:45,400 --> 00:16:49,180
Kezdek szerencsés. Megy, hogy a további bájt végén a tömb

274
00:16:49,180 --> 00:16:51,060
nem tűnik túl problematikus.

275
00:16:51,060 --> 00:16:56,370
De hadd, mégis, nem a józan ellenőrzést, ami csak annyit jelent, hogy ellenőrizze

276
00:16:56,370 --> 00:16:58,320
függetlenül attól, hogy ez valójában helyes.

277
00:16:58,320 --> 00:17:04,690
>> Tehát lássuk valgrind-v - szivárgás-ellenőrzés = teljes,

278
00:17:04,690 --> 00:17:07,520
majd a neve a program ebben az esetben memória, nem a.out.

279
00:17:07,520 --> 00:17:10,760
Szóval hadd menjen előre, és ezt. Hit Enter billentyűt.

280
00:17:10,760 --> 00:17:14,109
Édes Istenem. Ez a teljesítmény, és ez az, amit utalt korábban.

281
00:17:14,109 --> 00:17:17,550
De, ha megtanulják, hogy olvassa el az összes értelmetlen itt,

282
00:17:17,550 --> 00:17:20,760
ennek nagy része csak a diagnosztikai kimenet, hogy ez nem olyan érdekes.

283
00:17:20,760 --> 00:17:24,829
Mi a szeme igazán akar keresni bármilyen említése hiba vagy érvénytelen.

284
00:17:24,829 --> 00:17:26,800
Szavak, amelyek azt sugallják problémákat.

285
00:17:26,800 --> 00:17:29,340
És valóban, lássuk, mi baj idelent.

286
00:17:29,340 --> 00:17:35,230
Nekem van egy összefoglalót valamiféle "használatban lévő kijáratnál: 40 bytes in 1 blokkokat."

287
00:17:35,230 --> 00:17:38,750
Nem vagyok biztos benne, mi a blokk még, de 40 bájt

288
00:17:38,750 --> 00:17:41,260
tényleg olyan, mintha tudtam kitalálni, hogy hol ez jön.

289
00:17:41,260 --> 00:17:45,030
40 bájt. Miért 40 bájt használatban kijárat?

290
00:17:45,030 --> 00:17:48,780
És még pontosabban, ha lapozzunk lefelé ide,

291
00:17:48,780 --> 00:17:54,520
miért Én határozottan vereség a 40 bájt? Igen?

292
00:17:54,520 --> 00:17:59,520
[Student válasz, érthetetlen] Perfect. Igen, pontosan.

293
00:17:59,520 --> 00:18:03,540
Volt tíz egész számok, és minden egyes ilyen a méret 4, vagy 32 bit,

294
00:18:03,540 --> 00:18:08,300
így elvesztettem pontosan 40 bájt, mert, ahogy javasolta, én még nem hívott szabad.

295
00:18:08,300 --> 00:18:13,460
Ez egy hiba, és most nézzük meg egy kicsit tovább, és lásd a következő e,

296
00:18:13,460 --> 00:18:16,900
"Érvénytelen levelet a 4-es méretű." Most mi ez?

297
00:18:16,900 --> 00:18:21,150
Ez a cím van kifejezve mit bázis jelölés, látszólag?

298
00:18:21,150 --> 00:18:23,640
Ez hexadecimális, és minden alkalommal, amikor megjelenik egy számot kezdődő 0x,

299
00:18:23,640 --> 00:18:29,410
ez azt jelenti, hexadecimális, amit csináltunk utat vissza, azt hiszem, Pset 0 szekció kérdések,

300
00:18:29,410 --> 00:18:34,090
ami csak csinál egy warmup gyakorlat átalakítása tizedes hex bináris és így tovább.

301
00:18:34,090 --> 00:18:39,220
Hexadecimális, csak emberi konvenció, általában arra használják, hogy képviselje mutatók

302
00:18:39,220 --> 00:18:41,570
vagy még általánosabban foglalkozik. Ez csak egy egyezmény,

303
00:18:41,570 --> 00:18:45,340
mert ez egy kicsit könnyebb olvasni, ez egy kicsit kompaktabb, mint valami hasonlót decimális,

304
00:18:45,340 --> 00:18:47,720
és bináris használhatatlan a legtöbb ember használja.

305
00:18:47,720 --> 00:18:50,840
Tehát most mit jelent ez? Nos, úgy néz ki, van egy érvénytelen write

306
00:18:50,840 --> 00:18:54,480
A 4-es méretű on line 21 A memory.c.

307
00:18:54,480 --> 00:18:59,180
Akkor térjünk vissza a vonal 21, és valóban, itt van, hogy érvénytelen írás.

308
00:18:59,180 --> 00:19:02,640
Tehát Valgrind nem fog teljesen fogd meg a kezem, és mondd el, mi a javítás,

309
00:19:02,640 --> 00:19:05,520
de azt érzékeli, hogy csinálok egy érvénytelen write.

310
00:19:05,520 --> 00:19:08,800
Én megható 4 byte, amit nem kellene, és nyilvánvalóan azért, mert,

311
00:19:08,800 --> 00:19:13,960
ahogy rámutatott, csinálok [10] helyett [9] maximálisan

312
00:19:13,960 --> 00:19:16,660
vagy a [0] vagy valami a kettő között.

313
00:19:16,660 --> 00:19:19,690
A Valgrind, észre bármikor te most írásban a program

314
00:19:19,690 --> 00:19:24,190
használó mutatók és használ memóriát, és malloc még pontosabban,

315
00:19:24,190 --> 00:19:27,080
határozottan bejutni a szokása, futás a hosszú

316
00:19:27,080 --> 00:19:30,890
de nagyon könnyen a vágólapra másolni parancs Valgrind

317
00:19:30,890 --> 00:19:32,650
hogy ha van valami hiba van.

318
00:19:32,650 --> 00:19:34,820
És ez lesz nyomasztó minden alkalommal megjelenik a kimenet,

319
00:19:34,820 --> 00:19:39,430
de csak feldolgozni révén vizuálisan az összes kimenetet, és ha látod megemlíti hibák

320
00:19:39,430 --> 00:19:43,190
vagy figyelmeztetéseket vagy érvénytelen vagy elveszett.

321
00:19:43,190 --> 00:19:46,200
Bármely szó, hogy a hang, mint te elcseszted valahol.

322
00:19:46,200 --> 00:19:48,580
Szóval észre, hogy ez egy új eszköz a toolkit.

323
00:19:48,580 --> 00:19:51,270
>> Most hétfőn, volt egy csomó emberek jönnek ide

324
00:19:51,270 --> 00:19:53,150
és képviseli fogalma a láncolt lista.

325
00:19:53,150 --> 00:20:00,970
És mi vezetett a csatolt lista megoldást, hogy milyen probléma?

326
00:20:00,970 --> 00:20:04,590
Igen? [Student válasz, érthetetlen] Jó.

327
00:20:04,590 --> 00:20:06,530
Tömbök nem lehet memóriát szerepel.

328
00:20:06,530 --> 00:20:09,440
Ha osztja egy sor 10-es méret, ez minden, amit kap.

329
00:20:09,440 --> 00:20:13,690
Hívhatja egy függvény, mint realloc ha eredetileg hívott malloc,

330
00:20:13,690 --> 00:20:17,580
és hogy próbálja, hogy növekszik a tömb, ha van hely a vége felé, hogy

331
00:20:17,580 --> 00:20:21,610
hogy senki más nem használja, és ha ott nem, akkor csak meg egy nagyobb darab valahol máshol.

332
00:20:21,610 --> 00:20:25,040
De akkor azt fogja másolni az összes e bájt az új tömb.

333
00:20:25,040 --> 00:20:28,310
Ez úgy hangzik, mint egy nagyon helyes megoldást.

334
00:20:28,310 --> 00:20:34,790
Miért van ez vonzó?

335
00:20:34,790 --> 00:20:36,940
Úgy értem, hogy működik, az emberek már megoldotta ezt a problémát.

336
00:20:36,940 --> 00:20:40,710
Miért kell megoldani, hogy hétfőn a kapcsolt listák? Igen?

337
00:20:40,710 --> 00:20:44,060
[Student válasz, érthetetlen] Ez lehet hosszú időt vesz igénybe.

338
00:20:44,060 --> 00:20:49,260
Tény, hogy minden alkalommal, amikor hívsz malloc vagy realloc vagy calloc, ami még egy másik,

339
00:20:49,260 --> 00:20:52,470
minden alkalommal, amikor a program, beszél az operációs rendszer,

340
00:20:52,470 --> 00:20:54,310
Ön inkább lassítani a programot le.

341
00:20:54,310 --> 00:20:57,470
És ha csinálsz efféle dolgok hurkok, te tényleg lassul dolgokat.

342
00:20:57,470 --> 00:21:00,740
Nem fogod észrevenni ezt a legegyszerűbb "hello world" típusú programok,

343
00:21:00,740 --> 00:21:04,300
de sokkal nagyobb programok, kérve az operációs rendszer újra és újra a memória

344
00:21:04,300 --> 00:21:07,520
vagy arra, hogy újra és újra inkább, hogy nem egy jó dolog.

345
00:21:07,520 --> 00:21:11,210
Plusz, ez csak egyfajta intellektuális - ez egy teljes időpocsékolás.

346
00:21:11,210 --> 00:21:16,490
Miért fordítsanak több és több memóriát, kockázati másolás mindent az új tömb,

347
00:21:16,490 --> 00:21:21,980
ha van egy másik, amely lehetővé teszi kiosztani csak annyi memóriát valóban szükséged?

348
00:21:21,980 --> 00:21:24,130
Szóval van pluses és minuses itt.

349
00:21:24,130 --> 00:21:26,730
Az egyik pluses most, hogy van dinamizmus.

350
00:21:26,730 --> 00:21:29,100
Nem számít, ha a darabokat memória az, hogy szabad,

351
00:21:29,100 --> 00:21:32,070
Én csak egyfajta létrehozni ezeket a zsemlemorzsa keresztül mutatók

352
00:21:32,070 --> 00:21:34,470
hogy string az egész láncolt lista együtt.

353
00:21:34,470 --> 00:21:36,470
De fizetni legalább egy árat.

354
00:21:36,470 --> 00:21:40,060
>> Mit kell feladni árán kapcsolt listák?

355
00:21:40,060 --> 00:21:42,470
Igen? [Student válasz, érthetetlen] Jó.

356
00:21:42,470 --> 00:21:45,650
Szükséged van több memóriát igényel. Most kell helyet ezen mutatók,

357
00:21:45,650 --> 00:21:47,900
és abban az esetben ennek a szuper egyszerű láncolt lista

358
00:21:47,900 --> 00:21:51,410
hogy csak próbál tárolni egészek, amelyek 4 bájt, tartjuk mondván:

359
00:21:51,410 --> 00:21:54,240
is, a mutató 4 byte, így most már szó szerint megduplázódott

360
00:21:54,240 --> 00:21:57,290
A memória van szükségem, csak tárolni ezt a listát.

361
00:21:57,290 --> 00:21:59,680
De ismétlem, ez egy állandó kompromisszum számítástechnika

362
00:21:59,680 --> 00:22:03,440
közötti idő és a tér és fejlesztés, erőfeszítés és egyéb források.

363
00:22:03,440 --> 00:22:06,630
Mi van a másik hátránya segítségével láncolt lista? Igen?

364
00:22:06,630 --> 00:22:10,150
[Student válasz, érthetetlen]

365
00:22:10,150 --> 00:22:12,600
Jó. Nem olyan könnyű hozzáférni. Mi lehet többé tőkeáttétel

366
00:22:12,600 --> 00:22:15,530
hét 0 elveket, mint oszd meg és uralkodj.

367
00:22:15,530 --> 00:22:18,220
És konkrétabban, bináris keresés. Mert annak ellenére, hogy mi, emberek

368
00:22:18,220 --> 00:22:20,400
láthatjuk, ahol nagyjából a közepén ez a lista,

369
00:22:20,400 --> 00:22:25,840
A számítógépet csak tudja, hogy ez láncolt lista indul címen hívott először.

370
00:22:25,840 --> 00:22:28,250
És ez 0x123, vagy valami ilyesmi.

371
00:22:28,250 --> 00:22:30,990
És az egyetlen módja a program megtalálja a középső elem

372
00:22:30,990 --> 00:22:33,350
hogy valójában keresni a teljes listát.

373
00:22:33,350 --> 00:22:35,500
És még akkor is, szó szerint meg kell keresni a teljes lista, mert

374
00:22:35,500 --> 00:22:38,950
még akkor is, ha eléri a középső elem az alábbiak szerint mutatók,

375
00:22:38,950 --> 00:22:42,380
te, a programot, fogalmam sincs, milyen hosszú ez a lista, potenciálisan,

376
00:22:42,380 --> 00:22:45,250
amíg eléred a végét, és hogyan tudod programozottan

377
00:22:45,250 --> 00:22:48,600
hogy te vagy a végén a láncolt lista?

378
00:22:48,600 --> 00:22:51,120
Van egy speciális NULL pointer, így ismét egy ilyen egyezmény.

379
00:22:51,120 --> 00:22:53,870
Ahelyett, hogy ezt a mutatót, hogy biztosan nem akarom, hogy valami szemetet érték

380
00:22:53,870 --> 00:22:57,750
rámutatva a színpadon valahol, azt akarjuk, hogy kézzel le, NULL,

381
00:22:57,750 --> 00:23:01,530
annak érdekében, hogy itt van ez a végállomás ezen adatszerkezet, így tudjuk, hogy hol végződik.

382
00:23:01,530 --> 00:23:03,410
>> Mi van, ha azt akarjuk, hogy manipulálja ezt?

383
00:23:03,410 --> 00:23:05,980
Mi volt ennek nagy része vizuálisan, és az emberek,

384
00:23:05,980 --> 00:23:07,630
de mi van, ha azt akarjuk, hogy csinál egy helyezés?

385
00:23:07,630 --> 00:23:12,360
Így az eredeti listában volt a 9., 17., 20., 22., 29., 34..

386
00:23:12,360 --> 00:23:16,730
Mi lenne, ha akkor volna malloc hely száma 55, egy csomópont rá,

387
00:23:16,730 --> 00:23:20,730
és akkor szeretné szúrni 55 a lista ahogy tettük hétfőn?

388
00:23:20,730 --> 00:23:23,690
Hogyan tudjuk ezt megtenni? Nos, Anita jött, és ő lényegében elindult a listán.

389
00:23:23,690 --> 00:23:27,500
Elindult az első elem, akkor a következő, a következő, a következő, a következő, a következő.

390
00:23:27,500 --> 00:23:29,500
Végül nyomja meg a bal oldali egészen

391
00:23:29,500 --> 00:23:34,480
és rájött, oh, ez NULL. Tehát mi pointer manipuláció kellett tenni?

392
00:23:34,480 --> 00:23:37,980
Az a személy, aki a végén, a 34, szükséges a bal kezét emelte

393
00:23:37,980 --> 00:23:46,220
pont a 55, 55 szükséges, a bal kar lefelé, hogy az új, NULL terminátor. Kész.

394
00:23:46,220 --> 00:23:49,540
Elég könnyen be 55 egy rendezett listát.

395
00:23:49,540 --> 00:23:51,800
És hogyan lehet ezt ki?

396
00:23:51,800 --> 00:23:55,690
>> Hadd menjek előre, és nyissa fel néhány kódot példának.

397
00:23:55,690 --> 00:23:58,120
Majd én nyit gedit, hadd nyit két fájlt először.

398
00:23:58,120 --> 00:24:02,050
Az egyik list1.h, és hadd emlékeztessem, hogy ez a darab a kód

399
00:24:02,050 --> 00:24:04,920
hogy használják, hogy képviselje a csomópont.

400
00:24:04,920 --> 00:24:13,040
A csomópont egyaránt int hívott n, és egy mutatót nevű next hogy csak rámutat a következő dolog a listán.

401
00:24:13,040 --> 00:24:15,450
Ez most egy. H fájlt. Miért?

402
00:24:15,450 --> 00:24:19,090
Van ez a konvenció, és még nem vette igénybe ezt a hatalmas összeget magunkat,

403
00:24:19,090 --> 00:24:22,220
de az a személy, aki írta printf és egyéb funkciók

404
00:24:22,220 --> 00:24:27,150
adott, mint egy ajándék a világ összes ilyen funkciók írt nevű fájlt stdio.h.

405
00:24:27,150 --> 00:24:30,950
És akkor ott van string.h, és akkor ott van map.h, és ott ezek h fájl

406
00:24:30,950 --> 00:24:34,410
hogy lehet, hogy látott vagy használt futamideje alatt írta, más emberek.

407
00:24:34,410 --> 00:24:38,470
Jellemzően e. H fájlok csak dolgok, mint typedefs

408
00:24:38,470 --> 00:24:42,310
vagy nyilatkozatok egyéni típusú vagy nyilatkozatok állandók.

409
00:24:42,310 --> 00:24:47,890
Nem valósult funkciók "megvalósítások header fájlokat.

410
00:24:47,890 --> 00:24:50,570
Tedd helyett, csak a prototípusok.

411
00:24:50,570 --> 00:24:53,050
Azt tegyük a dolgokat szeretné megosztani a világgal, amire szükségük van

412
00:24:53,050 --> 00:24:55,640
annak érdekében, hogy lefordítanak kódokat. Szóval, csak azért, hogy ebbe a szokás,

413
00:24:55,640 --> 00:24:59,110
úgy döntöttünk, hogy nem ugyanaz a dolog. Nincs sok list1.h,

414
00:24:59,110 --> 00:25:02,070
de már fel valamit, ami talán érdekes lehet, hogy az emberek a világ

415
00:25:02,070 --> 00:25:05,030
, akik szeretnék használni a linkelt lista végrehajtását.

416
00:25:05,030 --> 00:25:08,040
Most, list1.c, nem megyek át ezt az egész dolgot

417
00:25:08,040 --> 00:25:11,390
mert ez egy kicsit hosszú, ez a program, de inkább futni it real gyorsan a billentyűket.

418
00:25:11,390 --> 00:25:15,720
Hadd összeállításához lista1, hadd majd futtassa lista1, és mit fog látni a

419
00:25:15,720 --> 00:25:18,070
voltunk szimulált egy egyszerű kis program itt

420
00:25:18,070 --> 00:25:20,990
hogy fog engedjék meg, hogy hozzá, és távolítsa el a számokat a listából.

421
00:25:20,990 --> 00:25:24,310
Szóval hadd menjen előre, és írja be 3 a 3 menüopció.

422
00:25:24,310 --> 00:25:27,880
Azt akarom, hogy illessze be a számot - csináljuk az első szám, ami 9,

423
00:25:27,880 --> 00:25:30,550
és most mondtam a lista most már 9.

424
00:25:30,550 --> 00:25:33,760
Hadd menjek előre, és csinálni egy másik beillesztés, így elütöttem 3 menüopció.

425
00:25:33,760 --> 00:25:36,760
Milyen számon akarok beszúrni? 17.

426
00:25:36,760 --> 00:25:39,220
Az Enter billentyűt. És én nem csak egy.

427
00:25:39,220 --> 00:25:41,720
Hadd illessze be a számot 22.

428
00:25:41,720 --> 00:25:45,850
Tehát a kezdetektől a láncolt lista, hogy mi volt a dia formában egy pillanattal ezelőtt.

429
00:25:45,850 --> 00:25:48,740
Hogy van ez helyezés valójában történik?

430
00:25:48,740 --> 00:25:52,000
Valóban, a 22-nél a jelenleg a lista végén.

431
00:25:52,000 --> 00:25:55,050
Szóval a történet mondtuk színpadra hétfőn és recapped most

432
00:25:55,050 --> 00:25:57,460
ténylegesen ki kell történik kódot.

433
00:25:57,460 --> 00:25:59,700
Vessünk egy pillantást. Hadd lapozzunk le ezt a fájlt.

434
00:25:59,700 --> 00:26:01,720
Majd elkendőz néhány funkciót,

435
00:26:01,720 --> 00:26:05,630
de megyünk le, mondjuk, a betét funkciót.

436
00:26:05,630 --> 00:26:11,720
>> Lássuk, hogyan megyünk behelyezésével egy új csomópont ebbe kapcsolt listát.

437
00:26:11,720 --> 00:26:14,550
Hol van a listán bejelentett? Nos, lapozzunk egészen a tetején,

438
00:26:14,550 --> 00:26:19,970
, és vegyük észre, hogy az én láncolt lista lényegében nyilvánították egyetlen mutató, ami kezdetben NULL.

439
00:26:19,970 --> 00:26:23,180
Szóval egy globális változó van, amely általában általunk ellen prédikált

440
00:26:23,180 --> 00:26:25,280
mert ez teszi a kódot egy kicsit rendetlen fenntartani,

441
00:26:25,280 --> 00:26:29,080
ez a fajta lusta, általában, de ez nem lusta, és ez nem rossz, és ez nem rossz

442
00:26:29,080 --> 00:26:33,660
ha a program egyetlen célja az életben, hogy szimulálja 1 linkelt listáról.

443
00:26:33,660 --> 00:26:35,460
Ami pontosan az, amit csinálunk.

444
00:26:35,460 --> 00:26:39,100
Tehát ahelyett, állapítsa meg ennek a fő, majd el kell telnie, hogy minden funkció

445
00:26:39,100 --> 00:26:42,640
amit írtam ebben a programban, akkor inkább észre oh, nézzük csak teszi a globális

446
00:26:42,640 --> 00:26:47,060
mert az egész célja a program célja, hogy bizonyítani egy és csak egy láncolt lista.

447
00:26:47,060 --> 00:26:50,700
Annak érdekében, hogy úgy érzi, oké. Itt vannak a prototípusok, és nem megyünk át mindezen,

448
00:26:50,700 --> 00:26:55,800
de én írtam egy törlés funkció, a talál funkció, insert funkció, és a traverse funkciót.

449
00:26:55,800 --> 00:26:59,080
De nézzük most már menj vissza le a Függvény beszúrása

450
00:26:59,080 --> 00:27:01,490
és látom, hogy ez itt dolgozik.

451
00:27:01,490 --> 00:27:09,940
Beszúrás az on-line - itt is vagyunk.

452
00:27:09,940 --> 00:27:12,850
Beszúrása. Tehát nem vállal semmilyen érvet, mert megyünk kérni

453
00:27:12,850 --> 00:27:15,930
A felhasználó belsejében ezt a funkciót a számot akarnak szúrni.

454
00:27:15,930 --> 00:27:19,410
De először készítünk, hogy adjon nekik egy kis teret.

455
00:27:19,410 --> 00:27:22,050
Ez a fajta másolás és beillesztés a másik példa.

456
00:27:22,050 --> 00:27:25,110
Ebben az esetben, mi volt kiosztásának int, ezúttal mi kiosztása egy csomópont.

457
00:27:25,110 --> 00:27:27,910
Nem igazán emlékszem, hogy hány bájt a csomópont, de ez rendben van.

458
00:27:27,910 --> 00:27:30,460
Sizeof tudja kitalálni nekem.

459
00:27:30,460 --> 00:27:33,340
És miért vagyok ellenőrzésekor NULL sorban 120?

460
00:27:33,340 --> 00:27:37,530
Mi lehet baj sorban 119? Igen?

461
00:27:37,530 --> 00:27:40,530
[Student válasz, érthetetlen]

462
00:27:40,530 --> 00:27:43,440
Jó. Csak lehet a helyzet, hogy én már kértem túl sok memóriát

463
00:27:43,440 --> 00:27:47,020
vagy valami baj van, és az operációs rendszer nem rendelkezik elegendő bytes adni nekem,

464
00:27:47,020 --> 00:27:50,640
így jelzi annyira visszaküldésével NULL, és ha nem ellenőrzi, hogy a

465
00:27:50,640 --> 00:27:54,710
és én csak vakon folytassa használni a visszaadott cím, lehet NULL.

466
00:27:54,710 --> 00:27:58,400
Ez lehet egy ismeretlen értéket nem egy jó dolog, ha I -

467
00:27:58,400 --> 00:28:00,590
valójában nem lesz ismeretlen érték. Ez lehet NULL, úgyhogy nem akarom

468
00:28:00,590 --> 00:28:02,550
visszaélésekre, és kockára dereferencing azt.

469
00:28:02,550 --> 00:28:07,410
Ha ez megtörténik, én csak vissza, és mi úgy tenni, mintha nem kaptam vissza semmilyen memória egyáltalán.

470
00:28:07,410 --> 00:28:12,270
>> Különben elmondom a felhasználó adjon nekem egy számot beszúrni, kérem régi barátunk getInt,

471
00:28:12,270 --> 00:28:15,530
és akkor ez volt az új szintaxist vezettünk be hétfőn.

472
00:28:15,530 --> 00:28:20,320
"Newptr-> n" az meghozza a címet, amit kaptak malloc

473
00:28:20,320 --> 00:28:23,490
amely az első bájt az egy új csomópont objektum,

474
00:28:23,490 --> 00:28:26,860
és aztán megy a mezőre hívott n.

475
00:28:26,860 --> 00:28:35,270
Egy kis trivia kérdés: Ez megegyezik azzal, amit több rejtélyes kódsort?

476
00:28:35,270 --> 00:28:38,110
Hogy mást írtam ezt? Szeretné, hogy a stab?

477
00:28:38,110 --> 00:28:41,480
[Student válasz, érthetetlen]

478
00:28:41,480 --> 00:28:44,870
Jó. A. N, de ez nem olyan egyszerű, mint ez.

479
00:28:44,870 --> 00:28:47,090
Mit először meg kell tennem? [Student válasz, érthetetlen]

480
00:28:47,090 --> 00:28:52,730
Jó. Meg kell tennem * newptr.n.

481
00:28:52,730 --> 00:28:55,610
Szóval azt mondja, az új mutató nyilvánvalóan egy címet. Miért?

482
00:28:55,610 --> 00:28:59,520
Mert azt malloc által visszaadott. A * newptr azt mondja: "menj oda"

483
00:28:59,520 --> 00:29:02,970
majd ha egyszer ott van, akkor használd a jobban ismert. n,

484
00:29:02,970 --> 00:29:05,730
de ez csak úgy néz ki, egy kicsit csúnya, különösen akkor, ha az ember megy

485
00:29:05,730 --> 00:29:10,360
döntetlen mutató nyilakkal egész idő alatt, a világ szabványosított változata az erre a nyílra jelölést,

486
00:29:10,360 --> 00:29:12,320
amely nem pontosan ugyanaz a dolog.

487
00:29:12,320 --> 00:29:16,070
Szóval csak a -> jelölést, ha a dolog, a bal oldalon van egy mutató.

488
00:29:16,070 --> 00:29:18,790
Ellenkező esetben, ha ez a tényleges struct, használja a. N.

489
00:29:18,790 --> 00:29:25,800
És akkor ez: Miért nem tudom inicializálni newptr-> next NULL?

490
00:29:25,800 --> 00:29:28,610
Nem akarjuk, hogy a lógó bal kéz le a végén a színpadon.

491
00:29:28,610 --> 00:29:31,630
Azt akarom, hogy egyenesen lefelé, ami azt jelenti, a végén ez a lista

492
00:29:31,630 --> 00:29:34,980
esetlegesen lehet ezen a csomóponton, úgyhogy jobb, győződjön meg róla, NULL.

493
00:29:34,980 --> 00:29:38,460
És általában inicializálja a változókat, vagy az adatok tagjai és struktúrákat

494
00:29:38,460 --> 00:29:40,470
valami csak jó gyakorlat.

495
00:29:40,470 --> 00:29:45,170
Csak bérbeadás szemét létezik, és továbbra is fennáll általában kapja meg bajba

496
00:29:45,170 --> 00:29:48,650
Ha elfelejtette, hogy tegyen valamit a későbbiekben.

497
00:29:48,650 --> 00:29:51,590
>> Itt van egy pár esetben. Ez megint a betét funkció,

498
00:29:51,590 --> 00:29:54,930
és az első dolog, amit ellenőrizni, ha a változó nevű első,

499
00:29:54,930 --> 00:29:58,240
hogy a globális változó NULL, azt jelenti, hogy nincs kapcsolt lista.

500
00:29:58,240 --> 00:30:02,460
Még nem egészül ki olyan számokat, így magától értetődő, hogy helyezze be a jelenlegi száma

501
00:30:02,460 --> 00:30:05,240
a lista, mert ez csak tartozik elején a lista.

502
00:30:05,240 --> 00:30:08,100
Szóval ez volt, amikor Anita csak állt fel ide egyedül, mintha

503
00:30:08,100 --> 00:30:11,390
senki sem volt itt fent a színpadon, amíg kiosztott egy csomópont,

504
00:30:11,390 --> 00:30:13,940
akkor tudta emelni a kezét az első alkalommal,

505
00:30:13,940 --> 00:30:17,420
ha mindenki jött fel a színpadra utána hétfőn.

506
00:30:17,420 --> 00:30:22,900
Most itt, ez egy kis ellenőrzés, ahol azt kell mondanom, hogy az új csomópont értéke n

507
00:30:22,900 --> 00:30:27,370
a <n értéke a jelenlegi első csomópont,

508
00:30:27,370 --> 00:30:29,930
azt jelenti, hogy van egy láncolt lista, ami elkezdődött.

509
00:30:29,930 --> 00:30:32,330
Van legalább egy csomópontot a listán, de ez az új fickó

510
00:30:32,330 --> 00:30:37,230
tartozik előtt, ezért meg kell mozgatni a dolgokat.

511
00:30:37,230 --> 00:30:43,450
Más szóval, ha a lista indult és csak, mondjuk,

512
00:30:43,450 --> 00:30:48,100
csak a szám 17, ez a - valójában, akkor ezt pontosabban.

513
00:30:48,100 --> 00:30:56,010
Ha elkezdjük a történet egy mutató van úgynevezett első,

514
00:30:56,010 --> 00:30:59,870
és kezdetben ez NULL, és illessze be a 9,

515
00:30:59,870 --> 00:31:02,510
A 9-es számú egyértelműen tartozik elején a listán.

516
00:31:02,510 --> 00:31:07,400
Szóval mintha mi csak malloced a címet vagy a 9 és tedd ide.

517
00:31:07,400 --> 00:31:13,170
Ha az első 9 alapértelmezés szerint az első forgatókönyv beszéltünk csak azt nézzük pont ezt a fickót itt,

518
00:31:13,170 --> 00:31:15,790
hagyja ezt NULL, most már a 9-es számú.

519
00:31:15,790 --> 00:31:18,280
A következő számot szeretnénk beszúrni a 17.

520
00:31:18,280 --> 00:31:22,420
17 tartozik ide, úgyhogy kell majd csinálni néhány logikai stepping keresztül.

521
00:31:22,420 --> 00:31:26,060
Szóval ahelyett, mielőtt csinálni, mondjuk úgy, mintha azt akartuk, hogy helyezze be a 8-as szám.

522
00:31:26,060 --> 00:31:28,650
>> Tehát csak a kényelem kedvéért, megyek, hogy dolgozzon itt.

523
00:31:28,650 --> 00:31:30,760
De ne feledje, malloc nem tud rá leginkább sehol.

524
00:31:30,760 --> 00:31:33,460
De a rajz kedvéért teszem ide.

525
00:31:33,460 --> 00:31:38,440
Szóval mintha épp most kiosztott egy csomópontot a 8-as szám, ez NULL alapértelmezés szerint.

526
00:31:38,440 --> 00:31:42,800
Mi most történni? Egy pár dolgot.

527
00:31:42,800 --> 00:31:47,090
Mi tette ezt a hibát a színpadon hétfőn, ahol frissített egy mutató, mint ez,

528
00:31:47,090 --> 00:31:51,890
akkor tette ezt, és aztán azt állította - mi elárvult mindenki más a színpadon.

529
00:31:51,890 --> 00:31:54,350
Mert Nem látom - a műveletek sorrendjére itt fontos,

530
00:31:54,350 --> 00:31:58,760
mert most már elvesztette ezt a 9 csomópont, amely csak egyfajta lebeg az űrben.

531
00:31:58,760 --> 00:32:01,150
Szóval nem ez volt a megfelelő megközelítés hétfőn.

532
00:32:01,150 --> 00:32:03,330
Először meg kell csinálni valami mást.

533
00:32:03,330 --> 00:32:06,280
Az állam, a világ úgy néz ki, mint ez. Kezdetben, 8 osztottak.

534
00:32:06,280 --> 00:32:10,550
Mi lenne jobb módja a behelyezése 8?

535
00:32:10,550 --> 00:32:14,720
Ahelyett frissítésével mutató az első, csak frissíteni ez itt helyette.

536
00:32:14,720 --> 00:32:17,720
Tehát szükségünk van egy sor kódot fog kapcsolni ezt NULL karaktert

537
00:32:17,720 --> 00:32:22,020
egy tényleges pointer, ami mutat node 9,

538
00:32:22,020 --> 00:32:27,970
és akkor nyugodtan változtatni először mutatni ezt a fickót itt.

539
00:32:27,970 --> 00:32:31,330
Most van egy lista, a láncolt lista, a két elem.

540
00:32:31,330 --> 00:32:33,580
És mit jelent ez valójában néz itt?

541
00:32:33,580 --> 00:32:36,900
Ha megnézzük a kódot, észreveszi, hogy én csináltam, hogy pontosan.

542
00:32:36,900 --> 00:32:41,970
Már mondtam newptr, és ez a történet, newptr mutatott meg ezt a fickót.

543
00:32:41,970 --> 00:32:45,520
>> Szóval hadd dolgozzon még egy dolog, és meg kellett volna hagyni egy kicsit több hely erre.

544
00:32:45,520 --> 00:32:48,540
Tehát megbocsátani apró rajzot.

545
00:32:48,540 --> 00:32:52,140
Ez a fickó hívják newptr.

546
00:32:52,140 --> 00:32:57,940
Ez a változó is bejelentett egy pár sort korábban, összhangban - csak a fenti 25.

547
00:32:57,940 --> 00:33:03,430
És ez mutat 8. Tehát amikor azt mondom newptr-> next, azt jelenti, hogy menj a struct

548
00:33:03,430 --> 00:33:07,910
ez alatt mutatott a newptr, ezért itt vagyunk, ott.

549
00:33:07,910 --> 00:33:13,990
Ezután a nyíl azt mondja hogy a következő mezőt, majd az = mond fel milyen értéket ott?

550
00:33:13,990 --> 00:33:17,280
Az érték volt az első, hogy mi az érték az első?

551
00:33:17,280 --> 00:33:21,930
Gyártási mutatott ezen a csomóponton, így azt jelenti, hogy ennek most már mutatni ezen a csomóponton.

552
00:33:21,930 --> 00:33:25,660
Más szóval, ami úgy néz ki még ha nevetséges rendetlenség az én kézírás,

553
00:33:25,660 --> 00:33:28,620
Mi egy egyszerű ötlet, csak ha ezeket a nyilak körül

554
00:33:28,620 --> 00:33:31,560
fordítja a kódot, csak ez az egy bélés.

555
00:33:31,560 --> 00:33:38,110
Tárolja mi van az első a következő mezőt, majd frissítse 1. mi valójában.

556
00:33:38,110 --> 00:33:40,900
Menjünk előre, és előre-valamilyen e,

557
00:33:40,900 --> 00:33:44,220
és nézd csak ezt a farok helyezés most.

558
00:33:44,220 --> 00:33:51,210
Tegyük fel, hogy jutok el a pontra, ahol azt találjuk, hogy a következő mező néhány csomópont NULL.

559
00:33:51,210 --> 00:33:53,410
És ezen a ponton a történet, egy részlet, hogy én vagyok számolunk

560
00:33:53,410 --> 00:33:58,170
az, hogy én már bevezetett egy másik mutatót ide sorban 142, elődje mutató.

561
00:33:58,170 --> 00:34:01,320
Lényegében ezen a ponton a történet, ha a lista lesz hosszú,

562
00:34:01,320 --> 00:34:04,800
Valahogy meg kell járni, hogy két ujjal mert ha túl messzire megy,

563
00:34:04,800 --> 00:34:08,219
emlékszem egy hosszúságú listát, nem mehetsz vissza.

564
00:34:08,219 --> 00:34:13,659
Szóval, ez a gondolat a predptr az én bal ujját, és newptr - nem newptr.

565
00:34:13,659 --> 00:34:17,199
Egy másik mutató, ami itt van a másik ujját, és én csak ilyen séta a listán.

566
00:34:17,199 --> 00:34:22,179
Ez az, hogy miért létezik. De nézzük csak úgy az egyik egyszerűbb esetek itt.

567
00:34:22,179 --> 00:34:26,620
Ha ez a mutató a következő mezőben NULL, mi a logikai következmény?

568
00:34:26,620 --> 00:34:30,840
Ha elmozdulási ezt a listát, és megüt egy NULL pointer?

569
00:34:30,840 --> 00:34:35,780
Nálunk az a lista végére, és így a kódot, akkor csatolja ezt még egy további elem

570
00:34:35,780 --> 00:34:41,230
A fajta az intuitív fog, hogy a csomópont, amelynek következő mutató NULL,

571
00:34:41,230 --> 00:34:46,120
így ez jelenleg NULL, és változtassa meg, bár hogy a címe az új csomópontot.

572
00:34:46,120 --> 00:34:52,260
Szóval, csak rajz kódot a nyíl, hogy felhívta a színpadon felemelésével valaki bal kezét.

573
00:34:52,260 --> 00:34:54,070
>> És a helyzet, hogy én hullám kezem a most,

574
00:34:54,070 --> 00:34:58,020
csak azért, mert úgy gondolom, hogy ez könnyű eltévedni, amikor csinálni ezt a fajta környezet,

575
00:34:58,020 --> 00:35:00,600
ellenőrzi a helyezés az a lista közepén.

576
00:35:00,600 --> 00:35:03,220
De csak ösztönösen, hogy minek kell történnie, ha azt szeretné, hogy kitaláljuk,

577
00:35:03,220 --> 00:35:06,600
ahol néhány szám tartozik, a középső akkor kell járni, hogy

578
00:35:06,600 --> 00:35:09,510
egynél több ujj, több mint egy mutató,

579
00:35:09,510 --> 00:35:12,920
kitalálni, ahová tartozik az ellenőrzés az elem <a jelenlegi,

580
00:35:12,920 --> 00:35:15,450
> Az aktuális, és ha úgy találja, hogy a helyet,

581
00:35:15,450 --> 00:35:20,400
akkor meg kell, hogy ezt a fajta héj játék, ahol mozog a mutató körül nagyon óvatosan.

582
00:35:20,400 --> 00:35:23,850
És ez a válasz, ha azt szeretné, hogy oka, ezen keresztül otthon a saját,

583
00:35:23,850 --> 00:35:28,340
csapódik le, csak azért, hogy e két sornyi kódot, de a sorrend az említett vonalak szuper fontos.

584
00:35:28,340 --> 00:35:31,390
Mert ha csökken valakinek a kezét, és fel valaki más a rossz érdekében,

585
00:35:31,390 --> 00:35:34,580
újra, akkor a végén orphaning a listán.

586
00:35:34,580 --> 00:35:39,500
Összefoglalva több fogalmi, a kurzort a farok viszonylag egyszerű.

587
00:35:39,500 --> 00:35:42,940
A behelyezés fejénél is viszonylag egyszerű,

588
00:35:42,940 --> 00:35:45,580
de meg kell frissíteni egy további mutató ebben az időben

589
00:35:45,580 --> 00:35:47,930
szorítani 5-ös szám a lista itt

590
00:35:47,930 --> 00:35:51,560
majd beillesztés a közepén jár, még nagyobb erőfeszítést,

591
00:35:51,560 --> 00:35:56,130
nagyon óvatosan illessze be a számot a 20 a helyes location,

592
00:35:56,130 --> 00:35:58,350
ami 17 és 22.

593
00:35:58,350 --> 00:36:02,700
Tehát meg kell, hogy tegyen valamit, mint hogy az új csomópont 20 pont 22,

594
00:36:02,700 --> 00:36:08,470
majd, amelyek csomópont mutató frissíteni kell utoljára?

595
00:36:08,470 --> 00:36:10,630
Ez 17, ténylegesen helyezze.

596
00:36:10,630 --> 00:36:14,080
Szóval megint én elhalasztja a tényleges kódot az adott végrehajtására.

597
00:36:14,080 --> 00:36:17,280
>> Első pillantásra ez egy kicsit nyomasztó, de ez tényleg csak egy végtelen ciklus

598
00:36:17,280 --> 00:36:21,770
ez hurok, a ciklusok, a ciklusok, a ciklusok, és a törés amint bejön a NULL pointer,

599
00:36:21,770 --> 00:36:24,590
ekkor meg tudod csinálni a szükséges szerelést.

600
00:36:24,590 --> 00:36:30,960
Ez tehát nem reprezentatív láncolt lista beillesztési kódot.

601
00:36:30,960 --> 00:36:34,590
Ez kedves volt egy csomó, és úgy érzi, mintha már megoldotta egy probléma,

602
00:36:34,590 --> 00:36:36,940
de már be egy egész másikat. Őszintén szólva, mi töltöttem ennyi idő

603
00:36:36,940 --> 00:36:40,540
a nagy O és Ω és működési idő, próbálják megoldani a problémákat gyorsabban,

604
00:36:40,540 --> 00:36:43,270
és itt teszünk egy nagy lépést hátra, érzés.

605
00:36:43,270 --> 00:36:45,380
És mégis, ha a cél az, hogy az adatok tárolására,

606
00:36:45,380 --> 00:36:48,010
úgy érzi, mint a Szent Grál, ahogy mondta hétfőn, azt valóban

607
00:36:48,010 --> 00:36:50,470
tárolni dolgokat azonnal.

608
00:36:50,470 --> 00:36:53,930
>> Sőt, tegyük fel, hogy megcsináltuk félretett láncolt lista egy pillanatra

609
00:36:53,930 --> 00:36:56,000
és mi helyette bevezette a fogalmat egy táblázatot.

610
00:36:56,000 --> 00:36:59,110
És nézzünk gondoljunk csak egy tábla egy pillanatra, mint egy tömb.

611
00:36:59,110 --> 00:37:03,790
Ez a tömb, és ebben az esetben itt is mintegy 26 elemet, 0-tól 25,

612
00:37:03,790 --> 00:37:07,940
és tegyük fel, hogy szükség van néhány darab a tárolási nevek:

613
00:37:07,940 --> 00:37:10,350
Alice és Bob és Charlie és hasonlók.

614
00:37:10,350 --> 00:37:12,880
És szükség van néhány adatszerkezet tárolja ezeket a neveket.

615
00:37:12,880 --> 00:37:15,000
Hát, jól jönne valami, mint egy láncolt lista

616
00:37:15,000 --> 00:37:20,260
és meg tudná járni a listát behelyezése Alice előtt, Bob és Charlie után Bob és így tovább.

617
00:37:20,260 --> 00:37:23,850
És valóban, ha meg akarja nézni kódot így, mint egy félre,

618
00:37:23,850 --> 00:37:27,230
tudják, hogy list2.h, mi pontosan ezt.

619
00:37:27,230 --> 00:37:30,610
Mi nem megy át a kódot, de ez a változat az első példa

620
00:37:30,610 --> 00:37:34,640
, amely bemutatja egy másik struct láttuk azelőtt hívott diák,

621
00:37:34,640 --> 00:37:40,330
és akkor mi valójában tárolja a csatolt lista egy mutató egy diák struktúrát

622
00:37:40,330 --> 00:37:44,520
inkább, mint egy egyszerű kis egész szám, n.

623
00:37:44,520 --> 00:37:46,900
Tehát észre ott kód van, amely magában foglalja a tényleges húrok,

624
00:37:46,900 --> 00:37:49,940
de ha a cél kéznél tényleg most, hogy foglalkozzon a hatékonysági probléma,

625
00:37:49,940 --> 00:37:53,380
nem lenne jó, ha mi az adott objektum neve Alice,

626
00:37:53,380 --> 00:37:56,020
akarjuk helyezni őt a megfelelő helyen egy adatszerkezet,

627
00:37:56,020 --> 00:37:58,860
úgy érzi, mintha lenne igazán jó, hogy csak fel Alice,

628
00:37:58,860 --> 00:38:01,180
akinek a neve kezdődik, az első helyen.

629
00:38:01,180 --> 00:38:05,270
És Bob, akinek a neve kezdődik B, a második helyen.

630
00:38:05,270 --> 00:38:09,580
Egy tömb, vagy kezdjük nevezni egy asztal, egy hash tábla, hogy a

631
00:38:09,580 --> 00:38:13,650
meg tudjuk csinálni, hogy pontosan. Ha adott egy nevet, mint Alice,

632
00:38:13,650 --> 00:38:16,700
egy string, mint Alice, hol teszed A-l-i-c-e?

633
00:38:16,700 --> 00:38:20,540
Szükségünk van egy hueristic. Szükségünk van egy funkció, hogy bizonyos bemeneti mint Alice

634
00:38:20,540 --> 00:38:24,610
és visszaküldi a választ: "Tedd Alice ezen a helyen."

635
00:38:24,610 --> 00:38:28,720
És ez a funkció, a fekete doboz, fog nevezni egy hash függvény.

636
00:38:28,720 --> 00:38:32,330
>> A hash függvény van valami, hogy vesz egy input, mint "Alice",

637
00:38:32,330 --> 00:38:38,080
és visszatér hozzád, jellemzően a numerikus helyét néhány adatszerkezet, ahol Alice tartozik.

638
00:38:38,080 --> 00:38:40,830
Ebben az esetben, a mi hash függvény legyen viszonylag egyszerű.

639
00:38:40,830 --> 00:38:47,510
A hash függvény kell mondani, ha az adott "Alice", amely képességgel kéne érdekel?

640
00:38:47,510 --> 00:38:55,660
Az első. Szóval nézd meg a [0], majd azt mondom, ha a [0] karakter A, térjen vissza a 0 szám.

641
00:38:55,660 --> 00:39:01,130
Ha ez a B, vissza 1. Ha ez a C, Beküldendő: 2, és így tovább.

642
00:39:01,130 --> 00:39:05,940
Összes 0 index, és ez lehetővé teszi számomra, hogy be Alice, majd Bob, majd Charlie és így tovább

643
00:39:05,940 --> 00:39:10,960
ebbe adatstruktúra. De van egy kis gond.

644
00:39:10,960 --> 00:39:13,060
Mi van, ha Anita jön megint?

645
00:39:13,060 --> 00:39:17,510
Hová tesszük Anita? A neve is kezdődik a betű,

646
00:39:17,510 --> 00:39:20,330
és úgy érzi, mint mi tettük még nagyobb rendetlenség ezt a problémát.

647
00:39:20,330 --> 00:39:24,380
Most azonnal helyezés, állandó idő helyezés, egy adatstruktúra

648
00:39:24,380 --> 00:39:27,100
ahelyett, legrosszabb esetre lineáris,

649
00:39:27,100 --> 00:39:29,510
de mit tehetünk Anita ebben az esetben?

650
00:39:29,510 --> 00:39:34,110
Mi a két lehetőség közül, tényleg? Igen?

651
00:39:34,110 --> 00:39:37,410
[Student válasz, érthetetlen] Oké, szóval tudtuk, hogy egy másik dimenzióba.

652
00:39:37,410 --> 00:39:42,320
Ez jó. Így tudjuk építeni a dolgokat, mint a 3D-ben beszélgettünk szóban hétfőn.

653
00:39:42,320 --> 00:39:46,700
Tudtunk újabb hozzáférés van, de tegyük fel, hogy nem, próbálom tartani ezt az egyszerű.

654
00:39:46,700 --> 00:39:50,160
Az egész cél itt az, hogy azonnali konstans idejű hozzáférést,

655
00:39:50,160 --> 00:39:52,170
Szóval ez ha túl sokat összetettségét.

656
00:39:52,170 --> 00:39:55,970
Milyen más lehetőségek, amikor megpróbálja beilleszteni Anita ebbe adatszerkezet? Igen?

657
00:39:55,970 --> 00:39:58,610
[Student válasz, érthetetlen] Jó. Így tudtunk mozogni mindenki más le,

658
00:39:58,610 --> 00:40:03,040
mint Charlie nudges le Bob és Alice, majd rakjuk Anita, ahol tényleg akar lenni.

659
00:40:03,040 --> 00:40:05,660
>> Persze, most van egy mellékhatása ennek.

660
00:40:05,660 --> 00:40:09,000
Ez az adat struktúra valószínűleg hasznos, nem azért, mert szeretné szúrni az emberek egyszer

661
00:40:09,000 --> 00:40:11,250
hanem azért, mert azt szeretnénk, ha szeretné ellenőrizni, hogy ott vannak később

662
00:40:11,250 --> 00:40:13,600
ha szeretnénk kinyomtatni az összes nevet az adatszerkezetet.

663
00:40:13,600 --> 00:40:15,850
Fogunk valamit csinálni ezekkel az adatokkal végül.

664
00:40:15,850 --> 00:40:20,810
Tehát most voltunk ilyen csavaros feletti Alice, aki már nem, hol kellene lennie.

665
00:40:20,810 --> 00:40:23,880
Sem Bob, sem Charlie.

666
00:40:23,880 --> 00:40:26,060
Szóval lehet, hogy ez nem is olyan jó ötlet.

667
00:40:26,060 --> 00:40:28,830
De valóban, ez az egyik lehetőség. Mi lehet váltani mindenkit le,

668
00:40:28,830 --> 00:40:32,240
vagy fene, Anita jött későn a játék, miért nem az imént Anita

669
00:40:32,240 --> 00:40:35,870
Nem itt, nem itt, nem itt, menjünk csak fel neki egy kicsit lejjebb a listán.

670
00:40:35,870 --> 00:40:38,680
De aztán ez a probléma kezd ruházni újra.

671
00:40:38,680 --> 00:40:41,630
Lehet, hogy képes megtalálni Alice azonnal alapuló, az első nevét.

672
00:40:41,630 --> 00:40:44,320
És Bob azonnal, és Charlie. De aztán keres Anita,

673
00:40:44,320 --> 00:40:46,360
és látod, hmm, Alice van az úton.

674
00:40:46,360 --> 00:40:48,770
Nos, hadd nézzem meg az alábbi Alice. Bob nem Anita.

675
00:40:48,770 --> 00:40:51,850
Charlie nem Anita. Oh, van Anita.

676
00:40:51,850 --> 00:40:54,720
És ha továbbra is, hogy a vonat a logika egész úton,

677
00:40:54,720 --> 00:41:00,690
mi a legrosszabb futási idő a megállapítás behelyezése vagy Anita ebbe az új adatstruktúra?

678
00:41:00,690 --> 00:41:03,280
Ez O (n), nem igaz?

679
00:41:03,280 --> 00:41:06,280
Mivel a legrosszabb esetben, ott van Alice, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
egészen a valaki nevű "Y", így már csak egy hely maradt.

681
00:41:10,150 --> 00:41:13,950
Szerencsére, nincs egy úgynevezett "Z", így tesszük Anita legalján.

682
00:41:13,950 --> 00:41:16,040
>> Még nem igazán megoldani ezt a problémát.

683
00:41:16,040 --> 00:41:19,890
Így talán nem kell bemutatni ezt a harmadik dimenzióba.

684
00:41:19,890 --> 00:41:22,230
És kiderült, ha mi bevezetni a harmadik dimenziót,

685
00:41:22,230 --> 00:41:25,240
nem tudjuk ezt tökéletesen, de a Szent Grál lesz, hogy egyre

686
00:41:25,240 --> 00:41:28,370
állandó idő helyezés és dinamikus beszúrások, hogy a

687
00:41:28,370 --> 00:41:30,960
nem kell a kemény-kód egy sor mérete 26.

688
00:41:30,960 --> 00:41:34,400
Mi lehet beszúrni annyi nevet, mint szeretnénk, de nézzük mi 5-perces szünet van

689
00:41:34,400 --> 00:41:38,790
majd csinálni rendesen.

690
00:41:38,790 --> 00:41:46,020
Rendben van. Én meg a történetet fel elég mesterségesen ott

691
00:41:46,020 --> 00:41:48,670
választásával Alice, majd Bob, majd Charlie majd Anita,

692
00:41:48,670 --> 00:41:51,000
akinek a neve nyilvánvalóan fog ütközni Alice.

693
00:41:51,000 --> 00:41:54,120
De a kérdés, amit én ért véget hétfőn mindössze mennyire valószínű ez

694
00:41:54,120 --> 00:41:56,370
hogy Ön is kap az ilyen típusú ütközések? Más szóval,

695
00:41:56,370 --> 00:42:00,490
ha elkezdjük használni ezt a táblázatos szerkezet, ami tényleg csak egy tömb,

696
00:42:00,490 --> 00:42:02,460
Ebben az esetben a 26-helyek,

697
00:42:02,460 --> 00:42:05,740
mi van, ha a bemenetek helyett egyenletesen oszlanak?

698
00:42:05,740 --> 00:42:09,620
Ez nem mesterségesen Alice és Bob és Charlie és David és így tovább betűrendben,

699
00:42:09,620 --> 00:42:12,380
ez egyenletesen eloszló A-tól Z-

700
00:42:12,380 --> 00:42:15,220
>> Talán majd most, hogy szerencsés és nem fogunk, hogy a két A-vagy 2 B

701
00:42:15,220 --> 00:42:17,640
nagyon nagy a valószínűsége, de valaki rámutatott,

702
00:42:17,640 --> 00:42:20,730
ha ezt általánosított probléma, és nem tesz 0-25

703
00:42:20,730 --> 00:42:26,060
hanem, mondjuk, a 0 és 364 vagy 65, gyakran a napok számát egy tipikus évben,

704
00:42:26,060 --> 00:42:31,170
és feltette a kérdést: "Mi a valószínűsége annak, hogy mi ketten ebben a szobában van egyforma születésnapja?"

705
00:42:31,170 --> 00:42:34,600
Másképp fogalmazva, mi a valószínűsége annak, hogy mi ketten egy nevet kezdődő A?

706
00:42:34,600 --> 00:42:37,190
Az a fajta kérdés ugyanaz, de ez a címtartomány,

707
00:42:37,190 --> 00:42:39,940
erre a keresési térben, nagyobb abban az esetben, születésnapok,

708
00:42:39,940 --> 00:42:42,820
mert van olyan sok több napot ebben az évben, mint betűk az ábécé.

709
00:42:42,820 --> 00:42:44,910
Mi a valószínűsége, hogy egy ütközés?

710
00:42:44,910 --> 00:42:48,410
Nos, azt hiszem ezt kitalálni a matek az ellenkező irányba.

711
00:42:48,410 --> 00:42:50,580
Mi a valószínűsége, hogy nincs ütközés?

712
00:42:50,580 --> 00:42:53,970
Nos, ez a kifejezés itt azt mondja, hogy mi a valószínűsége

713
00:42:53,970 --> 00:42:58,770
ha csak egy ember ebben a teremben, hogy van egy különleges születésnapja?

714
00:42:58,770 --> 00:43:01,190
Ez 100%-os. Mert ha csak egy ember a szobában,

715
00:43:01,190 --> 00:43:03,940
ő születésnapja bármelyike ​​lehet a 365 napot ki az év.

716
00:43:03,940 --> 00:43:08,650
Tehát 365/365 lehetőséget ad nekem az 1 értéket.

717
00:43:08,650 --> 00:43:11,250
Tehát a valószínűsége a kérdéses pillanatban mindössze 1.

718
00:43:11,250 --> 00:43:13,270
De ha van egy másik személy a szobában,

719
00:43:13,270 --> 00:43:16,490
mi a valószínűsége annak, hogy a születésnapját a különbség?

720
00:43:16,490 --> 00:43:20,680
Már csak 364 nap lehet, figyelmen kívül hagyva a szökőév,

721
00:43:20,680 --> 00:43:23,580
azok születésnapi ne ütközzenek a más személyekkel.

722
00:43:23,580 --> 00:43:31,920
Szóval, 364/365. Ha egy harmadik személy bejön, igen 363/365, és így tovább.

723
00:43:31,920 --> 00:43:35,790
Tehát folyamatosan szorzata együtt ezek frakciói, amelyek egyre kisebb és kisebb,

724
00:43:35,790 --> 00:43:40,720
hogy kitaláljuk, mi a valószínűsége, hogy mindannyian egyedülálló születésnap?

725
00:43:40,720 --> 00:43:43,570
De akkor mi is, persze, csak úgy, hogy a válasz és a flip körül

726
00:43:43,570 --> 00:43:47,210
és nem 1 mínusz az összes, hogy egy kifejezés akkor végül kap

727
00:43:47,210 --> 00:43:51,250
ha emlékszel a hátán a matek könyvet, úgy néz ki, egy kis valami, mint ez,

728
00:43:51,250 --> 00:43:54,590
amely sokkal könnyebben értelmezhető grafikusan.

729
00:43:54,590 --> 00:43:57,820
És ez a képe itt van az x tengelyen száma születésnapok,

730
00:43:57,820 --> 00:44:02,030
vagy a személyek száma a születésnapokat, és az y tengely a valószínűsége, hogy a mérkőzés.

731
00:44:02,030 --> 00:44:06,060
És mi ezt mondani, hogy ha, mondjuk, sőt,

732
00:44:06,060 --> 00:44:10,860
hadd válasszon valami hasonlót 22, 23.

733
00:44:10,860 --> 00:44:13,160
Ha van 22 vagy 23 ember van a szobában,

734
00:44:13,160 --> 00:44:17,100
a valószínűsége, hogy két ilyen nagyon kevés ember megy van egyforma születésnapja

735
00:44:17,100 --> 00:44:19,560
valójában szuper magas, kombinatorikusan.

736
00:44:19,560 --> 00:44:23,450
50%-os esélye, hogy egy osztályban mindössze 22 fő, a szeminárium, gyakorlatilag

737
00:44:23,450 --> 00:44:25,790
2-azok az emberek mennek, hogy ugyanazt a születésnapját.

738
00:44:25,790 --> 00:44:28,520
Mert van sok szempontból, amelyek segítségével ugyanaz a születésnapját.

739
00:44:28,520 --> 00:44:31,110
Még rosszabb, ha megnézi a jobb oldali diagram,

740
00:44:31,110 --> 00:44:34,040
mire van egy osztályban 58 tanuló azt,

741
00:44:34,040 --> 00:44:39,270
annak a valószínűsége, 2 fő részére, amelynek születésnap szuper, szuper magas, közel 100%-os.

742
00:44:39,270 --> 00:44:41,880
Nos, ez egyfajta szórakozás tény a valós életben.

743
00:44:41,880 --> 00:44:45,850
>> De a következmények, most, az adatstruktúrák és információ tárolására

744
00:44:45,850 --> 00:44:51,100
azt jelenti, hogy csak feltételezve, hogy van egy szép, tiszta, egyenletes eloszlású adatok

745
00:44:51,100 --> 00:44:53,650
és van egy elég nagy tömb, hogy illeszkedjen egy csomó dolgot

746
00:44:53,650 --> 00:44:59,360
nem jelenti azt fogod, hogy az emberek a különleges helyszíneken.

747
00:44:59,360 --> 00:45:03,810
Te megy, hogy ütközések. Tehát ez a fogalma kivonatoláshoz ahogy hívják,

748
00:45:03,810 --> 00:45:07,450
figyelembe bemeneti mint "Alice" és a masszázsnak, hogy valamilyen módon

749
00:45:07,450 --> 00:45:10,190
majd visszatérve a választ, mint a 0 vagy 1 vagy 2.

750
00:45:10,190 --> 00:45:17,500
Megközelítés vissza néhány kimenete ez a funkció nem sújtja ez a valószínűsége ütközés.

751
00:45:17,500 --> 00:45:19,530
Szóval, hogyan lehet kezelni ezeket ütközések?

752
00:45:19,530 --> 00:45:21,940
Nos, az egyik esetben, akkor tegye meg a gondolat, hogy javasolták.

753
00:45:21,940 --> 00:45:25,100
Mi is csak váltani mindenkit le, vagy talán egy kicsit egyszerű,

754
00:45:25,100 --> 00:45:29,870
ahelyett move mindenki, menjünk csak mozgatni Anita, hogy az alján a rendelkezésre álló helyet.

755
00:45:29,870 --> 00:45:32,810
Tehát, ha Alice in 0, Bob van 1, Charlie 2,

756
00:45:32,810 --> 00:45:35,260
akkor csak tedd Anita a helyszínen 3.

757
00:45:35,260 --> 00:45:38,860
És ez egy olyan technika adatszerkezetek nevű lineáris tapintás.

758
00:45:38,860 --> 00:45:41,310
Lineáris mert te csak séta ezen a vonalon, és te valami szondázás

759
00:45:41,310 --> 00:45:43,640
a rendelkezésre álló helyeket az adatszerkezetet.

760
00:45:43,640 --> 00:45:46,210
Természetesen, ez hárul az O (n).

761
00:45:46,210 --> 00:45:49,590
Ha az adatok szerkezete nagyon tele, van 25 ember már,

762
00:45:49,590 --> 00:45:54,120
majd Anita jön, ő végül, hogy mi lenne a helye Z, és ez rendben van.

763
00:45:54,120 --> 00:45:56,540
Még mindig illik, és megtalálja őt később.

764
00:45:56,540 --> 00:46:00,100
>> De ez ellentétes volt a célja, hogy felgyorsítsa a dolgokat.

765
00:46:00,100 --> 00:46:02,530
Szóval, mi lenne, ha helyette bevezette a harmadik dimenzióba?

766
00:46:02,530 --> 00:46:06,400
Ezt a technikát általában az úgynevezett külön chaining, vagy amelynek láncok.

767
00:46:06,400 --> 00:46:10,030
És mi a hash tábla most, ez a táblázatos szerkezet,

768
00:46:10,030 --> 00:46:13,450
a tábla csak egy tömb mutató.

769
00:46:13,450 --> 00:46:18,230
De mi a mutatókat mutasson az tudjátok mit?

770
00:46:18,230 --> 00:46:21,970
A csatolt listában. Szóval, mi van, ha vesszük a legjobb mindkét világ?

771
00:46:21,970 --> 00:46:26,500
Az általunk használt tömböket a kezdeti indexek

772
00:46:26,500 --> 00:46:32,070
az adatszerkezet így azonnal menni [0] [1], [30] vagy így tovább,

773
00:46:32,070 --> 00:46:36,480
de így, hogy van némi rugalmasságot, és mi fér Anita és Alice és Adam

774
00:46:36,480 --> 00:46:38,630
és bármely más, Egy név,

775
00:46:38,630 --> 00:46:43,470
akkor inkább hagyja, hogy a másik tengely nő önkényesen.

776
00:46:43,470 --> 00:46:47,340
És végül, mint a hétfői, van, hogy kifejező képesség a linkelt listát.

777
00:46:47,340 --> 00:46:49,530
Mi lehet a nő egy adatszerkezet önkényesen.

778
00:46:49,530 --> 00:46:52,450
Alternatív tudtunk csak, hogy egy hatalmas, 2-dimenziós tömb,

779
00:46:52,450 --> 00:46:57,190
de lesz egy szörnyű helyzetet, ha a sorok a 2-dimenziós tömb

780
00:46:57,190 --> 00:47:01,280
nem elég nagy a további személyt, akinek neve történik kezdeni A.

781
00:47:01,280 --> 00:47:04,200
Isten mentsen meg kell átcsoportosítása egy hatalmas 2-dimenziós szerkezet

782
00:47:04,200 --> 00:47:06,600
csak azért, mert van olyan sok ember nevezett A,

783
00:47:06,600 --> 00:47:09,480
különösen akkor, ha van olyan kevés ember nevű Z valamit.

784
00:47:09,480 --> 00:47:12,170
Ez csak megy, hogy egy nagyon ritka adatszerkezet.

785
00:47:12,170 --> 00:47:15,400
Szóval ez nem tökéletes bármilyen eszközzel, de most legalább megvan a képessége

786
00:47:15,400 --> 00:47:19,090
hogy azonnal megtalálja, amikor Alice és Anita tartozik,

787
00:47:19,090 --> 00:47:21,090
legalábbis szempontjából a függőleges tengely,

788
00:47:21,090 --> 00:47:25,850
és akkor csak azt kell eldönteni, hogy hova tegye Anita vagy Alice ebben a láncolt lista.

789
00:47:25,850 --> 00:47:32,480
Ha nem érdekel a válogatás dolgok milyen gyorsan tudnánk be Alice egy struktúra, mint ez?

790
00:47:32,480 --> 00:47:35,370
Ez az állandó idő. Mi index a [0], és ha senki nem ott van,

791
00:47:35,370 --> 00:47:37,550
Alice megy az elején, hogy a láncolt lista.

792
00:47:37,550 --> 00:47:40,000
De ez nem egy nagy dolog. Mert ha Anita, akkor jön

793
00:47:40,000 --> 00:47:42,160
Egyes lépések számát később, ha nem tartozik Anita?

794
00:47:42,160 --> 00:47:45,140
Nos, [0]. OOP. Alice már, hogy a láncolt lista.

795
00:47:45,140 --> 00:47:47,760
>> De ha nem érdekel a rendezési ezeket a neveket,

796
00:47:47,760 --> 00:47:53,580
tudjuk csak mozgatni Alice felett, betét Anita, de még ez konstans idő.

797
00:47:53,580 --> 00:47:57,010
Még ha van Alice és Ádám és az összes többi A nevek,

798
00:47:57,010 --> 00:47:59,410
ez nem igazán azáltal, hogy fizikailag. Miért?

799
00:47:59,410 --> 00:48:04,090
Mert mi csak volt itt láncolt lista, ki tudja, voltak ezek a csomópontok egyébként?

800
00:48:04,090 --> 00:48:06,550
Mindössze annyit kell tennie, hogy mozog a zsemlemorzsa.

801
00:48:06,550 --> 00:48:10,930
Mozgassa a nyilak körül, akkor nem kell fizikailag mozgatni bármilyen adat körül.

802
00:48:10,930 --> 00:48:14,610
Így tudjuk beszúrni Anita, abban az esetben, azonnal. Constant idő.

803
00:48:14,610 --> 00:48:20,250
Tehát állandó idő lookup, és állandó idő behelyezése valaki, mint Anita.

804
00:48:20,250 --> 00:48:22,740
De milyen oversimplifying a világ.

805
00:48:22,740 --> 00:48:28,510
Mi lenne, ha később akarjuk találni Alice?

806
00:48:28,510 --> 00:48:31,050
Mi lenne, ha később akarjuk találni Alice?

807
00:48:31,050 --> 00:48:35,690
Hány lépés az, hogy fog tartani?

808
00:48:35,690 --> 00:48:37,850
[Student válasz, érthetetlen]

809
00:48:37,850 --> 00:48:40,950
Pontosan. Az embereknek a száma, mielőtt Alice a láncolt lista.

810
00:48:40,950 --> 00:48:45,420
Szóval ez nem egészen tökéletes, mert adatszerkezet újra, van ez a függőleges hozzáféréssel

811
00:48:45,420 --> 00:48:50,240
és akkor van ilyen linkelt listák függő - valójában, ne dolgozzon ez egy tömb.

812
00:48:50,240 --> 00:48:56,020
Ez ilyen láncolt listák lógott le róla, hogy néz ki egy kicsit valami ilyesmi.

813
00:48:56,020 --> 00:48:59,110
De a probléma az, ha Aliz és Ádám és az összes többi A nevek

814
00:48:59,110 --> 00:49:01,720
végül egyre több ott,

815
00:49:01,720 --> 00:49:04,810
találni valakit a végén vesz egy csomó lépést,

816
00:49:04,810 --> 00:49:06,670
bcause van, hogy áthalad a linkelt lista

817
00:49:06,670 --> 00:49:08,090
amely egy lineáris művelet.

818
00:49:08,090 --> 00:49:14,270
Szóval tényleg, akkor a beillesztés idő végül O (n), ahol n az elemek száma a listában.

819
00:49:14,270 --> 00:49:21,780
Osztva, hadd önkényesen nevezik m, ahol m a száma kapcsolt listák

820
00:49:21,780 --> 00:49:24,500
hogy van ebben a függőleges tengelyen.

821
00:49:24,500 --> 00:49:27,180
Más szavakkal, ha feltételezzük, valóban egy egyenletes eloszlás a nevek,

822
00:49:27,180 --> 00:49:30,150
teljesen irreális. Van nyilvánvalóan valamilyen betű, mint mások.

823
00:49:30,150 --> 00:49:32,580
>> De ha feltételezzük a pillanatban egy egyenletes eloszlású,

824
00:49:32,580 --> 00:49:37,350
és mi n teljes ember, és m teljes láncok

825
00:49:37,350 --> 00:49:40,630
rendelkezésünkre álló, akkor a hossza egyenként ezeknek a láncoknak

826
00:49:40,630 --> 00:49:44,380
meglehetősen egyszerű lesz az összes, n osztva száma láncokat.

827
00:49:44,380 --> 00:49:48,900
Tehát n / m. De itt van, ahol lehet minden matematikailag okos.

828
00:49:48,900 --> 00:49:53,030
m egy állandó, mert van egy fix számú ezeket.

829
00:49:53,030 --> 00:49:54,620
Fogsz nyilvánítsa a tömb elején,

830
00:49:54,620 --> 00:49:58,450
és nem vagyunk átméretezés a függőleges tengelyen. A dolog természetéből adódóan, ez marad rögzített.

831
00:49:58,450 --> 00:50:01,220
Ez csak a vízszintes tengely, hogy úgy mondjam, ez változó.

832
00:50:01,220 --> 00:50:04,760
Így technikailag, ez egy konstans. Tehát most, a beillesztési idő

833
00:50:04,760 --> 00:50:09,700
nagyjából O (n).

834
00:50:09,700 --> 00:50:12,410
Annak érdekében, hogy nem érzi, hogy sok minden jobb.

835
00:50:12,410 --> 00:50:14,940
De mi az igazság itt? Nos, ebben az időben, a héten

836
00:50:14,940 --> 00:50:20,640
mi már azt mondja O (n ²). O (n), 2 x n ², - n, osztva 2-vel. . . ECH.

837
00:50:20,640 --> 00:50:23,580
Ez csak n ². De most, hogy ez a része a félév,

838
00:50:23,580 --> 00:50:25,560
tudunk kezdeni beszélni a valós világban újra.

839
00:50:25,560 --> 00:50:31,520
És N / m jelentése teljesen gyorsabb, mint csak egyedül n.

840
00:50:31,520 --> 00:50:35,170
Ha van egy ezer nevet, és szünet őket a több vödör

841
00:50:35,170 --> 00:50:37,820
úgy, hogy csak tíz neve minden ilyen láncok,

842
00:50:37,820 --> 00:50:41,670
Teljesen keres 10 dolog lesz gyorsabb, mint ezer dolgot.

843
00:50:41,670 --> 00:50:43,740
És így az egyik közelgő probléma készletek fog megtámadni téged

844
00:50:43,740 --> 00:50:46,100
gondolni, hogy pontosan, hogy bár igen,

845
00:50:46,100 --> 00:50:49,520
aszimptotikusan és matematikailag, ez még mindig csak a lineáris,

846
00:50:49,520 --> 00:50:51,700
ami szar általában, amikor megpróbálja megtalálni a dolgokat.

847
00:50:51,700 --> 00:50:54,530
A valóságban ez lesz gyorsabb, mint

848
00:50:54,530 --> 00:50:56,520
emiatt osztó.

849
00:50:56,520 --> 00:50:58,310
És így van ez megint lesz e trade-off

850
00:50:58,310 --> 00:51:01,390
és ez a konfliktus az elmélet és a valóság,

851
00:51:01,390 --> 00:51:03,550
és az egyik gombok indul fordulópontot ezen a ponton a félév

852
00:51:03,550 --> 00:51:07,510
több a valóság az egyiket mi egyfajta felkészülés semster végén,

853
00:51:07,510 --> 00:51:09,280
ahogy bemutatjuk a világ webes programozás,

854
00:51:09,280 --> 00:51:11,530
ha tényleg, a teljesítmény fog számítani, mert a felhasználók fognak

855
00:51:11,530 --> 00:51:14,880
kezd érezni és értékelni rossz tervezési döntéseket.

856
00:51:14,880 --> 00:51:19,950
>> Szóval hogyan megy a végrehajtó linkelt - egy hash tábla, 31 elemeket?

857
00:51:19,950 --> 00:51:22,600
És az előző példában volt önkényesen körülbelül születésnapok.

858
00:51:22,600 --> 00:51:26,190
Ha valaki születésnapja január 1-jétől, illetve február 1-jén fogjuk őket ebben a vödörben.

859
00:51:26,190 --> 00:51:28,960
Ha ez január 2. február 2., március 2, akkor tedd a vödörbe.

860
00:51:28,960 --> 00:51:32,220
Ezért volt 31. Hogyan nyilvánítja a hash tábla?

861
00:51:32,220 --> 00:51:37,480
Ez lehet nagyon egyszerű, node * asztal az én önkényes neve rá, [31].

862
00:51:37,480 --> 00:51:42,400
Ez ad nekem 31 mutatókat csomópontok,

863
00:51:42,400 --> 00:51:45,370
és amely lehetővé teszi számomra, hogy 31 mutató csatolt listák

864
00:51:45,370 --> 00:51:48,800
még ha e láncok kezdetben NULL.

865
00:51:48,800 --> 00:51:54,860
Mit akarok tenni, ha azt szeretné tárolni "Alice", "Bob", "Charlie"?

866
00:51:54,860 --> 00:51:57,010
Nos, meg kell, hogy lezárja ezeket a dolgokat a szerkezet

867
00:51:57,010 --> 00:52:00,530
mert meg kell mutatni, hogy Alice Bob, arra utalnak, hogy Charlie, és így tovább.

868
00:52:00,530 --> 00:52:04,940
Nem lehet csak a neveket egyedül, így tudtam létrehozni egy új struktúra nevű csomópontot itt.

869
00:52:04,940 --> 00:52:08,310
>> Mi az aktuális csomópont? Mi az a csomópont az új láncolt lista?

870
00:52:08,310 --> 00:52:11,840
Az első dolog, az úgynevezett szó, az a személy nevét.

871
00:52:11,840 --> 00:52:14,340
LENGTH, feltehetően összefügg a maximális hossza egy ember neve,

872
00:52:14,340 --> 00:52:18,210
bármi azaz, 20, 30, 40 karakter őrült sarokban esetekben,

873
00:52:18,210 --> 00:52:22,680
és +1 Az mi? Ez csak az extra NULL karaktert \ 0.

874
00:52:22,680 --> 00:52:27,410
Tehát ez a csomópont csomagolópapír "valami" belsejében is,

875
00:52:27,410 --> 00:52:29,640
hanem azt is kijelenti a pointer neve mellett

876
00:52:29,640 --> 00:52:32,580
annak érdekében, hogy tudjuk lánc Alice Bob Charlie és így tovább.

877
00:52:32,580 --> 00:52:36,700
Lehet NULL, de nem feltétlenül kell annak lennie.

878
00:52:36,700 --> 00:52:40,110
Van még kérdése ezeken hash táblát? Igen?

879
00:52:40,110 --> 00:52:46,190
[Student kérdezi kérdést, érthetetlen] Egy tömb - jó kérdés.

880
00:52:46,190 --> 00:52:50,120
Miért van ez char szót egy tömbben nem csak char *?

881
00:52:50,120 --> 00:52:53,830
Ebben a kissé önkényes példát, nem akartam, hogy kénytelenek

882
00:52:53,830 --> 00:52:56,190
malloc minden egyes eredeti nevek.

883
00:52:56,190 --> 00:52:59,530
Azt akartam, hogy nyilvánítsa a maximális memória a húr

884
00:52:59,530 --> 00:53:06,020
úgy, hogy tudtam másolni a szerkezet Alice \ 0, és nem kell foglalkozni a malloc és free és hasonlók.

885
00:53:06,020 --> 00:53:11,710
De tudtam csinálni, hogy ha akartam, hogy legyen tudatában a tér használatát. Jó kérdés.

886
00:53:11,710 --> 00:53:14,780
Szóval próbáljuk általánosítani távol a

887
00:53:14,780 --> 00:53:18,350
és fókuszáljon a fennmaradó mai adatszerkezetek általában

888
00:53:18,350 --> 00:53:21,170
és más problémák, hogy meg tudjuk oldani ugyanazt a fundamentumok

889
00:53:21,170 --> 00:53:24,590
bár az adatszerkezetek maguk is különböznek egymástól adatokat.

890
00:53:24,590 --> 00:53:27,910
>> Így kiderül, a számítógép-tudomány, a fák nagyon gyakoriak.

891
00:53:27,910 --> 00:53:29,760
És azt hiszem egy fa fajta, mint egy családfát,

892
00:53:29,760 --> 00:53:31,830
ha van valami gyökér, néhány matriarcha vagy pátriárka,

893
00:53:31,830 --> 00:53:34,540
nagymama vagy nagypapa vagy korábbi vissza,

894
00:53:34,540 --> 00:53:38,880
alatt, amely anya és apa vagy különböző testvérek vagy hasonlók.

895
00:53:38,880 --> 00:53:42,500
Tehát egy fa szerkezet csomópontok és azt gyermekek,

896
00:53:42,500 --> 00:53:45,260
általában 0 vagy több gyermek esetében minden egyes csomóponthoz.

897
00:53:45,260 --> 00:53:47,320
És néhány zsargon, amit látsz ezen a képen van

898
00:53:47,320 --> 00:53:50,630
minden olyan a kis gyerekek vagy unoka a széleit

899
00:53:50,630 --> 00:53:52,330
akiknek nincs nyilak származó őket,

900
00:53:52,330 --> 00:53:55,070
ezek az úgynevezett levelek, és bárki be a belső

901
00:53:55,070 --> 00:53:58,790
egy belső csomópont, hívhatja bármi ezekhez hasonlót.

902
00:53:58,790 --> 00:54:01,430
De ez a szerkezet elég gyakori. Ez egy kicsit önkényes.

903
00:54:01,430 --> 00:54:04,930
Van egy gyermek, a bal oldalon, már három gyermek a jobb oldalon,

904
00:54:04,930 --> 00:54:06,830
két gyerek a bal alsó sarokban.

905
00:54:06,830 --> 00:54:10,740
Tehát lehet különböző méretű fák, de ha elkezdjük, hogy egységesítsék a dolgokat,

906
00:54:10,740 --> 00:54:15,330
és lehet, hogy visszahívja ezt honnan Patrick videót a bináris keresés egy korábbi rövid

907
00:54:15,330 --> 00:54:19,490
online, bináris keresés nem kell végrehajtani egy sor

908
00:54:19,490 --> 00:54:21,410
vagy papírdarabok a táblára.

909
00:54:21,410 --> 00:54:25,490
Tegyük fel, hogy akarta, hogy tárolja a számokat kifinomultabb adatszerkezet.

910
00:54:25,490 --> 00:54:27,680
Lehet létrehozni egy fát, mint ez.

911
00:54:27,680 --> 00:54:35,290
Lehet, hogy egy csomópont a C-ben bejelentett, és a csomópont lehet legalább két elem belsejébe.

912
00:54:35,290 --> 00:54:39,470
Az egyik a kívánt számot tárolni, a másik pedig - nos, meg kell még egy.

913
00:54:39,470 --> 00:54:41,540
A másik a gyerekek.

914
00:54:41,540 --> 00:54:45,150
Tehát itt van egy másik adatszerkezet. Ez alkalommal, egy csomópont a meghatározás szerint tárolására szám n

915
00:54:45,150 --> 00:54:49,060
majd két mutatót, balra és jobbra gyermek gyermek.

916
00:54:49,060 --> 00:54:52,100
És ők nem önkényes. Mi érdekes ezt a fát?

917
00:54:52,100 --> 00:55:00,550
>> Mi van a minta, hogyan általunk meghatározott e ki, vagy hogyan Patrick fektette ki a videót?

918
00:55:00,550 --> 00:55:02,790
Elég nyilvánvaló, hogy van néhány válogatás folyik itt,

919
00:55:02,790 --> 00:55:04,460
de mi van az egyszerű szabály? Igen?

920
00:55:04,460 --> 00:55:08,350
[Student válasz, érthetetlen]

921
00:55:08,350 --> 00:55:12,040
Tökéletes. Ha ezt a pillantást, látod a kis számok a bal oldalon,

922
00:55:12,040 --> 00:55:14,690
nagy számok a bal oldalon, de ez igaz minden csomópont.

923
00:55:14,690 --> 00:55:20,370
Minden egyes csomópont a bal gyerek kevesebb, mint, és a jobb gyermek nagyobb, mint azt.

924
00:55:20,370 --> 00:55:25,210
Mi ez most azt jelenti, ha akarom keresni az adatok struktúrája, mondjuk, a szám 44,

925
00:55:25,210 --> 00:55:29,320
El kell kezdeni a gyökér, mert az összes ilyen bonyolultabb adatszerkezetek most,

926
00:55:29,320 --> 00:55:31,910
már csak egy mutató, egy dolog, az elején.

927
00:55:31,910 --> 00:55:35,010
És ebben az esetben, az elején a gyökér. Ez nem a bal szélen,

928
00:55:35,010 --> 00:55:39,530
ez a gyökere ennek a szerkezetnek. Látom itt van 55, és én keresem 44.

929
00:55:39,530 --> 00:55:41,430
Milyen irányba akarok menni?

930
00:55:41,430 --> 00:55:45,680
Nos, azt akarom, hogy a bal, mert nyilvánvaló, hogy a jobb lesz túl nagy.

931
00:55:45,680 --> 00:55:49,050
Tehát észre itt, te valami fogalmilag aprítás a fa fél

932
00:55:49,050 --> 00:55:51,700
mert te soha nem megy le a jobb oldali.

933
00:55:51,700 --> 00:55:55,410
Úgyhogy most megyek a 55 az 33. Ez túl kicsi egy szám.

934
00:55:55,410 --> 00:56:01,590
Ezt keresem: 44, de most már tudom, ha 44 van ez a fa, tudok menni természetesen a jobb oldalon.

935
00:56:01,590 --> 00:56:04,460
Szóval megint én vagyok metszést a fa felét.

936
00:56:04,460 --> 00:56:06,780
Ez nagyjából megegyezik fogalmilag a telefonkönyv.

937
00:56:06,780 --> 00:56:09,510
Ez megegyezik azzal, amit tettünk, a papírokat a táblára,

938
00:56:09,510 --> 00:56:13,940
de ez egy kifinomult szerkezet, amely lehetővé teszi számunkra, hogy ténylegesen

939
00:56:13,940 --> 00:56:16,880
ezt oszd meg és uralkodj a design az algoritmus,

940
00:56:16,880 --> 00:56:19,420
és valóban, átkelés a struktúra, mint ez - Hoppá.

941
00:56:19,420 --> 00:56:22,870
Mozgás a struktúra, mint ez, ahol ez csak "erre kell menni, vagy menjen, hogy így"

942
00:56:22,870 --> 00:56:26,870
azt jelenti, hogy az összes kódot, hogy behajlítva a fejedben, amikor az első végrehajtó szakaszban

943
00:56:26,870 --> 00:56:31,270
vagy séta otthon, a bináris keresés segítségével rekurzió és iteráció,

944
00:56:31,270 --> 00:56:35,060
ez a fájdalom a nyak. Keresse meg a középső elemet, majd tedd a kerekítés felfelé vagy lefelé.

945
00:56:35,060 --> 00:56:39,230
>> Van egy szépség, mert most már használhatja rekurzió ismét

946
00:56:39,230 --> 00:56:43,760
de sokkal tisztábban. Valóban, ha a szám 55, és meg akarja találni 44,

947
00:56:43,760 --> 00:56:48,450
menj maradt ebben az esetben, akkor mit csinálsz? Futtatja pontosan ugyanazt algoritmust.

948
00:56:48,450 --> 00:56:51,560
Kivárunk értékét a csomópont, akkor menj balra vagy jobbra.

949
00:56:51,560 --> 00:56:53,670
Ezután ellenőrizze az érték a csomópont, menj balra vagy jobbra.

950
00:56:53,670 --> 00:56:56,710
Ez tökéletesen megfelel rekurziót.

951
00:56:56,710 --> 00:57:00,920
Így annak ellenére, hogy a múltban tettünk néhány meglehetősen önkényes példát bevonásával rekurzió

952
00:57:00,920 --> 00:57:03,430
ez nem kell rekurzív adatokat tartalmazó struktúrák,

953
00:57:03,430 --> 00:57:07,820
különösen a fák, ez egy tökéletes alkalmazásának gondolatát vesz egy probléma,

954
00:57:07,820 --> 00:57:12,920
csökkenő, majd megoldása az azonos típusú, de kisebb, program.

955
00:57:12,920 --> 00:57:14,590
>> Szóval van egy másik adatszerkezet tudjuk bevezetni.

956
00:57:14,590 --> 00:57:18,760
Ez az egyik célja, első pillantásra nézni rejtélyes, de ez elképesztő.

957
00:57:18,760 --> 00:57:25,090
Tehát ez egy adatszerkezet úgynevezett Trie, Trie, amely örökölt szó visszakeresés,

958
00:57:25,090 --> 00:57:30,210
amely nem ejtik re-try-val, de ez az, amit a világ hívja ezeket a dolgokat. Megpróbálja. T-r-i-e.

959
00:57:30,210 --> 00:57:35,190
Ez egy fa struktúra néhány sort, de minden a csomópontok egy Trie

960
00:57:35,190 --> 00:57:41,280
Úgy tűnik, hogy mi? És ez egy kicsit félrevezető, mert ez a fajta rövidített.

961
00:57:41,280 --> 00:57:45,960
De úgy néz ki, minden egyes csomópontja e Trie valójában egy tömb.

962
00:57:45,960 --> 00:57:48,840
És bár a szerző ezt a diagram nem bizonyította azt,

963
00:57:48,840 --> 00:57:54,130
ebben az esetben, ez Trie egy adatstruktúra, melynek célja az életben tárolni szavak

964
00:57:54,130 --> 00:57:57,330
, mint az A-l-i-C-E vagy B-o-b.

965
00:57:57,330 --> 00:58:02,480
És ahogyan ezeket az adatokat tárolja Alice és Bob és Charlie és Anita, és így tovább

966
00:58:02,480 --> 00:58:06,970
van ez használ egy tömböt amelyben tárolni Alice egy Trie,

967
00:58:06,970 --> 00:58:09,820
kezdjük a gyökér csomópont, amely úgy néz ki, mint egy tömb,

968
00:58:09,820 --> 00:58:12,080
és ez már írva rövidített írásmódot.

969
00:58:12,080 --> 00:58:15,070
A szerző kihagyott abcdefg mert nem voltak nevek ezzel.

970
00:58:15,070 --> 00:58:19,150
Ezek csak azt mutatta, M és P és T, de ebben az esetben,

971
00:58:19,150 --> 00:58:22,780
menjünk el Alice és Bob és Charlie bizonyos neveket itt.

972
00:58:22,780 --> 00:58:25,670
Maxwell valójában ebben a diagram.

973
00:58:25,670 --> 00:58:29,570
Tehát hogyan volt a szerző bolt M-a-x-w-E-l-l?

974
00:58:29,570 --> 00:58:36,990
Ő kezdte a gyökér csomópontot, és elment [M], így nagyjából 13, a 13. helyen a tömbben.

975
00:58:36,990 --> 00:58:40,750
Aztán onnan, van egy mutató.

976
00:58:40,750 --> 00:58:42,760
A mutató, ami egy másik tömböt.

977
00:58:42,760 --> 00:58:47,880
Innen a szerző indexelt ebbe a tömb a helyszínen A., ahogyan azt ott a bal felső sarokban,

978
00:58:47,880 --> 00:58:52,250
aztán ő következett, hogy egy másik mutató tömb,

979
00:58:52,250 --> 00:58:55,460
és elment a mutató a következő helyen: X.

980
00:58:55,460 --> 00:58:59,840
Majd a következő tömb helyszín W, E, L, L, és így tovább,

981
00:58:59,840 --> 00:59:03,090
és végül, nézzük valóban megpróbál egy képet e.

982
00:59:03,090 --> 00:59:05,380
Mit jelent egy csomópont néz a kódot?

983
00:59:05,380 --> 00:59:11,820
A csomópont egy Trie tartalmaz egy sor mutató több csomópont.

984
00:59:11,820 --> 00:59:16,090
De ez is van, hogy valamilyen logikai érték, legalábbis ennek végrehajtásában.

985
00:59:16,090 --> 00:59:18,770
Én történetesen nevezni is_word. Miért?

986
00:59:18,770 --> 00:59:22,670
Mert amikor behelyezésekor Maxwell, te nem beillesztése

987
00:59:22,670 --> 00:59:25,300
bármit ebbe adatszerkezet.

988
00:59:25,300 --> 00:59:27,480
Te nem ír M. Te nem ír X.

989
00:59:27,480 --> 00:59:30,240
Minden, amit csinál a következő mutatók.

990
00:59:30,240 --> 00:59:33,360
A mutató, amely képviseli M, akkor a mutató, amely egy,

991
00:59:33,360 --> 00:59:36,310
akkor a mutató képviselő X, akkor W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
de mit kell tennie, hogy a végén van valami megy, ellenőrizze, én el ezt a helyet.

993
00:59:41,950 --> 00:59:45,560
Volt egy szó, amely itt ér véget az adatszerkezet.

994
00:59:45,560 --> 00:59:48,190
>> Tehát mi a Trie valóban tele van, és a szerző úgy döntött, hogy képviselje

995
00:59:48,190 --> 00:59:51,880
Ezen terminuses kis háromszög.

996
00:59:51,880 --> 00:59:56,470
Ez csak azt jelenti, hogy az a tény, ez a háromszög van itt, ez a boolean értéke true

997
00:59:56,470 --> 00:59:59,200
azt jelenti, ha megy visszafelé a fa,

998
00:59:59,200 --> 01:00:02,420
azt jelenti, hogy egy szó nevű Maxwell ebben.

999
01:00:02,420 --> 01:00:04,870
De a szó foo, például,

1000
01:00:04,870 --> 01:00:07,970
nem a fán, mert ha elkezdem a gyökér csomópont ide a csúcson,

1001
01:00:07,970 --> 01:00:14,030
Nincs f mutató, nem o pointer, nem o mutató. Foo nem nevet ez a szótár.

1002
01:00:14,030 --> 01:00:22,460
Hanem ezzel szemben, Turing, terc-u-r-i-n-g. Ismét, nem tárolja t vagy a u vagy r vagy i vagy n vagy g.

1003
01:00:22,460 --> 01:00:29,820
De tettem áruház e adatszerkezet értékű igaz utat fel ide a csomópont - a fa

1004
01:00:29,820 --> 01:00:33,030
azáltal, hogy ezt a boolean értéke is_word igaz.

1005
01:00:33,030 --> 01:00:35,740
Tehát egy Trie egyfajta nagyon érdekes meta szerkezet,

1006
01:00:35,740 --> 01:00:39,810
ha te nem igazán tárolására maguk a szavak ilyen típusú szótárban.

1007
01:00:39,810 --> 01:00:45,100
Ahhoz, hogy világos, te csak tárolása igen vagy nem, van egy szó, hogy itt ér véget.

1008
01:00:45,100 --> 01:00:46,430
>> Most mi a hatása?

1009
01:00:46,430 --> 01:00:51,120
Ha van 150.000 szót a szótárban, hogy akarsz tárolni a memóriában

1010
01:00:51,120 --> 01:00:53,400
használatával olyasmi, mint egy láncolt lista,

1011
01:00:53,400 --> 01:00:56,870
megy, hogy a 150.000 csomópontok a láncolt lista.

1012
01:00:56,870 --> 01:01:00,250
És találni egy olyan szavak betűrendben vehetné O (n) idő.

1013
01:01:00,250 --> 01:01:04,370
Lineáris idő. De abban az esetben van egy Trie,

1014
01:01:04,370 --> 01:01:09,210
mi a működési ideje találni a szóval?

1015
01:01:09,210 --> 01:01:17,390
Kiderült, hogy a szépség, az, hogy akkor is, ha 149.999 szó már ez a szótár,

1016
01:01:17,390 --> 01:01:20,170
mivel végrehajtani ezen adatok struktúrája,

1017
01:01:20,170 --> 01:01:25,560
mennyi időbe telik, hogy megtalálja, vagy helyezze még egy személyt, hogy mint Alice, Alice?

1018
01:01:25,560 --> 01:01:30,640
Nos, ez csak 5, talán 6 lépéseket a záró karakter.

1019
01:01:30,640 --> 01:01:32,880
Mivel a presense egyéb nevek a szerkezet

1020
01:01:32,880 --> 01:01:35,340
nem lesz az olyan behelyezése Alice.

1021
01:01:35,340 --> 01:01:39,640
Továbbá megállapította, Alice egyszer van 150.000 szó ebben a szótárban

1022
01:01:39,640 --> 01:01:41,960
nem kap az utat találni Alice egyáltalán,

1023
01:01:41,960 --> 01:01:46,880
mert Alice. . . . . itt, mert találtam egy boolean értéket.

1024
01:01:46,880 --> 01:01:50,920
És ha nincs boolean true, akkor Alice nincs ebben adatstruktúrájának szavak.

1025
01:01:50,920 --> 01:01:56,220
Más szóval, a futási idő megtalálni a dolgokat, és helyezze a dolgok ebbe az új

1026
01:01:56,220 --> 01:02:01,920
adatstruktúrája Trie O of - ez nem n.

1027
01:02:01,920 --> 01:02:05,730
Mivel a presense a 150.000 ember nincs hatással Alice, úgy tűnik.

1028
01:02:05,730 --> 01:02:11,560
Így nevezzük k, ahol k a maximális hossza egy szót angolul

1029
01:02:11,560 --> 01:02:14,050
amely jellemzően nem több, mint 20-valami karaktert.

1030
01:02:14,050 --> 01:02:17,940
Így k egy konstans. Tehát a Szent Grál úgy tűnik, hogy megtalálta már

1031
01:02:17,940 --> 01:02:26,000
olyan, mint egy Trie, állandó időt lapkák, a keresések, a törlések.

1032
01:02:26,000 --> 01:02:29,170
Mivel a néhány dolog már a szerkezetben,

1033
01:02:29,170 --> 01:02:32,600
amelyek nem is fizikailag ott. Ismét, ők csak egyfajta ellenőrzött le, igen vagy nem,

1034
01:02:32,600 --> 01:02:35,050
nincs hatása a jövőbeli működési idő.

1035
01:02:35,050 --> 01:02:37,940
>> De van, hogy a fogást, különben nem lett volna olyan sok időt elvesztegetett

1036
01:02:37,940 --> 01:02:41,460
az összes többi adat struktúrákat, csak hogy végre kap a titok egyik, hogy elképesztő.

1037
01:02:41,460 --> 01:02:46,410
Szóval, milyen áron fizetünk elérni ezt a nagyságot itt? Space.

1038
01:02:46,410 --> 01:02:49,010
Ez a dolog masszív. És az ok, hogy a szerző

1039
01:02:49,010 --> 01:02:52,400
nem nyújtott be itt, észreveheti, hogy mindezek a dolgok úgy néz ki, mint a tömbök,

1040
01:02:52,400 --> 01:02:55,400
hogy nem készít a többi fa, a többi Trie,

1041
01:02:55,400 --> 01:02:58,060
mert ők egyszerűen nem releváns a történetet.

1042
01:02:58,060 --> 01:03:01,870
De mindezek csomópont rendkívül széles, és minden csomópont a fában vesz fel

1043
01:03:01,870 --> 01:03:07,780
26 vagy ténylegesen, lehet 27 karakter, mert ebben az esetben én szóközökkel az aposztróf

1044
01:03:07,780 --> 01:03:09,980
hogy mi volna apostrophized szavakat.

1045
01:03:09,980 --> 01:03:14,450
Ebben az esetben, ezek széles tömbök. Így még ha ők nem picutured,

1046
01:03:14,450 --> 01:03:18,190
ez veszi fel a hatalmas mennyiségű RAM.

1047
01:03:18,190 --> 01:03:20,670
Ami lehet, hogy finom, especilly a modern hardver,

1048
01:03:20,670 --> 01:03:25,650
de ez a kompromisszum. Kapunk kevesebb időt töltenek több helyet foglalnak.

1049
01:03:25,650 --> 01:03:28,580
Szóval, hol van ez az egész megy?

1050
01:03:28,580 --> 01:03:32,640
Nos, van - lássuk itt.

1051
01:03:32,640 --> 01:03:39,510
Csináljuk egy ugrás, hogy ez a fickó itt.

1052
01:03:39,510 --> 01:03:43,450
>> Hiszed vagy sem, olyan vicces, mint a C már egy ideje,

1053
01:03:43,450 --> 01:03:48,130
vagyunk elérte azt a pontot, ahol a félévben az ideje, hogy átmenet dolgokat modern.

1054
01:03:48,130 --> 01:03:50,950
A dolgok egy magasabb szinten. És bár a következő hetekben

1055
01:03:50,950 --> 01:03:54,580
akkor még továbbra is merítse magunkat a világ a mutatók és a memória kezelése

1056
01:03:54,580 --> 01:03:57,210
kap, hogy a kényelmet, amit aztán építeni,

1057
01:03:57,210 --> 01:04:01,270
a végén játék végül bevezetni, ironikusan, nem ezt a nyelvet.

1058
01:04:01,270 --> 01:04:03,330
Fogunk költeni, mint 10 perc alatt beszél HTML.

1059
01:04:03,330 --> 01:04:05,950
Minden HTML egy leíró nyelv, és mi a leíró nyelv

1060
01:04:05,950 --> 01:04:10,220
ezek a sorozat nyitott zárójelet és zárt zárójelek azt mondják ", hogy ez a merész"

1061
01:04:10,220 --> 01:04:12,000
"Hogy ez a dőlt", "teszi ezt központú."

1062
01:04:12,000 --> 01:04:14,250
Ez nem minden, intellektuálisan érdekes, de ez szuper hasznos.

1063
01:04:14,250 --> 01:04:16,650
És ez minden bizonnyal mindenütt ezekben a napokban.

1064
01:04:16,650 --> 01:04:19,450
De mi erős a HTML világában, és a webes programozás általában

1065
01:04:19,450 --> 01:04:25,910
épület dinamikus dolgokat írni kódot a nyelvek, mint a PHP vagy a Python vagy a Ruby vagy Java vagy C #.

1066
01:04:25,910 --> 01:04:30,360
Tényleg, amit a nyelv választás, és a termelő HTML dinamikus.

1067
01:04:30,360 --> 01:04:32,960
Generálása úgynevezett CSS dinamikusan.

1068
01:04:32,960 --> 01:04:35,810
Cascading Style Sheets, ami szintén kb esztétika.

1069
01:04:35,810 --> 01:04:41,360
És így még akkor is, ma, ha elmegyek néhány weboldal, mint az ismerős Google.com,

1070
01:04:41,360 --> 01:04:46,100
és megyek többet, fejlesztő, kilátás forrás, amely talán már azelőtt,

1071
01:04:46,100 --> 01:04:49,800
de azt, hogy megtekinthesse forrása, ez a cucc talán úgy néz ki elég rejtélyes.

1072
01:04:49,800 --> 01:04:55,320
De ez a mögöttes kód, amely megvalósítja Google.com.

1073
01:04:55,320 --> 01:04:57,940
Az elülső vég. És tulajdonképpen ez mind fluffy esztétika cucc.

1074
01:04:57,940 --> 01:05:01,740
Ez a CSS itt. Ha folyamatosan legördülő szerzünk néhány színkódolt cucc.

1075
01:05:01,740 --> 01:05:06,890
Ez a HTML. Google kód így néz ki a rendetlenség, de ha valóban nyitni egy másik ablak,

1076
01:05:06,890 --> 01:05:09,380
láthatjuk egy szerkezetet ennek.

1077
01:05:09,380 --> 01:05:12,640
Ha kinyitom ezt, észre itt, ez egy kicsit olvashatóbb.

1078
01:05:12,640 --> 01:05:16,850
Fogunk látni nemsokára ezt a címkét, [szó] egy tag,

1079
01:05:16,850 --> 01:05:23,520
HTML, fej, test, div, script, szöveges terület, span, középre, div.

1080
01:05:23,520 --> 01:05:26,770
És ez is egyfajta rejtélyes külsejű első pillantásra,

1081
01:05:26,770 --> 01:05:30,890
de mindez zűrzavar következik bizonyos mintákat, és ismételhető minták,

1082
01:05:30,890 --> 01:05:33,850
annak érdekében, hogy amint megkapjuk az alapokat le, akkor képes lesz arra, hogy kódot írni, mint ez

1083
01:05:33,850 --> 01:05:37,550
majd manipulálni kód használatával, mint ez még egy másik nyelvet, az úgynevezett JavaScript programot.

1084
01:05:37,550 --> 01:05:40,440
És a JavaScript olyan nyelv, amely fut belül a böngésző

1085
01:05:40,440 --> 01:05:44,380
ma, hogy használja Harvard tanfolyamok, a tanfolyam vásárlási eszköz a Google maps használ

1086
01:05:44,380 --> 01:05:48,660
hogy kapsz egy csomó a dinamizmus, a Facebook ad mutatni állapotfrissítéseiket,

1087
01:05:48,660 --> 01:05:51,430
Twitter használja fel, hogy mutassa meg tweets azonnal.

1088
01:05:51,430 --> 01:05:53,820
Mindez akkor kezdődik merítsük be magunkat

1089
01:05:53,820 --> 01:05:57,190
De oda, meg kell értenünk, egy kis valamit az interneten.

1090
01:05:57,190 --> 01:06:01,130
Ez a klip itt csak egy perc hosszú, és tegyük fel, most ez, sőt,

1091
01:06:01,130 --> 01:06:08,380
hogy az internet működik, mint egy teaser, mit szól, hogy jöjjön. Adok "Warriors of a neten."

1092
01:06:08,380 --> 01:06:14,720
>> [♫ Slow kórus zenei ♫]

1093
01:06:14,720 --> 01:06:20,450
[Férfi elbeszélő] jött egy üzenet.

1094
01:06:20,450 --> 01:06:23,770
A protokoll minden saját.

1095
01:06:23,770 --> 01:06:37,270
[♫ Gyorsabb elektronikus zene ♫]

1096
01:06:37,270 --> 01:06:41,330
Azért jött, hogy a világ a hűvös tűzfalak, nemtörődöm routerek,

1097
01:06:41,330 --> 01:06:45,690
és veszélyek sokkal rosszabb, mint a halál.

1098
01:06:45,690 --> 01:06:55,400
Ő gyors. Ő erős. Ő a TCP / IP, és van neki a címet.

1099
01:06:55,400 --> 01:06:59,250
Warriors of a neten.

1100
01:06:59,250 --> 01:07:05,290
[Malan] A jövő héten, akkor. Az internet. Web programozás. Ez CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]