1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:05,120
[Zenelejátszó]

3
00:00:05,120 --> 00:00:12,026

4
00:00:12,026 --> 00:00:12,900
SPEAKER 1: Rendben.

5
00:00:12,900 --> 00:00:14,600
Mindenki szívesen vissza a szakasz.

6
00:00:14,600 --> 00:00:18,660
Remélem mindenki sikeresen
visszanyert kvíz

7
00:00:18,660 --> 00:00:19,510
a múlt héten.

8
00:00:19,510 --> 00:00:22,564
Tudom, hogy egy kicsit őrült időnként.

9
00:00:22,564 --> 00:00:25,230
Ahogy mondtam korábban, ha
a szórás,

10
00:00:25,230 --> 00:00:28,188
Nem igazán aggódni, főleg
a kevésbé kellemes rész.

11
00:00:28,188 --> 00:00:30,230
Ez az, hogy hol legyen.

12
00:00:30,230 --> 00:00:32,850
>> Ha nem nagy, akkor félelmetes.

13
00:00:32,850 --> 00:00:33,650
Kudos neked.

14
00:00:33,650 --> 00:00:36,149
És ha úgy érzi, mint amire szükség van
egy kicsit több segítséget, kérem

15
00:00:36,149 --> 00:00:38,140
nyugodtan, hogy elérje
ki, hogy bármely, a TF.

16
00:00:38,140 --> 00:00:40,030
Mindannyian itt, hogy segítsünk.

17
00:00:40,030 --> 00:00:40,960
>> Ezért tanítunk.

18
00:00:40,960 --> 00:00:44,550
Ezért vagyok itt, minden hétfőn az Ön számára
fiúk és munkaidőn csütörtökönként.

19
00:00:44,550 --> 00:00:48,130
Tehát ne habozzon, hogy tudassa velem
Ha aggódsz valami

20
00:00:48,130 --> 00:00:52,450
vagy ha van valami a kvíz
hogy tényleg szeretnék foglalkozni.

21
00:00:52,450 --> 00:00:56,940
>> Így hát a menetrend ma is
szól adatszerkezeteket.

22
00:00:56,940 --> 00:01:01,520
Néhány ezek közül csak lesz csak
hogy neked megismerjék ezeket.

23
00:01:01,520 --> 00:01:04,870
Lehet, hogy soha nem végre
őket ebben az osztályban.

24
00:01:04,870 --> 00:01:08,690
Néhányan közülük úgy tetszik,
mint a helyesírás PSET.

25
00:01:08,690 --> 00:01:11,380
>> Itt van a választás
között hash táblák és próbál.

26
00:01:11,380 --> 00:01:13,680
Szóval akkor biztosan megy át azokat.

27
00:01:13,680 --> 00:01:18,690
Ez lesz minden bizonnyal több fajta
a magas szintű szakasz ma, mégis,

28
00:01:18,690 --> 00:01:22,630
mert van egy csomó közülük, és ha
bementünk a végrehajtás részleteit

29
00:01:22,630 --> 00:01:26,490
Az összes ilyen, mi nem
még átjutni láncolt listák

30
00:01:26,490 --> 00:01:28,520
és talán egy kicsit a hash táblák.

31
00:01:28,520 --> 00:01:31,200
>> Tehát medve velem.

32
00:01:31,200 --> 00:01:33,530
Nem fogunk, hogy csinál
annyi kódoló ebben az időben.

33
00:01:33,530 --> 00:01:36,870
Ha bármilyen kérdése van az
vagy szeretne látni végre

34
00:01:36,870 --> 00:01:39,260
vagy próbáld ki magad,
Azt ajánlom

35
00:01:39,260 --> 00:01:44,250
megy study.cs50.net, amely
példákat az összes ilyen.

36
00:01:44,250 --> 00:01:46,400
Ez lesz az én PowerPoint
az megállapítja, hogy mi

37
00:01:46,400 --> 00:01:50,860
hajlanak arra, valamint néhány programozás
gyakorlatok, különösen a dolgok

38
00:01:50,860 --> 00:01:55,250
mint láncolt listák és bináris
fák és halmok dákó.

39
00:01:55,250 --> 00:01:59,590
Szóval kicsit magas, ami
jó lenne srácok.

40
00:01:59,590 --> 00:02:01,320
>> Tehát, hogy mi lesz az induláshoz.

41
00:02:01,320 --> 00:02:03,060
És azt is, yes-- vetélkedők.

42
00:02:03,060 --> 00:02:06,550
Azt hiszem, a legtöbben, akik a
én szakasz már a vetélkedők,

43
00:02:06,550 --> 00:02:12,060
de valaki jön, vagy valamilyen okból
nem, ők itt az első.

44
00:02:12,060 --> 00:02:12,740
>> Így kapcsolt listák.

45
00:02:12,740 --> 00:02:15,650
Tudom, hogy ez a fajta megy
vissza, mielőtt a kvíz.

46
00:02:15,650 --> 00:02:17,940
Ez volt a megelőző héten
hogy tanultunk erről.

47
00:02:17,940 --> 00:02:21,040
De ebben az esetben, akkor csak
megy egy kicsit mélyrehatóbban.

48
00:02:21,040 --> 00:02:25,900
>> Akkor miért lehet választani a
láncolt lista felett egy tömb?

49
00:02:25,900 --> 00:02:27,130
Mi különbözteti meg őket?

50
00:02:27,130 --> 00:02:27,630
Igen?

51
00:02:27,630 --> 00:02:30,464
>> KÖZÖNSÉG: bővítheti a kapcsolt
bejegyzés szemben egy tömb mérete rögzített.

52
00:02:30,464 --> 00:02:31,171
SPEAKER 1: Jobb.

53
00:02:31,171 --> 00:02:33,970
Egy tömb rögzített méretű, míg a
láncolt lista változtatható mérettel rendelkezik.

54
00:02:33,970 --> 00:02:36,970
Tehát, ha nem tudjuk, hogyan
nagyon szeretnénk tárolni,

55
00:02:36,970 --> 00:02:39,880
a kapcsolt listát ad nekünk egy nagy
módja, hogy azért, mert mi is csak

56
00:02:39,880 --> 00:02:43,730
add másik csomóponton és add tovább
másik csomópont és adjunk hozzá egy másik csomóponton.

57
00:02:43,730 --> 00:02:45,750
De mi lehet a kompromisszum?

58
00:02:45,750 --> 00:02:49,521
Tudja valaki emlékszik a trade-off
között tömbök és a kapcsolt listák?

59
00:02:49,521 --> 00:02:50,020
Mmhmm?

60
00:02:50,020 --> 00:02:51,460
>> KÖZÖNSÉG: Meg kell
menjen végig az úton

61
00:02:51,460 --> 00:02:53,738
a láncolt lista
talál egy elemet a listában.

62
00:02:53,738 --> 00:02:55,570
Egy sor, akkor
csak talál egy elemet.

63
00:02:55,570 --> 00:02:56,278
>> SPEAKER 1: Jobb.

64
00:02:56,278 --> 00:02:57,120
Tehát arrays--

65
00:02:57,120 --> 00:02:58,500
>> KÖZÖNSÉG: [hallható].

66
00:02:58,500 --> 00:03:01,090
>> SPEAKER 1: A tömbök, mi
az úgynevezett véletlen hozzáférés.

67
00:03:01,090 --> 00:03:04,820
Azt jelenti, hogy ha azt akarjuk, hogy mi
mindig az ötödik pont a lista

68
00:03:04,820 --> 00:03:07,230
vagy az ötödik pont a mi
tömb, mi csak fogd meg.

69
00:03:07,230 --> 00:03:10,440
Ha ez a láncolt lista, van
végiglépkedhetünk, ugye?

70
00:03:10,440 --> 00:03:14,020
Tehát hozzáférés egy elem
Egy tömb konstans idő,

71
00:03:14,020 --> 00:03:19,530
míg a kapcsolt listát is lenne
valószínűleg a lineáris idő, mert talán

72
00:03:19,530 --> 00:03:21,370
mi elem is egészen a végén.

73
00:03:21,370 --> 00:03:23,446
Meg kell keresni mindent.

74
00:03:23,446 --> 00:03:25,320
Tehát mind ezek az adatok
szerkezetek megyünk

75
00:03:25,320 --> 00:03:29,330
kell eltölteni egy kis időt a,
mi a pluses és negatívok.

76
00:03:29,330 --> 00:03:31,480
Ha lehet, szeretnénk
használja, mint a másik?

77
00:03:31,480 --> 00:03:34,970
És ez a fajta a
nagyobb dolog, hogy vegye el.

78
00:03:34,970 --> 00:03:40,140
>> Tehát itt a
meghatározása a csomópont.

79
00:03:40,140 --> 00:03:43,040
Ez olyan, mint egy eleme
a láncolt lista, ugye?

80
00:03:43,040 --> 00:03:46,180
Tehát mind ismerős
a mi typedef struktúrákat,

81
00:03:46,180 --> 00:03:47,980
amely mentünk át felülvizsgálat utoljára.

82
00:03:47,980 --> 00:03:53,180
Ez alapvetően csak létre
más adattípusok, hogy mi lehetett használni.

83
00:03:53,180 --> 00:03:57,930
>> És ebben az esetben, ez néhány csomópont
hogy tart néhány egész szám.

84
00:03:57,930 --> 00:04:00,210
És akkor mi van a második rész itt?

85
00:04:00,210 --> 00:04:03,192

86
00:04:03,192 --> 00:04:05,677
Valaki?

87
00:04:05,677 --> 00:04:06,680
>> KÖZÖNSÉG: [hallható].

88
00:04:06,680 --> 00:04:07,020
>> SPEAKER 1: Igen.

89
00:04:07,020 --> 00:04:08,400
Ez egy mutató a következő csomópont.

90
00:04:08,400 --> 00:04:12,610
Tehát ez valójában itt.

91
00:04:12,610 --> 00:04:18,790
Ez a mutató a típus
csomópont a következő dolog.

92
00:04:18,790 --> 00:04:22,410
És ez az, amit
magában foglalja a csomópont.

93
00:04:22,410 --> 00:04:24,060
Cool.

94
00:04:24,060 --> 00:04:29,390
>> Rendben, a keresés, mint mi voltunk
csak azt mondom, mielőtt kezét, ha

95
00:04:29,390 --> 00:04:31,840
fog keresni,
van, hogy valóban navigálhat

96
00:04:31,840 --> 00:04:33,660
át a láncolt lista.

97
00:04:33,660 --> 00:04:38,530
Tehát, ha keresünk a szám
9., mi lenne kezdődik a fejünk

98
00:04:38,530 --> 00:04:41,520
és hogy mutat nekünk az elején
mi láncolt lista, ugye?

99
00:04:41,520 --> 00:04:44,600
És azt mondjuk, rendben van, nem ez a
node tartalmazza a 9-es szám?

100
00:04:44,600 --> 00:04:45,690
Nem?

101
00:04:45,690 --> 00:04:47,500
>> Rendben, menj a következőre.

102
00:04:47,500 --> 00:04:48,312
Kövesse azt.

103
00:04:48,312 --> 00:04:49,520
Vajon tartalmaz a 9-es szám?

104
00:04:49,520 --> 00:04:50,570
Nem.

105
00:04:50,570 --> 00:04:51,550
Kövesse a következő.

106
00:04:51,550 --> 00:04:55,490
>> Tehát ténylegesen navigálhat
keresztül láncolt lista.

107
00:04:55,490 --> 00:05:00,070
Nem csak megy egyenesen, ahol 9.

108
00:05:00,070 --> 00:05:05,860
És ha ti valóban szeretne
látni néhány pszeudo-kód odafent.

109
00:05:05,860 --> 00:05:10,420
Van néhány keresési funkció itt
vevő in-- mit tart be?

110
00:05:10,420 --> 00:05:13,110

111
00:05:13,110 --> 00:05:14,320
Ön mit gondol?

112
00:05:14,320 --> 00:05:15,960
Így könnyű.

113
00:05:15,960 --> 00:05:17,784
Mi ez?

114
00:05:17,784 --> 00:05:18,700
KÖZÖNSÉG: [hallható].

115
00:05:18,700 --> 00:05:20,366
SPEAKER 1: Az a szám, amit keresünk.

116
00:05:20,366 --> 00:05:20,980
Jobb?

117
00:05:20,980 --> 00:05:22,875
És mi lenne ez felel meg?

118
00:05:22,875 --> 00:05:25,020
Ez egy mutatót?

119
00:05:25,020 --> 00:05:26,000
>> KÖZÖNSÉG: A csomópont.

120
00:05:26,000 --> 00:05:28,980
>> SPEAKER 1: A csomópont a listára
hogy keresünk, igaz?

121
00:05:28,980 --> 00:05:33,700
Tehát van néhány csomópont mutató itt.

122
00:05:33,700 --> 00:05:37,240
Ez az a pont, hogy fog
tulajdonképpen halad végig a listát.

123
00:05:37,240 --> 00:05:39,630
Mi meg azt egyenlő a listára
mert ez csak

124
00:05:39,630 --> 00:05:44,380
beállítás, hogy egyenlő a
kezdete a láncolt lista.

125
00:05:44,380 --> 00:05:50,660
>> És bár ez nem NULL, míg
még mindig a dolgokat listánkon,

126
00:05:50,660 --> 00:05:55,580
nézze meg, ha azt csomópont
a szám keresünk.

127
00:05:55,580 --> 00:05:57,740
Vissza igaz.

128
00:05:57,740 --> 00:06:01,070
Egyébként frissíti azt, ugye?

129
00:06:01,070 --> 00:06:04,870
>> Ha ez NULL, akkor lépjen ki a
while ciklus és return false

130
00:06:04,870 --> 00:06:08,340
mert ez azt jelenti, hogy nem találtam meg.

131
00:06:08,340 --> 00:06:11,048
Mindenki kap, hogy hogyan működik?

132
00:06:11,048 --> 00:06:11,548
OK.

133
00:06:11,548 --> 00:06:14,940

134
00:06:14,940 --> 00:06:20,260
>> Tehát beillesztés, akkor
Három különböző módon.

135
00:06:20,260 --> 00:06:25,250
Ön neve elé, akkor fűzze
és szúrhat be válogatott.

136
00:06:25,250 --> 00:06:28,215
Ebben az esetben, mi vagyunk
csinálni egy elő-.

137
00:06:28,215 --> 00:06:33,380
Tudja valaki, hogy ezek a
Három esetben eltérő lehet?

138
00:06:33,380 --> 00:06:36,920
>> Tehát azt jelenti, hogy átadjuk tesz
azt az első a listán.

139
00:06:36,920 --> 00:06:39,770
Tehát ez azt jelenti, hogy nem számít,
mi a csomópont, nem számít,

140
00:06:39,770 --> 00:06:43,160
mi az érték, mész
hogy azt itt előtte, OK?

141
00:06:43,160 --> 00:06:45,160
Ez lesz az első
elem a listában.

142
00:06:45,160 --> 00:06:49,510
>> Ha hozzáfűzi, ez megy
hogy menjen vissza az a lista.

143
00:06:49,510 --> 00:06:54,010
És helyezze válogatott azt jelenti, te
megy, hogy valóban arra a helyre,

144
00:06:54,010 --> 00:06:57,700
hol tartja a láncolt lista rendezésre.

