1
00:00:00,000 --> 00:00:03,423
>> [Zenelejátszási]

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> ANDI Peng: Üdvözöljük héten 6 szakasz.

4
00:00:08,210 --> 00:00:11,620
Mi eltért a szokásos
szakasza idején kedd

5
00:00:11,620 --> 00:00:14,130
délután ezt a szép vasárnap reggel.

6
00:00:14,130 --> 00:00:17,330
Köszönjük mindenkinek, hogy
csatlakozott hozzám ma, de komolyan,

7
00:00:17,330 --> 00:00:18,170
a tapsot.

8
00:00:18,170 --> 00:00:20,600
>> Ez egy elég nagy erőfeszítést.

9
00:00:20,600 --> 00:00:23,600
Én szinte nem is teszik
fel időben, de minden rendben volt.

10
00:00:23,600 --> 00:00:27,520
Így tudom, hogy mindannyian
imént tette, hogy a tesztre.

11
00:00:27,520 --> 00:00:30,370
Először is, szívesen
A másik oldala az, hogy.

12
00:00:30,370 --> 00:00:32,917
>> Másodszor, megbeszéljük.

13
00:00:32,917 --> 00:00:34,000
Megbeszéljük a teszt.

14
00:00:34,000 --> 00:00:35,700
Megbeszéljük, hogyan
csinálsz az osztályban.

15
00:00:35,700 --> 00:00:36,550
Rendben leszel.

16
00:00:36,550 --> 00:00:39,080
Nálam van a vetélkedők
Ön végén van,

17
00:00:39,080 --> 00:00:42,120
így ha akartok venni
nézzék meg, teljesen rendben van.

18
00:00:42,120 --> 00:00:46,590
>> Olyan gyorsan, mielőtt elkezdjük, a
napirendjét ma a következő.

19
00:00:46,590 --> 00:00:48,430
Mint látható, mi vagyunk
alapvetően a gyors tüzelés

20
00:00:48,430 --> 00:00:52,120
egy csomó adatstruktúrák
Nagyon, nagyon, nagyon gyorsan.

21
00:00:52,120 --> 00:00:54,380
Tehát mint ilyen, nem lesz
szuper interaktív ma.

22
00:00:54,380 --> 00:00:59,620
Akkor csak velem ilyen kiabálva
dolog, amit, és ha én megzavarja akkor,

23
00:00:59,620 --> 00:01:02,680
ha én is megyek gyorsan, hadd tudjam.

24
00:01:02,680 --> 00:01:05,200
Ezek csak a különböző adatok
struktúrák, és részeként

25
00:01:05,200 --> 00:01:07,070
a PSET ezt
következő hétre, akkor

26
00:01:07,070 --> 00:01:10,340
kérni, hogy hajtsák végre az egyiket,
talán a két them-- ketten

27
00:01:10,340 --> 00:01:12,319
a PSET.

28
00:01:12,319 --> 00:01:14,610
OK, szóval csak fog
először néhány bejelentéseket.

29
00:01:14,610 --> 00:01:19,070
Átnézzük halom és a sorban állás több
mélysége, mint amit tettünk, mielőtt a kvíz.

30
00:01:19,070 --> 00:01:20,990
Megyünk át kapcsolódik
listához újra, ismét,

31
00:01:20,990 --> 00:01:23,899
mélyebben, mint amit
miénk volt a teszt.

32
00:01:23,899 --> 00:01:26,440
És akkor fogunk beszélni hash
asztalok, fák és próbál, amelyek

33
00:01:26,440 --> 00:01:28,890
mind nagyon szükséges a PSET.

34
00:01:28,890 --> 00:01:32,925
És akkor megyünk át néhány
Hasznos tippek pset5.

35
00:01:32,925 --> 00:01:37,360
>> OK, így kvíz 0.

36
00:01:37,360 --> 00:01:41,090
Az átlag 58% -os.

37
00:01:41,090 --> 00:01:45,370
Ez nagyon alacsony volt, és így a srácok minden
nem nagyon, de nagyon jól szerint

38
00:01:45,370 --> 00:01:46,510
azzal.

39
00:01:46,510 --> 00:01:49,970
>> Elég sokat, ökölszabály, ha
belül szórás az átlag

40
00:01:49,970 --> 00:01:52,990
különösen azért, mert mi vagyunk a kevésbé
kényelmes részén, te teljesen rendben.

41
00:01:52,990 --> 00:01:54,120
Maga a pályán.

42
00:01:54,120 --> 00:01:55,190
Az élet jó.

43
00:01:55,190 --> 00:01:58,952
>> Tudom, hogy ez ijesztő arra gondolni, hogy
Kaptam, mint egy 40% -os ezt a kvízt.

44
00:01:58,952 --> 00:02:00,160
Megyek nem ebben az osztályban.

45
00:02:00,160 --> 00:02:02,243
Megígérem neked, hogy te nem
kudarcot vall az osztály.

46
00:02:02,243 --> 00:02:03,680
Te teljesen rendben.

47
00:02:03,680 --> 00:02:06,850
>> Azoknak, akik túltette
Az átlagos, lenyűgöző, impozáns,

48
00:02:06,850 --> 00:02:08,780
mint, komolyan jól sikerült.

49
00:02:08,780 --> 00:02:09,689
Én azokat velem.

50
00:02:09,689 --> 00:02:11,730
Nyugodtan gyere őket
A szakasz végén.

51
00:02:11,730 --> 00:02:14,520
Hadd tudja, ha bármilyen
kérdések, kérdések velük.

52
00:02:14,520 --> 00:02:17,204
Ha összeadjuk a pontszámot
rossz, ossza meg velünk.

53
00:02:17,204 --> 00:02:21,240
>> OK, így pset5, ez egy igazán
fura héten Yale abban az értelemben,

54
00:02:21,240 --> 00:02:24,240
hogy mi PSET miatt
Szerdán délben beleértve

55
00:02:24,240 --> 00:02:27,317
A nap végén, így ez valójában
elméletileg fizetni kedd délben.

56
00:02:27,317 --> 00:02:29,150
Valószínűleg senki sem fejezte
kedden délben.

57
00:02:29,150 --> 00:02:30,830
Ez teljesen rendben.

58
00:02:30,830 --> 00:02:33,700
Megyünk, hogy munkaidőben
Ma este, valamint hétfőn este.

59
00:02:33,700 --> 00:02:36,810
És az összes szakaszt ezen a héten
valójában alakítani műhelyek,

60
00:02:36,810 --> 00:02:38,800
így nyugodtan pop
bármely kívánt szakasz,

61
00:02:38,800 --> 00:02:42,810
és lesz egyfajta mini-PSET
műhelyek segítségért.

62
00:02:42,810 --> 00:02:45,620
Tehát mint ilyen, ez az egyetlen szakasz
ahol tanítunk anyagot.

63
00:02:45,620 --> 00:02:49,220
Az összes többi részt fog koncentrálni
kizárólag a segítség a PSET.

64
00:02:49,220 --> 00:02:50,146
Igen?

65
00:02:50,146 --> 00:02:52,000
>> Közönség: Hol vannak munkaidőben?

66
00:02:52,000 --> 00:02:56,120
>> ANDI PENG: Munkaidő
tonight-- ó, jó kérdés.

67
00:02:56,120 --> 00:03:00,580
Azt hiszem, munkaidőn este
vannak Teal vagy Commons.

68
00:03:00,580 --> 00:03:02,984
Ha megnézed az online CS50
és akkor megy a hivatali időben,

69
00:03:02,984 --> 00:03:05,650
léteznie kell egy ütemtervet, amely
árulja el, hol mindegyik.

70
00:03:05,650 --> 00:03:07,954
>> Tudom, akár ma este
illetve holnapi réce,

71
00:03:07,954 --> 00:03:10,120
és azt hiszem, lehet, hogy
commons a múltkor.

72
00:03:10,120 --> 00:03:11,020
Nem vagyok benne biztos.

73
00:03:11,020 --> 00:03:11,700
Jó kérdés.

74
00:03:11,700 --> 00:03:14,430
Ellenőrizze a CS50.

75
00:03:14,430 --> 00:03:18,780
>> Cool, kérdések merülnek
programomat a következő, mint három nap alatt?

76
00:03:18,780 --> 00:03:21,690
Megígérem nektek, mint David
azt mondta, ez a domb tetején.

77
00:03:21,690 --> 00:03:23,050
Srácok, már majdnem ott.

78
00:03:23,050 --> 00:03:24,644
Csak három napig.

79
00:03:24,644 --> 00:03:26,310
Oda, és akkor majd minden jön le.

80
00:03:26,310 --> 00:03:28,114
Mi lesz egy szép CS-mentes szünetet.

81
00:03:28,114 --> 00:03:28,780
Üdv újra.

82
00:03:28,780 --> 00:03:30,779
Majd belevetik magukat web
programozás és fejlesztés,

83
00:03:30,779 --> 00:03:35,150
dolog, hogy nagyon szórakoztató, mint
hogy néhány, a többi psets.

84
00:03:35,150 --> 00:03:37,974
És ez lesz hideg, és
mi lesz sok-sok móka.

85
00:03:37,974 --> 00:03:38,890
Majd több édességet.

86
00:03:38,890 --> 00:03:39,730
Elnézést a cukorkát.

87
00:03:39,730 --> 00:03:40,945
Elfelejtettem édességet.

88
00:03:40,945 --> 00:03:43,310
Ez volt egy durva reggel.

89
00:03:43,310 --> 00:03:46,340
Szóval ti majdnem ott,
és én nagyon büszke vagyok, srácok.

90
00:03:46,340 --> 00:03:49,570
>> OK, így halmozódik.

91
00:03:49,570 --> 00:03:53,331
Aki szerette a kérdés Jack
és a ruhája a kvízt?

92
00:03:53,331 --> 00:03:53,830
Senki?

93
00:03:53,830 --> 00:03:56,500
OK, ez rendben van.

94
00:03:56,500 --> 00:04:00,200
>> Tehát lényegében csak tudsz
Képet Jack, ez a fickó itt,

95
00:04:00,200 --> 00:04:03,350
szeret, hogy a ruházati
ki az a verem tetején,

96
00:04:03,350 --> 00:04:05,750
és ő hozza vissza rá
A verem után tett.

97
00:04:05,750 --> 00:04:07,600
Tehát ily módon, soha
Úgy tűnik, egyre

98
00:04:07,600 --> 00:04:10,090
hogy az alján a
verem a ruhája.

99
00:04:10,090 --> 00:04:12,600
Tehát ez a fajta leírja
Az alapadatok szerkezete

100
00:04:12,600 --> 00:04:16,610
hogyan verem megvalósítása.

101
00:04:16,610 --> 00:04:20,060
>> Lényegében, gondolom, egy
verem, mint bármely tárgyak halmaza

102
00:04:20,060 --> 00:04:24,900
hová tette a dolgokat rá a tetejére, és
akkor pop őket a tetején.

103
00:04:24,900 --> 00:04:28,600
Tehát LIFO a rövidítése szeretjük
hogy use-- utolsó, first out.

104
00:04:28,600 --> 00:04:32,480
És így is megmaradnak, hogy a tetején a
verem az első, hogy jön ki.

105
00:04:32,480 --> 00:04:34,260
És így a két fogalmat
szeretjük társítani

106
00:04:34,260 --> 00:04:36,190
azzal hívják Push és Pop.

107
00:04:36,190 --> 00:04:39,790
Ha megnyomja valamit rá a
verem, és akkor pop vissza.

108
00:04:39,790 --> 00:04:43,422
>> És így azt hiszem, ez a fajta egy
elvont fogalom azok számára,

109
00:04:43,422 --> 00:04:45,630
akik szeretnék látni, mint egy
tényleges végrehajtásának

110
00:04:45,630 --> 00:04:46,740
a valós világban.

111
00:04:46,740 --> 00:04:50,170
Hányan írtak esszét
Talán, mint egy órával korábban, hogy volt köszönhető,

112
00:04:50,170 --> 00:04:54,510
és véletlenül törölt egy hatalmas
darab ez, mint a véletlenül?

113
00:04:54,510 --> 00:04:58,560
És akkor mi vezérlő csinálni
használjuk, hogy tegye vissza?

114
00:04:58,560 --> 00:05:00,030
Control-V, igen?

115
00:05:00,030 --> 00:05:03,640
Ellenőrző-Z, így az összeg idők
Ennek az ellenőrző-Z megmentette az életemet,

116
00:05:03,640 --> 00:05:08,820
mentette meg a seggem, minden alkalommal
ami végre egy kéményen keresztül.

117
00:05:08,820 --> 00:05:13,020
>> Lényegében az összes információt
ez a Word dokumentumot,

118
00:05:13,020 --> 00:05:15,080
ez lesz tolta, és beugrott a fog.

119
00:05:15,080 --> 00:05:19,460
És így lényegében bármikor
töröl semmit, akkor pop vissza.

120
00:05:19,460 --> 00:05:22,820
És akkor, ha szükség van rá vissza, akkor
tolja, ami pedig a Control-C-nek.

121
00:05:22,820 --> 00:05:26,770
És így valós függvény
Az, hogy milyen egyszerű adatszerkezet

122
00:05:26,770 --> 00:05:28,690
segíthet a mindennapi életben.

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> Tehát egy struct az az út,
mi valójában létre egy verem.

125
00:05:40,150 --> 00:05:44,720
Mi írja meghatározzák struct, majd
hívjuk verem alján.

126
00:05:44,720 --> 00:05:47,440
És a verem,
van két paraméter

127
00:05:47,440 --> 00:05:51,580
hogy mi is lényegében manipulálni,
így van char csillagos húrok kapacitást.

128
00:05:51,580 --> 00:05:55,150
>> Minden, hogy csinál,
teremt egy tömböt

129
00:05:55,150 --> 00:05:58,835
hogy tudjuk tárolni, amit akarsz
ami meg tudjuk határozni a kapacitását.

130
00:05:58,835 --> 00:06:01,990
Kapacitás csak a max létszámú
tételek tudjuk helyezni ezt a tömböt.

131
00:06:01,990 --> 00:06:05,660
int mérete a számláló, ami megtartja
követni, hogy hány példány jelenleg

132
00:06:05,660 --> 00:06:07,850
a veremben.

133
00:06:07,850 --> 00:06:11,860
Tehát akkor mi is nyomon követni, A,
Mindkét mekkora a tényleges verem,

134
00:06:11,860 --> 00:06:14,850
és A, B, hogy mennyi az adott köteg
töltöttünk, mert nem akarjuk

135
00:06:14,850 --> 00:06:18,800
túlcsordulás alatt, amit a kapacitás.

136
00:06:18,800 --> 00:06:24,340
>> Így például, ez a szép
kérdés volt a kvíz.

137
00:06:24,340 --> 00:06:28,160
Lényegében hogyan is álljon
rá a tetejére egy halom.

138
00:06:28,160 --> 00:06:28,830
Elég egyszerű.

139
00:06:28,830 --> 00:06:30,621
Ha megnézzük azt,
megyünk végig ezt.

140
00:06:30,621 --> 00:06:32,640
Ha [hallhatatlan] size--
emlékszem, amikor

141
00:06:32,640 --> 00:06:35,300
szeretnénk hozzáférni
paraméter egy struct,

142
00:06:35,300 --> 00:06:40,320
te a neve a struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> Ebben az esetben, s értéke
a neve a mi verem.

144
00:06:42,720 --> 00:06:46,230
Azt szeretné elérni a méretet
belőle, így nem s.size.

145
00:06:46,230 --> 00:06:50,280
Tehát amíg a mérete nem
egyenlő kapacitással, vagy ameddig

146
00:06:50,280 --> 00:06:52,940
mivel ez kevesebb, mint a kapacitás,
sem lenne itt dolgozni.

147
00:06:52,940 --> 00:06:57,180
>> El szeretné érni a belső
a verem, így s.strings,

148
00:06:57,180 --> 00:07:00,790
és meg fogsz tenni, hogy az új számot
hogy akar szúrni ott.

149
00:07:00,790 --> 00:07:05,030
Mondjuk úgy, hogy mi lesz akar
helyezze int n a verembe,

150
00:07:05,030 --> 00:07:08,905
tudnánk tenni s.strings,
konzolok, s.size egyenlő n.

151
00:07:08,905 --> 00:07:11,030
Mivel a méret, ahol
Jelenleg a verem

152
00:07:11,030 --> 00:07:14,590
ha megyünk, hogy álljon
azt, mi csak hozzáférni

153
00:07:14,590 --> 00:07:17,370
bárhol a méret, a
aktuális teljessége a verem,

154
00:07:17,370 --> 00:07:21,729
és mi nyomja a int n rá.

155
00:07:21,729 --> 00:07:24,770
És akkor azt akarjuk, hogy győződjön meg arról, hogy
mi is megnő méret a N,

156
00:07:24,770 --> 00:07:27,436
így tudjuk nyomon követni voltunk
hozzáadott egy extra dolog, hogy a verem.

157
00:07:27,436 --> 00:07:29,660
Most van egy nagyobb méretű.

158
00:07:29,660 --> 00:07:33,196
Van ennek értelme itt
mindenki, hogyan logikusan működik?

159
00:07:33,196 --> 00:07:34,160
Ez kedves volt gyors.

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
Közönség: Tud megy át
A s.stringss.strings [s.size] újra?

162
00:07:42,160 --> 00:07:45,808
ANDI Peng: Persze, így mit jelent
s.size jelenleg nekünk?

163
00:07:45,808 --> 00:07:47,440
Közönség: Ez a jelenlegi méretét.