145
00:06:57,700 --> 00:07:00,810
Ismét hogyan használja
e és ha használja

146
00:07:00,810 --> 00:07:02,530
őket függ az Ön esetében.

147
00:07:02,530 --> 00:07:05,834

148
00:07:05,834 --> 00:07:07,750
Ha nem kell, hogy
rendezhetők, elő- hajlamos

149
00:07:07,750 --> 00:07:10,460
hogy amit a legtöbb ember
használni, mert nem

150
00:07:10,460 --> 00:07:15,680
kell, hogy menjen át a teljes lista
találni a végén, hogy add meg, igaz?

151
00:07:15,680 --> 00:07:17,720
Tudod csak kibír ez jobb.

152
00:07:17,720 --> 00:07:21,930
>> Így megy keresztül
1 beillesztés most.

153
00:07:21,930 --> 00:07:26,360
Tehát az egyik dolog, hogy megyek
nagyon ajánlom ezt a PSET

154
00:07:26,360 --> 00:07:29,820
hogy felhívja a dolgokat, mint mindig.

155
00:07:29,820 --> 00:07:35,130
Nagyon fontos, hogy frissítse
A mutatók a megfelelő sorrendben

156
00:07:35,130 --> 00:07:38,620
mert ha frissíti őket
kissé ki annak érdekében,

157
00:07:38,620 --> 00:07:42,210
fogsz a végén
vesztes részei a lista.

158
00:07:42,210 --> 00:07:49,680
>> Így például, ebben az esetben, vagyunk
mondja a fejét, hogy csak 1 pont.

159
00:07:49,680 --> 00:07:56,070
Ha csak tehetem
mentés nélkül ez 1,

160
00:07:56,070 --> 00:07:58,570
fogalmunk sincs, hogy mi
1 mutatnia kellene most

161
00:07:58,570 --> 00:08:02,490
mert elvesztettük mi
a fej mutatott.

162
00:08:02,490 --> 00:08:05,530
Tehát az egyik dolog, hogy emlékezzen
ha csinálsz egy elő-

163
00:08:05,530 --> 00:08:09,630
az, hogy mentse, ami a
fejjel pont az első,

164
00:08:09,630 --> 00:08:15,210
akkor újra ki kell jelölni, majd frissítse
mi az új csomópontot kell mutatnia.

165
00:08:15,210 --> 00:08:20,870

166
00:08:20,870 --> 00:08:22,560
Ebben az esetben, ez az egyik módja annak, hogy csináld.

167
00:08:22,560 --> 00:08:25,440
>> Tehát, ha azt tette ezt így
ahol csak újraosztani fej,

168
00:08:25,440 --> 00:08:30,320
elveszítjük alapvetően a
teljes lista, ugye?

169
00:08:30,320 --> 00:08:38,000
Az egyik módja, hogy az, hogy az 1. pont
következő, és ezt követően fej pont 1.

170
00:08:38,000 --> 00:08:42,650
Vagy meg tudod csinálni olyan, mint a
átmeneti tárolás, amit beszéltem.

171
00:08:42,650 --> 00:08:45,670
>> De átcsoportosítása a
mutatók a megfelelő sorrendben

172
00:08:45,670 --> 00:08:48,750
lesz nagyon, nagyon
fontos ez PSET.

173
00:08:48,750 --> 00:08:53,140
Ellenkező esetben, akkor lesz egy hash
tábla vagy egy próbát, ami csak lesz

174
00:08:53,140 --> 00:08:56,014
csak egy része a szavak, amit
szeretne, majd you're-- mmhmm?

175
00:08:56,014 --> 00:08:58,930
KÖZÖNSÉG: Mi volt az ideiglenes
tárolás dolog amiről beszélt?

176
00:08:58,930 --> 00:09:00,305
SPEAKER 1: az átmeneti tárolás.

177
00:09:00,305 --> 00:09:02,760
Tehát alapvetően egy másik
módja, hogy ezt

178
00:09:02,760 --> 00:09:07,650
A tárolja a fejét valami, mint
tárolja az ideiglenes változó.

179
00:09:07,650 --> 00:09:11,250
Rendelje meg 1 és
majd frissítse az 1. pont

180
00:09:11,250 --> 00:09:13,830
hogy bármilyen head használt mutatnak.

181
00:09:13,830 --> 00:09:16,920
Így nyilvánvalóan
elegánsabb, mert

182
00:09:16,920 --> 00:09:20,770
nem kell ideiglenes érték, de
csak újabb lehetőséget, hogy csináld.

183
00:09:20,770 --> 00:09:23,999

184
00:09:23,999 --> 00:09:25,790
És valóban van
néhány kód.

185
00:09:25,790 --> 00:09:28,080
Tehát láncolt lista, mi
valóban van némi kódot.

186
00:09:28,080 --> 00:09:31,930
Tehát itt beilleszteni, ez elé írott.

187
00:09:31,930 --> 00:09:34,290
Szóval ez beírja a fejét.

188
00:09:34,290 --> 00:09:38,820
>> Tehát az első dolog, amit meg kell
létrehozhatunk új node, persze,

189
00:09:38,820 --> 00:09:40,790
és ellenőrizze a NULL.

190
00:09:40,790 --> 00:09:43,250
Mindig jó.

191
00:09:43,250 --> 00:09:47,840
És akkor meg kell rendelni az értékeket.

192
00:09:47,840 --> 00:09:51,260
Amikor létrehoz egy új csomópont, akkor
nem tudom, mi ez mutat a jövő,

193
00:09:51,260 --> 00:09:54,560
így szeretnénk inicializálni azt a NULL.

194
00:09:54,560 --> 00:09:58,760
Ha ez nem fog mutatni, hogy valami
más, ez lesz újraosztani, és ez rendben van.

195
00:09:58,760 --> 00:10:00,740
Ha ez az első dolog,
a listán, akkor kell

196
00:10:00,740 --> 00:10:04,270
hogy pont azért, mert NULL
ez az a lista végére.

197
00:10:04,270 --> 00:10:12,410
>> Így majd helyezze, látjuk itt
rendel hozzá a következő értéke a csomópont

198
00:10:12,410 --> 00:10:17,380
hogy bármi fej,
amelyet mi volt itt.

199
00:10:17,380 --> 00:10:19,930
Ez az, amit csináltál.

200
00:10:19,930 --> 00:10:25,820
És akkor mi hozzárendelése fej pont
az új csomópont, mert emlékszem,

201
00:10:25,820 --> 00:10:31,090
néhány új mutató a csomópont,
és pontosan ez az, amit fej.

202
00:10:31,090 --> 00:10:34,370
Pontosan ezért
ezt arrow accessor.

203
00:10:34,370 --> 00:10:37,030

204
00:10:37,030 --> 00:10:37,530
Cool?

205
00:10:37,530 --> 00:10:38,130
Mmhmm?

206
00:10:38,130 --> 00:10:41,100
>> KÖZÖNSÉG: Muszáj
formáznia az új mellett NULL első,

207
00:10:41,100 --> 00:10:44,240
vagy mi csak inicializálása fej?

208
00:10:44,240 --> 00:10:48,210
>> SPEAKER 1: Új next
kell lennie NULL kezdeni

209
00:10:48,210 --> 00:10:53,760
mert nem tudod
ahol lesz.

210
00:10:53,760 --> 00:10:56,100
Továbbá, ez a fajta
Csakúgy, mint a paradigma.

211
00:10:56,100 --> 00:10:59,900
Beállítod egyenlő NULL csak azért, hogy
meg arról, hogy minden a bázisok vonatkozik

212
00:10:59,900 --> 00:11:04,070
Mielőtt tegye átváltoztató, hogy
Ön mindig biztos, hogy ez lesz

213
00:11:04,070 --> 00:11:08,880
mutatva, hogy egy adott érték
szemben, mint a szemét érték.

214
00:11:08,880 --> 00:11:12,210
Mert, igen, rendelni
új next automatikusan,

215
00:11:12,210 --> 00:11:15,420
de ez több, mint egy
helyes gyakorlat inicializálása

216
00:11:15,420 --> 00:11:19,270
ily módon, majd hozzárendelését.

217
00:11:19,270 --> 00:11:23,420
>> OK, így kétszeresen láncolt listák most.

218
00:11:23,420 --> 00:11:24,601
Mit gondolsz?

219
00:11:24,601 --> 00:11:26,350
Mi a különbség az
kétszeresen láncolt listák?

220
00:11:26,350 --> 00:11:30,750

221
00:11:30,750 --> 00:11:34,300
>> Tehát a mi láncolt listák, tudjuk
csak mozog egy irányba, igaz?

222
00:11:34,300 --> 00:11:35,270
Már csak a következő.

223
00:11:35,270 --> 00:11:36,760
Csak megy előre.

224
00:11:36,760 --> 00:11:40,300
>> A kétszeresen láncolt lista,
mi is hátrafelé.

225
00:11:40,300 --> 00:11:44,810
Tehát nem csak a
számot szeretnénk tárolni,

226
00:11:44,810 --> 00:11:50,110
van, ahol a következő pontok
és ahol csak jött.

227
00:11:50,110 --> 00:11:52,865
Így ez lehetővé teszi, hogy
néhány jobb bejárás.

228
00:11:52,865 --> 00:11:56,620

229
00:11:56,620 --> 00:12:01,240
>> Így kétszeresen kötött csomópontok,
nagyon hasonló, ugye?

230
00:12:01,240 --> 00:12:05,000
Csak a különbség most
egy következő és az előző.

231
00:12:05,000 --> 00:12:06,235
Ez az egyetlen különbség.

232
00:12:06,235 --> 00:12:09,570

233
00:12:09,570 --> 00:12:14,790
>> Tehát, ha mi voltunk az elé vagy mi append--
nincs kód fel here--

234
00:12:14,790 --> 00:12:17,830
de ha úgy döntesz, hogy megpróbálja
helyezze be, az a fontos,

235
00:12:17,830 --> 00:12:19,980
az meg kell, hogy
meg róla, hogy kiosztása

236
00:12:19,980 --> 00:12:23,360
mind a korábbi, és a
következő mutató helyesen.

237
00:12:23,360 --> 00:12:29,010
Tehát ebben az esetben, ha lenne
nem csak inicializálni következő,

238
00:12:29,010 --> 00:12:31,820
inicializálja a korábbi.

239
00:12:31,820 --> 00:12:36,960
Ha mi vagyunk a lista élére, mi
Nem csak, hogy egyenlő fej új,

240
00:12:36,960 --> 00:12:41,750
de az új előző kellene
pont a fej, igaz?

241
00:12:41,750 --> 00:12:43,380
>> Ez az egyetlen különbség.

242
00:12:43,380 --> 00:12:47,200
Ha többet szeretne gyakorlatot
ezeket kapcsolt listák, a beszúrás,

243
00:12:47,200 --> 00:12:49,900
törlésének, betéttel
egy válogatott lista,

244
00:12:49,900 --> 00:12:52,670
kérlek nézd meg study.cs50.net.

245
00:12:52,670 --> 00:12:54,870
Van egy csomó nagy gyakorlatokat.

246
00:12:54,870 --> 00:12:55,870
Én nagyon ajánlom őket.

247
00:12:55,870 --> 00:12:59,210
Bárcsak lenne ideje, hogy menjen át őket
de van egy csomó adat struktúrák

248
00:12:59,210 --> 00:13:01,530
átvészelni.

249
00:13:01,530 --> 00:13:02,650
>> OK, így hash táblák.

250
00:13:02,650 --> 00:13:07,070
Ez talán a legnagyobb
hasznos bit a PSET

251
00:13:07,070 --> 00:13:11,090
itt, mert te leszel
végrehajtása egy ilyen, vagy egy próbát.

252
00:13:11,090 --> 00:13:12,200
Én nagyon szeretem hash táblák.

253
00:13:12,200 --> 00:13:13,110
Ők elég jó.

254
00:13:13,110 --> 00:13:17,080
>> Tehát alapvetően mi
történik, a hash tábla

255
00:13:17,080 --> 00:13:22,050
az, amikor valóban szükség van gyors
beszúrás, törlés és keresés.

256
00:13:22,050 --> 00:13:25,010
Ezek azok a dolgok, hogy mi vagyunk
előnyben egy hash tábla.

257
00:13:25,010 --> 00:13:29,500
Ők tud elég nagy,
de mint látni fogjuk a próbálkozás,

258
00:13:29,500 --> 00:13:33,040
vannak olyan dolgok, amelyek sokkal nagyobb.

259
00:13:33,040 --> 00:13:38,330
>> De alapvetően, mind a hash
táblázat egy hash függvény

260
00:13:38,330 --> 00:13:47,215
hogy megmondja, melyik vödröt, hogy az egyes
az adatokat, minden egyes elemek.

261
00:13:47,215 --> 00:13:51,140
Egy egyszerű módja annak, hogy úgy gondolja, a hash tábla
az, hogy ez csak vödör dolgok,

262
00:13:51,140 --> 00:13:51,770
ugye?

263
00:13:51,770 --> 00:13:59,720
Tehát, ha a dolgokat rendezés
mint az első levél a nevüket,

264
00:13:59,720 --> 00:14:01,820
ez olyan, mint egy hash tábla.

265
00:14:01,820 --> 00:14:06,180
>> Tehát, ha én a csoportos srácok is
a csoport, aki a neve kezdődik

266
00:14:06,180 --> 00:14:11,670
val ide, vagy akárki születésnap
a január, február, március,

267
00:14:11,670 --> 00:14:15,220
bármi, ami hatékonyan
létrehozása hash tábla.

268
00:14:15,220 --> 00:14:18,120
Ez csak létre gyűjtőmezők
Ön rendezheti elemek

269
00:14:18,120 --> 00:14:19,520
így megtalálja őket könnyebb.

270
00:14:19,520 --> 00:14:22,300
Tehát így, amikor szükségem van
találni egy van,

271
00:14:22,300 --> 00:14:24,680
Nem kell keresni
keresztül minden a nevét.

272
00:14:24,680 --> 00:14:29,490
Én lehet, mint, oh, tudom, hogy
Danielle születésnapja in--

273
00:14:29,490 --> 00:14:30,240
KÖZÖNSÉG: --April.

274
00:14:30,240 --> 00:14:30,948
SPEAKER 1: április.

275
00:14:30,948 --> 00:14:33,120
Így nézek én április
vödör, és egy kis szerencsével,

276
00:14:33,120 --> 00:14:38,270
ő lesz az egyetlen, és ott
időmet állandó volt abban az értelemben,

277
00:14:38,270 --> 00:14:41,230
mivel ha azt kell nézni
egy csomó ember,

278
00:14:41,230 --> 00:14:43,090
ez fog sokkal tovább tart.

279
00:14:43,090 --> 00:14:45,830
Tehát hash táblák tényleg csak kanalak.

280
00:14:45,830 --> 00:14:48,630
Könnyű módja annak, hogy gondolunk rájuk.

281
00:14:48,630 --> 00:14:52,930
>> Tehát egy nagyon fontos dolog
a hash tábla egy hash függvény.

282
00:14:52,930 --> 00:14:58,140
Így a dolog, amit csak beszéltem, mint
az első betű a név első

283
00:14:58,140 --> 00:15:01,450
vagy a születésnapját hónapban,
Ezek ötletek

284
00:15:01,450 --> 00:15:03,070
valóban korrelál a hash függvény.