164
00:07:47,440 --> 00:07:50,890
ANDI Peng: Pontosan, tehát a
aktuális index, hogy mi nagysága lesz,

165
00:07:50,890 --> 00:07:57,780
és így akarjuk helyezni az új egész
hogy mi akar szúrni s.size.

166
00:07:57,780 --> 00:07:58,760
Ennek van értelme?

167
00:07:58,760 --> 00:08:01,110
Mert s.strings, minden,
ez a neve a tömbben.

168
00:08:01,110 --> 00:08:03,510
Minden ez a hozzáférés a
tömb a mi struct,

169
00:08:03,510 --> 00:08:06,030
és ezért ha azt akarjuk, hogy
helyezze n át az indexnek,

170
00:08:06,030 --> 00:08:09,651
mi csak hozzáférni
konzollal s.size.

171
00:08:09,651 --> 00:08:10,150
Hűvös.

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> Rendben, pop, én pszeudókód ki
srácok, de hasonló elgondolás.

174
00:08:18,916 --> 00:08:19,790
Ennek van értelme?

175
00:08:19,790 --> 00:08:22,310
Ha a méret nagyobb
nullánál, akkor

176
00:08:22,310 --> 00:08:25,350
tudom, hogy azt szeretné, hogy valamit
ki, mert ha a mérete nem

177
00:08:25,350 --> 00:08:27,620
nullánál nagyobb, akkor
Nincs semmi a veremben.

178
00:08:27,620 --> 00:08:29,840
>> Szóval csak azt akarom, hogy végre
ezt a kódot, akkor csak

179
00:08:29,840 --> 00:08:32,320
pop ha van valami, hogy a pop.

180
00:08:32,320 --> 00:08:35,830
Tehát, ha a méret nagyobb
mint 0, mi mínusz a méretét.

181
00:08:35,830 --> 00:08:40,020
Mi gyel csökkenti a méretet, majd visszatér
bármi belsejében van, mert

182
00:08:40,020 --> 00:08:42,710
popping, szeretnénk
hozzáférést bármilyen tárolják

183
00:08:42,710 --> 00:08:45,694
Az index a tetején a verem.

184
00:08:45,694 --> 00:08:46,610
Minden van értelme?

185
00:08:46,610 --> 00:08:49,693
Ha tettem srácok írom ezt ki,
kíván srácok tudják, írja le?

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
OK, maguk játszadozik vele.

188
00:08:53,570 --> 00:08:55,252
Nem gond, ha nem kap meg.

189
00:08:55,252 --> 00:08:57,460
Nincs ideje, hogy kódot
ki még ma, mert már

190
00:08:57,460 --> 00:08:59,959
Van egy csomó ilyen szerkezetek
hogy menjen át, de lényegében

191
00:08:59,959 --> 00:09:02,214
pszeudokódja, nagyon, nagyon hasonló, hogy álljon.

192
00:09:02,214 --> 00:09:03,380
Csak kövesse végig a logikát.

193
00:09:03,380 --> 00:09:06,092
Győződjön meg róla Ön által elérni az összes
funkciók a struktúra megfelelően.

194
00:09:06,092 --> 00:09:06,574
Igen?

195
00:09:06,574 --> 00:09:09,282
>> Közönség: Will ezeket a diákat és
ez az egész dolog akár ma-szerű?

196
00:09:09,282 --> 00:09:11,586
ANDI Peng: Mindig, aha.

197
00:09:11,586 --> 00:09:13,710
Megyek próbálja fel
ezt fel, mint egy óra után.

198
00:09:13,710 --> 00:09:16,626
Én e-mailt Davidnek, David megpróbálja
tedd fel, mint egy óra után.

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> OK, így aztán beköltözik a másik
szép adatstruktúra nevű sorban.

201
00:09:25,470 --> 00:09:30,140
Ahogy ti is látható, a
sorban, a brit köztünk,

202
00:09:30,140 --> 00:09:32,010
Mindenek előtt ez egy sort.

203
00:09:32,010 --> 00:09:34,680
Tehát ellentétben azzal, amit
Szerinted egy köteg,

204
00:09:34,680 --> 00:09:37,750
egy sort, hogy pontosan mit
logikusan úgy gondolja, hogy ez.

205
00:09:37,750 --> 00:09:41,914
Ez birtokában szabályai FIFO,
amely First In, First Out.

206
00:09:41,914 --> 00:09:43,705
Ha te vagy az első
egy a sorban, akkor

207
00:09:43,705 --> 00:09:46,230
Az első, hogy
jön ki a sor.

208
00:09:46,230 --> 00:09:49,680
>> Tehát mi szeretjük hívni ezt
A dequeueing és enqueueing.

209
00:09:49,680 --> 00:09:52,380
Ha azt akarjuk, hogy adjunk valamit
a mi sorban, mi sorba állítását.

210
00:09:52,380 --> 00:09:55,690
Ha azt akarjuk, hogy dequeue, vagy tegyen
valamit el, mi dequeue.

211
00:09:55,690 --> 00:10:03,350
>> Így ugyanabban az értelemben, hogy mi vagyunk a fajta
megteremtése fix méretű elemeket, hogy

212
00:10:03,350 --> 00:10:06,500
tárolhatja bizonyos
dolgok, de mi is

213
00:10:06,500 --> 00:10:10,100
megváltoztatni, ahol mi vagyunk forgalomba
paraméterek bennük

214
00:10:10,100 --> 00:10:13,140
alapján, hogy milyen típusú
funkcionalitást szeretnénk.

215
00:10:13,140 --> 00:10:16,700
Szóval halom, azt akartuk az utolsó
Egy, az N, hogy az első, aki ki.

216
00:10:16,700 --> 00:10:19,800
Várólista szeretnénk az első dolog,
be az első dolgot.

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> Így a struktúra-típus
meghatározni, mint látható,

219
00:10:26,710 --> 00:10:29,470
ez egy kicsit más
attól, amit a verem volt

220
00:10:29,470 --> 00:10:33,120
mert nem csak meg kell tartani
követni, ahol a méret jelenleg,

221
00:10:33,120 --> 00:10:37,420
mi is szeretnénk nyomon követni a fej
valamint, ahol jelenleg is.

222
00:10:37,420 --> 00:10:39,580
Tehát úgy gondolom, hogy könnyebb
ha rajzolok ezt fel.

223
00:10:39,580 --> 00:10:53,270
Szóval képzeljük el mi van egy sorban,
Mondjuk a feje itt van.

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
A fej a vonal, hadd
Csak azt mondják, hogy jelenleg,

226
00:10:58,310 --> 00:11:01,809
és szeretnénk beszúrni
valamit a sorba.

227
00:11:01,809 --> 00:11:04,350
Én fogom hívni mérete lényegében
ez ugyanaz, mint a farok,

228
00:11:04,350 --> 00:11:06,314
A végén, ahol a várólista van.

229
00:11:06,314 --> 00:11:07,730
Mondjuk úgy, hogy a méret itt.

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> Szóval hogyan lehet ténylegesen
helyezze valamit egy sorban?

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
Mit index akarunk helyezni
ahol szeretnénk szúrni.

234
00:11:24,130 --> 00:11:29,320
Ha ez az elején a
sorba, és ez a vége

235
00:11:29,320 --> 00:11:31,860
vagy a mérete is, ahol mi is
kívánja adni a következő objektumot?

236
00:11:31,860 --> 00:11:32,920
>> Közönség: [hallható]

237
00:11:32,920 --> 00:11:35,920
ANDI Peng: Pontosan, a felvenni kívánt
hogy attól függően írtál meg.

238
00:11:35,920 --> 00:11:37,840
Vagy ez üres, vagy, hogy üres.

239
00:11:37,840 --> 00:11:42,630
Tehát a felvenni kívánt valószínűleg
itt, mert ha a méret is--

240
00:11:42,630 --> 00:11:50,540
ha ezek teljesen tele van, azt szeretnénk,
hozzá, hogy jobb itt, ugye?

241
00:11:50,540 --> 00:11:57,150
>> És ez az, miközben nagyon, nagyon
egyszerű, nem egészen mindig helyes

242
00:11:57,150 --> 00:12:00,690
mert a fő különbség
között a sorba, és egy halom

243
00:12:00,690 --> 00:12:04,350
az, hogy a várólista is
valójában manipulálható

244
00:12:04,350 --> 00:12:06,980
úgy, hogy a fej változások
attól függően, hogy hol szeretné

245
00:12:06,980 --> 00:12:08,650
Az elején a végszó kezdeni.

246
00:12:08,650 --> 00:12:11,900
És ennek eredményeként, a farok
is fog változni.

247
00:12:11,900 --> 00:12:14,770
És így vessen egy pillantást
ezt a kódot most.

248
00:12:14,770 --> 00:12:18,620
Ahogy ti is megkérdezték, hogy
írjon ki a kvízt, Enqueue.

249
00:12:18,620 --> 00:12:22,580
Talán majd átbeszéljük, hogy miért
A válasz az volt, hogy mi az.

250
00:12:22,580 --> 00:12:26,790
>> Nem tudtam elég illik ez a vonal egyik,
de alapvetően ez a kódrészletet

251
00:12:26,790 --> 00:12:29,030
legyen egy sorban.

252
00:12:29,030 --> 00:12:30,140
Költeni, mint 30 másodperc.

253
00:12:30,140 --> 00:12:33,000
Vessen egy pillantást, és miért
ez a módja, hogy az.

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> Nagyon, nagyon hasonló struktúra, nagyon, nagyon
hasonló szerkezetű, mint az előző

256
00:12:55,420 --> 00:12:58,090
verem, kivéve talán
egy sor kód.

257
00:12:58,090 --> 00:13:01,190
És, hogy egy sor kód
meghatározza a funkcionalitást.

258
00:13:01,190 --> 00:13:03,900
És ez igazán megkülönbözteti
sorban kéményből.

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> Bárki, aki akar, hogy a stab
elmagyarázása, miért voltál

261
00:13:22,010 --> 00:13:24,980
Van ez a bonyolult dolog itt?

262
00:13:24,980 --> 00:13:27,845
Látjuk a visszatérés a mi
csodálatos barátom modulus.

263
00:13:27,845 --> 00:13:31,020
Mivel a srácok hamarosan
felismerni a programozásban,

264
00:13:31,020 --> 00:13:34,910
szinte bármikor szükséged van valamire
tekerje körül semmit,

265
00:13:34,910 --> 00:13:36,850
modulus lesz a módja annak, hogy csináld.

266
00:13:36,850 --> 00:13:40,510
Így tudta, hogy nem akarna bárki is
kipróbálni kifejtve, hogy a kódsort?

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
Igen, minden a válaszok
elfogadott és üdvözlendő.

269
00:13:47,507 --> 00:13:48,840
Közönség: Te beszélsz velem?

270
00:13:48,840 --> 00:13:49,506
ANDI Peng: Igen.

271
00:13:49,506 --> 00:13:56,200
Közönség: Ó, nem sajnálom.

272
00:13:56,200 --> 00:14:00,250
ANDI Peng: OK, úgyhogy
séta ezt a kódot.

273
00:14:00,250 --> 00:14:03,642
Tehát, ha akarsz
adjunk valamit rá egy sorban,

274
00:14:03,642 --> 00:14:08,510
a gyönyörű esetben, ha a fej történik
hogy igaza van, akkor nagyon könnyű számunkra

275
00:14:08,510 --> 00:14:10,960
hogy csak megy a végére
helyezze valamit, nem?

276
00:14:10,960 --> 00:14:14,690
De a lényeg az egy sort
hogy a fej ténylegesen dinamikusan

277
00:14:14,690 --> 00:14:17,280
változhat attól függően, hol vagyunk
szeretné, hogy a kezdete a q lenni,

278
00:14:17,280 --> 00:14:19,880
és mint ilyen, a farok
is fog változni.

279
00:14:19,880 --> 00:14:31,100
>> És így elképzelhető, hogy nem ez volt a
sorba, hanem ez volt a sorban.

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
Mondjuk a feje itt van.

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
Mondjuk mi sorban így nézett ki.

284
00:14:56,980 --> 00:15:00,190
Ha akarnánk váltani, ahol
az elején a vonal,

285
00:15:00,190 --> 00:15:03,400
mondjuk toltuk vezetője
Ily módon és méretben itt.

286
00:15:03,400 --> 00:15:07,100
>> Most szeretnénk adni valamit
ez a sorban, de ahogy ti is látni,

287
00:15:07,100 --> 00:15:11,150
ez nem olyan egyszerű, mint, hogy csak
hozzá, amit az a méret után

288
00:15:11,150 --> 00:15:13,630
mert akkor elfogy a
határait a tényleges tömb.

289
00:15:13,630 --> 00:15:16,190
Ahol szeretnénk igazán hozzá van itt.

290
00:15:16,190 --> 00:15:18,610
Ez a szépség egy sorban
az, hogy nekünk, vizuálisan is

291
00:15:18,610 --> 00:15:22,380
néz ki, mint a vonal megy, mint ez,
de amikor tárolt adatszerkezetet,

292
00:15:22,380 --> 00:15:29,370
Adnak, hogy úgy, mint egy ciklus.

293
00:15:29,370 --> 00:15:32,360
Ez a fajta körbe
az elülső ugyanúgy

294
00:15:32,360 --> 00:15:34,780
hogy egy sort is csomagolja
körül függően bárhova is

295
00:15:34,780 --> 00:15:36,279
szeretné a sor elején kell lennie.

296
00:15:36,279 --> 00:15:38,630
És így ha veszünk egy
nézz le ide, hadd

297
00:15:38,630 --> 00:15:40,880
mondjuk akart létrehozni
nevezett funkció Enqueue.

298
00:15:40,880 --> 00:15:43,980
Azt akartuk, hogy adjunk int n át, hogy q.

299
00:15:43,980 --> 00:15:49,250
Ha q.size q-- fogjuk hívni, hogy adatainkat
structure-- ha a mi queue.size nem

300
00:15:49,250 --> 00:15:52,520
egyenlő kapacitása, vagy ha
ez kevesebb, mint a kapacitás,

301
00:15:52,520 --> 00:15:55,120
q.strings a tömb a mi q.

302
00:15:55,120 --> 00:15:58,380
Fogunk beállítani
hogy egyenlő q.heads,

303
00:15:58,380 --> 00:16:02,730
ami itt van, plusz q.size
modulus a kapacitást, amely

304
00:16:02,730 --> 00:16:04,290
csavarja vissza minket errefelé.

305
00:16:04,290 --> 00:16:08,040
>> Tehát ebben a példában, index
A fej 1, ugye?

306
00:16:08,040 --> 00:16:11,480
Az index a mérete 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Így nem tehetünk 1 plusz 4 modulusa
az a képességünk, amely 5.

308
00:16:19,500 --> 00:16:20,920
Mit jelent, hogy adjon nekünk?

309
00:16:20,920 --> 00:16:23,270
Mi az index, hogy
jön ki ez?

310
00:16:23,270 --> 00:16:24,080
>> Közönség: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI Peng: 0, ami
előfordul, hogy éppen itt,

312
00:16:27,870 --> 00:16:30,640
és ezért szeretnénk, hogy képes
beilleszteni itt.

313
00:16:30,640 --> 00:16:34,730
És így ez az egyenlet itt fajta
csak működik minden szám

314
00:16:34,730 --> 00:16:36,750
attól függően, hol
fej és a mérete is.

315
00:16:36,750 --> 00:16:38,541
Ha tudod, hogy mik azok
dolgok, tudod,

316
00:16:38,541 --> 00:16:43,170
pontosan ott, ahol be szeretné szúrni
bármit, ami után a sorban.

317
00:16:43,170 --> 00:16:44,640
Van ennek értelme mindenki?

318
00:16:44,640 --> 00:16:48,560
>> Tudom, milyen az agy
teaser különösen azért, mert ez a

319
00:16:48,560 --> 00:16:50,512
jött a utóhatásaként a kvíz.

320
00:16:50,512 --> 00:16:52,220
De remélhetőleg mindenki
Most megértem

321
00:16:52,220 --> 00:16:57,800
Ezért ez a megoldás, vagy ezt
funkció a módon, hogy az.

322
00:16:57,800 --> 00:16:59,840
Bárki egy kicsit nem világos, hogy?

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
OKÉ.

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> És így most, ha
akarta dequeue, ennek

327
00:17:09,970 --> 00:17:15,240
van, ahol a fej lenne váltás
mert ha voltunk dequeue,

328
00:17:15,240 --> 00:17:17,030
nem vesszük le a végén a q.

329
00:17:17,030 --> 00:17:19,130
Azt akarjuk, hogy vegye le a fejét, nem igaz?

330
00:17:19,130 --> 00:17:24,260
Tehát ennek eredményeként, a fej nem fogja megváltoztatni,
és ezért, ha sorba állítását,

331
00:17:24,260 --> 00:17:26,800
neked kell nyomon követni
ahol a fej és a méretet

332
00:17:26,800 --> 00:17:29,450
vannak, hogy képes legyen beszúrni
a megfelelő helyzetbe.

333
00:17:29,450 --> 00:17:32,740
>> És így ha dequeue,
Én is pszeudókód ki.

334
00:17:32,740 --> 00:17:35,480
Nyugodtan ha azt szeretné,
hogy megpróbálja kódolási ezt.

335
00:17:35,480 --> 00:17:36,980
Azt akarod, hogy mozog a feje, igaz?

336
00:17:36,980 --> 00:17:39,320
Ha akartam dequeue, én
mozgatja feje fölött.

337
00:17:39,320 --> 00:17:40,800
Ez lenne a fejét.

338
00:17:40,800 --> 00:17:45,617
>> És a jelenlegi méret lenne
kivonni, mert mi már nem