285
00:15:03,070 --> 00:15:08,900
Ez csak egy módja annak eldöntésekor, hogy mely
vödör Te elem megy, OK?

286
00:15:08,900 --> 00:15:14,850
Tehát ez PSET, akkor nézz fel
elég sok olyan hash kívánt funkciót.

287
00:15:14,850 --> 00:15:16,030
>> Nem kell a saját.

288
00:15:16,030 --> 00:15:21,140
Van néhány igazán jó is ki
ott nem mindenféle őrült matematika.

289
00:15:21,140 --> 00:15:25,170
És ha azt szeretnénk, hogy a
helyesírás szuper gyors,

290
00:15:25,170 --> 00:15:27,620
Szeretném határozottan
vizsgálja meg egy ilyen.

291
00:15:27,620 --> 00:15:32,390
>> De vannak még a
egyszerű is, mint a compute

292
00:15:32,390 --> 00:15:39,010
az összeget a szavak, mint például a
minden betű egy szám.

293
00:15:39,010 --> 00:15:39,940
Számoljuk ki az összeget.

294
00:15:39,940 --> 00:15:42,230
Ez határozza meg a vödröt.

295
00:15:42,230 --> 00:15:45,430
Ők is az egyszerű is, hogy
olyanok, mint az összes A itt van,

296
00:15:45,430 --> 00:15:47,050
az összes B itt.

297
00:15:47,050 --> 00:15:48,920
Bármelyik ilyen.

298
00:15:48,920 --> 00:15:55,770
>> Alapvetően, csak megmondja, hogy melyik
tömb index az elem kell mennie.

299
00:15:55,770 --> 00:15:58,690
Csak döntés a bucket--
ez az egész egy hash függvény.

300
00:15:58,690 --> 00:16:04,180
Tehát itt van egy példa, amely
csak az első betű a húr

301
00:16:04,180 --> 00:16:05,900
hogy én csak beszélek.

302
00:16:05,900 --> 00:16:11,900
>> Szóval van valami hash ez csak a
első betű a húr mínusz A,

303
00:16:11,900 --> 00:16:16,090
ami ad egy kis
szám 0 és 25 között.

304
00:16:16,090 --> 00:16:20,790
És mit akarsz csinálni az
győződjön meg arról, hogy ez jelent

305
00:16:20,790 --> 00:16:24,110
A méret a hash table--
hány vödör van.

306
00:16:24,110 --> 00:16:25,860
Sok ilyen
hash függvények, ők

307
00:16:25,860 --> 00:16:31,630
majd visszatér értékeket esetleg
Sokkal felett száma kanalak

308
00:16:31,630 --> 00:16:33,610
hogy valóban van
a hash tábla,

309
00:16:33,610 --> 00:16:37,240
így meg kell, hogy
biztos és mod azok.

310
00:16:37,240 --> 00:16:42,190
Egyébként, ez fog mondani,
ó, meg kell vödör 5000

311
00:16:42,190 --> 00:16:46,040
de már csak 30
kanalak a hash tábla.

312
00:16:46,040 --> 00:16:49,360
És persze mindannyian tudjuk, hogy ez
fog eredményezni néhány őrült hibákat.

313
00:16:49,360 --> 00:16:52,870
Ezért győződjön meg arról, hogy a mod
mérete a hash tábla.

314
00:16:52,870 --> 00:16:58,430

315
00:16:58,430 --> 00:16:58,930
Cool.

316
00:16:58,930 --> 00:17:00,506
Így ütközések.

317
00:17:00,506 --> 00:17:02,620
Mindenki jó eddig?

318
00:17:02,620 --> 00:17:03,120
Mmhmm?

319
00:17:03,120 --> 00:17:05,900
>> KÖZÖNSÉG: Miért lenne
vissza ilyen nagy érték?

320
00:17:05,900 --> 00:17:09,210
>> SPEAKER 1: Attól függően, hogy az algoritmus
hogy a hash függvény.

321
00:17:09,210 --> 00:17:12,270
Néhányan közülük fog tenni
őrült szorzás.

322
00:17:12,270 --> 00:17:16,270
És ez az egész kezd
egy egyenletes eloszlás,

323
00:17:16,270 --> 00:17:18,490
így meg néhány igazán
őrült dolgokat néha.

324
00:17:18,490 --> 00:17:20,960
Ez minden.

325
00:17:20,960 --> 00:17:22,140
Bármi más?

326
00:17:22,140 --> 00:17:22,829
OK.

327
00:17:22,829 --> 00:17:24,480
>> Így ütközések.

328
00:17:24,480 --> 00:17:29,270
Alapvetően, ahogy már mondtam,
A legjobb esetben,

329
00:17:29,270 --> 00:17:32,040
minden vödör Nézek az
megy, hogy egy dolog,

330
00:17:32,040 --> 00:17:34,160
így nem kell nézni minden, igaz?

331
00:17:34,160 --> 00:17:37,040
Azt sem tudom, hogy ott van, vagy ez
Nem, és ez az, amit igazán akar.

332
00:17:37,040 --> 00:17:43,960
De ha van több tízezer
adatpontok és kevesebb, mint ez a szám

333
00:17:43,960 --> 00:17:48,700
A kanalak, mi megy, hogy
ütközések ahol végül valami

334
00:17:48,700 --> 00:17:54,210
megy, hogy a végén egy
vödör, amely már rendelkezik egy elem.

335
00:17:54,210 --> 00:17:57,390
>> A kérdés tehát az, hogy mi
teszünk ebben az ügyben?

336
00:17:57,390 --> 00:17:58,480
Mit tegyünk?

337
00:17:58,480 --> 00:17:59,300
Már van ott valami?

338
00:17:59,300 --> 00:18:00,060
Vajon csak dobd ki?

339
00:18:00,060 --> 00:18:00,700
>> Nem.

340
00:18:00,700 --> 00:18:01,980
Meg kell tartani mind a ketten.

341
00:18:01,980 --> 00:18:06,400
Így az is, hogy mi
általában erre van, mi?

342
00:18:06,400 --> 00:18:08,400
Mi az adatstruktúra
mi csak beszélgettünk?

343
00:18:08,400 --> 00:18:09,316
KÖZÖNSÉG: láncolt lista.

344
00:18:09,316 --> 00:18:10,500
SPEAKER 1: A láncolt lista.

345
00:18:10,500 --> 00:18:16,640
Tehát most, ahelyett, hogy minden egyes ilyen
vödrök csak úgy, egyik eleme,

346
00:18:16,640 --> 00:18:24,020
ez meg fog tartalmaz csatolt listát
az elemeket, amelyeket kivonatos bele.

347
00:18:24,020 --> 00:18:27,588
OK, nem mindenki olyan, hogy ez az ötlet?

348
00:18:27,588 --> 00:18:30,546
Mert nem lehetett tömb
mert nem tudom, hogy sok mindent

349
00:18:30,546 --> 00:18:31,730
lesznek ott.

350
00:18:31,730 --> 00:18:36,540
A láncolt lista lehetővé teszi számunkra, hogy
már csak a pontos számot,

351
00:18:36,540 --> 00:18:38,465
a kivonatos ebbe a vödör, ugye?

352
00:18:38,465 --> 00:18:42,260

353
00:18:42,260 --> 00:18:50,500
>> Tehát lineáris tapintás
alapvetően ez ötletem

354
00:18:50,500 --> 00:18:52,300
ez az egyik módja annak, hogy foglalkozik az ütközést.

355
00:18:52,300 --> 00:18:58,010
Mit tehetünk, ha ebben a
ügy, bogyó volt a kivonatos 1

356
00:18:58,010 --> 00:19:01,130
és mi már
valamit, csak

357
00:19:01,130 --> 00:19:04,840
menj le, amíg
találsz egy üres helyet.

358
00:19:04,840 --> 00:19:06,370
Ez az egyik módja annak, hogy kezelni.

359
00:19:06,370 --> 00:19:09,020
A másik módja, hogy
ez, amit mi csak

360
00:19:09,020 --> 00:19:12,280
called-- a kapcsolt
lista hívják láncolás.

361
00:19:12,280 --> 00:19:20,510
>> Tehát ez a gondolat akkor működik, ha
A hash tábla úgy gondolja,

362
00:19:20,510 --> 00:19:24,150
sokkal nagyobb, mint
az adathalmaz, vagy ha

363
00:19:24,150 --> 00:19:28,870
szeretné próbálni, és minimalizálni láncolás
amíg nem feltétlenül szükséges.

364
00:19:28,870 --> 00:19:34,050
Tehát az egyik dolog lineáris
szondázás nyilvánvalóan azt jelenti,

365
00:19:34,050 --> 00:19:37,290
hogy a hash függvény
nem annyira hasznos

366
00:19:37,290 --> 00:19:42,200
mert fogsz a végén segítségével
A hash függvény, kapok egy pontot,

367
00:19:42,200 --> 00:19:46,400
Ön lineáris szondával le
Néhány hely, ami elérhető.

368
00:19:46,400 --> 00:19:49,670
De most, persze, semmi
más, ami végül oda,

369
00:19:49,670 --> 00:19:52,050
fogsz kell
keresés még lejjebb.

370
00:19:52,050 --> 00:19:55,650
>> És van egy sokkal nagyobb
keresés költség, amelyet

371
00:19:55,650 --> 00:19:59,820
megy bevitele egy elemet
a hash tábla, igaz?

372
00:19:59,820 --> 00:20:05,640
És most, ha megy, és próbálja megtalálni
bogyó megint, fogsz hash azt,

373
00:20:05,640 --> 00:20:07,742
és azt fogja mondani,
ó, nézz vödör 1,

374
00:20:07,742 --> 00:20:09,700
és ez nem lesz
1 vödör, szóval

375
00:20:09,700 --> 00:20:11,970
kell majd áthalad
keresztül a többi hasonló.

376
00:20:11,970 --> 00:20:17,720
Szóval ez néha hasznos,
de a legtöbb esetben,

377
00:20:17,720 --> 00:20:22,660
fogjuk mondani, hogy
láncolás az, amit akarok.

378
00:20:22,660 --> 00:20:25,520
>> Így beszéltünk erről korábban.

379
00:20:25,520 --> 00:20:27,812
Van egy kis magam előtt.

380
00:20:27,812 --> 00:20:33,560
De láncolás alapvetően azt
minden vödör a hash tábla

381
00:20:33,560 --> 00:20:36,120
csak egy láncolt lista.

382
00:20:36,120 --> 00:20:39,660
>> Tehát más módon, vagy több műszaki
Így, hogy gondoljanak egy hash tábla

383
00:20:39,660 --> 00:20:44,490
az, hogy ez csak egy tömb
kapcsolt listák, amelyek

384
00:20:44,490 --> 00:20:49,330
amikor írsz a szótárba
és próbál betölteni azt,

385
00:20:49,330 --> 00:20:52,070
gondolt rá, mint egy
tömb kapcsolt listák

386
00:20:52,070 --> 00:20:54,390
teszi sokkal könnyebb
az Ön inicializálása.

387
00:20:54,390 --> 00:20:57,680
>> KÖZÖNSÉG: Tehát hash tábla
van egy előre meghatározott méretű,

388
00:20:57,680 --> 00:20:58,980
mint a [hallható] kanalak?

389
00:20:58,980 --> 00:20:59,220
>> SPEAKER 1: Jobb.

390
00:20:59,220 --> 00:21:01,655
Tehát van egy meghatározott számú
kanalak hogy determine--

391
00:21:01,655 --> 00:21:03,530
amely srácok kellene
nyugodtan játszani.

392
00:21:03,530 --> 00:21:05,269
Ez is elég jó
hogy mi történik

393
00:21:05,269 --> 00:21:06,810
ahogy változik a több vödör.

394
00:21:06,810 --> 00:21:09,410

395
00:21:09,410 --> 00:21:11,510
De igen, van egy
meghatározott számú kanalak.

396
00:21:11,510 --> 00:21:15,360
Mi teszi lehetővé, hogy illeszkedjen a
sok elem, amennyire szüksége van

397
00:21:15,360 --> 00:21:19,350
ez külön láncolás, ahol
összekapcsolta listákat minden vödör.

398
00:21:19,350 --> 00:21:22,850
Ez azt jelenti, a hash tábla
lesz pontosan a méret

399
00:21:22,850 --> 00:21:25,440
hogy meg kell, hogy legyen, nem igaz?

400
00:21:25,440 --> 00:21:27,358
Ez a lényege a kapcsolt listák.

401
00:21:27,358 --> 00:21:30,850

402
00:21:30,850 --> 00:21:32,480
Cool.

403
00:21:32,480 --> 00:21:38,780
>> Tehát mindenki OK ott?

404
00:21:38,780 --> 00:21:39,801
Rendben van.

405
00:21:39,801 --> 00:21:40,300
Ah.

406
00:21:40,300 --> 00:21:41,860
Mi történt?

407
00:21:41,860 --> 00:21:42,960
Tényleg most.

408
00:21:42,960 --> 00:21:45,250
Találd valaki megöl.

409
00:21:45,250 --> 00:21:52,060
>> OK fogunk menni
próbálkozás, ami egy kicsit őrült.

410
00:21:52,060 --> 00:21:53,140
Szeretem hash táblák.

411
00:21:53,140 --> 00:21:54,460
Azt hiszem, nagyon jó.

412
00:21:54,460 --> 00:21:56,710
Megpróbálja hűvös is.

413
00:21:56,710 --> 00:21:59,590
>> Tehát nem mindenki emlékszik, mi egy próbát az?

414
00:21:59,590 --> 00:22:01,740
Meg kellett volna át
azt röviden előadás?

415
00:22:01,740 --> 00:22:04,570

416
00:22:04,570 --> 00:22:06,377
Emlékszel milyen, hogyan működik?

417
00:22:06,377 --> 00:22:08,460
KÖZÖNSÉG: Én csak bólogat
hogy mi nem megy rajta.

418
00:22:08,460 --> 00:22:09,626
SPEAKER 1: Mi nem megy rajta.

419
00:22:09,626 --> 00:22:13,100
OK, mi igazán fog menni
mint most az, amit mondasz.

420
00:22:13,100 --> 00:22:14,860
>> KÖZÖNSÉG: Ez a visszakeresés fa.

421
00:22:14,860 --> 00:22:15,280
>> SPEAKER 1: Igen.

422
00:22:15,280 --> 00:22:16,196
Ez egy visszakeresés fa.

423
00:22:16,196 --> 00:22:16,960
Félelmetes.

424
00:22:16,960 --> 00:22:23,610
Tehát az egyik dolog, hogy észre itt az, hogy mi
keres az egyes karaktereket

425
00:22:23,610 --> 00:22:24,480
itt, ugye?

426
00:22:24,480 --> 00:22:29,710
>> Szóval mielőtt a mi hash függvény,
keresték meg a szavak, mint az egész,

427
00:22:29,710 --> 00:22:32,270
és most keresünk tovább
a karakterek, igaz?

428
00:22:32,270 --> 00:22:38,380
Tehát Maxwell ide, és Mendel.

429
00:22:38,380 --> 00:22:47,840
Tehát alapvetően egy try-- módon gondolkodni
ez, hogy minden szinten van

430
00:22:47,840 --> 00:22:49,000
egy tömb betűk.

431
00:22:49,000 --> 00:22:53,310

432
00:22:53,310 --> 00:22:55,790
Szóval ez a gyökér csomópont itt, ugye?

433
00:22:55,790 --> 00:23:01,980
Ez az összes karakter a
ábécé a kezdete minden szó.

434
00:23:01,980 --> 00:23:06,480
>> És mit akarsz csinálni az
mondjuk, OK, van néhány M szó.

435
00:23:06,480 --> 00:23:10,590
Fogunk keresni Maxwell, így
megyünk M. és M pontok egy egész

436
00:23:10,590 --> 00:23:14,800
másik a tömb, ahol minden
szó, amíg van

437
00:23:14,800 --> 00:23:17,044
van szó, hogy van egy
mivel a második levél,

438
00:23:17,044 --> 00:23:19,460
amíg van egy szó,
van B, mint a második levél,

439
00:23:19,460 --> 00:23:24,630
akkor azt a mutató
majd néhány következő tömb.

440
00:23:24,630 --> 00:23:29,290
>> Ott valószínűleg nem a
szó MP valami,

441
00:23:29,290 --> 00:23:32,980
így a P álláspontját e
tömb, ez csak NULL.

442
00:23:32,980 --> 00:23:38,840
Azt mondaná, rendben van, nincs szó
hogy a M követ P, OK?

443
00:23:38,840 --> 00:23:43,100
Tehát, ha belegondolunk, minden
az egyik ilyen kisebb dolgokat

444
00:23:43,100 --> 00:23:47,990
valójában egyik ilyen
nagy tömbök, A-tól Z

445
00:23:47,990 --> 00:23:55,064
Szóval, mi lehet az egyik dolog
ez egyfajta hátránya egy próbát?

446
00:23:55,064 --> 00:23:56,500
>> KÖZÖNSÉG: Sok memóriát.

447
00:23:56,500 --> 00:23:59,940
>> SPEAKER 1: Ez egy csomó emlék, ugye?

448
00:23:59,940 --> 00:24:08,750
Mindegyik blokk itt
jelentése 26. terek, 26 elem tömb.

449
00:24:08,750 --> 00:24:13,680
Így próbál helyet kap hihetetlenül nehéz.

450
00:24:13,680 --> 00:24:17,100
>> De nagyon gyorsan.

451
00:24:17,100 --> 00:24:22,540
Szóval hihetetlenül gyors, de
igazán tér hatékony.

452
00:24:22,540 --> 00:24:24,810
Kicsit ki kell találnom
ki melyiket szeretné.

453
00:24:24,810 --> 00:24:29,470
Ezek nagyon klassz a PSET,
de ők nem vesznek fel sok memóriát,

454
00:24:29,470 --> 00:24:30,290
így kompromisszumot.

455
00:24:30,290 --> 00:24:31,480
Igen?

456
00:24:31,480 --> 00:24:34,300
>> KÖZÖNSÉG: Lehetséges volna
hogy hozzanak létre egy próbát, majd

457
00:24:34,300 --> 00:24:37,967
ha az összes
adatokat, hogy te need--

458
00:24:37,967 --> 00:24:39,550
Én nem tudom, hogy lenne értelme.

459
00:24:39,550 --> 00:24:42,200
Én megszabadulni az összes
NULL karaktert, de aztán

460
00:24:42,200 --> 00:24:42,910
akkor nem lesz képes index them--

461
00:24:42,910 --> 00:24:43,275
>> SPEAKER 1: Még mindig szükség van rájuk.

462
00:24:43,275 --> 00:24:44,854
>> KÖZÖNSÉG: - az azonos módon minden alkalommal.

463
00:24:44,854 --> 00:24:45,520
SPEAKER 1: Igen.

464
00:24:45,520 --> 00:24:50,460
Meg kell a NULL karakter legyen
tudod, ha nem egy szó ott.

465
00:24:50,460 --> 00:24:52,040
Ben ettél, amit akar?

466
00:24:52,040 --> 00:24:52,540
OK.

467
00:24:52,540 --> 00:24:54,581
Rendben, megyünk
hogy menjen egy kicsit

468
00:24:54,581 --> 00:24:58,920
a technikai részletek mögött
egy próbát és a munka egy példán keresztül.

469
00:24:58,920 --> 00:25:01,490
>> OK, így ez ugyanaz a dolog.

470
00:25:01,490 --> 00:25:06,290
Mivel a láncolt lista, a legfontosabb
kedves of-- mi a szó, amit akar? -

471
00:25:06,290 --> 00:25:08,350
mint építőköve volt a csomópont.

472
00:25:08,350 --> 00:25:12,280
Egy próbát, mi is van egy csomópont,
de ez mást jelent.

473
00:25:12,280 --> 00:25:17,000
>> Tehát néhány bool hogy
jelenti, hogy a szó valóban

474
00:25:17,000 --> 00:25:23,530
létezik ezen a helyen, majd
van néhány tömb here-- vagy inkább,

475
00:25:23,530 --> 00:25:27,840
ez a mutató egy
sor 27 karakter.

476
00:25:27,840 --> 00:25:33,339
És ez az, ebben az esetben, ez a
27-- Biztos vagyok benne, mindannyian olyanok, mint a vár,

477
00:25:33,339 --> 00:25:34,880
van 26 betű az ábécében.

478
00:25:34,880 --> 00:25:36,010
Miért van 27?

479
00:25:36,010 --> 00:25:37,870
>> Tehát attól függően, hogy
Így végre ezt,

480
00:25:37,870 --> 00:25:43,240
ez egy PSET hogy
engedélyezett aposztróf.

481
00:25:43,240 --> 00:25:46,010
Szóval ezért a plusz egy.

482
00:25:46,010 --> 00:25:50,500
Akkor is van néhány
esetben a null terminátor

483
00:25:50,500 --> 00:25:53,230
szerepel, mint az egyik
karakterek, hogy ez lehetővé tette, hogy,

484
00:25:53,230 --> 00:25:56,120
és ez hogyan ellenőrizze,
hogy ha ez a vége a szó.

485
00:25:56,120 --> 00:26:01,340
Ha érdekel, nézd meg a
Kevin videó study.cs50,

486
00:26:01,340 --> 00:26:04,790
valamint Wikipedia
jó források hiányában.

487
00:26:04,790 --> 00:26:09,000
>> De megyünk, hogy menjen át csak egyfajta
arra, hogyan lehet a munka révén egy próbát

488
00:26:09,000 --> 00:26:11,010
ha az adott ember.

489
00:26:11,010 --> 00:26:16,230
Tehát van egy szuper egyszerű, hogy itt
rendelkezik a "denevér" és a "zoom" bennük.

490
00:26:16,230 --> 00:26:18,920
És mint látjuk itt,
ez a kis hely itt

491
00:26:18,920 --> 00:26:22,560
képviseli bool hogy
azt mondja, igen, ez egy szó.

492
00:26:22,560 --> 00:26:27,060
És akkor ennek a
tömbök karakterek, ugye?

493
00:26:27,060 --> 00:26:33,480
>> Így fogunk átmenni
megtalálása "denevér" ebben a próbát.

494
00:26:33,480 --> 00:26:38,340
Így kezdődik a tetején, igaz?

495
00:26:38,340 --> 00:26:46,290
És tudjuk, hogy b megfelel
A második index, a második elem

496
00:26:46,290 --> 00:26:47,840
ebben tömb, mert a és b.

497
00:26:47,840 --> 00:26:51,340
Tehát nagyjából a második.

498
00:26:51,340 --> 00:26:58,820
>> És azt mondja, rendben van, hűvös, következik, hogy a
a következő sor, mert ha emlékszünk,

499
00:26:58,820 --> 00:27:02,160
ez nem, hogy minden ilyen
valójában tartalmazza az elemet.

500
00:27:02,160 --> 00:27:07,110
Mindegyik tömbök
egy mutatót tartalmaz, igaz?

501
00:27:07,110 --> 00:27:10,030
Ez egy fontos különbség, hogy a.

502
00:27:10,030 --> 00:27:13,450
>> Tudom, hogy ez fog be-- megpróbálja a
nagyon nehéz, hogy az első alkalom,

503
00:27:13,450 --> 00:27:15,241
így akkor is, ha ez a
második vagy harmadik alkalommal

504
00:27:15,241 --> 00:27:18,370
és még mindig kedves
A látszólag nehéz,

505
00:27:18,370 --> 00:27:21,199
Ígérem, ha megy az óra
Rövid megint holnap,

506
00:27:21,199 --> 00:27:22,740
ez lesz valószínűleg, hogy sokkal több értelme van.

507
00:27:22,740 --> 00:27:23,890
Nagyon nagy megemészteni.

508
00:27:23,890 --> 00:27:27,800
Én néha még mindig vagyok
mint, várj, mi egy próbát?

509
00:27:27,800 --> 00:27:29,080
Hogyan kell használni ezt?

510
00:27:29,080 --> 00:27:33,880
>> Így már b ebben az esetben,
amely a második index.

511
00:27:33,880 --> 00:27:40,240
Ha lenne, mondjuk, c vagy
d vagy bármely más betű,

512
00:27:40,240 --> 00:27:45,810
kell feltérképezni, hogy vissza az index
mi tömb, amely megfelel.

513
00:27:45,810 --> 00:27:56,930
Így venné mint rchar és mi csak
vonjuk le a leképezni a 0 és 25.

514
00:27:56,930 --> 00:27:58,728
Mindenki jó, hogyan
Térkép a karaktereket?

515
00:27:58,728 --> 00:28:00,440
OK.

516
00:28:00,440 --> 00:28:05,980
>> Szóval megy a második, és
látni, hogy igen, akkor nem NULL.

517
00:28:05,980 --> 00:28:07,780
Mi lehet lépni ezt a következő tömb.

518
00:28:07,780 --> 00:28:12,300
Így megyünk tovább, hogy ez a következő tömb itt.

519
00:28:12,300 --> 00:28:15,500
>> És azt mondjuk, rendben van, most
kell, hogy ha egy van itt.

520
00:28:15,500 --> 00:28:18,590
Van egy null vagy mégsem
valójában előrelépni?

521
00:28:18,590 --> 00:28:21,880
Így a valóban mozog
továbbítja az ezt a tömböt.

522
00:28:21,880 --> 00:28:24,570
És azt mondjuk, OK, t az utolsó levél.

523
00:28:24,570 --> 00:28:27,580
Szóval megy a t az index.

524
00:28:27,580 --> 00:28:30,120
És akkor haladunk előre
mert van egy másik.

525
00:28:30,120 --> 00:28:38,340
És ezt mondja lényegében, hogy igen,
azt mondja, hogy van egy szó here--

526
00:28:38,340 --> 00:28:41,750
hogy ha követi ezt
út, megérkezett

527
00:28:41,750 --> 00:28:43,210
olyan szó, amiről tudjuk, hogy "denevér".

528
00:28:43,210 --> 00:28:43,800
Igen?

529
00:28:43,800 --> 00:28:46,770
>> KÖZÖNSÉG: Vajon szabvány is, hogy a
a 0. index, majd egy sort 1

530
00:28:46,770 --> 00:28:47,660
vagy hogy a végén?

531
00:28:47,660 --> 00:28:48,243
>> SPEAKER 1: Nem.

532
00:28:48,243 --> 00:28:55,360
Tehát, ha visszatekintünk a mi
nyilatkozat itt, ez egy bool,

533
00:28:55,360 --> 00:28:59,490
így saját eleme a csomópont.

534
00:28:59,490 --> 00:29:03,331
Szóval ez nem része a tömb.

535
00:29:03,331 --> 00:29:03,830
Cool.

536
00:29:03,830 --> 00:29:08,370
Tehát, ha véget ér a szó, és mi vagyunk
Ebben a tömb, amit akarunk csinálni

537
00:29:08,370 --> 00:29:12,807
ez nem egy csekket ez a szó.

538
00:29:12,807 --> 00:29:14,390
És ebben az esetben, akkor visszatér igen.

539
00:29:14,390 --> 00:29:17,220

540
00:29:17,220 --> 00:29:24,090
>> Szóval ez a megjegyzés, tudjuk, hogy "állatkert" -
, mint tudjuk, az emberek, hogy a "állatkert" egy szó,

541
00:29:24,090 --> 00:29:24,820
ugye?

542
00:29:24,820 --> 00:29:28,990
De próbáld itt lenne
azt mondják, nem, ez nem az.

543
00:29:28,990 --> 00:29:33,980
És azt mondják, hogy azért, mert
nem jelöltek meg, mint a szó itt.

544
00:29:33,980 --> 00:29:40,440
Annak ellenére, hogy tud elmozdulni
át ez a tömb,

545
00:29:40,440 --> 00:29:43,890
ezt próbálja azt mondaná, hogy nem,
állatkert nincs a szótárban

546
00:29:43,890 --> 00:29:47,070
mert mi nem
megjelölt, mint olyan.

547
00:29:47,070 --> 00:29:52,870
>> Tehát az egyik módja, hogy--
ó, bocsánat, ez egy.

548
00:29:52,870 --> 00:29:59,450
Így ebben az esetben a "állatkert" nem
egy szó, de ez a mi próbát.

549
00:29:59,450 --> 00:30:05,690
De ez, mondjuk azt akarjuk
bevezetni a "fürdő", hogy mi történik

550
00:30:05,690 --> 00:30:08,260
az követjük through-- b, a, t.

551
00:30:08,260 --> 00:30:11,820
Vagyunk ebben a tömbben, és
megyünk keresni órán.

552
00:30:11,820 --> 00:30:15,220
>> Ebben az esetben, amikor
nézd meg a mutató az óra,

553
00:30:15,220 --> 00:30:17,890
ez mutató NULL, OK?

554
00:30:17,890 --> 00:30:20,780
Tehát, ha ez kifejezetten
rámutatva, hogy egy másik tömb,

555
00:30:20,780 --> 00:30:25,000
ha feltételezzük, hogy a mutatók
ebben tömb mutatnak null.

556
00:30:25,000 --> 00:30:28,270
Így ebben az esetben, h mutat
null így nem tehetünk semmit,

557
00:30:28,270 --> 00:30:31,540
így ez is visszatér
hamis, "fürdő" nem itt.

558
00:30:31,540 --> 00:30:34,102

559
00:30:34,102 --> 00:30:35,810
Tehát most vagyunk valójában
megyek át

560
00:30:35,810 --> 00:30:39,790
hogyan valójában mondjuk
hogy "állatkert" a mi próbát.

561
00:30:39,790 --> 00:30:42,920
Hogyan helyezze "állatkert" a mi próbát?

562
00:30:42,920 --> 00:30:47,810
Így az azonos módon, hogy kezdtük
a láncolt lista, kezdjük a gyökér.

563
00:30:47,810 --> 00:30:50,600
Ha kétségei vannak, kezdődik
a gyökere ezeket a dolgokat.

564
00:30:50,600 --> 00:30:53,330
>> És mi mondjuk, OK, z.

565
00:30:53,330 --> 00:30:55,650
z van ebben, és igen.

566
00:30:55,650 --> 00:30:58,370
Szóval áttérnek az
a következő tömb, OK?

567
00:30:58,370 --> 00:31:01,482
És akkor a következő,
azt mondjuk, OK, nem o létezik?

568
00:31:01,482 --> 00:31:03,000
Ez nem.

569
00:31:03,000 --> 00:31:04,330
Ez megint.