339
00:17:45,617 --> 00:17:46,950
Van négy elem a tömbben.

340
00:17:46,950 --> 00:17:51,370
Már csak három, majd azt akarjuk,
vissza bármi is volt tárolt

341
00:17:51,370 --> 00:17:56,260
A fej, mert azt akarjuk, hogy ezt
érték el, így nagyon hasonlít a verem.

342
00:17:56,260 --> 00:17:58,010
Csak szedi
egy másik helyre,

343
00:17:58,010 --> 00:18:01,770
és van, hogy hozzárendelése mutatót
a másik helyen eredményeként.

344
00:18:01,770 --> 00:18:03,890
Logikusan, mindenki követni?

345
00:18:03,890 --> 00:18:05,690
Nagy.

346
00:18:05,690 --> 00:18:10,156
>> OK, így fogunk beszélni egy kicsit
mélyebben mintegy láncolt listák

347
00:18:10,156 --> 00:18:13,280
mert akkor nagyon, nagyon értékes
Önnek során e heti

348
00:18:13,280 --> 00:18:14,964
psets.

349
00:18:14,964 --> 00:18:17,130
Láncolt listák, ahogy a srácok
emlékszem, ezek csak

350
00:18:17,130 --> 00:18:22,570
a csomópontok, amelyek csomópontok bizonyos
értékei mindkét érték és mutatóját

351
00:18:22,570 --> 00:18:26,290
hogy egymáshoz kapcsolódnak
azok a mutatók.

352
00:18:26,290 --> 00:18:29,880
És így a struktúra hogyan
létrehozunk egy node itt vagyunk

353
00:18:29,880 --> 00:18:33,569
van int n, amely bármilyen
Az érték egy üzletben vagy string n

354
00:18:33,569 --> 00:18:35,610
vagy amit akarsz
nevezni, a char csillagos n.

355
00:18:35,610 --> 00:18:41,482
Struct csomópont csillag, amely a mutató
hogy azt szeretné, hogy az egyes csomópontok,

356
00:18:41,482 --> 00:18:43,690
fogsz is, hogy a
pointer pont felé jövő.

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
Itt van a feje
Egy hivatkozott lista, amelyet

359
00:18:50,040 --> 00:18:53,140
fog mutatni a többi
az értékeket így tovább és így tovább

360
00:18:53,140 --> 00:18:55,290
amíg meg végül elérjük a végét.

361
00:18:55,290 --> 00:18:58,040
És ez az utolsó csomópont csak
megy, hogy nem egy mutatót.

362
00:18:58,040 --> 00:18:59,952
Meg fog mutatni
null, és ez az, amikor

363
00:18:59,952 --> 00:19:01,910
tudod, hogy elérje a
végén a láncolt lista

364
00:19:01,910 --> 00:19:04,076
az, amikor az utolsó mutatót
nem mutat sehova.

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> Így fogunk menni egy kicsit többet
mélysége tekintetében hogyan feltehetően

367
00:19:10,990 --> 00:19:12,400
Keressen egy láncolt lista.

368
00:19:12,400 --> 00:19:15,460
Ne feledje, mik a
Hátránya az láncolt listák

369
00:19:15,460 --> 00:19:19,340
verseket tömb kapcsolatos keresések.

370
00:19:19,340 --> 00:19:22,565
Egy tömb tudsz bináris keresés, de
miért nem tudsz csinálni, hogy egy láncolt lista?

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> Közönség: Mert ők az összes csatlakoztatott,
de nem igazán tudom, hol

373
00:19:30,320 --> 00:19:31,330
[NEM HALLHATÓ].

374
00:19:31,330 --> 00:19:34,600
>> ANDI Peng: Igen, pontosan úgy emlékszem,
hogy a fényessége tömb

375
00:19:34,600 --> 00:19:37,190
volt az a tény, hogy mi volt
véletlen hozzáférésű memória, ahol

376
00:19:37,190 --> 00:19:41,580
ha akartam az érték indexe
hat, tudtam csak mondani index hat,

377
00:19:41,580 --> 00:19:42,407
adj ez az érték.

378
00:19:42,407 --> 00:19:45,240
És ez azért van, mert tömbök vannak sorolva,
egy összefüggő tér memória

379
00:19:45,240 --> 00:19:48,020
egy helyen, míg
fajta láncolt listák

380
00:19:48,020 --> 00:19:52,820
a véletlenszerűen tarkított körül,
és az egyetlen módja van az ország egyik

381
00:19:52,820 --> 00:19:56,890
van egy mutatót, amely megmondja,
A címe, ha ez a következő csomópont.

382
00:19:56,890 --> 00:20:00,290
>> És így ennek eredményeként, az egyetlen módja
keresgélni egy láncolt lista

383
00:20:00,290 --> 00:20:01,560
lineáris keresést.

384
00:20:01,560 --> 00:20:05,890
Mert én nem tudom pontosan, hol
A 12. értéke a kapcsolódó lista,

385
00:20:05,890 --> 00:20:08,780
Én áthalad a teljes
e kapcsolt lista egyik

386
00:20:08,780 --> 00:20:12,450
egy a fejét az első csomóponthoz,
a második csomóponthoz, hogy a harmadik csomópont,

387
00:20:12,450 --> 00:20:17,690
egészen addig, amíg végül kap
hogy ha ez a csomópont keresem az.

388
00:20:17,690 --> 00:20:22,110
És így ebben az értelemben, keresés
egy láncolt lista mindig n.

389
00:20:22,110 --> 00:20:23,040
Mindig n.

390
00:20:23,040 --> 00:20:25,690
Ez mindig lineáris időben.

391
00:20:25,690 --> 00:20:28,470
>> Ezért a kód, amelyben
mi végre ezt, és ezt a

392
00:20:28,470 --> 00:20:32,620
egy kicsit az új srácok, mióta
srácok még nem igazán beszéltünk, vagy soha

393
00:20:32,620 --> 00:20:35,000
láttam a mutatókat, hogy hogyan
keresgélni mutatók,

394
00:20:35,000 --> 00:20:37,670
így megyünk végig
ez nagyon, nagyon lassan.

395
00:20:37,670 --> 00:20:40,200
Szóval bool kereső, igaz,
képzeljük el akarunk

396
00:20:40,200 --> 00:20:42,820
hogy hozzon létre olyan függvény is
kereső, amely igazat ad vissza

397
00:20:42,820 --> 00:20:46,820
Ha találtál egy értéket belül a kapcsolt
listára, és hamis értékkel tér vissza másként.

398
00:20:46,820 --> 00:20:50,030
Node csillagos lista
Jelenleg csak a mutató

399
00:20:50,030 --> 00:20:52,960
Az első elem a láncolt lista.

400
00:20:52,960 --> 00:20:56,700
int n az az érték, hogy te
keresnek fel a listára.

401
00:20:56,700 --> 00:20:58,770
>> Tehát csomópont csillagos mutató értéke listát.

402
00:20:58,770 --> 00:21:00,970
Ez azt jelenti, hogy az aktuális állítást
és megteremti a mutatót

403
00:21:00,970 --> 00:21:03,592
ebben az első csomópont belsejében a lista.

404
00:21:03,592 --> 00:21:04,300
Mindenki velem?

405
00:21:04,300 --> 00:21:06,530
Tehát, ha mennénk
vissza ide, szerettem volna

406
00:21:06,530 --> 00:21:13,850
inicializált egy mutatót, amely arra utal, hogy
a feje, amit ez a lista.

407
00:21:13,850 --> 00:21:18,600
>> És majd ha egyszer gyere le,
míg a mutató nem egyenlő null,

408
00:21:18,600 --> 00:21:22,160
úgy, hogy az a hurok, amelyben vagyunk
lesz a későbbiekben áthaladó

409
00:21:22,160 --> 00:21:25,940
A többi a mi lista, mert mi
történik, amikor a mutató értéke null?

410
00:21:25,940 --> 00:21:27,550
Tudjuk, hogy have--

411
00:21:27,550 --> 00:21:28,450
>> Közönség: [hallható]

412
00:21:28,450 --> 00:21:31,491
>> ANDI Peng: Pontosan, tehát tudjuk, hogy
elértük a lista végére, ugye?

413
00:21:31,491 --> 00:21:34,470
Ha megy vissza, minden csomópont
kell néznie egy másik csomópont

414
00:21:34,470 --> 00:21:36,550
és így tovább, és így tovább
amíg eléred végül

415
00:21:36,550 --> 00:21:41,589
A farok a láncolt lista,
amely egy mutatót, hogy csak

416
00:21:41,589 --> 00:21:43,130
nem pont máshol, mint nem.

417
00:21:43,130 --> 00:21:47,510
És így alapvetően tudjuk, hogy
A lista még mindig ott fel

418
00:21:47,510 --> 00:21:50,900
amíg a mutató nem egyenlő
null, mert ha egyszer eléri null,

419
00:21:50,900 --> 00:21:53,310
Tudja, hogy nincs több cuccot.

420
00:21:53,310 --> 00:21:56,930
>> Tehát ez a hurok, amelyben vagyunk
megy, hogy a tényleges keresést.

421
00:21:56,930 --> 00:22:01,690
És ha a pointer-- látod
ez a fajta nyíl funkciója van?

422
00:22:01,690 --> 00:22:06,930
Tehát, ha mutató n, ha
A mutató a n összege egyenlő n,

423
00:22:06,930 --> 00:22:09,180
így ez azt jelenti, hogy ha
A mutató, hogy te

424
00:22:09,180 --> 00:22:13,420
keresi a végén minden
csomópont valójában értékével egyenlő

425
00:22:13,420 --> 00:22:15,990
keres, akkor
vissza akar térni igaz.

426
00:22:15,990 --> 00:22:19,280
Tehát alapvetően, ha egy csomópont,
az értéke, amit keres,

427
00:22:19,280 --> 00:22:23,550
tudod, hogy te voltál
Sikeresen keresni.

428
00:22:23,550 --> 00:22:27,150
>> Ellenkező esetben, ha szeretné beállítani
A mutató a következő csomópontot.

429
00:22:27,150 --> 00:22:28,850
Ez az, amit a vonal itt csinál.

430
00:22:28,850 --> 00:22:31,750
Pointer egyenlő melletti mutatóra.

431
00:22:31,750 --> 00:22:33,360
Mindenki látni, hogy hogyan működik?

432
00:22:33,360 --> 00:22:36,580
>> És lényegében fogsz most
áthalad a teljes a lista,

433
00:22:36,580 --> 00:22:41,920
újraindítani a mutatót minden alkalommal, amíg
akkor végül csúnyán a lista végén.

434
00:22:41,920 --> 00:22:45,030
És tudod, hogy nincs
több csomópont keresgélni,

435
00:22:45,030 --> 00:22:47,999
és akkor return false
mert tudja, hogy, jaj, nos,

436
00:22:47,999 --> 00:22:50,540
Ha képes voltam keresni
keresztül a teljes egészében a lista.

437
00:22:50,540 --> 00:22:54,530
Ha ebben a példában, ha akarnám
hogy keresse meg a 10-es érték,

438
00:22:54,530 --> 00:22:57,250
és elkezdem a fejét, és
Én keresni egészen,

439
00:22:57,250 --> 00:23:00,550
és én végül kapott erre, ami
egy mutatót, amely arra utal, hogy null,

440
00:23:00,550 --> 00:23:04,415
Tudom, hogy szar, azt hiszem, 10 nem
ez a lista, mert nem tudtam megtalálni.

441
00:23:04,415 --> 00:23:06,520
És én vagyok az a lista végén.

442
00:23:06,520 --> 00:23:11,040
És ebben az esetben tudja
Megyek vissza hamis.

443
00:23:11,040 --> 00:23:12,900
>> Legyen ez hatni egy kicsit.

444
00:23:12,900 --> 00:23:17,350
Ez lesz elég
fontos a PSET.

445
00:23:17,350 --> 00:23:21,140
A logika nagyon egyszerű, talán
mondattanilag csak végrehajtásában.

446
00:23:21,140 --> 00:23:23,365
Kértek, hogy
arról, hogy érti.

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
Hűvös.

449
00:23:27,650 --> 00:23:32,560
>> OK, akkor hogyan lennénk
behelyezése csomópontok, igaz,

450
00:23:32,560 --> 00:23:35,380
egy listát, mert emlékszem
mi a mi a haszon

451
00:23:35,380 --> 00:23:39,230
Az rendelkező kapcsolt lista versus
tömb a tárolás szempontjából?

452
00:23:39,230 --> 00:23:41,110
>> Közönség: Ez a dinamikus,
így könnyebb az alábbiakra:

453
00:23:41,110 --> 00:23:43,180
>> ANDI Peng: Pontosan,
így ez a dinamikus, amelyek

454
00:23:43,180 --> 00:23:46,880
azt jelenti, hogy bővítse és összezsugorodik
attól függően, hogy a felhasználó igényeinek.

455
00:23:46,880 --> 00:23:56,570
És így, ebben az értelemben, hogy nem kell
pazarolni felesleges emlék, mert

456
00:23:56,570 --> 00:24:00,850
ha nem tudom, hány érték akarok
a boltba, akkor nincs értelme számomra

457
00:24:00,850 --> 00:24:04,310
hogy hozzon létre egy tömböt, mert
ha azt akarom, hogy tárolja 10 értékek

458
00:24:04,310 --> 00:24:08,380
és én létrehozunk egy tömböt 1000, ez
a sok elvesztegetett memória, kiosztott.

459
00:24:08,380 --> 00:24:11,180
Ezért szeretnénk, ha készítesz egy
lista, hogy képes legyen a dinamikusan

460
00:24:11,180 --> 00:24:13,860
megváltoztatni, vagy csökken a mérete.

461
00:24:13,860 --> 00:24:17,040
>> És így teszi beillesztés
egy kicsit bonyolultabb.

462
00:24:17,040 --> 00:24:20,810
Mivel nem tudjuk véletlenszerűen hozzáférés elemei
az is, hogy mi lenne a tömb.

463
00:24:20,810 --> 00:24:24,270
Ha azt szeretnénk, hogy helyezzen be egy elemet
a hetedik index,

464
00:24:24,270 --> 00:24:26,930
Egyszerűen helyezze
a hetedik index.

465
00:24:26,930 --> 00:24:30,020
Egy láncolt lista, ez nem
egészen működik olyan könnyen,

466
00:24:30,020 --> 00:24:34,947
és így ha azt akartuk, hogy helyezze
Az egyik itt, a láncolt lista,

467
00:24:34,947 --> 00:24:36,280
vizuálisan, ez nagyon könnyen látható.

468
00:24:36,280 --> 00:24:39,363
Csak azt akarjuk, hogy helyezze ott,
jobb elején a listán,

469
00:24:39,363 --> 00:24:40,840
után a fejét.

470
00:24:40,840 --> 00:24:44,579
>> De milyen módon van átminősítése
A mutatók egy kicsit nyakatekert

471
00:24:44,579 --> 00:24:47,620
vagy, logikusan, akkor van értelme, de
azt szeretnénk, hogy győződjön meg arról, hogy van ez

472
00:24:47,620 --> 00:24:50,250
Teljesen le, mert
Az utolsó dolog, amit szeretnénk,

473
00:24:50,250 --> 00:24:52,990
az, hogy hozzárendelése egy mutatót a
hogy itt csinálunk.

474
00:24:52,990 --> 00:24:58,170
Ha dereference a
pointer tetőtől 1,

475
00:24:58,170 --> 00:25:01,086
majd hirtelen a
többi a láncolt lista

476
00:25:01,086 --> 00:25:04,680
elvész, mert mi még nem próbáltuk
létrehozott egy ideiglenes semmit.

477
00:25:04,680 --> 00:25:06,220
Ez az, rámutatott, hogy a 2.

478
00:25:06,220 --> 00:25:10,080
Ha hozzárendeli a mutatót, majd a
többi a lista teljesen elveszett.

479
00:25:10,080 --> 00:25:13,310
Szóval azt szeretné, hogy
Nagyon, nagyon vigyáznunk

480
00:25:13,310 --> 00:25:17,010
az első rendelheti
pointer, amit

481
00:25:17,010 --> 00:25:20,150
akar szúrni bárhova
akarsz, és akkor

482
00:25:20,150 --> 00:25:22,710
lehet követéssel, a többi a lista.

483
00:25:22,710 --> 00:25:25,250
>> Tehát ez vonatkozik bárhova
akarsz szúrni.

484
00:25:25,250 --> 00:25:27,520
Ha azt szeretnénk, hogy helyezze át a
fejét, ha azt szeretné, hogy válaszoljon itt,

485
00:25:27,520 --> 00:25:29,455
Ha azt szeretnénk, hogy helyezze át
A végén, nos, a végén én

486
00:25:29,455 --> 00:25:30,910
hiszem, akkor csak
nincs mutató, de

487
00:25:30,910 --> 00:25:33,830
szeretnénk, hogy győződjön meg arról, hogy nem
elveszíti a többi a lista.

488
00:25:33,830 --> 00:25:36,640
Mindig akarja, hogy megbizonyosodjon arról
Az új csomópont mutat

489
00:25:36,640 --> 00:25:39,330
felé, amit
akar szúrni,

490
00:25:39,330 --> 00:25:42,170
majd felveheti a láncolás tovább.

491
00:25:42,170 --> 00:25:43,330
Mindenki tiszta?

492
00:25:43,330 --> 00:25:45,427
>> Ez lesz
az egyik az igazi kérdés.

493
00:25:45,427 --> 00:25:48,010
Az egyik legfontosabb kérdések
fogsz van a PSET

494
00:25:48,010 --> 00:25:51,340
az, hogy meg fogsz megpróbál létrehozni
A láncolt lista és betét dolgokat

495
00:25:51,340 --> 00:25:53,340
de aztán csak elveszti az
többi a láncolt lista.

496
00:25:53,340 --> 00:25:54,900
És te leszel, mint én
Nem tudom, miért történik mindez?

497
00:25:54,900 --> 00:25:58,040
És ez a fájdalom, hogy menjen át
és keresni az összes mutató.

498
00:25:58,040 --> 00:26:02,100
>> És garantálom, hogy ezen PSET,
írás és rajz ezek a csomópontok ki

499
00:26:02,100 --> 00:26:03,344
lesz nagyon, nagyon hasznos.

500
00:26:03,344 --> 00:26:06,010
Szóval akkor teljesen nyomon követni
Az, ahol minden a pointerek,

501
00:26:06,010 --> 00:26:08,540
mi baj,
ahol minden csomópont,

502
00:26:08,540 --> 00:26:12,660
mit kell tennie, hogy elérje vagy
beszúrni vagy törölni, vagy ezek közül bármelyik.

503
00:26:12,660 --> 00:26:14,550
Mindenki jó ebben?

504
00:26:14,550 --> 00:26:15,050
Hűvös.

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> Tehát ha azt akartuk, hogy nézd meg a kódot?

507
00:26:22,600 --> 00:26:24,470
Ó, nem tudom, ha
Láthatjuk the-- OK, így

508
00:26:24,470 --> 00:26:27,940
a tetején is ez egy olyan funkció,
elemzi betét, ahol szeretnénk

509
00:26:27,940 --> 00:26:31,365
beszúrni int n a láncolt lista.

510
00:26:31,365 --> 00:26:32,740
Fogunk séta ezt.

511
00:26:32,740 --> 00:26:34,770
Ez egy csomó kódot, sok új szintaxis.

512
00:26:34,770 --> 00:26:36,220
Mi minden rendben lesz.

513
00:26:36,220 --> 00:26:39,120
>> Szóval fel a tetején, amikor
akarunk létrehozni semmit

514
00:26:39,120 --> 00:26:42,380
Mit kell tennünk, különösen akkor, ha
akarjuk, hogy ne a veremben tárolt

515
00:26:42,380 --> 00:26:43,920
de a kupac?

516
00:26:43,920 --> 00:26:45,460
Elmegyünk egy malloc, ugye?

517
00:26:45,460 --> 00:26:48,240
Mi is így fogjuk létrehozni egy mutató.

518
00:26:48,240 --> 00:26:52,074
Node, mutató, új egyenlők
malloc a mérete egy csomópont

519
00:26:52,074 --> 00:26:53,740
mert azt szeretnénk, hogy létrehozandó csomóponttal.

520
00:26:53,740 --> 00:26:56,720
Szeretnénk, ha az összeg
memória hogy egy csomópont vesz fel

521
00:26:56,720 --> 00:26:59,300
felosztható a
létrehozására az új csomópont.

522
00:26:59,300 --> 00:27:02,270
>> És akkor mi lesz, hogy ellenőrizze, hogy
hátha új egyenlők egyenlő null.

523
00:27:02,270 --> 00:27:03,370
Emlékszel, mit mondtunk?

524
00:27:03,370 --> 00:27:06,470
Bármit malloc,
Mit kell mindig csinálni?

525
00:27:06,470 --> 00:27:09,490
Mindig ellenőrizni kell, hogy
e vagy sem, hogy null.

526
00:27:09,490 --> 00:27:13,620
>> Például, ha az operációs
rendszer teljesen megtelt,

527
00:27:13,620 --> 00:27:17,060
ha nem volt több memóriát
minden, és megpróbálja malloc,

528
00:27:17,060 --> 00:27:18,410
lenne visszatérni null az Ön számára.

529
00:27:18,410 --> 00:27:21,094
És így ha megpróbál használni
amikor mutató null,

530
00:27:21,094 --> 00:27:23,260
ugye nem fog tudni
hozzáférni az információkhoz.

531
00:27:23,260 --> 00:27:27,010
És így mint ilyen, azt akarta, hogy
arról, hogy ha te mallocing,

532
00:27:27,010 --> 00:27:30,500
te mindig ellenőrzi, hogy ha
hogy a memória adott neked null.

533
00:27:30,500 --> 00:27:33,670
És ha nem, akkor meg tudjuk mozgatni
tovább a többi a mi kódot.

534
00:27:33,670 --> 00:27:36,140
>> Szóval megyünk
inicializálja az új csomópont.

535
00:27:36,140 --> 00:27:39,050
Fogunk csinálni új n összege n.

536
00:27:39,050 --> 00:27:42,390
És akkor fogunk csinálni
meg az új a mutatót az új

537
00:27:42,390 --> 00:27:46,900
null, mert most nem tesszük
akar semmit érte, hogy pont.

538
00:27:46,900 --> 00:27:48,755
Fogalmunk sincs, hol
ez fog téged,

539
00:27:48,755 --> 00:27:50,630
majd ha azt akarjuk, hogy
illessze be a fejét,

540
00:27:50,630 --> 00:27:53,820
akkor tudjuk hozzárendelése
A mutatót a fejét.

541
00:27:53,820 --> 00:27:58,530
Mindenkinek logikáját követik
hol, ami történik?

542
00:27:58,530 --> 00:28:02,502
>> Minden csinálunk teremt egy új
csomópont, amelyben a mutató értéke NULL,

543
00:28:02,502 --> 00:28:04,210
majd átcsoportosítása
azt, hogy a fej, ha

544
00:28:04,210 --> 00:28:06,320
tudni akarjuk illessze be a fejét.

545
00:28:06,320 --> 00:28:09,420
És akkor a fej fog
pont felé, hogy az új csomópont.

546
00:28:09,420 --> 00:28:11,060
Mindenki rendben van ezzel?

547
00:28:11,060 --> 00:28:12,380
>> Tehát ez egy kétlépcsős folyamat.

548
00:28:12,380 --> 00:28:14,760
Megvan az első hozzárendelése
Bármit létre.

549
00:28:14,760 --> 00:28:18,260
Állítsa hogy a mutató a
hivatkozás, és akkor

550
00:28:18,260 --> 00:28:21,400
lehet ilyen hivatkozás feloldási
Az első mutató

551
00:28:21,400 --> 00:28:22,972
és pont ez iránt az új csomópont.

552
00:28:22,972 --> 00:28:25,680
Ahol szeretné, hogy helyezze,
E logika fog tartani igaz.

553
00:28:25,680 --> 00:28:27,530
>> Ez olyan, mint hozzárendelése
ideiglenes változók.

554
00:28:27,530 --> 00:28:28,700
Ne feledje, ha már van
hogy megbizonyosodjon arról, hogy

555
00:28:28,700 --> 00:28:30,346
Nem veszítjük el, ha csere.

556
00:28:30,346 --> 00:28:33,470
Azt akarod, hogy megbizonyosodjon arról, hogy van egy
ideiglenes változó, hogy milyen tart

557
00:28:33,470 --> 00:28:35,620
követni, ahol a dolog
van tárolva úgy, hogy

558
00:28:35,620 --> 00:28:41,190
ne vesszenek el érték során
hasonló szórakozni vele.

559
00:28:41,190 --> 00:28:42,710
>> OK, így kódot itt lesz.

560
00:28:42,710 --> 00:28:45,020
Srácok, nézzen szakasz után.

561
00:28:45,020 --> 00:28:48,060
Ott lesz.

562
00:28:48,060 --> 00:28:50,280
>> Szóval azt hiszem, hogyan működik
ez különböznek ha akarnánk

563
00:28:50,280 --> 00:28:52,300
szúrni a közepén vagy végén?

564
00:28:52,300 --> 00:28:57,892
Van valakinek ötlete, hogy mi a
pszeudokódja, mint a logikai referencia

565
00:28:57,892 --> 00:29:00,350
hogy mi lenne, hogy ha akarnánk
hogy helyezze a közepén?

566
00:29:00,350 --> 00:29:03,391
Tehát ha azt akartuk, hogy illessze be a
fejét, csak annyit teszünk, hozzon létre egy új csomópontot.

567
00:29:03,391 --> 00:29:06,311
Mi meg a mutatót az, hogy
új csomópont bármilyen fejét,

568
00:29:06,311 --> 00:29:08,310
majd elindultunk a fejét
Az új csomópont, ugye?

569
00:29:08,310 --> 00:29:11,560
Ha akartuk, hogy helyezze a közepén
A lista, hogy mi kell tennünk?

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> Közönség: ez még mindig
lehet egy hasonló folyamat

572
00:29:16,110 --> 00:29:19,114
A oszt ki például a mutató és a
ezt rendelve, hogy a mutató,

573
00:29:19,114 --> 00:29:20,530
de mi lett volna, hogy keresse meg ott.

574
00:29:20,530 --> 00:29:23,560
>> ANDI Peng: Pontosan, tehát pontosan
ugyanez a folyamat csak akkor

575
00:29:23,560 --> 00:29:27,820
hogy keresse meg, pontosan hogy
szeretnénk, hogy az új mutató bemenni,

576
00:29:27,820 --> 00:29:44,790
így ha akar szúrni
közepén kapcsolódik list-- OK,

577
00:29:44,790 --> 00:29:46,370
Tegyük fel, hogy a mi láncolt lista.

578
00:29:46,370 --> 00:29:49,500
Ha azt akarjuk, hogy beillessze azt itt,
fogunk létrehozni egy új csomópontot.

579
00:29:49,500 --> 00:29:50,520
Megyünk malloc.

580
00:29:50,520 --> 00:29:52,220
Megyünk, hogy hozzon létre egy új csomópont.

581
00:29:52,220 --> 00:29:55,940
Megyünk rendelheti
pointer e csomópont van.

582
00:29:55,940 --> 00:29:58,335
>> De a probléma, amely különbözik
ahonnan a fej

583
00:29:58,335 --> 00:30:00,490
az, hogy pontosan tudtuk,
ahol a fej.

584
00:30:00,490 --> 00:30:01,930
Helyes volt az első, ugye?

585
00:30:01,930 --> 00:30:04,870
De itt megvan, hogy nyomon követhesse
hol vagyunk, ha behelyezi.

586
00:30:04,870 --> 00:30:07,930
Ha behelyezésekor a
node itt, nálunk

587
00:30:07,930 --> 00:30:12,270
hogy győződjön meg arról, hogy a
Egy korábbi ehhez a csomóponthoz

588
00:30:12,270 --> 00:30:14,172
az egyik, hogy ismét kiosztja a mutatót.

589
00:30:14,172 --> 00:30:16,380
Szóval akkor meg kell egyfajta
nyomon követheti a két dolgot.

590
00:30:16,380 --> 00:30:19,420
Ha nyomon követni, ahol ezt
csomópont jelenleg be van vezetve.

591
00:30:19,420 --> 00:30:23,280
Azt is meg kell nyomon követni, ahol
Az előző csomópont, amely nézel

592
00:30:23,280 --> 00:30:24,340
is ott volt.

593
00:30:24,340 --> 00:30:25,830
Mindenki jó ebben?

594
00:30:25,830 --> 00:30:26,500
OKÉ.

595
00:30:26,500 --> 00:30:28,000
>> Hogyan behelyezésével a végén?

596
00:30:28,000 --> 00:30:34,220
Ha akartam felvenni here-- ha akarnék
hogy egy új csomópont a végén egy listát,

597
00:30:34,220 --> 00:30:37,009
hogyan lehet azt járni csinálja?

598
00:30:37,009 --> 00:30:39,300
Közönség: Tehát jelenleg a
Utolsó ember mutatott null.

599
00:30:39,300 --> 00:30:40,960
ANDI Peng: Igen.

600
00:30:40,960 --> 00:30:43,560
Pontosan, így ez az egyik
Jelenleg is rámutatott, hogy tudja,

601
00:30:43,560 --> 00:30:46,720
és így azt hiszem, ebben az értelemben, hogy
Nagyon könnyű hozzáadni, hogy a végén egy listát.

602
00:30:46,720 --> 00:30:51,810
Mindössze annyit kell tennie, hogy állítsa
egyenlő null majd bumm.

603
00:30:51,810 --> 00:30:53,070
Pont ott, nagyon könnyű.

604
00:30:53,070 --> 00:30:53,960
Nagyon egyszerű.

605
00:30:53,960 --> 00:30:56,430
>> Nagyon hasonló a
fejét, de logikailag akkor

606
00:30:56,430 --> 00:30:59,690
szeretnénk, hogy győződjön meg arról, hogy a lépések
veszel cél megvalósítása sem ezt,

607
00:30:59,690 --> 00:31:01,500
te követi végig.

608
00:31:01,500 --> 00:31:04,420
Ez nagyon könnyű, a közepén
a kód, akad fenn,

609
00:31:04,420 --> 00:31:05,671
ó, kaptam sok tanácsot.

610
00:31:05,671 --> 00:31:07,461
Nem tudom, hol
bármit mutat.

611
00:31:07,461 --> 00:31:09,170
Azt sem tudom, melyik csomópont vagyok.

612
00:31:09,170 --> 00:31:11,490
Mi történik?

613
00:31:11,490 --> 00:31:13,620
>> Pihenjen, nyugodj meg, vegyél egy mély lélegzetet.

614
00:31:13,620 --> 00:31:15,530
Felhívni arra a láncolt lista.

615
00:31:15,530 --> 00:31:18,800
Ha azt mondod, tudom, hogy pontosan hol
Azt kell helyeznie ezt figyelembe

616
00:31:18,800 --> 00:31:22,970
és pontosan tudom, hogyan kell átminősítése én
mutatók, sokkal, de sokkal könnyebb elképzelni

617
00:31:22,970 --> 00:31:27,200
out-- sokkal, de sokkal könnyebb és nem
eltévedni a hibákat a kódot.

618
00:31:27,200 --> 00:31:29,410
Mindenki rendben van ezzel?

619
00:31:29,410 --> 00:31:31,380
OKÉ.

620
00:31:31,380 --> 00:31:35,120
>> Szóval azt hiszem, a koncepció, hogy mi nem
Tényleg beszélt előtt most,

621
00:31:35,120 --> 00:31:38,131
és azt hiszem, akkor valószínűleg
nem fog találkozni sok yet--

622
00:31:38,131 --> 00:31:40,880
ez a fajta fejlett concept--
az, hogy mi valóban van egy adat

623
00:31:40,880 --> 00:31:43,900
szerkezet az úgynevezett kétszeresen láncolt lista.

624
00:31:43,900 --> 00:31:46,390
Tehát ahogy ti is látni,
minden, amit csinálunk létrehozása

625
00:31:46,390 --> 00:31:50,400
a tényleges érték, egy extra
mutatót minden a mi csomópontok

626
00:31:50,400 --> 00:31:52,660
hogy arra is rámutat, hogy az előző csomópont.

627
00:31:52,660 --> 00:31:58,170
Tehát nem csak mi van a
csomópontok pont a következő alkalommal.

628
00:31:58,170 --> 00:32:01,430
Arra is rámutatnak, hogy az előzőt.

629
00:32:01,430 --> 00:32:04,310
Megyek figyelmen kívül hagyni ezt a két most.

630
00:32:04,310 --> 00:32:06,740
>> Tehát akkor van egy lánc
hogy lehet mozgatni mindkét irányban,

631
00:32:06,740 --> 00:32:09,630
és akkor ez egy kicsit könnyebb
hogy logikusan kövesse végig.

632
00:32:09,630 --> 00:32:11,896
Mint itt, ahelyett,
követi nyomon a, ó,

633
00:32:11,896 --> 00:32:14,520
Tudnunk kell, hogy ez a csomópont
Az egyik, hogy azt kell átminősítése,

634
00:32:14,520 --> 00:32:17,532
Én is csak megy itt, és
csak húzza az előző.

635
00:32:17,532 --> 00:32:19,490
Akkor tudom, hogy hol
azaz, és akkor

636
00:32:19,490 --> 00:32:21,130
Nem kell, hogy áthalad a
teljes egészében a láncolt lista.

637
00:32:21,130 --> 00:32:22,180
Ez egy kicsit könnyebb.

638
00:32:22,180 --> 00:32:24,960
>> De mint ilyen, akkor kétszeresen is
az összeg a mutatók,

639
00:32:24,960 --> 00:32:26,960
ez duplája a memóriát.

640
00:32:26,960 --> 00:32:28,950
Ez egy csomó mutatók nyomon követni.

641
00:32:28,950 --> 00:32:32,140
Ez egy kicsit bonyolultabb, de ez
egy kicsit felhasználóbarátabb függően

642
00:32:32,140 --> 00:32:34,080
hogy mit akarsz elérni.

643
00:32:34,080 --> 00:32:36,910
>> Tehát ilyen típusú adatok
struktúra teljesen létezik,

644
00:32:36,910 --> 00:32:40,280
és a struktúra nagyon, nagyon
egyszerű kivéve az összes Ön rendelkezik az,

645
00:32:40,280 --> 00:32:43,850
ahelyett, hogy csak egy mutató a következő,
Önnek is van egy mutató az előző.

646
00:32:43,850 --> 00:32:45,940
Ez minden volt a különbség.

647
00:32:45,940 --> 00:32:47,740
Mindenki jó ebben?

648
00:32:47,740 --> 00:32:48,240
Hűvös.

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> Rendben, akkor most én vagyok
hogy valóban költeni valószínűleg

651
00:32:53,280 --> 00:32:56,870
mint a 15-től 20 percig, vagy az ömlesztett
a fennmaradó időben szakaszban

652
00:32:56,870 --> 00:32:58,360
beszélünk hash táblák.