570
00:31:04,330 --> 00:31:08,670
>> És így tovább a következő, azt mondtam,
OK, "állatkert" már létezik itt.

571
00:31:08,670 --> 00:31:12,440
Csak annyit kell tennie, hogy megadja ezt az egyenlő
igaz, hogy van egy szó van.

572
00:31:12,440 --> 00:31:15,260
Ha követték mindent
akár korábban azon a ponton,

573
00:31:15,260 --> 00:31:17,030
ez egy szó, így csak a
állítsd egyenlő ilyen.

574
00:31:17,030 --> 00:31:17,530
Igen?

575
00:31:17,530 --> 00:31:22,550
>> KÖZÖNSÉG: Tehát akkor ez azt
azt jelenti, hogy a "ba" szó is?

576
00:31:22,550 --> 00:31:24,120
>> SPEAKER 1: Nem.

577
00:31:24,120 --> 00:31:28,870
Tehát ebben az esetben a "ba" kapnánk
itt, azt mondanám, hogy egy szó,

578
00:31:28,870 --> 00:31:31,590
és ez még mindig nem lehet.

579
00:31:31,590 --> 00:31:32,822
OK?

580
00:31:32,822 --> 00:31:33,740
Mmhmm?

581
00:31:33,740 --> 00:31:36,360
>> KÖZÖNSÉG: Tehát, ha ez a
szó és igent mondasz, akkor

582
00:31:36,360 --> 00:31:38,380
tartalmaznak menni m?

583
00:31:38,380 --> 00:31:42,260
>> SPEAKER 1: Tehát ez arról szól, hogy
with-- töltöd ezt.

584
00:31:42,260 --> 00:31:43,640
Azt mondják, hogy "állatkert" szó.

585
00:31:43,640 --> 00:31:47,020
Ha megy a check--
mint, mondjuk azt akarom mondani,

586
00:31:47,020 --> 00:31:49,400
jelent "állatkert" létezik ebben a szótárban?

587
00:31:49,400 --> 00:31:54,200
Te csak akkor fog keresni "állatkert"
és nézze meg, hogy ha ez a szó.

588
00:31:54,200 --> 00:31:57,291
Te soha nem fog mozogni
át m, mert ez nem

589
00:31:57,291 --> 00:31:58,290
amit keres.

590
00:31:58,290 --> 00:32:02,690

591
00:32:02,690 --> 00:32:08,070
>> Tehát, ha azt akarta, hogy valóban
add "fürdő" ebbe a próbálkozás,

592
00:32:08,070 --> 00:32:11,390
tennénk ugyanezt
mint mi a "állatkert"

593
00:32:11,390 --> 00:32:15,380
kivéve azt látnánk, hogy amikor
megpróbál és kap h, ez nem létezik.

594
00:32:15,380 --> 00:32:20,090
Szóval lehet gondolni ezt próbálják
kell egy új csomópont egy láncolt lista,

595
00:32:20,090 --> 00:32:27,210
ezért kellene egy újabb
egy ilyen tömbök, mint így.

596
00:32:27,210 --> 00:32:35,670
És akkor mit teszünk mi van csak meg a h
eleme a tömb mutató ezt.

597
00:32:35,670 --> 00:32:39,430
>> És akkor mi akarunk itt csinálni?

598
00:32:39,430 --> 00:32:43,110
Add meg egyenlő a valódi
mert ez egy szó.

599
00:32:43,110 --> 00:32:46,350

600
00:32:46,350 --> 00:32:48,150
Cool.

601
00:32:48,150 --> 00:32:48,700
Tudom.

602
00:32:48,700 --> 00:32:51,170
Megpróbálja nem a legizgalmasabb.

603
00:32:51,170 --> 00:32:54,250
Hidd el, én tudom.

604
00:32:54,250 --> 00:32:58,040
>> Tehát az egyik dolog, hogy észre a próbálkozás,
Azt mondtam, ők nagyon hatékony.

605
00:32:58,040 --> 00:33:00,080
Így láttuk őket
vesz fel egy csomó helyet.

606
00:33:00,080 --> 00:33:01,370
Ők olyan zavaros.

607
00:33:01,370 --> 00:33:03,367
Szóval miért is valaha is használni ezeket?

608
00:33:03,367 --> 00:33:05,450
Használjuk ezeket, mert ők
hihetetlenül hatékony.

609
00:33:05,450 --> 00:33:08,130
>> Tehát, ha valaha is keresett
egy szó, akkor csak a

610
00:33:08,130 --> 00:33:10,450
által határolt hossza a szó.

611
00:33:10,450 --> 00:33:15,210
Tehát, ha keres egy
szó, hogy a hossza öt,

612
00:33:15,210 --> 00:33:20,940
te csak mindig kell majd
hogy legfeljebb öt összehasonlítás, OK?

613
00:33:20,940 --> 00:33:25,780
Így teszi alapvetően állandó.

614
00:33:25,780 --> 00:33:29,150
Mint beillesztés és keresés
alapvetően konstans idő.

615
00:33:29,150 --> 00:33:33,750
>> Tehát, ha valaha is
valami állandó időben,

616
00:33:33,750 --> 00:33:35,150
ez olyan jó dolog.

617
00:33:35,150 --> 00:33:37,990
Nem lehet jobb, mint
állandó ideje ezeket a dolgokat.

618
00:33:37,990 --> 00:33:43,150
Úgy, hogy az egyik
hatalmas pluses próbál.

619
00:33:43,150 --> 00:33:46,780
>> De ez sok helyet.

620
00:33:46,780 --> 00:33:50,380
Szóval ilyen van dönteni
mi a fontosabb az Ön számára.

621
00:33:50,380 --> 00:33:54,700
És a mai számítógépek, a
hely, hogy a próbát is eltarthat

622
00:33:54,700 --> 00:33:57,740
talán nem befolyásolja
, hogy sok, de talán

623
00:33:57,740 --> 00:34:01,350
van dolgunk valami
amely sokkal, sokkal több dolgot,

624
00:34:01,350 --> 00:34:02,810
és egy próbát csak nem ésszerű.

625
00:34:02,810 --> 00:34:03,000
Igen?

626
00:34:03,000 --> 00:34:05,610
>> KÖZÖNSÉG: Várj, így van 26
levelek minden egyes ember?

627
00:34:05,610 --> 00:34:07,440
>> SPEAKER 1: Mmhmm.

628
00:34:07,440 --> 00:34:08,570
Igen, van 26.

629
00:34:08,570 --> 00:34:16,984
Van néhány olyan szó, marker, majd
Van 26 eligazítást mindenki.

630
00:34:16,984 --> 00:34:17,775
És ők point--

631
00:34:17,775 --> 00:34:20,280
>> KÖZÖNSÉG: És minden 26,
nem mindegyikük 26?

632
00:34:20,280 --> 00:34:21,500
>> SPEAKER 1: Igen.

633
00:34:21,500 --> 00:34:27,460
És ezért, mint te
látni, hogy kiterjeszti elég gyorsan.

634
00:34:27,460 --> 00:34:28,130
Rendben van.

635
00:34:28,130 --> 00:34:32,524
Így fogunk bejutni a fák, ami
Úgy érzem, könnyebb, és valószínűleg

636
00:34:32,524 --> 00:34:36,150
egy szép kis haladékot
re próbál ott.

637
00:34:36,150 --> 00:34:39,620
Így remélhetőleg a legtöbben
láttam egy fa előtt.

638
00:34:39,620 --> 00:34:41,820
Nem úgy, mint a szép
azok kívül, amit

639
00:34:41,820 --> 00:34:44,340
Nem tudom, ha valaki
ment szabadban mostanában.

640
00:34:44,340 --> 00:34:49,230
Elmentem alma szedés ezen a hétvégén,
és jaj, istenem, gyönyörű volt.

641
00:34:49,230 --> 00:34:52,250
Nem tudtam, hogy a levelek
lehet nézni, hogy a szép.

642
00:34:52,250 --> 00:34:53,610
>> Tehát ez csak egy fa, igaz?

643
00:34:53,610 --> 00:34:56,790
Ez csak néhány csomópont, és azt
rámutat arra, hogy egy csomó más csomópontok.

644
00:34:56,790 --> 00:34:59,570
Amint látod itt, ez
egyfajta visszatérő téma.

645
00:34:59,570 --> 00:35:03,720
Csomópontok mutató csomópontok a fajta
a lényeg a sok adatstruktúrák.

646
00:35:03,720 --> 00:35:06,670
Ez csak attól függ, hogy mi
azokat mutatnak egymással

647
00:35:06,670 --> 00:35:08,600
és hogyan áthalad
rajtuk keresztül és hogyan

648
00:35:08,600 --> 00:35:14,500
helyezze be a dolgokat, hogy meghatározza,
eltérő jellemzőkkel.

649
00:35:14,500 --> 00:35:17,600
>> Így csak néhány terminológia,
amit eddig látott.

650
00:35:17,600 --> 00:35:20,010
Tehát gyökér bármi is legtetején.

651
00:35:20,010 --> 00:35:21,200
ez, ahol mindig kezdeni.

652
00:35:21,200 --> 00:35:23,610
Akkor úgy mondanám, hogy a feje is.

653
00:35:23,610 --> 00:35:28,750
De a fák, hajlamosak vagyunk
hivatkoznak rá, mint a gyökér.

654
00:35:28,750 --> 00:35:32,820
>> Bármi alul here--
A nagyon, nagyon bottom--

655
00:35:32,820 --> 00:35:34,500
a figyelembe vett levelek.

656
00:35:34,500 --> 00:35:37,210
Így együtt jár a
egész fa, ugye?

657
00:35:37,210 --> 00:35:39,860
A levelek a széleken a fa.

658
00:35:39,860 --> 00:35:45,820
>> És akkor mi is van egy pár
feltételek beszélni csomópontok kapcsolatban

659
00:35:45,820 --> 00:35:46,680
egymáshoz.

660
00:35:46,680 --> 00:35:49,700
Tehát szülő,
gyermekek és testvérek.

661
00:35:49,700 --> 00:35:56,260
Így ebben az esetben, 3 a
szülő 5, 6, és 7.

662
00:35:56,260 --> 00:36:00,370
Így a szülő bármi is
egy lépés felett bármit is

663
00:36:00,370 --> 00:36:02,940
hivatkozva, így csak
mint a családfa.

664
00:36:02,940 --> 00:36:07,090
Remélhetőleg, ez az egész egy kicsit
bit intuitívabb, mint a próbálkozás.

665
00:36:07,090 --> 00:36:10,970
>> Testvérek bármilyen, amelyek
ugyanazon anyavállalat, ugye?

666
00:36:10,970 --> 00:36:13,470
Ők ugyanazon a szinten van.

667
00:36:13,470 --> 00:36:16,960
És akkor, mint én
mondván, a gyerekek csak

668
00:36:16,960 --> 00:36:22,630
bármi is van egy lépés alatt
a kérdéses csomópont, OK?

669
00:36:22,630 --> 00:36:23,470
Cool.

670
00:36:23,470 --> 00:36:25,610
Tehát egy bináris fa.

671
00:36:25,610 --> 00:36:31,450
Tud valaki Megkockáztatom az egyik
jellemzői a bináris fa?

672
00:36:31,450 --> 00:36:32,770
>> KÖZÖNSÉG: Max két levél.

673
00:36:32,770 --> 00:36:33,478
>> SPEAKER 1: Jobb.

674
00:36:33,478 --> 00:36:34,640
Tehát max két levél.

675
00:36:34,640 --> 00:36:39,730
Tehát ez előtt, mi volt ez
bizonyítjuk a három, de egy bináris fa,

676
00:36:39,730 --> 00:36:45,000
van egy max két
gyermekek egy szülő, ugye?

677
00:36:45,000 --> 00:36:46,970
Van egy másik
érdekes jellemző.

678
00:36:46,970 --> 00:36:51,550
Tudja valaki, hogy?

679
00:36:51,550 --> 00:36:52,620
Bináris fa.

680
00:36:52,620 --> 00:37:00,350
>> Tehát egy bináris fa lesz minden
A a-- ez nem sorted--

681
00:37:00,350 --> 00:37:05,320
de egy rendezett bináris fa,
mindent a jobb

682
00:37:05,320 --> 00:37:08,530
nagyobb, mint a szülő,
és minden a bal oldalon

683
00:37:08,530 --> 00:37:10,035
kevesebb, mint a szülő.

684
00:37:10,035 --> 00:37:15,690
És ez volt a teszt
kérdés előtt, ezért jó tudni.

685
00:37:15,690 --> 00:37:19,500
Tehát ahogy mi határozza ezt meg,
megint, van egy másik csomópont.

686
00:37:19,500 --> 00:37:21,880
Ez nagyon hasonlít ahhoz, amit?

687
00:37:21,880 --> 00:37:28,336

688
00:37:28,336 --> 00:37:28,836
Kétszeresen

689
00:37:28,836 --> 00:37:29,320
>> KÖZÖNSÉG: láncolt listák

690
00:37:29,320 --> 00:37:31,100
>> SPEAKER 1: A kettős láncolt lista, ugye?

691
00:37:31,100 --> 00:37:33,690
Tehát, ha kicseréljük ezt
az előző és a következő,

692
00:37:33,690 --> 00:37:35,670
ez egy kétszeresen láncolt lista.

693
00:37:35,670 --> 00:37:40,125
De ebben az esetben, mi valójában
van bal és jobb, és ennyi.

694
00:37:40,125 --> 00:37:41,500
Egyébként ez pontosan ugyanaz.

695
00:37:41,500 --> 00:37:43,374
Még mindig az elem
keres,

696
00:37:43,374 --> 00:37:45,988
és csak két mutatót
fog, bármi is legyen a következő.

697
00:37:45,988 --> 00:37:49,210

698
00:37:49,210 --> 00:37:51,870
Igen, így bináris kereső fába.

699
00:37:51,870 --> 00:37:57,665
Ha azt vesszük észre, mindent a
Itt nagyobb than--

700
00:37:57,665 --> 00:37:59,850
vagy mindent azonnal
Az itt

701
00:37:59,850 --> 00:38:02,840
nagyobb, mint, minden
itt kisebb, mint.

702
00:38:02,840 --> 00:38:06,980

703
00:38:06,980 --> 00:38:14,000
>> Tehát, ha mi voltunk keresgélni, azt
meg kell nézni, nagyon közel a bináris keresés

704
00:38:14,000 --> 00:38:14,910
itt, ugye?

705
00:38:14,910 --> 00:38:17,640
Kivéve ahelyett,
fele a tömb,

706
00:38:17,640 --> 00:38:21,720
mi csak nézte vagy a bal
oldali vagy a jobb oldalon a fa.

707
00:38:21,720 --> 00:38:24,850
Szóval ez egy kicsit egyszerűbb, azt hiszem.

708
00:38:24,850 --> 00:38:29,300
>> Tehát, ha a gyökér NULL,
nyilván ez csak hamis.

709
00:38:29,300 --> 00:38:33,470
És ha ott van, nyilván ez igaz.

710
00:38:33,470 --> 00:38:35,320
Ha ez kevesebb, mint keressük a bal oldalon.

711
00:38:35,320 --> 00:38:37,070
Ha ez nagyobb, mint,
keressük a megfelelő.

712
00:38:37,070 --> 00:38:39,890
Ez pontosan olyan, mint a bináris keresés,
csak egy másik adat struktúra