653
00:32:58,360 --> 00:33:02,590
Hányan vagytok srácok
Elolvastam pset5 spec?

654
00:33:02,590 --> 00:33:03,620
Rendben, jó.

655
00:33:03,620 --> 00:33:06,160
Ez magasabb, mint a 50% -a általában.

656
00:33:06,160 --> 00:33:07,560
Oké.

657
00:33:07,560 --> 00:33:10,345
>> Tehát ahogy a srácok fogják látni,
Ön kihívás pset5

658
00:33:10,345 --> 00:33:16,790
lesz, hogy végre egy szótár
ahol betöltöd több mint 140.000 szó

659
00:33:16,790 --> 00:33:20,610
hogy adunk és helyesírás-ellenőrzés
ez ellen a szöveg.

660
00:33:20,610 --> 00:33:22,580
Adunk véletlenszerű
szépirodalmi műveket.

661
00:33:22,580 --> 00:33:23,520
Adunk az Odüsszeia.

662
00:33:23,520 --> 00:33:24,561
Adunk az Iliász.

663
00:33:24,561 --> 00:33:26,350
Adunk Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> És a kihívás
az lesz, hogy helyesírás-ellenőrző

665
00:33:28,220 --> 00:33:31,760
minden egyes szót minden
e szótárak

666
00:33:31,760 --> 00:33:34,960
lényegében a mi helyesírás-ellenőrző.

667
00:33:34,960 --> 00:33:38,620
És így van egy pár alkatrészt
létrehozzák az említett PSET,

668
00:33:38,620 --> 00:33:41,970
első akar lenni
valóban képes betölteni

669
00:33:41,970 --> 00:33:43,970
minden szavakat a
szótár, és akkor

670
00:33:43,970 --> 00:33:45,530
akarjuk, hogy képes legyen
helyesírás-ellenőrzés mindet.

671
00:33:45,530 --> 00:33:48,780
És így mint ilyen, akkor lesz szükség
adatszerkezetet, hogy képes erre gyorsan

672
00:33:48,780 --> 00:33:50,790
és hatékonyan és dinamikusan.

673
00:33:50,790 --> 00:33:52,900
>> Szóval azt hiszem, a legegyszerűbb
módja ennek, akkor

674
00:33:52,900 --> 00:33:55,010
Valószínűleg létrehozunk egy tömböt, ugye?

675
00:33:55,010 --> 00:33:58,910
A legegyszerűbb módja a tárolás te
létrehozhat egy sor 140.000 szó

676
00:33:58,910 --> 00:34:03,400
és csak helyezze őket oda, és
ezután keresztülmegy őket bináris keresés

677
00:34:03,400 --> 00:34:06,780
vagy választás vagy nem--
Sajnálom, hogy ez a válogatás.

678
00:34:06,780 --> 00:34:10,729
Tudod rendezni őket, majd áthalad őket
a bináris keresés, vagy csak lineáris keresés

679
00:34:10,729 --> 00:34:13,730
és csak végső szava, de ez
vesz egy hatalmas mennyiségű memória,

680
00:34:13,730 --> 00:34:15,190
és ez nem túl hatékony.

681
00:34:15,190 --> 00:34:18,350
>> És így fogunk kezdeni
beszélünk módon teszi

682
00:34:18,350 --> 00:34:20,110
a futási idő hatékonyabb.

683
00:34:20,110 --> 00:34:23,190
És a célunk az, hogy
konstans időben, amikor

684
00:34:23,190 --> 00:34:25,810
ez majdnem olyan, mint tömbök, ahol
Ön azonnali hozzáférést.

685
00:34:25,810 --> 00:34:28,560
Ha akartam keresni valamit,
Azt akarom, hogy képes legyen igazságos,

686
00:34:28,560 --> 00:34:30,810
boom, meg pontosan, és húzza ki.

687
00:34:30,810 --> 00:34:34,100
És így egy olyan struktúra, amelyben
fogunk egyre nagyon közel

688
00:34:34,100 --> 00:34:37,569
hogy képes legyen hozzáférni konstans
idő, ez a szent grál

689
00:34:37,569 --> 00:34:41,370
A programozásban állandó
alkalommal hívják hash tábla.

690
00:34:41,370 --> 00:34:45,370
És így David korábban említettük
[Hallhatatlan] egy kicsit az előadás,

691
00:34:45,370 --> 00:34:49,100
de mi lesz igazán
merülés mélyen a héten

692
00:34:49,100 --> 00:34:51,780
egy darab, ami kapcsolatban
hogy egy hash tábla működik.

693
00:34:51,780 --> 00:34:53,949
>> Tehát az is, hogy a hash
táblázat munkák, például,

694
00:34:53,949 --> 00:35:00,230
ha akartam, hogy tárolja egy csomó szó, a
csomó szó az angol nyelv,

695
00:35:00,230 --> 00:35:02,940
Én elméletileg fel
banán, alma, kiwi, mangó, pár,

696
00:35:02,940 --> 00:35:04,980
és sárgadinnye mind csak egy tömbben.

697
00:35:04,980 --> 00:35:07,044
Tudtak fér bele, és lehet találni.

698
00:35:07,044 --> 00:35:09,210
Jó lenne egyfajta fájdalom, hogy
keresgélni és a hozzáférés,

699
00:35:09,210 --> 00:35:12,920
de az egyszerűbb módja, ez
hogy mi is létrehozhatunk valójában egy struktúra

700
00:35:12,920 --> 00:35:15,680
úgynevezett hash tábla, ahol hash.

701
00:35:15,680 --> 00:35:19,880
Futunk minden kedves gombok segítségével
hash függvény, egy egyenletet,

702
00:35:19,880 --> 00:35:22,600
amely bekapcsolja őket mind
valamiféle értéket

703
00:35:22,600 --> 00:35:28,740
hogy akkor tudjuk tárolni rá
Lényegében egy sor láncolt lista.

704
00:35:28,740 --> 00:35:32,570
>> És így van, ha akarnánk
tárolni angol szavak,

705
00:35:32,570 --> 00:35:37,250
tudnánk esetleg csak, én nem
tudom, viszont minden az első betű

706
00:35:37,250 --> 00:35:39,630
valamiféle egy számot.

707
00:35:39,630 --> 00:35:43,140
És így, például, ha akartam
Egy, hogy egyet apple--

708
00:35:43,140 --> 00:35:47,460
vagy az index 0, és
B, hogy egyet 1,

709
00:35:47,460 --> 00:35:51,030
mi lehet 26 bejegyzés
amely csak tárolja

710
00:35:51,030 --> 00:35:53,610
minden betűjét a
ábécét, hogy kezdjük.

711
00:35:53,610 --> 00:35:56,130
És akkor mi lehet
Az Apple a indexe 0.

712
00:35:56,130 --> 00:35:59,160
Mi lehet a banán, a indexe
1, sárgadinnye meg az index a 2,

713
00:35:59,160 --> 00:36:00,540
és így tovább, és így tovább.

714
00:36:00,540 --> 00:36:04,460
És így ha akartam keresni
én hash tábla és a hozzáférés alma,

715
00:36:04,460 --> 00:36:07,560
Tudom, alma kezdődik
egy A, és pontosan tudom,

716
00:36:07,560 --> 00:36:10,860
hogy kell, és a hash
asztal index 0, mert

717
00:36:10,860 --> 00:36:13,620
A korábban kijelölt funkciót.

718
00:36:13,620 --> 00:36:16,572
>> Szóval nem tudom, mi
felhasználói program, ahol

719
00:36:16,572 --> 00:36:18,780
akkor terhelhetik
arbitrarily-- nem önkényesen,

720
00:36:18,780 --> 00:36:22,530
A próbál elgondolkodva
gondolom jó egyenletek

721
00:36:22,530 --> 00:36:25,460
hogy képes terjedni
ki az összes értékek

722
00:36:25,460 --> 00:36:29,370
oly módon, egyszerűen érhetőek el
hogy a későbbiekben a hasonló egyenlet

723
00:36:29,370 --> 00:36:31,130
hogy te magad tudod.

724
00:36:31,130 --> 00:36:35,210
Tehát abban az értelemben, ha akartam menni
mangó, tudom, ó, azzal kezdődik, m.

725
00:36:35,210 --> 00:36:37,134
Meg kell lennie az index a 12.

726
00:36:37,134 --> 00:36:38,800
Nem kell keresni semmit.

727
00:36:38,800 --> 00:36:42,080
Tudom exactly-- tudnék menni
Az index 12 és húzza, hogy ki.

728
00:36:42,080 --> 00:36:45,520
>> Mindenki tisztában, hogy egy
hash tábla funkció?

729
00:36:45,520 --> 00:36:48,380
Elég csak egy bonyolultabb tömb.

730
00:36:48,380 --> 00:36:50,010
Ez minden van.

731
00:36:50,010 --> 00:36:51,630
OKÉ.

732
00:36:51,630 --> 00:36:57,690
>> Szóval azt hiszem, befut
ezt a kérdést, hogy mi

733
00:36:57,690 --> 00:37:06,390
előfordul, ha több dolgot
hogy megadja ugyanazt index?

734
00:37:06,390 --> 00:37:10,570
Tehát mondjuk a függvényt, mindent meg
az volt, hogy az első levél

735
00:37:10,570 --> 00:37:14,490
és viszont, hogy egy
megfelelő 0 és 25 index.

736
00:37:14,490 --> 00:37:17,137
Ezt teljesen rendben van, ha
már csak egy minden.

737
00:37:17,137 --> 00:37:18,970
De a második indításakor
hogy több, maga

738
00:37:18,970 --> 00:37:20,910
megy, hogy az úgynevezett ütközés.

739
00:37:20,910 --> 00:37:25,580
>> Szóval, ha megpróbál beilleszteni temetni egy hash
táblázatot, amely már a banán rajta,

740
00:37:25,580 --> 00:37:27,870
mi fog történni, ha
megpróbál beilleszteni ezt?

741
00:37:27,870 --> 00:37:30,930
Rossz dolgok, mert a banán
Már létezik az index

742
00:37:30,930 --> 00:37:33,800
kívánt tárolja.

743
00:37:33,800 --> 00:37:35,560
Berry fajta, mint, ah, mit tegyek?

744
00:37:35,560 --> 00:37:37,080
Nem tudom, hová menjen.

745
00:37:37,080 --> 00:37:38,410
Hogyan tudom megoldani ezt?

746
00:37:38,410 --> 00:37:41,150
>> És így a srácok a fajta
lásd ezt tesszük trükkös dolog

747
00:37:41,150 --> 00:37:44,810
ahol tudunk ilyen ténylegesen
hozzon létre láncolt lista a mi tömböket.

748
00:37:44,810 --> 00:37:46,840
És így a legegyszerűbb módja
ezen gondolkodni,

749
00:37:46,840 --> 00:37:50,830
Az összes hash tábla egy
tömb láncolt listák.

750
00:37:50,830 --> 00:37:55,670
És így, ebben az értelemben, hogy van
ez a gyönyörű tömb mutató,

751
00:37:55,670 --> 00:37:58,740
majd minden mutatót
ezt az értéket, az adott index,

752
00:37:58,740 --> 00:38:00,740
valójában pont az más dolog.

753
00:38:00,740 --> 00:38:05,720
És így van mindezen külön
láncok jön ki egy nagy tömb.

754
00:38:05,720 --> 00:38:07,960
>> És így van, ha én
akarta szúrni bogyó,

755
00:38:07,960 --> 00:38:11,220
Tudom, OK, megyek bemenet
ez az én hash függvény.

756
00:38:11,220 --> 00:38:15,070
Megyek, hogy a végén az index
1, majd fogok tudni kell

757
00:38:15,070 --> 00:38:20,410
Csak egy kisebb részét ennek
óriás 140.000 szavas szótárban.

758
00:38:20,410 --> 00:38:24,220
És akkor tudok csak nézz
keresztül 1/26 e.

759
00:38:24,220 --> 00:38:27,910
>> És így akkor tudok csak helyezze
bogyó előtt vagy után banán

760
00:38:27,910 --> 00:38:28,820
ebben az esetben?

761
00:38:28,820 --> 00:38:29,700
Miután, ugye?

762
00:38:29,700 --> 00:38:33,920
És így fogsz akar
helyezze a csomópont után banán,

763
00:38:33,920 --> 00:38:36,667
és így fogsz szúrni
a farka, hogy láncolt lista.

764
00:38:36,667 --> 00:38:38,500
Én megyek vissza
ehhez előző diára

765
00:38:38,500 --> 00:38:40,680
Szóval ti láthatod, hogy
hash függvény működik.

766
00:38:40,680 --> 00:38:43,980
>> Tehát hash függvény ennek az egyenletnek
hogy futsz fajta a bemeneti

767
00:38:43,980 --> 00:38:46,940
keresztül kap bármilyen index
hozzárendelni kívánt felé.

768
00:38:46,940 --> 00:38:51,130
És így, ebben a példában az összes akartunk
tennem, hogy tegye meg az első levelet,

769
00:38:51,130 --> 00:38:55,890
viszont, hogy egy indexet, akkor
tárolhatja, hogy a hasító függvény.

770
00:38:55,890 --> 00:39:00,160
Minden csinálunk itt vagyunk
konvertáló az első levél.

771
00:39:00,160 --> 00:39:04,770
Tehát KeyKey [0] csak az első betű
bármilyen karakterlánc vagyunk, amelynek,

772
00:39:04,770 --> 00:39:05,720
mi halad.

773
00:39:05,720 --> 00:39:09,740
Mi konvertáló, hogy a felső és
mi levonjuk a nagybetűs Egy,

774
00:39:09,740 --> 00:39:11,740
így minden, ami csinál
ad nekünk egy számot

775
00:39:11,740 --> 00:39:13,670
ahol tudunk hash értékeinket rá.

776
00:39:13,670 --> 00:39:16,550
>> És akkor mi lesz
visszatérni hash modulus SIZE.

777
00:39:16,550 --> 00:39:19,340
Legyen nagyon, nagyon óvatos
mert, elméletileg, ide

778
00:39:19,340 --> 00:39:21,870
A hash érték lehet végtelen.

779
00:39:21,870 --> 00:39:23,660
Lehet, hogy csak megy tovább és tovább és tovább.

780
00:39:23,660 --> 00:39:26,080
Ez lehet néhány igazán,
Nagyon nagy érték,

781
00:39:26,080 --> 00:39:29,849
hanem azért, mert a hash tábla
Ön erről csak 26 indexek,

782
00:39:29,849 --> 00:39:31,890
azt szeretnénk, hogy győződjön meg róla,
modulusing úgy, hogy

783
00:39:31,890 --> 00:39:33,848
Nem run-- ez ugyanaz
dolog, mint a queue--

784
00:39:33,848 --> 00:39:36,320
úgy, hogy ne fogyjon ki a
alján a hash függvény.

785
00:39:36,320 --> 00:39:39,210
>> Azt akarod, hogy csavarja vissza mintegy
azonos módon [hallható], amikor

786
00:39:39,210 --> 00:39:41,750
Önnek volt, mint egy nagyon,
nagyon nagy levelet, akkor

787
00:39:41,750 --> 00:39:43,740
Nem akartam, hogy a
csak fuss ki a végét.

788
00:39:43,740 --> 00:39:46,948
Ugyanezt itt, azt szeretnénk, hogy győződjön meg arról,
nem fut le a végén a csomagolás

789
00:39:46,948 --> 00:39:48,330
körül, hogy a táblázat tetején.

790
00:39:48,330 --> 00:39:50,530
Tehát ez csak egy nagyon
egyszerű hash függvény.

791
00:39:50,530 --> 00:39:56,570
Minden, ami az volt, hogy az első
levelében, amit mi bemeneti volt

792
00:39:56,570 --> 00:40:01,660
és kapcsolja be, hogy egy index,
tudtuk helyezni a hash tábla.

793
00:40:01,660 --> 00:40:05,450
>> Ja, és így mint már mondtam,
az is, hogy elhatározzuk ütközések

794
00:40:05,450 --> 00:40:09,330
a hasító táblák vannak,
hívjuk, láncolt.

795
00:40:09,330 --> 00:40:13,860
Tehát, ha megpróbál beilleszteni több
szóval kezdődő ugyanaz a dolog,

796
00:40:13,860 --> 00:40:16,145
fogsz egy hash értéket.

797
00:40:16,145 --> 00:40:18,770
Az avokádó és alma, ha már
futtassuk át a hash függvény,

798
00:40:18,770 --> 00:40:21,450
fog adni a
ugyanazt a számot, a szám a 0.

799
00:40:21,450 --> 00:40:24,550
És így, ahogy mi megoldani, hogy az
hogy mi is valójában milyen összekapcsolják őket

800
00:40:24,550 --> 00:40:27,010
okon láncolt listák.

801
00:40:27,010 --> 00:40:29,600
>> És így ebben az értelemben,
srácok láthatjuk a fajta

802
00:40:29,600 --> 00:40:32,640
hogyan adatszerkezetekről
mi már korábban beállítása

803
00:40:32,640 --> 00:40:35,870
mint egy mazsola láncolt lista természetbeni
Az jöhet össze egy.

804
00:40:35,870 --> 00:40:38,860
És akkor hozhat létre messze
hatékonyabb adatszerkezetek

805
00:40:38,860 --> 00:40:43,350
amely képes kezelni nagyobb mennyiségű
adatokat, amelyek dinamikusan átméretezni függően

806
00:40:43,350 --> 00:40:44,870
hogy az Ön igényeinek.

807
00:40:44,870 --> 00:40:45,620
Mindenki tiszta?

808
00:40:45,620 --> 00:40:47,580
Mindenki fajta tiszta
mi történik itt?

809
00:40:47,580 --> 00:40:52,110
>> Ha akartam insert-- mi egy
gyümölcsöt, hogy kezdődik, nem tudom,

810
00:40:52,110 --> 00:40:54,726
B, kivéve bogyó, banán.

811
00:40:54,726 --> 00:40:55,710
>> Közönség: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI Peng: Blackberry, szeder.

813
00:40:57,910 --> 00:41:00,530
Hol szeder megy itt?

814
00:41:00,530 --> 00:41:04,251
Nos, valójában nem rendezve
ez még, de elméletileg

815
00:41:04,251 --> 00:41:06,250
ha azt akartuk, hogy ezt
ábécésorrendben,

816
00:41:06,250 --> 00:41:07,944
hol kellene szeder menni?

817
00:41:07,944 --> 00:41:09,210
>> Közönség: [hallható]

818
00:41:09,210 --> 00:41:11,100
>> ANDI Peng: Pontosan, miután itt, ugye?

819
00:41:11,100 --> 00:41:14,950
De mivel ez nagyon nehéz
reorder-- Azt hiszem, ez akár srácok.

820
00:41:14,950 --> 00:41:17,920
Srácok lehet teljesen
végrehajtja, amit akarsz.

821
00:41:17,920 --> 00:41:20,730
A hatékonyabb módszer
Az ezt talán

822
00:41:20,730 --> 00:41:24,570
lenne rendezni a kapcsolt
sorolja be, betűrendben

823
00:41:24,570 --> 00:41:26,520
és így, ha éppen
behelyezése a dolgokat, azt szeretnénk,

824
00:41:26,520 --> 00:41:28,632
hogy biztos, hogy be őket
betűrendbe

825
00:41:28,632 --> 00:41:30,590
így aztán, ha éppen
próbál keresni őket,

826
00:41:30,590 --> 00:41:32,410
Önnek nem kell bejárására mindent.

827
00:41:32,410 --> 00:41:35,290
Pontosan tudod, hol
ez, és akkor könnyebb.

828
00:41:35,290 --> 00:41:39,100
>> De ha ilyen van,
dolgokat tarkított véletlenszerűen,

829
00:41:39,100 --> 00:41:41,420
még mindig megy, hogy
bejárására is egyébként.

830
00:41:41,420 --> 00:41:44,990
És így ha akartam csak
helyezze szeder itt

831
00:41:44,990 --> 00:41:47,470
és szerettem volna keresni
ez, tudom, ó, szeder

832
00:41:47,470 --> 00:41:52,012
kell kezdeni az index az 1, úgyhogy
tudni azonnal, csak keresni 1.

833
00:41:52,012 --> 00:41:53,970
És akkor én is egyfajta
keresztezik a láncolt lista

834
00:41:53,970 --> 00:41:56,120
amíg nem kap a BlackBerry,
és then-- igen?

835
00:41:56,120 --> 00:41:59,550
>> Közönség: Ha akarsz create--
Azt hiszem, ez egy nagyon egyszerű hash

836
00:41:59,550 --> 00:42:00,050
funkció.

837
00:42:00,050 --> 00:42:02,835
És ha azt akartuk csinálni
több réteg, amely, mint,

838
00:42:02,835 --> 00:42:05,870
OK, azt akarjuk, hogy szét lehessen választani
mint az összes abc betűk

839
00:42:05,870 --> 00:42:09,040
majd ismét szeretnék egy másik
alfabetikus betűk belül,

840
00:42:09,040 --> 00:42:11,715
vagyunk üzembe, mint egy hash
asztal belül hash tábla,

841
00:42:11,715 --> 00:42:13,256
vagy mint egy programon belül egy funkciót?

842
00:42:13,256 --> 00:42:14,880
Vagy hogy--

843
00:42:14,880 --> 00:42:17,510
>> ANDI Peng: Szóval a hash
function-- a hash tábla

844
00:42:17,510 --> 00:42:19,360
lehet olyan nagy, mint azt akarja, hogy.

845
00:42:19,360 --> 00:42:21,930
Tehát ebben az értelemben, azt hittem,
nagyon könnyű volt, nagyon

846
00:42:21,930 --> 00:42:25,320
egyszerű számomra, hogy csak egyfajta alapján
A leveleket az első szó.

847
00:42:25,320 --> 00:42:28,690
És így már csak 26 lehetőségeket.

848
00:42:28,690 --> 00:42:32,650
Csak azt tudom, hogy 26 opciókat
0-25 hiszen csak

849
00:42:32,650 --> 00:42:36,510
kezdeni tól Z-ig, de ha akarod
hozzá, talán még összetettsége

850
00:42:36,510 --> 00:42:39,260
vagy gyorsabb futás közben a
hash tábla, amit feltétlenül

851
00:42:39,260 --> 00:42:40,760
tehetünk mindenféle dolgot.

852
00:42:40,760 --> 00:42:43,330
Tudod, hogy a saját
egyenletet, hogy megadja neked

853
00:42:43,330 --> 00:42:48,000
Több elosztó a
szavakat, majd amikor keresni,

854
00:42:48,000 --> 00:42:49,300
ez lesz gyorsabb.

855
00:42:49,300 --> 00:42:52,100
>> Ez teljesen rajtad múlik srácok
hogyan szeretné megvalósítani ezt.

856
00:42:52,100 --> 00:42:55,140
Gondold azt, hogy csak vödrök.

857
00:42:55,140 --> 00:42:57,376
Ha azt akartam, hogy
26 vödrök, megyek

858
00:42:57,376 --> 00:42:59,420
rendezni a dolgokat abba a vödörben.

859
00:42:59,420 --> 00:43:02,980
De megyek van egy rakás
A cucc minden vödör,

860
00:43:02,980 --> 00:43:05,890
ezért ha azt szeretnénk, hogy győződjön meg
gyorsabb és hatékonyabb,

861
00:43:05,890 --> 00:43:07,190
hadd száz vödör.

862
00:43:07,190 --> 00:43:09,290
>> De akkor meg kell kitalálni a
milyen módon rendezi a dolgokat, hogy azok

863
00:43:09,290 --> 00:43:11,040
a megfelelő vödör kellene lennie.

864
00:43:11,040 --> 00:43:13,331
De akkor, ha valóban
szeretné nézni, hogy vödröt,

865
00:43:13,331 --> 00:43:16,410
ez sokkal gyorsabb, mert van
kevesebb cucc minden vödör.

866
00:43:16,410 --> 00:43:20,250
És igen, igen, ez valóban
A trükk az Ön srácok pset5

867
00:43:20,250 --> 00:43:22,360
az, hogy te leszel
vitatta, hogy csak teremt

868
00:43:22,360 --> 00:43:26,170
függetlenül a leghatékonyabb
funkcióval lehet gondolni, hogy

869
00:43:26,170 --> 00:43:28,520
képes tárolni, és ellenőrizze ezeket az értékeket.

870
00:43:28,520 --> 00:43:30,840
>> Teljesen fel srácok
ahogy akarod csinálni,

871
00:43:30,840 --> 00:43:32,229
de ez egy nagyon jó pont.

872
00:43:32,229 --> 00:43:34,520
Hogy a fajta logika akkor
szeretnénk kezdeni gondolkodni

873
00:43:34,520 --> 00:43:37,236
van, nos, miért nem érzem, hogy több vödör.

874
00:43:37,236 --> 00:43:39,527
És akkor azt kell keresni
kevesebb dolgokat, és akkor talán

875
00:43:39,527 --> 00:43:41,640
Van egy másik hash függvény.

876
00:43:41,640 --> 00:43:45,500
>> Igen, van egy csomó módon, hogy ezt
PSET, néhány gyorsabb, mint mások.

877
00:43:45,500 --> 00:43:50,630
Én teljesen fog éppen milyen
gyors volt a leggyorsabb srácok lesz

878
00:43:50,630 --> 00:43:55,170
tudja, hogy a funkciók dolgozni.

879
00:43:55,170 --> 00:43:58,176
OK, mindenki jó
láncolás és hash táblák?

880
00:43:58,176 --> 00:44:00,800
Ez valójában, mint egy nagyon egyszerű
fogalmát, ha belegondolsz.

881
00:44:00,800 --> 00:44:05,160
Minden ez az elválasztó bármi
A bemenetek gyűjtőzónákba,

882
00:44:05,160 --> 00:44:10,670
válogatás őket, majd keresni a
felsorolja, hogy van társítva.

883
00:44:10,670 --> 00:44:11,852
>> Hűvös.

884
00:44:11,852 --> 00:44:18,160
Rendben, most van egy másik fajta
Az adatok szerkezete, hogy hívják a fa.

885
00:44:18,160 --> 00:44:20,850
Menjünk tovább és beszélni próbál
amelyek határozottan eltérő,

886
00:44:20,850 --> 00:44:22,330
de ugyanabban a kategóriában.

887
00:44:22,330 --> 00:44:29,010
Lényegében minden a fa helyett
A szervező adatok a lineárisan

888
00:44:29,010 --> 00:44:32,560
hogy a hash tábla does-- Önnek
Tudja, hogy van egy felső és egy alsó

889
00:44:32,560 --> 00:44:37,900
és akkor milyen hivatkoznak le it-- egy
fa egy felső, amely hívja a gyökér,

890
00:44:37,900 --> 00:44:40,220
és akkor van levelek minden körülötte.

891
00:44:40,220 --> 00:44:42,390
>> És így minden, ami itt
csak a legfelső csomópont

892
00:44:42,390 --> 00:44:45,980
hogy pont más csomópontok, hogy pont
hogy több csomópont, és így tovább, és így tovább.

893
00:44:45,980 --> 00:44:48,130
És így csak ki hasító ágak.

894
00:44:48,130 --> 00:44:53,255
Ez csak egy másik módja a szervező
adatok, és mert ez egy fa,

895
00:44:53,255 --> 00:44:56,270
srácok csak-- ez csak
modellezett ki néz ki, mint egy fa.

896
00:44:56,270 --> 00:44:57,670
Ezért nevezzük ezt fák.

897
00:44:57,670 --> 00:44:59,370
>> Hash tábla úgy néz ki, mint egy asztal.

898
00:44:59,370 --> 00:45:01,310
A fa csak úgy néz ki, mint egy fa.

899
00:45:01,310 --> 00:45:03,300
Minden ez egy külön
szervezési módja csomópontok

900
00:45:03,300 --> 00:45:06,020
attól függően, hogy milyen igényei.

901
00:45:06,020 --> 00:45:11,810
>> Szóval van egy gyökér és
akkor már a levelek.

902
00:45:11,810 --> 00:45:15,380
Az így tudjuk különösen
belegondolsz egy bináris fa,

903
00:45:15,380 --> 00:45:18,150
egy bináris fa csak egy
bizonyos típusú fát

904
00:45:18,150 --> 00:45:22,450
ahol minden csomópont csak pont
a, max, két másik csomópont.

905
00:45:22,450 --> 00:45:25,434
És így itt van külön
szimmetria a fán

906
00:45:25,434 --> 00:45:28,600
hogy megkönnyíti a fajta néz
hogy milyen értékek vagytok, mert akkor

907
00:45:28,600 --> 00:45:30,150
mindig a bal vagy jobbra.

908
00:45:30,150 --> 00:45:33,150
Soha nincs, mint egy bal harmadával
A bal vagy egy negyedik balról.

909
00:45:33,150 --> 00:45:36,358
Csak van egy jobb és bal
és kereshetünk akár az említett kettő.

910
00:45:36,358 --> 00:45:38,980
És így ez miért hasznos?

911
00:45:38,980 --> 00:45:40,980
Az út, hogy ez
hasznos az, ha keres

912
00:45:40,980 --> 00:45:42,890
keresgélni értékek, ugye?

913
00:45:42,890 --> 00:45:45,640
Ahelyett végrehajtási bináris
Keressen egy hiba tömb,

914
00:45:45,640 --> 00:45:49,260
ha akarod, hogy tudja beszúrni csomópontok
és elvenni a csomópontok lesz, és azt is

915
00:45:49,260 --> 00:45:52,185
megőrizni a keresési
kapacitásainak bináris keresés.

916
00:45:52,185 --> 00:45:54,560
Tehát így vagyunk a fajta
tricking-- emlékszem, amikor

917
00:45:54,560 --> 00:45:56,530
említett kapcsolt listák nem bináris keresés?

918
00:45:56,530 --> 00:46:01,700
Mi vagyunk a fajta létre egy adatstruktúra
hogy trükkök, hogy a munka.

919
00:46:01,700 --> 00:46:05,034
>> És így, mert láncolt listák lineáris,
ők csak hivatkozó egyik a másik után.

920
00:46:05,034 --> 00:46:06,950
Mi lehet ilyen van
másfajta mutatók

921
00:46:06,950 --> 00:46:09,408
Ezen a ponton a különböző csomópontok
amely segíthet a keresésben.

922
00:46:09,408 --> 00:46:12,590
És így van, ha akartam
Van egy bináris kereső fa,

923
00:46:12,590 --> 00:46:14,090
Tudom, hogy a középső, ha 55.

924
00:46:14,090 --> 00:46:18,280
Én csak létre fog hozni, hogy
mint az én közepén, mint az én gyökér,

925
00:46:18,280 --> 00:46:20,770
és akkor én megyek is
értékeket spin off belőle.

926
00:46:20,770 --> 00:46:25,610
>> Tehát itt, ha fogom keresni
értékének 66, kezdhetem 55.

927
00:46:25,610 --> 00:46:27,310
Ez 66 több mint 55?

928
00:46:27,310 --> 00:46:30,970
Igen ez, így tudom, hogy a MUS keresni
i n jobb mutatót ennek a fának.

929
00:46:30,970 --> 00:46:32,440
Megyek 77.

930
00:46:32,440 --> 00:46:35,367
OK, 66-nél kisebb vagy nagyobb, mint a 77?

931
00:46:35,367 --> 00:46:37,950
Ez kevesebb, mint, hogy tudd, ó,
hogy kell lennie a bal csomópont.

932
00:46:37,950 --> 00:46:41,410
>> És így itt vagyunk a fajta megőrzése
Minden nagy dolog tömbök,

933
00:46:41,410 --> 00:46:44,420
így, mint a dinamikus átméretezés
tárgyak, hogy

934
00:46:44,420 --> 00:46:49,530
tudja beszúrni és törölni az akarat,
anélkül, hogy aggódnia a rögzített

935
00:46:49,530 --> 00:46:50,370
mennyiségű helyet.

936
00:46:50,370 --> 00:46:52,820
Még mindig megőrizze az összes
ezek a csodálatos dolgokat

937
00:46:52,820 --> 00:46:57,140
míg a szintén képes megőrizni a
jelentkezzen, és keressen ideje bináris keresés

938
00:46:57,140 --> 00:47:00,450
hogy mi volt korábban csak
tudja, hogy egy mondatot.

939
00:47:00,450 --> 00:47:06,310
>> Cool adatok szerkezete, egyfajta
megvalósításuk, a csomópont.

940
00:47:06,310 --> 00:47:08,311
Mint látható, minden tőle
a struktúra a csomópont

941
00:47:08,311 --> 00:47:10,143
az, hogy van egy bal
és a jobb mutatót.

942
00:47:10,143 --> 00:47:11,044
Ez minden van.

943
00:47:11,044 --> 00:47:12,960
Tehát ahelyett, hogy csak
amelynek x vagy korábbi.

944
00:47:12,960 --> 00:47:15,920
Van egy bal vagy jobb oldali, majd
akkor milyen összekapcsolja őket

945
00:47:15,920 --> 00:47:16,836
azonban úgy döntenek.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, mi történt valójában
Csak egy pár percig.

948
00:47:24,270 --> 00:47:25,790
Így fogunk visszamenni itt.

949
00:47:25,790 --> 00:47:28,270
Ahogy korábban mondtam,
Valahogy magyarázható

950
00:47:28,270 --> 00:47:31,520
a logikája, hogy hogyan
lenne végig ezt.

951
00:47:31,520 --> 00:47:33,860
Fogunk próbálni
pseudocoding ezt ki, hogy

952
00:47:33,860 --> 00:47:38,000
ha tudjuk milyen alkalmazni a
Ugyanez a logika a bináris keresés

953
00:47:38,000 --> 00:47:40,055
egy másik típusú adat struktúrát.

954
00:47:40,055 --> 00:47:45,049
Ha akartok venni, mint egy pár
perc, hogy csak gondol erről.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
OKÉ.

957
00:48:46,925 --> 00:48:51,407
Rendben, megyek
valójában csak kapsz the-- nem,

958
00:48:51,407 --> 00:48:52,990
fogunk beszélni a pszeudokódja először.

959
00:48:52,990 --> 00:48:56,580
Tehát nem mindenki szeretné,
hogy a stab a mi

960
00:48:56,580 --> 00:49:02,100
Az első dolog, amit akarok, amikor
kezded el keresés?

961
00:49:02,100 --> 00:49:04,460
Ha keresünk
értékének 66, mi

962
00:49:04,460 --> 00:49:07,940
Az első dolog, amit akarok, ha
azt akarjuk, hogy a bináris keresés ezt a fát?

963
00:49:07,940 --> 00:49:10,760
>> Közönség: Azt akarod, hogy néz ki jól
és nézd bal és látni [hallhatatlan]

964
00:49:10,760 --> 00:49:11,230
nagyobb számot.

965
00:49:11,230 --> 00:49:12,271
>> ANDI Peng: Igen, pontosan.

966
00:49:12,271 --> 00:49:15,350
Szóval nézzük át a root.