713
00:38:39,890 --> 00:38:40,600
hogy mi használ.

714
00:38:40,600 --> 00:38:42,790
Helyett egy tömb,
ez csak egy bináris fa.

715
00:38:42,790 --> 00:38:45,820

716
00:38:45,820 --> 00:38:48,090
>> OK, halom.

717
00:38:48,090 --> 00:38:51,550
És azt is, úgy néz ki, mint mi
Lehet, hogy egy kis időt.

718
00:38:51,550 --> 00:38:54,460
Ha így teszünk, boldog vagyok, hogy menjen
bármely e újra.

719
00:38:54,460 --> 00:38:56,856
OK, így halmozódik.

720
00:38:56,856 --> 00:39:02,695
Tudja valaki emlékszik mi stacks--
bármely jellemzői kéményen?

721
00:39:02,695 --> 00:39:05,550

722
00:39:05,550 --> 00:39:10,400
>> OK, így a legtöbben, azt hiszem,
eszik az étkezőben halls--

723
00:39:10,400 --> 00:39:13,100
mint ahogy mi nem szeretnénk.

724
00:39:13,100 --> 00:39:16,900
De természetesen, akkor gondolom, egy halom
szó szerint csak egy halom tálcák

725
00:39:16,900 --> 00:39:18,460
vagy egy halom dolog.

726
00:39:18,460 --> 00:39:21,820
És ami fontos
észre, hogy ez az

727
00:39:21,820 --> 00:39:26,850
something-- jellemző
hogy hívjuk by-- a LIFO.

728
00:39:26,850 --> 00:39:28,450
Tudja valaki, hogy mi áll az?

729
00:39:28,450 --> 00:39:29,070
Mmhmm?

730
00:39:29,070 --> 00:39:30,650
>> KÖZÖNSÉG: Utolsó in, first out.

731
00:39:30,650 --> 00:39:32,250
>> SPEAKER 1: Jobb, utolsóként, first out.

732
00:39:32,250 --> 00:39:36,585
Tehát, ha tudjuk, hogy mi a dolgok egymásra rakható
fel, a legegyszerűbb dolog, hogy megragad off--

733
00:39:36,585 --> 00:39:39,570
és talán az egyetlen dolog, amit megragad
ki, ha a verem nagy enough--

734
00:39:39,570 --> 00:39:40,850
az, hogy a felső elem.

735
00:39:40,850 --> 00:39:43,460
Tehát bármit került a
last-- mint látjuk itt,

736
00:39:43,460 --> 00:39:46,370
bármilyen szorult
A legtöbb recently-- a

737
00:39:46,370 --> 00:39:51,160
lesz az első
dolog, hogy elsül, OK?

738
00:39:51,160 --> 00:39:56,324
>> Szóval mi van itt
másik typedef struct.

739
00:39:56,324 --> 00:39:58,740
Ez tényleg csak olyan, mint egy
gyorstalpaló az adat struktúra,

740
00:39:58,740 --> 00:40:01,650
így van egy csomó dobott srácok.

741
00:40:01,650 --> 00:40:02,540
Tudom.

742
00:40:02,540 --> 00:40:04,970
Így még egy struct.

743
00:40:04,970 --> 00:40:06,740
Yay szerkezetekhez.

744
00:40:06,740 --> 00:40:16,660
>> És ebben az esetben, ez néhány mutató
egy tömb, amely bizonyos kapacitás.

745
00:40:16,660 --> 00:40:20,830
Tehát ez azt jelenti, a stack
itt, mint a mi jelenlegi tömb

746
00:40:20,830 --> 00:40:22,520
ami tartja az elemeket.

747
00:40:22,520 --> 00:40:24,850
És akkor itt van egy kis méret.

748
00:40:24,850 --> 00:40:31,170
>> És általában, meg szeretné tartani
követi, hogy nagy a verem

749
00:40:31,170 --> 00:40:36,180
mert mi ez lesz, hogy
, hogy nem az, ha tudod, hogy a méret,

750
00:40:36,180 --> 00:40:39,170
lehetővé teszi, hogy azt mondják,
OK, én vagyok a kapacitás?

751
00:40:39,170 --> 00:40:40,570
Adhatok mást?

752
00:40:40,570 --> 00:40:44,650
És azt is mondja,
ahol a tetején a verem

753
00:40:44,650 --> 00:40:48,180
annyira tudod, mit
ténylegesen felszállni.

754
00:40:48,180 --> 00:40:51,760
És ez valóban lesz
egy kicsit világos van.

755
00:40:51,760 --> 00:40:57,350
>> Így push, egy dolog, ha
valaha végrehajtani tolja,

756
00:40:57,350 --> 00:41:01,330
mivel én csak azt mondom, a
verem korlátozott méret, ugye?

757
00:41:01,330 --> 00:41:03,990
A tömb volt némi kapacitással.

758
00:41:03,990 --> 00:41:04,910
Ez egy tömb.

759
00:41:04,910 --> 00:41:08,930
Ez egy fix méretű, így meg kell
győződjön meg arról, hogy nem vagyunk hogy több

760
00:41:08,930 --> 00:41:11,950
a mi tömb, mint mi
valójában hely.

761
00:41:11,950 --> 00:41:16,900
>> Ha tehát létre egy push
funkció, az első dolog, amit teszel, mondjuk, rendben van,

762
00:41:16,900 --> 00:41:18,570
tudom van hely az én verem?

763
00:41:18,570 --> 00:41:23,330
Mert ha én nem, bocs,
Nem tudom tárolni a elemet.

764
00:41:23,330 --> 00:41:28,980
Ha igen, akkor a tárolni kívánt
azt a tetején a halom, ugye?

765
00:41:28,980 --> 00:41:31,325
>> És ez miért van
nyomon követni a méret.

766
00:41:31,325 --> 00:41:35,290
Ha nem követhető nyomon méret,
nem tudjuk, hová tegye.

767
00:41:35,290 --> 00:41:39,035
Azt nem tudom, hogy sok mindent
vannak a tömbben már.

768
00:41:39,035 --> 00:41:41,410
Mint nyilván vannak olyan módon,
hogy talán meg tudná csinálni.

769
00:41:41,410 --> 00:41:44,610
Lehet inicializálni mindent NULL
majd ellenőrizze a legújabb NULL,

770
00:41:44,610 --> 00:41:47,950
de egy sokkal egyszerűbb dolog csak
mondani, hogy rendben van, nyomon követheti a méret.

771
00:41:47,950 --> 00:41:51,840
Mint tudom, hogy van négy elem
az én tömb, így a következő dolog

772
00:41:51,840 --> 00:41:55,930
hogy mi fel vagyunk
majd tárolja index 4.

773
00:41:55,930 --> 00:42:00,940
És akkor, természetesen, ez azt jelenti, hogy
Sikeresen tolt valami

774
00:42:00,940 --> 00:42:03,320
rá a verem, akkor
szeretnék növelni a méretét

775
00:42:03,320 --> 00:42:08,880
úgy, hogy tudja, hol van olyan
hogy akkor nyomja jobban a dolgokat.

776
00:42:08,880 --> 00:42:12,730
>> Tehát, ha megpróbáljuk a pop
valamit a verem,

777
00:42:12,730 --> 00:42:16,072
mi lehet az első dolog
hogy szeretnénk ellenőrizni?

778
00:42:16,072 --> 00:42:18,030
Megpróbálod venni
valami ki a verem.

779
00:42:18,030 --> 00:42:21,710

780
00:42:21,710 --> 00:42:24,781
Biztos benne van
valami a stack?

781
00:42:24,781 --> 00:42:25,280
Nem.

782
00:42:25,280 --> 00:42:26,894
Szóval mit is akarunk ellenőrizni?

783
00:42:26,894 --> 00:42:27,810
>> KÖZÖNSÉG: [hallható].

784
00:42:27,810 --> 00:42:29,880
SPEAKER 1. Ellenőrizze a méret?

785
00:42:29,880 --> 00:42:31,840
Méret.

786
00:42:31,840 --> 00:42:38,520
Ezért szeretnénk, hogy ellenőrizze, hogy
a mérete nagyobb, mint 0, OK?

787
00:42:38,520 --> 00:42:44,970
És ha igen, akkor szeretnénk csökkenteni
mi mérete 0 és vissza azt.

788
00:42:44,970 --> 00:42:45,840
Miért?

789
00:42:45,840 --> 00:42:49,950
>> Az első voltunk
toló, mi tolta

790
00:42:49,950 --> 00:42:52,460
ra méretet, majd frissített méretét.

791
00:42:52,460 --> 00:42:57,850
Ebben az esetben, mi fogásvétel- csökkentéssel méret
és akkor vesz le, kopasztás azt

792
00:42:57,850 --> 00:42:58,952
a mi tömb.

793
00:42:58,952 --> 00:42:59,826
Miért is tesszük ezt?

794
00:42:59,826 --> 00:43:04,800

795
00:43:04,800 --> 00:43:11,811
Tehát, ha van egy dolog, én verem,
mi lenne az én méretem ezen a ponton?

796
00:43:11,811 --> 00:43:13,140
1.

797
00:43:13,140 --> 00:43:15,180
>> És hol van 1 elem tárolva?

798
00:43:15,180 --> 00:43:17,621
A mi index?

799
00:43:17,621 --> 00:43:18,120
KÖZÖNSÉG: 0.

800
00:43:18,120 --> 00:43:19,060
SPEAKER 1: 0-ra.

801
00:43:19,060 --> 00:43:22,800
Így ebben az esetben, mi
Mindig kell, hogy sure--

802
00:43:22,800 --> 00:43:27,630
visszatérés helyett
méret mínusz 1, mert

803
00:43:27,630 --> 00:43:31,730
tudják, hogy mi az elem
fog tárolni 1-gyel kevesebb

804
00:43:31,730 --> 00:43:34,705
függetlenül a mérete, ez a
csak vigyáz rá.

805
00:43:34,705 --> 00:43:36,080
Ez egy kicsit elegáns módon.

806
00:43:36,080 --> 00:43:41,220
És mi csak csökkentse a
méret majd vissza méretét.

807
00:43:41,220 --> 00:43:42,330
Mmhmm?

808
00:43:42,330 --> 00:43:45,300
>> KÖZÖNSÉG: Azt hiszem, csak általánosságban,
miért lenne ez az adat struktúra

809
00:43:45,300 --> 00:43:47,800
előnyös?

810
00:43:47,800 --> 00:43:50,660
>> SPEAKER 1: Attól függ, hogy az összefüggésben.

811
00:43:50,660 --> 00:43:57,420
Így néhány elmélet,
ha dolgozik with-- OK,

812
00:43:57,420 --> 00:44:02,750
hadd lássa, van egy előnyös egy
ami előnyös a több, mint kívül

813
00:44:02,750 --> 00:44:05,420
CS.

814
00:44:05,420 --> 00:44:15,780
Halom, bármikor szüksége
nyomon követni valamit, ami

815
00:44:15,780 --> 00:44:20,456
a legutóbb hozzáadott amikor
fogsz használni kívánt a verem.

816
00:44:20,456 --> 00:44:24,770
>> És én nem hiszem, egy jó
példája, hogy most.

817
00:44:24,770 --> 00:44:29,955
De amikor a legutóbbi
dolog a legfontosabb az Ön számára,

818
00:44:29,955 --> 00:44:31,705
ez az, amikor egy halom
lesz hasznos.

819
00:44:31,705 --> 00:44:35,797

820
00:44:35,797 --> 00:44:39,330
Próbálok gondolkodni, ha
van egy jó ehhez.

821
00:44:39,330 --> 00:44:43,720
Ha azt hiszem, egy jó példa a következő
20 percig, én biztosan mondani.

822
00:44:43,720 --> 00:44:49,455
>> De összességében, ha van valami,
mint mondtam a legtöbb, ahol a legutóbbi

823
00:44:49,455 --> 00:44:52,470
a legfontosabb, hogy ez
ahol egy halom kerül szóba.

824
00:44:52,470 --> 00:44:58,860
Mivel a sorok a fajta az ellenkezőjét.

825
00:44:58,860 --> 00:44:59,870
És a kis kutya.

826
00:44:59,870 --> 00:45:00,890
Hát nem ez a jó hír, nem?

827
00:45:00,890 --> 00:45:03,299
Úgy érzem, kellene
csak egy nyuszi videó

828
00:45:03,299 --> 00:45:05,090
kellős közepén
szakasz srácok

829
00:45:05,090 --> 00:45:08,870
mert ez egy intenzív szakasz.

830
00:45:08,870 --> 00:45:10,480
>> Így a sor.

831
00:45:10,480 --> 00:45:12,710
Alapvetően egy sor olyan, mint egy vonal.

832
00:45:12,710 --> 00:45:15,780
Srácok én biztos vagyok benne, ez a mindennapi használat,
csakúgy, mint a mi étkezőben.

833
00:45:15,780 --> 00:45:18,160
Tehát menni
és megkapjuk a tálcák, én vagyok

834
00:45:18,160 --> 00:45:21,260
arról, hogy van, hogy sorban
hogy ellop vagy kap az étel.

835
00:45:21,260 --> 00:45:24,650
>> Tehát itt a különbség
az, hogy ez FIFO.

836
00:45:24,650 --> 00:45:30,090
Tehát, ha LIFO volt utolsó, első
ki, FIFO először, first out.

837
00:45:30,090 --> 00:45:33,400
Szóval, ez az, ahol bármit tesz
az első a legfontosabb.

838
00:45:33,400 --> 00:45:35,540
Tehát, ha vártál
Egy line-- te is

839
00:45:35,540 --> 00:45:39,130
képzeld el, ha elment
megy kap az új iPhone

840
00:45:39,130 --> 00:45:42,800
és ez volt a verem, ahol az
utolsó ember a sorban megvan az első,

841
00:45:42,800 --> 00:45:44,160
emberek megölik egymást.

842
00:45:44,160 --> 00:45:49,800
>> Szóval FIFO, mindannyian nagyon ismerős
és a való világban itt,

843
00:45:49,800 --> 00:45:54,930
és ez mind köze van a ténylegesen
milyen felüdítő az egész vonalon

844
00:45:54,930 --> 00:45:56,900
és sorban szerkezet.

845
00:45:56,900 --> 00:46:02,390
Így mivel a verem,
mi nyomja és pop.

846
00:46:02,390 --> 00:46:06,440
Egy sor, mi
Enqueue és dequeue.

847
00:46:06,440 --> 00:46:10,910
Így Enqueue lényegében azt jelenti,
tedd rá a hátsó,

848
00:46:10,910 --> 00:46:13,680
és dequeue eszközök figyelembe
le elölről.

849
00:46:13,680 --> 00:46:18,680
Így a adatstruktúra a
kicsit bonyolult.

850
00:46:18,680 --> 00:46:21,060
Van egy másik dolog, hogy nyomon követni.

851
00:46:21,060 --> 00:46:25,950
>> Így anélkül, hogy a fej, ez a
pontosan egy halom, ugye?

852
00:46:25,950 --> 00:46:27,900
Ez ugyanaz a szerkezet, mint egy verem.

853
00:46:27,900 --> 00:46:32,480
Az egyetlen dolog, más most az, hogy mi
ezt a fejet, ami mit gondolsz

854
00:46:32,480 --> 00:46:34,272
fog nyomon követni?