967
00:49:15,350 --> 00:49:18,180
Van sok módon lehet hívni
ez, a szülő csomópont az emberek mondanak.

968
00:49:18,180 --> 00:49:21,317
Azt szoktam mondani, gyökér, mert
ez olyan, mint a gyökér a fa.

969
00:49:21,317 --> 00:49:23,400
Fogsz nézni
a gyökér csomópontot, és te

970
00:49:23,400 --> 00:49:26,940
fog látni a 66 nagyobb
kisebb vagy kevesebb mint 55.

971
00:49:26,940 --> 00:49:30,360
És ha ez nagyobb, mint, nos, ez
nél nagyobb, hol akarunk nézni?

972
00:49:30,360 --> 00:49:32,000
Hol akarunk keresni, igaz?

973
00:49:32,000 --> 00:49:34,340
Azt akarjuk, hogy keressen a
jobb fele ezt a fát.

974
00:49:34,340 --> 00:49:38,390
>> Tehát van, kényelmesen, egy
a mutató, mely arra utal, hogy a jobb oldalon.

975
00:49:38,390 --> 00:49:44,325
És akkor tudjuk meg
Az új gyökér, hogy 77.

976
00:49:44,325 --> 00:49:46,450
Mi is csak menni bárhova
A mutató mutat.

977
00:49:46,450 --> 00:49:49,100
Nos, ó, itt kezdünk
77, és mi csak

978
00:49:49,100 --> 00:49:51,172
Ehhez rekurzív újra és újra.

979
00:49:51,172 --> 00:49:52,880
Ily módon, akkor milyen
A funkciója van.

980
00:49:52,880 --> 00:49:57,430
Van egy módja a keresést, hogy
egyszerűen csak ismételni újra és újra és újra,

981
00:49:57,430 --> 00:50:02,720
attól függően, hogy hol szeretné nézni
amíg meg előbb-utóbb eljut arra az értékre

982
00:50:02,720 --> 00:50:04,730
hogy maga keresett.

983
00:50:04,730 --> 00:50:05,230
Van értelme?

984
00:50:05,230 --> 00:50:07,800
>> Én azon vagyok, hogy mutassa meg a tényleges
kódot, és ez sok kód.

985
00:50:07,800 --> 00:50:08,674
Nem kell kiborulni.

986
00:50:08,674 --> 00:50:09,910
Beszélni fogunk rajta.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Igazából nem.

989
00:50:14,020 --> 00:50:15,061
Ez csak pszeudokódja.

990
00:50:15,061 --> 00:50:17,860
OK, ez csak a pszeudokódja,
ami egy kicsit komplex,

991
00:50:17,860 --> 00:50:19,751
de ez teljesen rendben van.

992
00:50:19,751 --> 00:50:21,000
Mindenki a következő mentén itt?

993
00:50:21,000 --> 00:50:24,260
Ha a gyökér null, cserébe
hamis, mert azt jelenti

994
00:50:24,260 --> 00:50:26,850
akkor nem is kell semmit ott.

995
00:50:26,850 --> 00:50:31,376
>> Ha a root n az érték, így ha ez
előfordul, hogy az egyik nézel,

996
00:50:31,376 --> 00:50:34,000
akkor fogsz visszatérni igaz
mert tudod, hogy megtaláltad.

997
00:50:34,000 --> 00:50:36,250
De ha az érték kisebb,
a root-n, akkor

998
00:50:36,250 --> 00:50:38,332
fog keresni a bal
gyermek vagy a bal levél,

999
00:50:38,332 --> 00:50:39,540
amit csak akarsz nevezni.

1000
00:50:39,540 --> 00:50:41,750
És ha az érték nagyobb, mint gyökér,
fogsz keresni a megfelelő fát,

1001
00:50:41,750 --> 00:50:44,610
akkor csak futtassa a funkciót
a keresési újra.

1002
00:50:44,610 --> 00:50:48,037
>> És ha gyökér null, hogy ez a
azt jelenti, hogy elérte a végén?

1003
00:50:48,037 --> 00:50:50,120
Ez azt jelenti, hogy nincs
tovább tovább levelek keresni,

1004
00:50:50,120 --> 00:50:52,230
akkor tudod, ó,
Szerintem ez nem ide

1005
00:50:52,230 --> 00:50:55,063
mert miután már átnéztem
az egészet, és nincs itt,

1006
00:50:55,063 --> 00:50:56,930
ez csak lehet nem lesz itt.

1007
00:50:56,930 --> 00:50:58,350
>> Van ennek értelme mindenki?

1008
00:50:58,350 --> 00:51:03,230
Tehát ez olyan, mint a bináris keresés megőrzése
képességeit láncolt listák.

1009
00:51:03,230 --> 00:51:09,200
Cool, és így a második típus
Az adatok szerkezete srácok

1010
00:51:09,200 --> 00:51:13,180
kipróbálhatják végrehajtási a PSET,
Önnek csak ki kell választani egy módszer.

1011
00:51:13,180 --> 00:51:19,430
De talán egy alternatív módszert
A hash tábla, hogy mit nevezünk Trie.

1012
00:51:19,430 --> 00:51:24,080
>> Minden olyan Trie van egy
bizonyos típusú fa

1013
00:51:24,080 --> 00:51:28,600
vannak olyan értékei megy más értékeket.

1014
00:51:28,600 --> 00:51:31,450
Tehát ahelyett, hogy a bináris
fa, abban az értelemben, hogy csak egy

1015
00:51:31,450 --> 00:51:35,940
dolog is pont két, akkor már
Egy dolog pont sok-sok dolgot.

1016
00:51:35,940 --> 00:51:39,450
Meg kell főként tömbök
amelynek belsejében tárolt

1017
00:51:39,450 --> 00:51:41,790
mutatók, mely egy másik tömböt.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Tehát a csomópont, hogy hogyan
meghatározná a Trie

1020
00:51:49,460 --> 00:51:52,590
az azt akarjuk, hogy a
Logikai, c szót, ugye?

1021
00:51:52,590 --> 00:51:54,920
Tehát a csomópont logikai
mint igaz vagy hamis,

1022
00:51:54,920 --> 00:51:58,490
Először élén
tömb, ez a szó?

1023
00:51:58,490 --> 00:52:03,620
Másodszor, azt akarjuk, hogy a mutatók
mindenre, amit a többiek is.

1024
00:52:03,620 --> 00:52:07,470
Egy kicsit bonyolult, egy kicsit elvont, de
Meg fogom magyarázni, mi, hogy minden eszközt.

1025
00:52:07,470 --> 00:52:13,800
>> Tehát itt, a tetején, ha
Van egy sor kijelentette már,

1026
00:52:13,800 --> 00:52:17,040
Egy csomópont, ahol van egy logikai
tárolt érték az elülső

1027
00:52:17,040 --> 00:52:19,490
hogy megmondja, hogy ez a szó?

1028
00:52:19,490 --> 00:52:20,520
Ez nem egy szó?

1029
00:52:20,520 --> 00:52:23,240
És akkor már a
többi a tömb

1030
00:52:23,240 --> 00:52:26,040
ténylegesen eltárolja az összes
lehetőségeit, mi lehet az.

1031
00:52:26,040 --> 00:52:28,660
Tehát, például, mint a
a tetején van

1032
00:52:28,660 --> 00:52:32,140
Az első dolog, hogy azt mondja, igaz, vagy
hamis, igen vagy nem, ez az egy szó.

1033
00:52:32,140 --> 00:52:38,130
>> És akkor már 0-tól 26
A levelek tárolható.

1034
00:52:38,130 --> 00:52:42,790
Ha akartam keresni itt
A denevér, megyek a top

1035
00:52:42,790 --> 00:52:49,200
és nézek B. találom B én
tömb, és így tudom, OK, B egy szót?

1036
00:52:49,200 --> 00:52:53,010
B nem egy szó, így tehát
Azt kell tovább keresni.

1037
00:52:53,010 --> 00:52:56,410
Menjek a B, és nézek a
mutatót, hogy a B felé mutat

1038
00:52:56,410 --> 00:53:00,900
és látok egy másik sor információt,
ugyanazt a szerkezetet, hogy a miénk volt.

1039
00:53:00,900 --> 00:53:05,240
>> És here-- ó, a következő
levél [hallhatatlan] az A.

1040
00:53:05,240 --> 00:53:07,210
Szóval nézzük, hogy tömbben.

1041
00:53:07,210 --> 00:53:10,860
Találunk a nyolcadik értéket,
majd megnézzük, hogy, jaj,

1042
00:53:10,860 --> 00:53:12,840
hé, hogy egy szó, van B-A szó?

1043
00:53:12,840 --> 00:53:13,807
Ez nem egy szó.

1044
00:53:13,807 --> 00:53:14,890
Van, hogy keresd.

1045
00:53:14,890 --> 00:53:17,850
>> És akkor nézzük, hogy hol
A mutató az egy pontot,

1046
00:53:17,850 --> 00:53:21,130
és megjegyzi, hogy más módon is
amely már több értéket tárolni.

1047
00:53:21,130 --> 00:53:24,150
És végül eljutunk
B-A-T, amely egy szót.

1048
00:53:24,150 --> 00:53:25,970
És így a következő alkalommal
nézel, te leszel

1049
00:53:25,970 --> 00:53:30,850
is, hogy a csekket a, igen,
ez a logikai függvény igaz.

1050
00:53:30,850 --> 00:53:35,450
És így abban az értelemben mi vagyunk a fajta
Az rendelkező fa tömböket.

1051
00:53:35,450 --> 00:53:39,890
>> Tehát akkor milyen keressen meg.

1052
00:53:39,890 --> 00:53:43,650
Ahelyett hashing egy funkciót, és
értékadásra a láncolt lista,

1053
00:53:43,650 --> 00:53:49,190
ha csak végre egy
Trie, hogy a keresések downwords.

1054
00:53:49,190 --> 00:53:50,850
Nagyon, nagyon bonyolult dolog.

1055
00:53:50,850 --> 00:53:54,060
Nem könnyű gondolkodni, mert olyan vagyok, mint
köpködni számos adat struktúrákat

1056
00:53:54,060 --> 00:53:58,710
rád, de nem mindenki ilyen
megérteni, hogy a logika működik?

1057
00:53:58,710 --> 00:54:01,920
>> OK, hűvös.

1058
00:54:01,920 --> 00:54:05,600
Tehát a B-A-T, majd
fogsz keresni.

1059
00:54:05,600 --> 00:54:07,940
A következő alkalommal fogsz
látni, ó, hé, ez igaz,

1060
00:54:07,940 --> 00:54:09,273
így tudom, hogy ez legyen szó.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Ugyanezt állatkertben.

1063
00:54:13,770 --> 00:54:17,960
Tehát itt van a dolog most, ha
akart keresni állatkertbe, most,

1064
00:54:17,960 --> 00:54:20,780
Jelenleg állatkertben nem
szó, hogy a szótár

1065
00:54:20,780 --> 00:54:25,300
mert, ahogy ti is látni, a
Először is, hogy van egy logikai

1066
00:54:25,300 --> 00:54:28,590
return true van végén zoom.

1067
00:54:28,590 --> 00:54:30,430
Van Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> És így van, akkor valójában nem is
a szó, állatkert, az, hogy a szótár

1069
00:54:33,900 --> 00:54:36,070
mert ez a jelölőnégyzet nincs bejelölve.

1070
00:54:36,070 --> 00:54:39,540
Így a számítógép nem
tudjuk, hogy állatkertben egy szót

1071
00:54:39,540 --> 00:54:42,430
mert az is, hogy mi már
tárolta, csak zoom itt

1072
00:54:42,430 --> 00:54:44,920
valójában egy logikai értéket
hogy a már megfordult igaz.

1073
00:54:44,920 --> 00:54:49,380
Tehát, ha azt akarjuk, hogy helyezze be a
szót, állatkert, figyelembe, hogy a szótár,

1074
00:54:49,380 --> 00:54:51,770
hogyan érjük el ezt csinálod?

1075
00:54:51,770 --> 00:54:55,960
Mit kell tennünk, hogy győződjön meg arról, mi
számítógép tudja, hogy a Z-O-O egy szó

1076
00:54:55,960 --> 00:54:58,130
és nem az első szó a Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> Közönség: [hallható]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI Peng: Pontosan, mi
szeretnénk, hogy győződjön meg arról, hogy ez a

1079
00:55:01,450 --> 00:55:07,890
Itt, hogy logikai érték
pipálni, hogy ez igaz.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, akkor megyünk, hogy ellenőrizze, hogy
így pontosan tudjuk, hé, állatkertben egy szót sem.

1081
00:55:13,297 --> 00:55:15,380
Azt fogom mondani a
számítógép, hogy ez az egy szó, így

1082
00:55:15,380 --> 00:55:18,000
hogy amikor a számítógép ellenőrzi,
tudja, hogy állatkertben egy szót sem.

1083
00:55:18,000 --> 00:55:21,269
>> Mert emlékszem mindezen adatok
struktúrák, akkor nagyon könnyű számunkra

1084
00:55:21,269 --> 00:55:22,310
mondani, ó, a BAT szó.

1085
00:55:22,310 --> 00:55:22,851
Zoo egy szó.

1086
00:55:22,851 --> 00:55:23,611
Zoom egy szó.

1087
00:55:23,611 --> 00:55:25,860
De ha építünk rá,
A számítógép nem tudja.

1088
00:55:25,860 --> 00:55:28,619
>> Tehát meg kell mondani, hogy pontosan
mi pont ez a szó?

1089
00:55:28,619 --> 00:55:29,910
Mi az a pont ez nem egy szó?

1090
00:55:29,910 --> 00:55:31,784
És mi pont tudom
kell keresni a dolgokat,

1091
00:55:31,784 --> 00:55:34,000
és mi pont kell ahhoz, hogy a következő?

1092
00:55:34,000 --> 00:55:37,010
Mindenki egyértelmű, hogy?

1093
00:55:37,010 --> 00:55:39,540
Hűvös.

1094
00:55:39,540 --> 00:55:42,530
>> És akkor jön a
probléma, hogy hogyan tennénk

1095
00:55:42,530 --> 00:55:45,560
menj behelyezésével valamit
hogy valójában nem létezik?

1096
00:55:45,560 --> 00:55:49,090
Tehát mondjuk, szeretnénk beszúrni
a szó, fürdő, a mi Trie.

1097
00:55:49,090 --> 00:55:53,589
Ahogy ti is látni, mint a jelenleg
minden van most a B-A-T,

1098
00:55:53,589 --> 00:55:55,630
és ez az új adatstruktúra
ott volt egy korsó, amely

1099
00:55:55,630 --> 00:55:59,740
Rámutatott, hogy null mert azt feltételezzük
hogy, jaj, nincs szó után a B-A-T,

1100
00:55:59,740 --> 00:56:02,530
miért kell tartani
miután a dolgok után, hogy a T.

1101
00:56:02,530 --> 00:56:06,581
>> De a probléma merül fel, ha nem teszünk Önnek
szeretnénk, hogy egy szó, ami után

1102
00:56:06,581 --> 00:56:07,080
A T.

1103
00:56:07,080 --> 00:56:09,500
Ha van fürdő, te
szeretne majd egy H jogot.

1104
00:56:09,500 --> 00:56:13,290
És így, ahogy mi fogunk tenni, hogy az
fogunk létrehozni egy külön csomópont.

1105
00:56:13,290 --> 00:56:16,840
Mi nem oszt bármilyen mennyiségű
A memória az új tömb,

1106
00:56:16,840 --> 00:56:20,720
és megyünk máshová átirányítani mutatók.

1107
00:56:20,720 --> 00:56:22,947
>> Megyünk rendelheti
H Először is, ez a null,

1108
00:56:22,947 --> 00:56:24,030
fogunk megszabadulni.

1109
00:56:24,030 --> 00:56:26,590
Fogunk van
A H-pont lefelé.

1110
00:56:26,590 --> 00:56:30,600
Ha látunk egy H, azt akarjuk,
hogy menjen máshová.

1111
00:56:30,600 --> 00:56:33,910
>> Itt, akkor ellenőrizze le igen.

1112
00:56:33,910 --> 00:56:38,170
Ha elérünk egy H után T, ó,
akkor tudjuk, hogy ez a szó.

1113
00:56:38,170 --> 00:56:41,110
A logikai fog visszatérni igaz.

1114
00:56:41,110 --> 00:56:42,950
Mindenki tisztában, hogy történhetett?

1115
00:56:42,950 --> 00:56:45,110
OKÉ.

1116
00:56:45,110 --> 00:56:47,214
>> Tehát lényegében az összes
Ezen adatok struktúrák

1117
00:56:47,214 --> 00:56:50,130
hogy eljutottunk addig több mint ma, én már
ment át őket nagyon, nagyon gyorsan

1118
00:56:50,130 --> 00:56:52,192
és nem az, hogy sokkal
részletek és ez rendben.

1119
00:56:52,192 --> 00:56:53,900
Miután elkezdte a Messiás
vele, akkor lesz

1120
00:56:53,900 --> 00:56:55,733
nyomon követése, ahol
minden pointerek,

1121
00:56:55,733 --> 00:56:58,060
mi folyik a
adatstruktúrák, satöbbi.

1122
00:56:58,060 --> 00:56:59,810
Ők lesznek nagyon hasznos,
és ez rajtad múlik

1123
00:56:59,810 --> 00:57:03,890
srácok, hogy teljesen kitalálni, hogyan
azt szeretné, hogy végre a dolgokat.

1124
00:57:03,890 --> 00:57:07,650
>> És így pset4, a 5-- ó, hogy rossz.

1125
00:57:07,650 --> 00:57:10,140
Pset5 a helyesírási hibák.