855
00:46:34,272 --> 00:46:35,510
>> KÖZÖNSÉG: Az első.

856
00:46:35,510 --> 00:46:38,685
>> SPEAKER 1: Igaz, a
az első dolog, amit hozott.

857
00:46:38,685 --> 00:46:41,130
A feje a sor.

858
00:46:41,130 --> 00:46:42,240
Aki az első a sorban.

859
00:46:42,240 --> 00:46:45,300

860
00:46:45,300 --> 00:46:49,420
Rendben, ha mi Enqueue.

861
00:46:49,420 --> 00:46:52,720

862
00:46:52,720 --> 00:46:55,920
Ismét bármelyikével
ezeket az adatstruktúrákat,

863
00:46:55,920 --> 00:46:59,760
mivel van dolgunk tömb,
azt kell ellenőrizni, ha van hely.

864
00:46:59,760 --> 00:47:03,290
>> Ez olyan, mint én mondom
srácok, ha megnyit egy fájlt,

865
00:47:03,290 --> 00:47:04,760
meg kell, hogy ellenőrizze a null.

866
00:47:04,760 --> 00:47:08,330
Ezekkel a halom
és sorok, meg kell

867
00:47:08,330 --> 00:47:13,420
hogy ha van hely, mert vagyunk
foglalkozik a fix méretű tömb,

868
00:47:13,420 --> 00:47:16,030
mint látjuk here-- 0, 1 mind 5.

869
00:47:16,030 --> 00:47:20,690
Mi tehát ebben az esetben az ellenőrzés
hogy ha van még hely.

870
00:47:20,690 --> 00:47:23,110
A mi mérete kisebb, mint képesség?

871
00:47:23,110 --> 00:47:28,480
>> Ha igen, meg kell tárolni a
a farok és mi frissítjük méret.

872
00:47:28,480 --> 00:47:30,250
Tehát mi is a farok lesz ebben az esetben?

873
00:47:30,250 --> 00:47:32,360
Ez nem kifejezetten írva.

874
00:47:32,360 --> 00:47:33,380
Hogyan tároljuk?

875
00:47:33,380 --> 00:47:34,928
Mi lenne a farok lesz?

876
00:47:34,928 --> 00:47:38,600

877
00:47:38,600 --> 00:47:40,190
>> Szóval séta ezt a példát.

878
00:47:40,190 --> 00:47:44,590
Tehát ez egy sor 6-os méret, ugye?

879
00:47:44,590 --> 00:47:49,220
És mi van most, a mérete 5.

880
00:47:49,220 --> 00:47:55,240
És amikor betette, ez lesz
hogy menjen be az ötödik index, igaz?

881
00:47:55,240 --> 00:47:57,030
Így tárolja farok.

882
00:47:57,030 --> 00:48:05,600
>> Egy másik módja, hogy írjon farok lenne csak
a mi tömbbel index a méret, ugye?

883
00:48:05,600 --> 00:48:07,560
Ez a méret 5.

884
00:48:07,560 --> 00:48:11,490
Következő dolog fog menni 5.

885
00:48:11,490 --> 00:48:12,296
Cool?

886
00:48:12,296 --> 00:48:13,290
OK.

887
00:48:13,290 --> 00:48:16,350
Egyre kissé bonyolultabb
amikor elkezdjük Messiás a fejét.

888
00:48:16,350 --> 00:48:17,060
Igen?

889
00:48:17,060 --> 00:48:20,090
>> KÖZÖNSÉG: Ez azt jelenti, hogy
volna nyilvánítani tömb

890
00:48:20,090 --> 00:48:23,880
öt elem hosszú és
akkor mi adunk rá?

891
00:48:23,880 --> 00:48:24,730
>> SPEAKER 1: Nem.

892
00:48:24,730 --> 00:48:27,560
Így ebben az esetben, ez egy verem.

893
00:48:27,560 --> 00:48:31,760
Ez kell bejelenteni
mint egy sor 6-os méret.

894
00:48:31,760 --> 00:48:37,120
És ebben az esetben, mi
csak egy hely maradt.

895
00:48:37,120 --> 00:48:42,720
>> OK, így egy dolog ebben
esetben, ha a fej 0,

896
00:48:42,720 --> 00:48:45,270
akkor egyszerűen hozzá a méret.

897
00:48:45,270 --> 00:48:51,020
De ez egy kicsit trükkösebb
mert valóban, azok

898
00:48:51,020 --> 00:48:52,840
nincs dia
ezt, úgyhogy megyek

899
00:48:52,840 --> 00:48:56,670
felhívni egy, mert ez nem
ennyire egyszerű, ha egyszer

900
00:48:56,670 --> 00:48:59,230
kezdeni megszabadulni a dolgokat.

901
00:48:59,230 --> 00:49:03,920
Tehát míg a verem
még mindig csak

902
00:49:03,920 --> 00:49:08,920
aggódnia, hogy mi a mérete
amikor hozzá valamit,

903
00:49:08,920 --> 00:49:15,710
egy sor akkor is kell, hogy
arról, hogy a fejed elszámolni,

904
00:49:15,710 --> 00:49:20,760
mert egy klassz dolog sorok
az, hogy ha nem a kapacitás,

905
00:49:20,760 --> 00:49:23,040
akkor valóban tenni kerületi.

906
00:49:23,040 --> 00:49:28,810
>> OK, így egy thing-- ó,
Ez szörnyű kréta.

907
00:49:28,810 --> 00:49:31,815
Egy dolog, hogy fontolja meg a helyzet.

908
00:49:31,815 --> 00:49:35,514

909
00:49:35,514 --> 00:49:37,140
Majd csak nem öt.

910
00:49:37,140 --> 00:49:41,810
OK, így megyünk
azt mondják, a fej itt.

911
00:49:41,810 --> 00:49:46,140
Ez értéke 0, 1, 2, 3, 4.

912
00:49:46,140 --> 00:49:54,210
>> A fej ott van, és
Kérjük, a dolgok bennük.

913
00:49:54,210 --> 00:49:58,340
És azt akarjuk, hogy adjunk valamit, nem?

914
00:49:58,340 --> 00:50:01,170
Tehát a dolog, hogy meg kell
tudom, hogy a fej mindig

915
00:50:01,170 --> 00:50:05,620
fog mozogni, és így
akkor visszahurkoló körül, OK?

916
00:50:05,620 --> 00:50:10,190
>> Tehát ez a sor van hely, igaz?

917
00:50:10,190 --> 00:50:13,950
Ez hely a legelején,
milyen a fordítottja.

918
00:50:13,950 --> 00:50:17,920
Szóval, mit kell tennie, hogy mi
kell számítani a farok.

919
00:50:17,920 --> 00:50:20,530
Ha tudja, hogy a
fej nem mozdult, farok

920
00:50:20,530 --> 00:50:24,630
csak a tömbbel
az index a méretét.

921
00:50:24,630 --> 00:50:30,000
>> De a valóságban, ha egy sor,
a feje valószínűleg frissítése.

922
00:50:30,000 --> 00:50:33,890
Szóval, mit kell tennie, hogy
tulajdonképpen kiszámítja a farok.

923
00:50:33,890 --> 00:50:39,990
Mi tehát ez a formula
itt, amit én hagyom, hogy

924
00:50:39,990 --> 00:50:42,680
srácok gondol, és
aztán majd beszélünk róla.

925
00:50:42,680 --> 00:50:49,567

926
00:50:49,567 --> 00:50:50,400
Tehát ez a képesség.

927
00:50:50,400 --> 00:50:55,890

928
00:50:55,890 --> 00:50:59,660
>> Tehát ez valóban
kapsz egy módja annak, hogy csináld.

929
00:50:59,660 --> 00:51:03,205

930
00:51:03,205 --> 00:51:04,330
Mert ebben az esetben, mi?

931
00:51:04,330 --> 00:51:09,205
Fejünk az 1, a mérete 4.

932
00:51:09,205 --> 00:51:11,760

933
00:51:11,760 --> 00:51:18,490
Ha mod, hogy 5, megkapjuk 0,
ott, ahol mi kellene bemenet is.

934
00:51:18,490 --> 00:51:23,320

935
00:51:23,320 --> 00:51:26,080
>> Tehát akkor a következő helyzet,
ha mi voltunk erre,

936
00:51:26,080 --> 00:51:33,390
azt mondjuk, OK, menjünk dequeue valamit.

937
00:51:33,390 --> 00:51:34,390
Mi dequeue ezt.

938
00:51:34,390 --> 00:51:37,740
Mi ki ezt az elemet, ugye?

939
00:51:37,740 --> 00:51:47,930
>> És most a fejünk mutat itt,
és szeretnénk adni egy másik dolog.

940
00:51:47,930 --> 00:51:52,470
Ez alapvetően a
vissza a mi sor, ugye?

941
00:51:52,470 --> 00:51:55,450
Sorok tekerje körbe a tömböt.

942
00:51:55,450 --> 00:51:57,310
Ez az egyik fő különbség.

943
00:51:57,310 --> 00:51:58,780
Stacks, akkor nem ezt.

944
00:51:58,780 --> 00:52:01,140
>> A sorok, akkor
mert minden, ami számít

945
00:52:01,140 --> 00:52:03,940
az, hogy tudod, mi
legutóbb hozzá.

946
00:52:03,940 --> 00:52:10,650
Mivel minden lesz hozzá
ez balra irányban, ebben az esetben,

947
00:52:10,650 --> 00:52:16,480
, majd tekerje körbe, akkor
tovább üzembe új elemek

948
00:52:16,480 --> 00:52:18,830
elején a tömb
mert ez nem igazán

949
00:52:18,830 --> 00:52:20,640
az első a tömb többé.

950
00:52:20,640 --> 00:52:26,320
Azt hiszem az elején a
tömb, ahol a feje valójában.

951
00:52:26,320 --> 00:52:29,710
>> Szóval ez a képlet, hogy hogyan
kiszámítja a farok.

952
00:52:29,710 --> 00:52:32,780

953
00:52:32,780 --> 00:52:35,610
Van ennek értelme?

954
00:52:35,610 --> 00:52:36,110
OK.

955
00:52:36,110 --> 00:52:39,400

956
00:52:39,400 --> 00:52:44,040
OK, dequeue, majd
srácok 10 perc

957
00:52:44,040 --> 00:52:48,840
kérdezd bármilyen tisztázó kérdéseket
akarsz, mert tudom, hogy őrült.

958
00:52:48,840 --> 00:52:51,980
>> Rendben, tehát ugyanabban a way--
Nem tudom, hogy ti észre,

959
00:52:51,980 --> 00:52:53,450
de CS szól mintákat.

960
00:52:53,450 --> 00:52:57,370
A dolgok nagyjából az
ugyanaz, csak apró trükk.

961
00:52:57,370 --> 00:52:58,950
Tehát ugyanaz a dolog itt.

962
00:52:58,950 --> 00:53:04,040
Meg kell nézni, hogy mi valójában
Van valami a sorban, igaz?

963
00:53:04,040 --> 00:53:05,960
Mondjuk, OK, mi mérete nagyobb, mint 0?

964
00:53:05,960 --> 00:53:06,730
Cool.

965
00:53:06,730 --> 00:53:10,690
>> Ha így teszünk, akkor haladunk a fej, amely
az, amit én most itt bemutatott.

966
00:53:10,690 --> 00:53:13,870
Mi frissítjük fejét, hogy még egy.

967
00:53:13,870 --> 00:53:18,390
És akkor csökkentse a
méret és vissza az elemet.

968
00:53:18,390 --> 00:53:21,000

969
00:53:21,000 --> 00:53:26,250
>> Sokkal több konkrét
kód study.cs50.net,

970
00:53:26,250 --> 00:53:29,440
és én nagyon ajánlom megy
keresztül, ha van időd,

971
00:53:29,440 --> 00:53:30,980
akkor is, ha ez csak egy pszeudo-kódot.

972
00:53:30,980 --> 00:53:35,980
És ha akartok beszélni keresztül
hogy velem egy az egy, kérem tudassa velem

973
00:53:35,980 --> 00:53:37,500
tudom.

974
00:53:37,500 --> 00:53:38,770
Lennék szívesen.

975
00:53:38,770 --> 00:53:42,720
Adatszerkezetek, ha
szedése CS 124, akkor

976
00:53:42,720 --> 00:53:47,830
tudom, hogy nagyon fog adatszerkezetek
szórakoztató és ez csak a kezdet.

977
00:53:47,830 --> 00:53:50,350
>> Szóval tudom, hogy nehéz.

978
00:53:50,350 --> 00:53:51,300
Ez rendben van.

979
00:53:51,300 --> 00:53:52,410
Küzdünk.

980
00:53:52,410 --> 00:53:53,630
Még mindig.

981
00:53:53,630 --> 00:53:56,660
Szóval ne aggódj túl sokat róla.

982
00:53:56,660 --> 00:54:02,390
>> De ez alapvetően a
gyorstalpaló az adatszerkezeteket.

983
00:54:02,390 --> 00:54:03,400
Tudom, hogy sokat.

984
00:54:03,400 --> 00:54:06,860
Van valami, amit
szeretnék menni újra?

985
00:54:06,860 --> 00:54:09,400
Bármit akarunk beszélni keresztül?

986
00:54:09,400 --> 00:54:10,060
Igen?

987
00:54:10,060 --> 00:54:16,525
>> KÖZÖNSÉG: Az, hogy például így
az új farok 0 keresztül?

988
00:54:16,525 --> 00:54:17,150
SPEAKER 1: Igen.

989
00:54:17,150 --> 00:54:18,230
KÖZÖNSÉG: OK.

990
00:54:18,230 --> 00:54:24,220
Akkor megy keresztül,
ha volna 1 plusz 4 or--

991
00:54:24,220 --> 00:54:27,671
>> SPEAKER 1: Szóval mondtál,
amikor akarunk menni ezt megint?

992
00:54:27,671 --> 00:54:28,296
KÖZÖNSÉG: Igen.

993
00:54:28,296 --> 00:54:38,290
Tehát, ha arra rájönni out-- hol vannak
Ön kiszámításának farok ebben?

994
00:54:38,290 --> 00:54:44,260
>> SPEAKER 1: Tehát a farok
volt in-- megváltoztattam ezt.

995
00:54:44,260 --> 00:54:52,010
Tehát ebben a példában ide, ez volt
A tömb keresünk, OK?

996
00:54:52,010 --> 00:54:54,670
Tehát a dolgokat az 1., 2., 3., és 4..

997
00:54:54,670 --> 00:55:05,850
Tehát fejünk egyenlő 1-es
Ezen a ponton, és a mi mérete egyenlő 4

998
00:55:05,850 --> 00:55:07,050
ezen a ponton, igaz?

999
00:55:07,050 --> 00:55:08,960
>> Mindannyian egyetértenek abban, hogy ez a helyzet?

1000
00:55:08,960 --> 00:55:14,620
Tehát mi a fej és a méret, ami
ad nekünk az 5, majd mi mod 5.

1001
00:55:14,620 --> 00:55:20,690
Kapunk 0, ami azt mondja, hogy 0
hol van a farok, ahol van hely.

1002
00:55:20,690 --> 00:55:22,010
>> KÖZÖNSÉG: Mi az a sapka?

1003
00:55:22,010 --> 00:55:23,520
>> SPEAKER 1: kapacitása.