1126
00:57:10,140 --> 00:57:13,710
Mint már mondtam, fogsz, ha egyszer
újra letölteni a forráskódot tőlünk.

1127
00:57:13,710 --> 00:57:16,210
Ott lesz három fő
Ez az, amire lehet letölteni.

1128
00:57:16,210 --> 00:57:18,470
Majd letölthető szótárak,
KERS, és a szövegeket.

1129
00:57:18,470 --> 00:57:21,660
>> Mindazok a dolgok vannak
sem szótárak a szavak

1130
00:57:21,660 --> 00:57:25,190
hogy azt akarom, hogy ellenőrizze
vagy vizsgálati információk

1131
00:57:25,190 --> 00:57:26,930
hogy szeretnénk, ha a helyesírás-ellenőrző.

1132
00:57:26,930 --> 00:57:29,670
És így a szótárak
adunk fogsz

1133
00:57:29,670 --> 00:57:34,870
hogy az Ön aktuális szó, hogy szeretnénk
tárolását valahogy oly módon, hogy az

1134
00:57:34,870 --> 00:57:36,530
hatékonyabb, mint egy tömb.

1135
00:57:36,530 --> 00:57:38,470
És akkor a szövegek
lesz, amit mi

1136
00:57:38,470 --> 00:57:43,900
megkérdezi, hogy pontosan ellenőrizze, hogy
Minden a szavait vannak valós szavakat.

1137
00:57:43,900 --> 00:57:47,970
>> És így a három blokk
programok, akkor adunk Önnek

1138
00:57:47,970 --> 00:57:51,130
nevezzük dictionary.c,
dictionary.h, és speller.c.

1139
00:57:51,130 --> 00:57:56,500
És így az egész dictionary.c tesz,
amit kért, hogy hajtsák végre.

1140
00:57:56,500 --> 00:57:57,880
Betölti szó.

1141
00:57:57,880 --> 00:58:02,000
Ez helyesírás ellenőrzést őket, és ez biztosítja,
hogy minden megfelelően van behelyezve.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h csak egy könyvtár fájl
hogy kijelenti mindazokat a funkciókat.

1143
00:58:05,180 --> 00:58:07,650
És speller.c, fogunk adni.

1144
00:58:07,650 --> 00:58:09,290
Önnek nem kell módosítani semmit.

1145
00:58:09,290 --> 00:58:14,290
Minden speller.c jelent az, hogy ezt,
betölti azt, sebességét ellenőrzi azt,

1146
00:58:14,290 --> 00:58:19,190
teszteli a benchmark, mint hogy hogyan
Gyorsan te képes csinálni a dolgokat.

1147
00:58:19,190 --> 00:58:20,410
>> Ez egy helyesírás.

1148
00:58:20,410 --> 00:58:23,920
Csak ne szórakozz vele, de hogy
Biztosan érti, hogy mit csinál.

1149
00:58:23,920 --> 00:58:28,090
Az általunk használt nevezett funkció getrusage, hogy
teszteli a teljesítményét a varázslat

1150
00:58:28,090 --> 00:58:28,590
ellenőrzőt.

1151
00:58:28,590 --> 00:58:32,200
Csak annyit tesz, alapvetően tesztelésére
ideje mindent a szótárban,

1152
00:58:32,200 --> 00:58:33,680
úgyhogy győződjön meg róla, hogy te érted.

1153
00:58:33,680 --> 00:58:36,660
Legyen óvatos, hogy ne szórakozz vele, vagy
más dolgok nem fog megfelelően futni.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> És ennek nagy része Kihívást jelent
srácok, hogy valóban módosítani dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Megyünk, hogy az Ön
140.000 szavak szótára.

1157
00:58:48,526 --> 00:58:50,900
Fogunk kapsz egy szöveges
fájlt, amely ezeket a szavakat,

1158
00:58:50,900 --> 00:58:54,840
és azt szeretnénk, ha meg tudjuk szervezni
őket egy hash tábla vagy Trie

1159
00:58:54,840 --> 00:58:58,140
mert amikor azt kérjük, hogy pontosan
check-- elképzelni, ha varázslat

1160
00:58:58,140 --> 00:59:00,690
ellenőrzésére, mint Homérosz Odüsszeia.

1161
00:59:00,690 --> 00:59:03,010
Ez olyan, mint ez a hatalmas, óriási tesztet.

1162
00:59:03,010 --> 00:59:05,190
>> Képzeld el, ha minden egyes
szó, amit meg kellett nézni

1163
00:59:05,190 --> 00:59:08,100
keresztül egy sor 140.000 értékeket.

1164
00:59:08,100 --> 00:59:10,350
Ez lenne, hogy örökre
a gép futtatására.

1165
00:59:10,350 --> 00:59:14,490
Ezért is szeretnénk szervezni a
adatok hatékonyabb adatszerkezetek

1166
00:59:14,490 --> 00:59:17,270
például egy hash tábla vagy Trie.

1167
00:59:17,270 --> 00:59:20,700
És akkor ti is egyfajta
A keresés esetén elérhető

1168
00:59:20,700 --> 00:59:22,570
dolgokat könnyebben és gyorsabban.

1169
00:59:22,570 --> 00:59:24,934
>> És ezért legyen óvatos, hogy megoldja ütközések.

1170
00:59:24,934 --> 00:59:27,350
Fogsz kapni egy csomó
A szavai kezdetű A.

1171
00:59:27,350 --> 00:59:29,957
Fogsz kapni egy csomó szó
kezdetű B. Akár te

1172
00:59:29,957 --> 00:59:31,290
srácok hogyan szeretné megoldani azt.

1173
00:59:31,290 --> 00:59:34,144
Talán van még
hatékony hash függvény

1174
00:59:34,144 --> 00:59:36,810
mint az első betű
valamit, és így rajtad múlik

1175
00:59:36,810 --> 00:59:38,190
srácok, hogy milyen csinálsz, amit akarsz.

1176
00:59:38,190 --> 00:59:40,148
>> Talán szeretne hozzáadni
összes betűt együtt.

1177
00:59:40,148 --> 00:59:43,410
Lehet, hogy szeretne tetszik csinálni furcsa dolgokat
hogy számot a betűk száma,

1178
00:59:43,410 --> 00:59:43,970
bármi.

1179
00:59:43,970 --> 00:59:45,386
Akár srácok hogyan akarsz csinálni.

1180
00:59:45,386 --> 00:59:49,262
Ha azt szeretnénk, hogy csinál egy hash tábla, ha
szeretnék kipróbálni egy Trie, teljesen rajtad múlik.

1181
00:59:49,262 --> 00:59:52,470
Én figyelmezteti Önt idő előtt, hogy a
Trie jellemzően egy kicsit nehezebb

1182
00:59:52,470 --> 00:59:54,520
csak azért, mert van egy csomó
több mutató nyomon követni.

1183
00:59:54,520 --> 00:59:55,645
De teljesen rajtad múlik srácok.

1184
00:59:55,645 --> 00:59:58,742
Ez sokkal hatékonyabb
a legtöbb esetben.

1185
00:59:58,742 --> 01:00:01,450
Azt akarod, hogy valóban képes tartani
követhetjük a mutatók.

1186
01:00:01,450 --> 01:00:03,850
Mint ugyanezt csinálja
hogy csinálok itt.

1187
01:00:03,850 --> 01:00:06,871
Ha akarsz beszúrni
értékeket egy hash tábla vagy törölni,

1188
01:00:06,871 --> 01:00:08,620
győződjön meg róla, hogy te
Tényleg nyomon követése

1189
01:00:08,620 --> 01:00:11,860
ahol minden azért van, mert
ez nagyon egyszerű, mert ha én vagyok

1190
01:00:11,860 --> 01:00:14,727
próbál beszúrni, mint a szó, Andy.

1191
01:00:14,727 --> 01:00:16,810
Mondjuk azt, hogy ez egy
igazi szó, a szó, Andy,

1192
01:00:16,810 --> 01:00:19,640
egy hatalmas listát A szavak.

1193
01:00:19,640 --> 01:00:22,450
>> Ha én csak véletlenül átminősítése
egy mutató rossz, hoppá,

1194
01:00:22,450 --> 01:00:24,940
ott megy a teljes egészében
A többi az én láncolt lista.

1195
01:00:24,940 --> 01:00:26,897
Most az egyetlen szó, amit
van Andy, és most

1196
01:00:26,897 --> 01:00:29,230
az összes többi szavakat a
Szótár elvesztek.

1197
01:00:29,230 --> 01:00:31,370
És így azt szeretnénk, hogy győződjön meg róla,
nyomon követni az összes mutató

1198
01:00:31,370 --> 01:00:33,661
különben meg fogsz kapni
hatalmas gondok vannak a kódot.

1199
01:00:33,661 --> 01:00:35,840
Döntetlen a dolgokat alaposan, lépésről lépésre.

1200
01:00:35,840 --> 01:00:37,870
Azt teszi, hogy sokkal könnyebb gondolni.

1201
01:00:37,870 --> 01:00:40,910
>> És végül, azt szeretné, hogy képes legyen
tesztelje a teljesítményét a programot

1202
01:00:40,910 --> 01:00:41,618
a táblán.

1203
01:00:41,618 --> 01:00:43,710
Ha a srácok, hogy egy
nézd meg CS50 most,

1204
01:00:43,710 --> 01:00:45,210
mi nevezzük a nagy táblára.

1205
01:00:45,210 --> 01:00:50,200
Ez a ponttáblára a leggyorsabb
helyesírás-ellenőrzés alkalommal minden a CS50

1206
01:00:50,200 --> 01:00:55,720
most, azt hiszem, a felső, mint 10
alkalommal azt hiszem, nyolc közülük személyzet.

1207
01:00:55,720 --> 01:00:57,960
Valóban szeretnénk srácok verni minket.

1208
01:00:57,960 --> 01:01:00,870
>> Mindannyiunkat igyekszünk végrehajtani
a leggyorsabb kódot, mint lehetséges.

1209
01:01:00,870 --> 01:01:04,880
Szeretnénk, ha a srácok, hogy megpróbálja megtámadni
velünk, és végrehajtása gyorsabb, mint mindannyiunk

1210
01:01:04,880 --> 01:01:05,550
tud.

1211
01:01:05,550 --> 01:01:07,970
És így ez valóban
az első alkalom, hogy mi vagyunk

1212
01:01:07,970 --> 01:01:12,680
kérve srácok, hogy nem egy PSET, hogy
akkor tényleg bármilyen módszerrel

1213
01:01:12,680 --> 01:01:13,760
akarsz.

1214
01:01:13,760 --> 01:01:17,730
>> Mindig azt mondom, ez inkább hasonlít
hogy egy valós megoldást, igaz?

1215
01:01:17,730 --> 01:01:19,550
Azt mondják, hé, szükségem van rád, hogy ezt.

1216
01:01:19,550 --> 01:01:21,380
Építeni egy program, amely nem ezt nekem.

1217
01:01:21,380 --> 01:01:22,630
Csináld, ahogy akarod.

1218
01:01:22,630 --> 01:01:24,271
Csak azt tudom, hogy én akarom, hogy gyors.

1219
01:01:24,271 --> 01:01:25,770
Ez a kihívás ezen a héten.

1220
01:01:25,770 --> 01:01:27,531
Srácok, megyünk
hogy kapsz egy feladatot.

1221
01:01:27,531 --> 01:01:29,030
Fogunk kapsz egy kihívás.

1222
01:01:29,030 --> 01:01:31,559
És akkor ez akár a srácok
hogy teljesen csak kitalálni

1223
01:01:31,559 --> 01:01:34,100
mi a leggyorsabb és
hatékony módja annak, hogy végre ezt.

1224
01:01:34,100 --> 01:01:34,600
Igen?

1225
01:01:34,600 --> 01:01:37,476
>> Közönség: Megengedi, ha
akart kutatás gyorsabb módja

1226
01:01:37,476 --> 01:01:40,821
csinálni hash táblák online tehetünk
hogy és idézik valaki másnak a kódot?

1227
01:01:40,821 --> 01:01:42,070
ANDI Peng: Igen, teljesen jól.

1228
01:01:42,070 --> 01:01:44,320
Tehát, ha a srácok olvassa el a
spec, van egy határ

1229
01:01:44,320 --> 01:01:48,310
a spec, amely azt mondja, srácok
teljesen mentesek a kutatás hash

1230
01:01:48,310 --> 01:01:51,070
funkciók mik
A gyorsabb hash függvények

1231
01:01:51,070 --> 01:01:54,720
futtatni a dolgokat, mint
Amíg arra hivatkoznak, hogy kódot.

1232
01:01:54,720 --> 01:01:57,220
Tehát egyesek már
kitalálta gyors módja

1233
01:01:57,220 --> 01:02:00,250
csinál helyesírás-ellenőrző, a gyors
módjait információ tárolására.

1234
01:02:00,250 --> 01:02:02,750
Teljesen rajtad múlik srácok, ha
szeretnénk, hogy csak úgy, hogy, ugye?

1235
01:02:02,750 --> 01:02:04,045
Győződjön meg róla hivatkozva.

1236
01:02:04,045 --> 01:02:06,170
A kihívás itt tényleg
hogy próbálunk tesztelni

1237
01:02:06,170 --> 01:02:09,750
ügyelve arra, hogy tudod,
magad körül mutatók.

1238
01:02:09,750 --> 01:02:12,700
Amennyire csak végrehajtási
a tényleges hash függvény

1239
01:02:12,700 --> 01:02:15,070
és jön, mint
A matematikai erre,

1240
01:02:15,070 --> 01:02:17,570
srácok a kutatás bármi
módszerek Online akartok.

1241
01:02:17,570 --> 01:02:17,996
Igen?

1242
01:02:17,996 --> 01:02:19,700
>> Közönség: Meg tudjuk idézni csak
használja a [hallhatatlan]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI Peng: Igen.

1244
01:02:20,120 --> 01:02:22,328
Tudod csak, itt a magyarázat,
akkor idézni, mint, ó,

1245
01:02:22,328 --> 01:02:26,127
kivett yada, blabla,
blabla, hash függvény.

1246
01:02:26,127 --> 01:02:27,210
Bárki bármilyen kérdése?

1247
01:02:27,210 --> 01:02:29,694
Igazából libbent
a szekció ma.

1248
01:02:29,694 --> 01:02:31,610
Én leszek itt, hogy
válaszoljon a kérdésekre is.

1249
01:02:31,610 --> 01:02:36,570
>> Is, mint mondtam, irodai
órát ma és holnap.

1250
01:02:36,570 --> 01:02:40,307
A specifikáció ezen a héten valóban
szuper könnyű és szuper rövid olvasni.

1251
01:02:40,307 --> 01:02:43,140
Azt javasoljuk, hogy egy pillantást, csak
olvassa el a teljes egészében meg.

1252
01:02:43,140 --> 01:02:45,730
>> És Zamyla ténylegesen végigvezet
keresztül minden egyes funkciók

1253
01:02:45,730 --> 01:02:49,796
meg kell végrehajtani, és így
Nagyon, nagyon világos, hogyan kell csinálni mindent.

1254
01:02:49,796 --> 01:02:51,920
Csak azért, hogy győződjön meg róla,
követi nyomon a mutatók.

1255
01:02:51,920 --> 01:02:53,650
Ez egy nagyon nehéz PSET.

1256
01:02:53,650 --> 01:02:56,744
>> Ez nem támadja, mert tetszik,
ó, a fogalmak sokkal több

1257
01:02:56,744 --> 01:02:59,160
nehéz, vagy meg kell tanulni
annyira új szintaxist az utat

1258
01:02:59,160 --> 01:03:00,650
hogy te az utolsó PSET.

1259
01:03:00,650 --> 01:03:03,320
Ez PSET nehéz, mert
olyan sok mutató,

1260
01:03:03,320 --> 01:03:06,980
és akkor nagyon, nagyon könnyen egyszer
Van egy hiba a kód nem lesz képes

1261
01:03:06,980 --> 01:03:08,315
találni, ahol ez a bogár van.

1262
01:03:08,315 --> 01:03:13,200
>> És így teljes és tökéletes benned
srácok, hogy képes legyen legyőzni [hallhatatlan]

1263
01:03:13,200 --> 01:03:13,700
szócikk.

1264
01:03:13,700 --> 01:03:16,640
Igazából már nem olyan írásos bányában
még, de én vagyok arról, hogy írjon az enyém.

1265
01:03:16,640 --> 01:03:19,070
Tehát miközben írsz
tiéd, én leszek az írás az enyém.

1266
01:03:19,070 --> 01:03:21,070
Én fogom próbálni, hogy
az enyém gyorsabb, mint a tiéd.

1267
01:03:21,070 --> 01:03:23,940
Meglátjuk, aki a leggyorsabb.

1268
01:03:23,940 --> 01:03:27,340
>> És igen, én is látni az összes
srácok itt kedden.

1269
01:03:27,340 --> 01:03:29,510
Futok egyfajta mint egy PSET műhely.

1270
01:03:29,510 --> 01:03:32,640
Az összes szakasz ezen
heti PSET műhelyek,

1271
01:03:32,640 --> 01:03:36,690
így a srácok sok lehetőséget
segítségért, hivatali időben, mint mindig,

1272
01:03:36,690 --> 01:03:41,330
és én nagyon várom, hogy
elolvasás a srácok "kódot.

1273
01:03:41,330 --> 01:03:44,160
Van vetélkedők ide, ha
srácok akarnak jönni kap e.

1274
01:03:44,160 --> 01:03:45,880
Ez minden.

1275
01:03:45,880 --> 01:03:48,180