1004
00:55:23,520 --> 00:55:24,020
Bocsánat.

1005
00:55:24,020 --> 00:55:29,640
Annak érdekében, hogy a méret a tömb.

1006
00:55:29,640 --> 00:55:35,210

1007
00:55:35,210 --> 00:55:36,047
Igen?

1008
00:55:36,047 --> 00:55:39,210
>> KÖZÖNSÉG: [hallható] előtt
térjünk vissza az elem?

1009
00:55:39,210 --> 00:55:46,270
>> SPEAKER 1: így haladunk a
fej vagy vissza a pillanat?

1010
00:55:46,270 --> 00:55:52,680
Tehát, ha valaki mozog, csökkentse a méret?

1011
00:55:52,680 --> 00:55:54,150
Várj.

1012
00:55:54,150 --> 00:55:55,770
Én biztosan elfelejtettem másik.

1013
00:55:55,770 --> 00:56:00,646

1014
00:56:00,646 --> 00:56:01,990
Semmi baj.

1015
00:56:01,990 --> 00:56:04,980
Nincs még egy formula.

1016
00:56:04,980 --> 00:56:09,980
Igen, amit szeretne visszatérni
a fejét, majd helyezze vissza.

1017
00:56:09,980 --> 00:56:13,270
>> KÖZÖNSÉG: OK, mert ez
pont, a fej volt a 0,

1018
00:56:13,270 --> 00:56:18,452
és akkor vissza akar térni
index 0 és végezze fej 1?

1019
00:56:18,452 --> 00:56:19,870
>> SPEAKER 1: Jobb.

1020
00:56:19,870 --> 00:56:22,820
Azt hiszem, van egy másik
formula olyan, mint ez.

1021
00:56:22,820 --> 00:56:26,970
Nem tudom, hogy a tetején a fejét,
Én nem akarom, hogy ön a rossz.

1022
00:56:26,970 --> 00:56:35,470
De azt hiszem, ez teljesen érvényes
mondjuk, OK, tárolja ezt element-- bármi

1023
00:56:35,470 --> 00:56:40,759
fej elem ez-- csökkentse a
méret, mozog a feje fölött, és visszatérés

1024
00:56:40,759 --> 00:56:41,800
bármi ez az elem.

1025
00:56:41,800 --> 00:56:44,760
Ez tökéletesen érvényes.

1026
00:56:44,760 --> 00:56:45,260
OK.

1027
00:56:45,260 --> 00:56:48,360

1028
00:56:48,360 --> 00:56:53,560
Úgy érzem, ez nem
mint a most-- te nem

1029
00:56:53,560 --> 00:56:55,740
fog kisétálni innen
mint, igen, tudom, hogy próbál.

1030
00:56:55,740 --> 00:56:56,880
Megvan minden.

1031
00:56:56,880 --> 00:56:57,670
Ez rendben van.

1032
00:56:57,670 --> 00:57:00,200
Ígérem.

1033
00:57:00,200 --> 00:57:05,240
De adatszerkezetek van valami, hogy
ez veszi el a legtöbb időt, hogy megszokja a.

1034
00:57:05,240 --> 00:57:10,010
Talán az egyik legnehezebb
dolog, azt hiszem, a tanfolyam.

1035
00:57:10,010 --> 00:57:15,330
>> Így biztosan tart
ismétlés és keres at-- én

1036
00:57:15,330 --> 00:57:20,050
Nem igazán tudom, láncolt listák
amíg én túl sokat velük,

1037
00:57:20,050 --> 00:57:22,550
ugyanúgy, hogy én nem
igazán értem mutatók

1038
00:57:22,550 --> 00:57:27,040
míg Elegem tanítani két
év, és nem a saját psets vele.

1039
00:57:27,040 --> 00:57:28,990
Beletelik sok újraiterálási és idő.

1040
00:57:28,990 --> 00:57:32,600
És végül, ez a fajta kattintson.

1041
00:57:32,600 --> 00:57:36,320
>> De addig is, ha van ilyen
a magas szintű megértése, hogy mit

1042
00:57:36,320 --> 00:57:39,321
ezek nem, a profik
és cons-- amely a mi

1043
00:57:39,321 --> 00:57:41,820
valóban hajlamosak hangsúlyozni,
különösen az intro során.

1044
00:57:41,820 --> 00:57:45,511
Mint, miért használjuk
egy próbát át egy tömb?

1045
00:57:45,511 --> 00:57:48,010
Mint, mi a pozitív
és negatív a minden egyes ilyen?

1046
00:57:48,010 --> 00:57:51,610
>> És megérteni a trade-off
között minden egyes ilyen struktúrák

1047
00:57:51,610 --> 00:57:54,910
az, ami sokkal fontosabb most.

1048
00:57:54,910 --> 00:57:58,140
Lehet, hogy egy őrült
kérdést, vagy két, ez

1049
00:57:58,140 --> 00:58:03,710
fog kérni, hogy végre push or
végre pop vagy Enqueue és dequeue.

1050
00:58:03,710 --> 00:58:07,340
De a legtöbb esetben, hogy miután
magasabb szintű megértést és több

1051
00:58:07,340 --> 00:58:09,710
Egy intuitív megértése is
sokkal fontosabb, mint a ténylegesen

1052
00:58:09,710 --> 00:58:11,250
hogy képes végrehajtani azt.

1053
00:58:11,250 --> 00:58:14,880
>> Ez lenne igazán félelmetes, ha mindannyian
mehet, és megy végre egy próbát,

1054
00:58:14,880 --> 00:58:19,720
de megértjük, hogy nem feltétlenül
a legésszerűbb dolog most.

1055
00:58:19,720 --> 00:58:23,370
De akkor a PSET, ha azt szeretnénk,
a, és akkor kapsz gyakorlat,

1056
00:58:23,370 --> 00:58:27,200
és akkor talán azt is megtudhatod
igazán megérteni.

1057
00:58:27,200 --> 00:58:27,940
Igen?

1058
00:58:27,940 --> 00:58:30,440
>> KÖZÖNSÉG: OK, tehát melyek azok, amelyek
azt jelentette, hogy használja a PSET?

1059
00:58:30,440 --> 00:58:31,916
Muszáj, hogy az egyik közülük?

1060
00:58:31,916 --> 00:58:32,540
SPEAKER 1: Igen.

1061
00:58:32,540 --> 00:58:34,199
Szóval van a választás.

1062
00:58:34,199 --> 00:58:36,740
Azt hiszem, ebben az esetben tudjuk
beszélni a PSET egy kicsit

1063
00:58:36,740 --> 00:58:40,480
mert én futottam át ezeket.

1064
00:58:40,480 --> 00:58:47,779
Így a PSET, akkor az
választás próbálkozások vagy hash táblák.

1065
00:58:47,779 --> 00:58:49,570
Vannak, akik megpróbálják
és használja virágzás szűrők,

1066
00:58:49,570 --> 00:58:51,840
de ezek technikailag nem helyes.

1067
00:58:51,840 --> 00:58:55,804
Mivel a valószínűségi jellegű,
adnak álpozitív néha.

1068
00:58:55,804 --> 00:58:57,095
Ők hűvös pillantást, bár.

1069
00:58:57,095 --> 00:58:59,030
Erősen javasoljuk, akik
őket legalább.

1070
00:58:59,030 --> 00:59:03,260
De van a választás
között a hash tábla és egy próbát.

1071
00:59:03,260 --> 00:59:06,660
És ez lesz, ha
betölt a szótárban.

1072
00:59:06,660 --> 00:59:09,230
>> És akkor el kell választani
A hash függvény,

1073
00:59:09,230 --> 00:59:13,420
akkor el kell választani, hogy hány
kanalak van, és ez változhat.

1074
00:59:13,420 --> 00:59:17,440
Mint ha több kanalak,
talán ez lesz gyorsabban fusson.

1075
00:59:17,440 --> 00:59:22,790
De talán te pazarlás
sok helyet, hogy így, bár.

1076
00:59:22,790 --> 00:59:26,320
Meg kell kitalálni.

1077
00:59:26,320 --> 00:59:27,140
Mmhmm?

1078
00:59:27,140 --> 00:59:29,875
>> KÖZÖNSÉG: Azt mondtam, hogy
tudjuk használni más hash függvények,

1079
00:59:29,875 --> 00:59:31,750
hogy nem kell
hozzon létre egy hash függvény?

1080
00:59:31,750 --> 00:59:32,666
>> SPEAKER 1: Igen, van.

1081
00:59:32,666 --> 00:59:38,150
Tehát a szó szoros értelmében a hash függvény,
mint a Google "hash függvény"

1082
00:59:38,150 --> 00:59:40,770
és keresni valami jó is.

1083
00:59:40,770 --> 00:59:43,250
Nem várható, hogy épít
saját hash függvények.

1084
00:59:43,250 --> 00:59:46,100
Az emberek töltik
tézisek ezeket a dolgokat.

1085
00:59:46,100 --> 00:59:50,250
>> Szóval ne aggódj épület saját.

1086
00:59:50,250 --> 00:59:53,350
Keresse meg az egyik online kezdeni.

1087
00:59:53,350 --> 00:59:56,120
Néhányan közülük van, hogy
manipulálni egy kicsit

1088
00:59:56,120 --> 00:59:59,430
hogy megbizonyosodjon arról, visszatérő típusok egyeznek meg
és miegymás, így az elején,

1089
00:59:59,430 --> 01:00:02,420
Azt javasoljuk valamit
nagyon egyszerű, hogy talán csak

1090
01:00:02,420 --> 01:00:04,680
hash az első betű.

1091
01:00:04,680 --> 01:00:08,760
És akkor, ha már a munka-,
beépített hűtő hash függvény.

1092
01:00:08,760 --> 01:00:09,260
Mmhmm?

1093
01:00:09,260 --> 01:00:13,020
>> KÖZÖNSÉG: Lenne egy próbát lehet, vagy
hatékony, de csak nehezebb, like--

1094
01:00:13,020 --> 01:00:15,880
>> SPEAKER 1: Tehát egy próbát, azt hiszem,
intuitíve nehezen megvalósítható

1095
01:00:15,880 --> 01:00:18,310
de nagyon gyors.

1096
01:00:18,310 --> 01:00:20,620
Ugyanakkor több helyet.

1097
01:00:20,620 --> 01:00:25,270
Ismét optimalizálhatja mindkét lévők
különböző módon, és olyan módon to--

1098
01:00:25,270 --> 01:00:26,770
KÖZÖNSÉG: Hogy vagyunk osztályozzák ezt?

1099
01:00:26,770 --> 01:00:27,540
Vajon matter--

1100
01:00:27,540 --> 01:00:29,164
>> SPEAKER 1: Szóval osztályozni szokásos módon.

1101
01:00:29,164 --> 01:00:31,330
Fogsz osztályozni a design.

1102
01:00:31,330 --> 01:00:36,020
Bárhogyan is csinál, azt szeretnénk, hogy
győződjön meg róla, hogy olyan elegáns, mint lehet

1103
01:00:36,020 --> 01:00:38,610
és olyan hatékony, mint lehet.

1104
01:00:38,610 --> 01:00:41,950
De ha úgy dönt, egy próbát vagy hash
táblázat, amíg működik,

1105
01:00:41,950 --> 01:00:45,350
vagyunk boldogok vele.

1106
01:00:45,350 --> 01:00:48,370
És ha használni valamit, hash
az első betű, ez rendben van,

1107
01:00:48,370 --> 01:00:51,410
mint talán hasonló design-bölcs.

1108
01:00:51,410 --> 01:00:53,410
Mi is elérte a
pont ebben semester--

1109
01:00:53,410 --> 01:00:55,340
Nem tudom, ha
srácok noticed-- ha

1110
01:00:55,340 --> 01:00:58,780
PSET évfolyamon csökken egy kicsit
mert a tervezés és miegymás,

1111
01:00:58,780 --> 01:00:59,900
ez tökéletesen megfelel.

1112
01:00:59,900 --> 01:01:02,960
Ez kezd arra a pontra, ahol a
programok egyre bonyolultabb.

1113
01:01:02,960 --> 01:01:04,830
Van több helyen
akkor javítani.

1114
01:01:04,830 --> 01:01:06,370
>> Tehát ez teljesen normális.

1115
01:01:06,370 --> 01:01:08,810
Ez nem, hogy te
rosszabbul a PSET.

1116
01:01:08,810 --> 01:01:11,885
Ez csak mi vagyunk, hogy nehezebb most.

1117
01:01:11,885 --> 01:01:13,732
Szóval mindenki érzi azt.

1118
01:01:13,732 --> 01:01:14,940
Csak osztályozott összes psets.

1119
01:01:14,940 --> 01:01:16,490
Tudom, hogy mindenki érzi azt.

1120
01:01:16,490 --> 01:01:19,600
>> Tehát ne legyen aggódik, hogy.

1121
01:01:19,600 --> 01:01:23,580
És ha bármilyen kérdése van
korábbi psets vagy módon lehet javítani,

1122
01:01:23,580 --> 01:01:27,760
Megpróbálom, és írja meg véleményét a konkrét
helyen, de néha késő

1123
01:01:27,760 --> 01:01:30,840
és kapok fáradt.

1124
01:01:30,840 --> 01:01:34,885
Vannak más dolgok
körülbelül adatszerkezetek?

1125
01:01:34,885 --> 01:01:37,510
Biztos vagyok benne, a srácok nem igazán
akar beszélni őket többé,

1126
01:01:37,510 --> 01:01:42,650
de ha van, boldog vagyok, hogy
megy át őket, valamint bármi

1127
01:01:42,650 --> 01:01:45,580
ettől előadás a múlt
hét vagy a múlt héten.

1128
01:01:45,580 --> 01:01:51,580
>> Tudom, hogy a múlt héten volt az egész felülvizsgálat, így
akkor lehet, hogy kimarad néhány felülvizsgálat

1129
01:01:51,580 --> 01:01:54,190
tól előadás.

1130
01:01:54,190 --> 01:01:58,230
Minden egyéb kérdésre tudok válaszolni?

1131
01:01:58,230 --> 01:01:59,350
OK, rendben.

1132
01:01:59,350 --> 01:02:02,400
Hát, srácok, hogy ki 15 perccel korábban.

1133
01:02:02,400 --> 01:02:08,370
>> Remélem, ez volt a félig segítőkész legalábbis,
és én találkozunk a jövő héten,

1134
01:02:08,370 --> 01:02:12,150
vagy csütörtök munkaidőben.

1135
01:02:12,150 --> 01:02:15,285
Vannak kéri snackek
A jövő héten, ez a dolog?

1136
01:02:15,285 --> 01:02:17,459
Mert elfelejtettem édességet ma.

1137
01:02:17,459 --> 01:02:19,750
És én hozott édességet utolsó
hét, de nem volt Columbus Day,

1138
01:02:19,750 --> 01:02:25,400
így volt, mint a hat ember, aki
négy zsák cukorkát magukat.

1139
01:02:25,400 --> 01:02:28,820
Tudom hozni starbursts
újra, ha úgy tetszik.

1140
01:02:28,820 --> 01:02:29,580
Starbursts?

1141
01:02:29,580 --> 01:02:32,250
OK, jól hangzik.

1142
01:02:32,250 --> 01:02:35,050
Volna egy nagy nap, srácok.

1143
01:02:35,050 --> 01:02:39,510