1
00:00:00,000 --> 00:00:03,423
>> [Predvaja glasba]

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

3
00:00:05,380 --> 00:00:08,210
>> ANDI PENG: Dobrodošli v 6. tednu oddelka.

4
00:00:08,210 --> 00:00:11,620
Oddaljil smo iz našega standarda
Čas sekcija torek

5
00:00:11,620 --> 00:00:14,130
popoldne na to lepo nedeljo zjutraj.

6
00:00:14,130 --> 00:00:17,330
Hvala za vse, ki
se mi je pridružila danes, ampak resno,

7
00:00:17,330 --> 00:00:18,170
krog aplavz.

8
00:00:18,170 --> 00:00:20,600
>> To je kar velik napor.

9
00:00:20,600 --> 00:00:23,600
Sem skoraj niti ni uspelo
v času, vendar je bilo v redu.

10
00:00:23,600 --> 00:00:27,520
Zato vem, da vas vse
so jo samo na kvizu.

11
00:00:27,520 --> 00:00:30,370
First of all, dobrodošli v
druga plat tega.

12
00:00:30,370 --> 00:00:32,917
>> Drugič, bomo govorili o tem.

13
00:00:32,917 --> 00:00:34,000
O tem bomo govorili v kvizu.

14
00:00:34,000 --> 00:00:35,700
Bomo govorili o tem, kako
delaš v razredu.

15
00:00:35,700 --> 00:00:36,550
Boste v redu.

16
00:00:36,550 --> 00:00:39,080
Imam svoje kvize za
si na koncu tod

17
00:00:39,080 --> 00:00:42,120
tako da, če hočete, da bi
poglej na njej, popolnoma v redu.

18
00:00:42,120 --> 00:00:46,590
>> Tako hitro, preden začnemo se
agenda za danes je, kot sledi.

19
00:00:46,590 --> 00:00:48,430
Kot lahko vidite, smo
v bistvu hitro streljanje

20
00:00:48,430 --> 00:00:52,120
skozi cel kup podatkovnih struktur
res, res, res hitro.

21
00:00:52,120 --> 00:00:54,380
Tako kot tak ne bo
super interactive danes.

22
00:00:54,380 --> 00:00:59,620
To bo samo se mi nekako kričali
stvari, ki jih, in če sem vas zmedlo,

23
00:00:59,620 --> 00:01:02,680
če grem prehitro, povej mi.

24
00:01:02,680 --> 00:01:05,200
Oni so samo različne podatke
strukture, in kot del

25
00:01:05,200 --> 00:01:07,070
vašega pset za to
prihajajoči teden, boste

26
00:01:07,070 --> 00:01:10,340
morali izvajati enega od njih,
morda dve them-- dva od njih

27
00:01:10,340 --> 00:01:12,319
V vašem pset.

28
00:01:12,319 --> 00:01:14,610
OK, tako da sem le, da bo
začeti z nekaj objav.

29
00:01:14,610 --> 00:01:19,070
Mi bomo šli čez nizov in čakalnih vrst več v
globina od tistega, kar smo storili pred kviz.

30
00:01:19,070 --> 00:01:20,990
Mi bomo šli čez povezana
Seznam enkrat, še enkrat,

31
00:01:20,990 --> 00:01:23,899
bolj poglobljeno kot kaj
smo imeli pred kviz.

32
00:01:23,899 --> 00:01:26,440
In potem bomo govorili o hash
mize, drevesa in poskuša, ki

33
00:01:26,440 --> 00:01:28,890
so vsi zelo potrebno za vašo pset.

34
00:01:28,890 --> 00:01:32,925
In potem bomo šli čez nekaj
koristnih nasvetov za pset5.

35
00:01:32,925 --> 00:01:37,360
>> OK, tako kviz 0.

36
00:01:37,360 --> 00:01:41,090
Povprečna bil 58%.

37
00:01:41,090 --> 00:01:45,370
To je bila zelo nizka, in tako vidva vse
naredila zelo, zelo dobro, v skladu

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

39
00:01:46,510 --> 00:01:49,970
>> Precej, pravilo palca je, če ste
v standardni odmik od srednje vrednosti

40
00:01:49,970 --> 00:01:52,990
še posebej, ker smo v manj
udoben oddelek, ste popolnoma v redu.

41
00:01:52,990 --> 00:01:54,120
Si na pravi poti.

42
00:01:54,120 --> 00:01:55,190
Življenje je dobro.

43
00:01:55,190 --> 00:01:58,952
>> Vem, da je strašljivo, da misliš, da
Imam kot 40% na tem kvizu.

44
00:01:58,952 --> 00:02:00,160
Grem na neuspeh ta razred.

45
00:02:00,160 --> 00:02:02,243
Obljubljam vam, da niste
dogaja, da ne razred.

46
00:02:02,243 --> 00:02:03,680
Vi ste popolnoma v redu.

47
00:02:03,680 --> 00:02:06,850
>> Za tiste med vami, ki je dobil več kot
srednja, impresivna, impresivno,

48
00:02:06,850 --> 00:02:08,780
kot resno dobro opravljeno.

49
00:02:08,780 --> 00:02:09,689
Sem jih imel z mano.

50
00:02:09,689 --> 00:02:11,730
Vas prosimo, da pridejo jih dobite
Na koncu dela.

51
00:02:11,730 --> 00:02:14,520
Dovolite mi, da vem, če imate
vprašanja, vprašanja z njimi.

52
00:02:14,520 --> 00:02:17,204
Če bomo dodali svoj rezultat
narobe, nam to sporočite.

53
00:02:17,204 --> 00:02:21,240
>> OK, tako pset5, da je to res
čudno teden Yale v smislu

54
00:02:21,240 --> 00:02:24,240
da je naša pset zaradi
Sreda opoldne vključno

55
00:02:24,240 --> 00:02:27,317
pozno dan, tako da je dejansko
teoretično zaradi torek opoldne.

56
00:02:27,317 --> 00:02:29,150
Verjetno nihče ni končana
v torek opoldne.

57
00:02:29,150 --> 00:02:30,830
To je povsem v redu.

58
00:02:30,830 --> 00:02:33,700
Bomo imeli uradnih ur
Nocoj kot tudi v ponedeljek zvečer.

59
00:02:33,700 --> 00:02:36,810
In vsi oddelki ta teden bo
dejansko spremenila v delavnicah,

60
00:02:36,810 --> 00:02:38,800
zato vas prosimo, da v pop
vsaka sekcija hočeš,

61
00:02:38,800 --> 00:02:42,810
in oni bodo vrste mini-pset
Delavnice za pomoč pri tem.

62
00:02:42,810 --> 00:02:45,620
Tako kot tak, to je samo odsek
kjer smo učno gradivo.

63
00:02:45,620 --> 00:02:49,220
Vsi ostali oddelki bodo poudarkom
izključno na pomoč za pset.

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

65
00:02:50,146 --> 00:02:52,000
>> OBČINSTVO: Kje so uradne ure?

66
00:02:52,000 --> 00:02:56,120
>> ANDI PENG: Govorilne ure
tonight-- oh, dobro vprašanje.

67
00:02:56,120 --> 00:03:00,580
Mislim, da uradne ure nocoj
so v Teal ali na Commons.

68
00:03:00,580 --> 00:03:02,984
Če preverite spletno CS50
in greste na uradnih ur,

69
00:03:02,984 --> 00:03:05,650
ne bi smelo biti časovni razpored, ki
vas, kjer so vse od njih pove.

70
00:03:05,650 --> 00:03:07,954
>> Vem, da nocoj bodisi
ali jutri je teal,

71
00:03:07,954 --> 00:03:10,120
in mislim, da smo lahko
commons za drugo noč.

72
00:03:10,120 --> 00:03:11,020
Nisem prepričan.

73
00:03:11,020 --> 00:03:11,700
Dobro vprašanje.

74
00:03:11,700 --> 00:03:14,430
Preverite na CS50.

75
00:03:14,430 --> 00:03:18,780
>> Cool, vsa vprašanja v zvezi z
urnik za naslednji kot tri dni?

76
00:03:18,780 --> 00:03:21,690
Obljubim vam fantje, kot Davidova
je dejal, da je to vrh hriba.

77
00:03:21,690 --> 00:03:23,050
Vidva sta skoraj tam.

78
00:03:23,050 --> 00:03:24,644
Samo še tri dni.

79
00:03:24,644 --> 00:03:26,310
Tja, in potem bomo vsi prišli dol.

80
00:03:26,310 --> 00:03:28,114
Bomo imeli lepo CS-premor.

81
00:03:28,114 --> 00:03:28,780
Se bomo vrnili.

82
00:03:28,780 --> 00:03:30,779
Bomo potopite v spletu
načrtovanje in razvoj,

83
00:03:30,779 --> 00:03:35,150
Stvari, ki so zelo zabavno primerjavi
za nekatere druge psets.

84
00:03:35,150 --> 00:03:37,974
In to bo chill, in
bomo imeli veliko zabave.

85
00:03:37,974 --> 00:03:38,890
Bomo imeli več sladkarij.

86
00:03:38,890 --> 00:03:39,730
Žal mi je za sladkarije.

87
00:03:39,730 --> 00:03:40,945
Pozabil sem sladkarije.

88
00:03:40,945 --> 00:03:43,310
Grobo jutro je bilo.

89
00:03:43,310 --> 00:03:46,340
Torej, fantje so skoraj tam,
in res sem ponosen na vaju.

90
00:03:46,340 --> 00:03:49,570
>> OK, tako nizov.

91
00:03:49,570 --> 00:03:53,331
Kdo je ljubil vprašanje o Jacku
in njegova oblačila na kvizu?

92
00:03:53,331 --> 00:03:53,830
Nihče?

93
00:03:53,830 --> 00:03:56,500
OK, da je v redu.

94
00:03:56,500 --> 00:04:00,200
>> Torej, v bistvu, kot si lahko
slika Jack, ta tip tukaj,

95
00:04:00,200 --> 00:04:03,350
ljubi vzeti oblačila
od vrha dimnika,

96
00:04:03,350 --> 00:04:05,750
in on ga postavi nazaj na
Sveženj, potem ko je to storjeno.

97
00:04:05,750 --> 00:04:07,600
Torej, na ta način, da nikoli ne
Zdi se, da postaja

98
00:04:07,600 --> 00:04:10,090
na dnu
kup v njegovi oblačila.

99
00:04:10,090 --> 00:04:12,600
Tako da je ta vrsta opisuje
osnovna struktura podatkov

100
00:04:12,600 --> 00:04:16,610
o tem, kako se izvaja kup.

101
00:04:16,610 --> 00:04:20,060
>> V bistvu, pomislite
kup vsaka skladu predmetov

102
00:04:20,060 --> 00:04:24,900
kjer si dal stvari na vrhu, in
potem jih pop ven iz vrha.

103
00:04:24,900 --> 00:04:28,600
Torej LIFO je kratica želimo
da use-- Zadnji noter, prvi ven.

104
00:04:28,600 --> 00:04:32,480
In tako zadnji noter na vrhu
Sveženj je prvi, da pride ven.

105
00:04:32,480 --> 00:04:34,260
In tako oba izraza
smo želeli povezati

106
00:04:34,260 --> 00:04:36,190
s tem se imenujejo potiskanje in pop.

107
00:04:36,190 --> 00:04:39,790
Ko potisnete nekaj na
kup in ga pop nazaj gor.

108
00:04:39,790 --> 00:04:43,422
>> In zato mislim, da je to nekakšna
abstrakten pojem za tiste med vami

109
00:04:43,422 --> 00:04:45,630
ki želijo videti kot
dejansko izvajanje te

110
00:04:45,630 --> 00:04:46,740
v resničnem svetu.

111
00:04:46,740 --> 00:04:50,170
Koliko od vas je napisal esej
morda kot eno uro, preden je bila posledica,

112
00:04:50,170 --> 00:04:54,510
in ste pomotoma izbrisali velik
kos njem, kot po naključju?

113
00:04:54,510 --> 00:04:58,560
In potem, kaj storiti nadzor
bomo uporabili, da ga proda nazaj?

114
00:04:58,560 --> 00:05:00,030
Control-Z, ja?

115
00:05:00,030 --> 00:05:03,640
Control-Z, tako da je količina roki
da je Control-Z mi je rešil življenje,

116
00:05:03,640 --> 00:05:08,820
je rešil rit, vsakič
ki je izvajal prek dimnika.

117
00:05:08,820 --> 00:05:13,020
>> V bistvu vse informacije
da je na vašem Wordov dokument,

118
00:05:13,020 --> 00:05:15,080
da dobi potiska in izstrelil po volji.

119
00:05:15,080 --> 00:05:19,460
In tako v bistvu vsakič, ko vas
izbrisati ničesar, ga pop nazaj gor.

120
00:05:19,460 --> 00:05:22,820
In potem, če jo potrebujete nazaj na vas
ga potisnite, ki je tisto, kar Control-C ne.

121
00:05:22,820 --> 00:05:26,770
In tako v realnem svetu funkcija
kako enostavno strukturo podatkov

122
00:05:26,770 --> 00:05:28,690
lahko pomaga pri vašem vsakdanjem življenju.

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

124
00:05:31,710 --> 00:05:40,150
>> Torej struct je način, da
smo dejansko ustvarili kup.

125
00:05:40,150 --> 00:05:44,720
Tip definiramo struct, in nato
pravimo, da kup na dnu.

126
00:05:44,720 --> 00:05:47,440
In v skladovnice,
imamo dva parametra

127
00:05:47,440 --> 00:05:51,580
da bomo lahko v bistvu manipulirati,
tako da imamo char zvezdic strune zmogljivosti.

128
00:05:51,580 --> 00:05:55,150
>> Vse to počne
ustvarja niz

129
00:05:55,150 --> 00:05:58,835
da bomo lahko shranite kar hočeš
ki jih lahko določi svoje zmogljivosti.

130
00:05:58,835 --> 00:06:01,990
Kapaciteta je samo max znesek
Predmeti, ki jih lahko postavimo v to paleto.

131
00:06:01,990 --> 00:06:05,660
Velikost int je števec, ki ohranja
tir koliko predmetov so trenutno

132
00:06:05,660 --> 00:06:07,850
v plasteh.

133
00:06:07,850 --> 00:06:11,860
Torej, potem bomo lahko spremljate, A,
tako, kako velika je dejansko dimnika je,

134
00:06:11,860 --> 00:06:14,850
in, B, koliko tega skladovnice
smo napolnjena, ker ne želimo,

135
00:06:14,850 --> 00:06:18,800
overflow nad tem, kaj je naša zmogljivost.

136
00:06:18,800 --> 00:06:24,340
>> Tako, na primer, to čudovito
Vprašanje je bilo na kvizu.

137
00:06:24,340 --> 00:06:28,160
V bistvu, kako bomo potisnite
na vrhu kupa.

138
00:06:28,160 --> 00:06:28,830
Zelo preprosta.

139
00:06:28,830 --> 00:06:30,621
Če pogledaš na to,
bomo sprehod skozi to.

140
00:06:30,621 --> 00:06:32,640
Če [neslišno] size--
se spomnite, ko ste

141
00:06:32,640 --> 00:06:35,300
želijo dostop do kateregakoli
parameter v struct,

142
00:06:35,300 --> 00:06:40,320
vam ime struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> V tem primeru je s
ime našega dimnika.

144
00:06:42,720 --> 00:06:46,230
Želimo, da za dostop do velikosti
od tega, da naredimo s.size.

145
00:06:46,230 --> 00:06:50,280
Torej, dokler je velikost ne
enako kapaciteto ali dokler

146
00:06:50,280 --> 00:06:52,940
kot je manjša od prostornine,
bodisi bi delo tukaj.

147
00:06:52,940 --> 00:06:57,180
>> Želite dostopati do notranjosti
žetonov, tako s.strings,

148
00:06:57,180 --> 00:07:00,790
in boš dal, da novo številko
da želite vstaviti v tam.

149
00:07:00,790 --> 00:07:05,030
Recimo samo, da bomo želeli
vstavite int n na stack,

150
00:07:05,030 --> 00:07:08,905
kar lahko storimo s.strings,
nosilci, s.size enaka n.

151
00:07:08,905 --> 00:07:11,030
Ker velikost je kje smo
Trenutno so v plasteh

152
00:07:11,030 --> 00:07:14,590
če bomo za potiskanje
je on, smo pravkar dostop

153
00:07:14,590 --> 00:07:17,370
povsod, kjer je velikost,
Sedanji polnost dimnika,

154
00:07:17,370 --> 00:07:21,729
in smo potisnite int n nanjo.

155
00:07:21,729 --> 00:07:24,770
In potem smo se želeli prepričati, da
smo tudi povečevanje velikosti n,

156
00:07:24,770 --> 00:07:27,436
tako da bomo lahko spremljate smo jih
dodal dodatno stvar dimnika.

157
00:07:27,436 --> 00:07:29,660
Zdaj imamo večjo velikost.

158
00:07:29,660 --> 00:07:33,196
Ali to tukaj smiselno
vsakdo, kako logično deluje?

159
00:07:33,196 --> 00:07:34,160
Bilo je nekako hitro.

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

161
00:07:39,535 --> 00:07:42,160
OBČINSTVO: Lahko greš čez
se s.stringss.strings [s.size] spet?

162
00:07:42,160 --> 00:07:45,808
ANDI PENG: Seveda, pa kaj počne
s.size trenutno nam dali?

163
00:07:45,808 --> 00:07:47,440
OBČINSTVO: To je sedanja velikost.

164
00:07:47,440 --> 00:07:50,890
ANDI PENG: Točno, zato je
tekoči indeks, da je naša velikost na,

165
00:07:50,890 --> 00:07:57,780
in tako smo želeli postaviti nov celo število
da želimo vstaviti v s.size.

166
00:07:57,780 --> 00:07:58,760
Ali to smiselno?

167
00:07:58,760 --> 00:08:01,110
Ker s.strings, vse,
se je ime array.

168
00:08:01,110 --> 00:08:03,510
Vse to se je dostopom do
Niz v naši struct,

169
00:08:03,510 --> 00:08:06,030
in zato, če želimo, da
postavite n v ta indeks,

170
00:08:06,030 --> 00:08:09,651
bomo lahko le dostop do njega
uporabljajo nosilci s.size.

171
00:08:09,651 --> 00:08:10,150
Cool.

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

173
00:08:13,580 --> 00:08:18,916
>> Vredu, pop, sem ga psevdokoda ven
za vas, ampak podoben koncept.

174
00:08:18,916 --> 00:08:19,790
Ali to smiselno?

175
00:08:19,790 --> 00:08:22,310
Če je velikost večja
od nič, potem ste

176
00:08:22,310 --> 00:08:25,350
veš, da si želiš, da bi nekaj
ven, ker če je velikost ne

177
00:08:25,350 --> 00:08:27,620
večja od nič, potem ste
nimajo nič dimnika.

178
00:08:27,620 --> 00:08:29,840
>> Torej si le želite izvesti
Ta koda, ki lahko samo to

179
00:08:29,840 --> 00:08:32,320
pop če obstaja nekaj, da pop.

180
00:08:32,320 --> 00:08:35,830
Torej, če je velikost večja
od 0, smo minus velikost.

181
00:08:35,830 --> 00:08:40,020
Pojemanje smo velikost in se nato vrnite
vse, kar je znotraj njega, ker

182
00:08:40,020 --> 00:08:42,710
jih popping, želimo
Dostop kar je shranjena

183
00:08:42,710 --> 00:08:45,694
v indeksu vrhu kupa.

184
00:08:45,694 --> 00:08:46,610
Vse, kar je smiselno?

185
00:08:46,610 --> 00:08:49,693
Če sem ti fantje napisali tole,
bi vidva lahko to napisali?

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

187
00:08:52,029 --> 00:08:53,570
OK, lahko vidva igral z njim.

188
00:08:53,570 --> 00:08:55,252
Brez skrbi, če ga ne bi dobili.

189
00:08:55,252 --> 00:08:57,460
Nimamo časa, da kodo
ven danes, ker smo jih

190
00:08:57,460 --> 00:08:59,959
dobil veliko teh struktur
da gredo skozi, vendar v bistvu

191
00:08:59,959 --> 00:09:02,214
psevdokoda, zelo, zelo podobno kot potiskanje.

192
00:09:02,214 --> 00:09:03,380
Samo sledite skupaj z logiko.

193
00:09:03,380 --> 00:09:06,092
Prepričajte se, da dostop do vseh
značilnosti vašega struct pravilno.

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

195
00:09:06,574 --> 00:09:09,282
>> OBČINSTVO: Bo ta diapozitivov in
ta stvar lahko še danes-ish?

196
00:09:09,282 --> 00:09:11,586
ANDI PENG: Vedno, ja.

197
00:09:11,586 --> 00:09:13,710
Bom poskusil, da dajo
to gor, kot eno uro kasneje.

198
00:09:13,710 --> 00:09:16,626
Bom email Davida, bo David poskušali
ga dal gor, kot eno uro po tem.

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

200
00:09:20,040 --> 00:09:25,470
>> OK, potem pa gremo v to drugo
Lep podatkovno strukturo, imenovano čakalno vrsto.

201
00:09:25,470 --> 00:09:30,140
Kot lahko vi vidite tukaj, A
Čakalna vrsta za Britancev med nami,

202
00:09:30,140 --> 00:09:32,010
vse, kar je, je črta.

203
00:09:32,010 --> 00:09:34,680
Torej, v nasprotju s tem, kar
misliš, da stack,

204
00:09:34,680 --> 00:09:37,750
čakalna vrsta je natanko tisto,
logično mislite, da je.

205
00:09:37,750 --> 00:09:41,914
To je potekalo po pravilih FIFO,
ki je prvi noter, prvi ven.

206
00:09:41,914 --> 00:09:43,705
Če ste prvi
eden v vrsti, da ste

207
00:09:43,705 --> 00:09:46,230
prvi, ki
prihaja iz vrste.

208
00:09:46,230 --> 00:09:49,680
>> Torej, kaj mi je všeč, da to imenujemo
je dequeueing in enqueueing.

209
00:09:49,680 --> 00:09:52,380
Če želimo dodati nekaj
za našo vrsto, smo enqueue.

210
00:09:52,380 --> 00:09:55,690
Če želimo dequeue, ali pa
nekaj proč, smo dequeue.

211
00:09:55,690 --> 00:10:03,350
>> Torej enak občutek, da smo nekako
ustvarjanje fiksne velikosti elementov, ki smo

212
00:10:03,350 --> 00:10:06,500
lahko shranite nekatere
stvari, vendar smo lahko tudi

213
00:10:06,500 --> 00:10:10,100
spremeniti, kjer smo dajanje
parametri znotraj njih

214
00:10:10,100 --> 00:10:13,140
temelji na kakšnem tipu
funkcionalnost želimo.

215
00:10:13,140 --> 00:10:16,700
Torej nizov, smo želeli zadnji
on, N, da je prva ven.

216
00:10:16,700 --> 00:10:19,800
Čakalna vrsta je želimo, je prva stvar,
v biti prva stvar ven.

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

218
00:10:22,510 --> 00:10:26,710
>> Torej je struct-type
opredeliti, kot lahko vidite,

219
00:10:26,710 --> 00:10:29,470
to je malo drugačna
od tistega, kar je bilo kup

220
00:10:29,470 --> 00:10:33,120
ker ne samo, da moramo hraniti
tir, kjer trenutno je velikost,

221
00:10:33,120 --> 00:10:37,420
želimo tudi, da spremljate glave
kakor tudi, kjer smo trenutno so.

222
00:10:37,420 --> 00:10:39,580
Zato mislim, da je lažje
če sem to pripraviti.

223
00:10:39,580 --> 00:10:53,270
Torej, kaj je zamisliti imamo čakalno vrsto,
tako recimo glava je tukaj.

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

225
00:10:55,811 --> 00:10:58,310
Vodja linije, dajmo
samo povem, da je trenutno tam,

226
00:10:58,310 --> 00:11:01,809
in želimo, da vstavite
nekaj v čakalno vrsto.

227
00:11:01,809 --> 00:11:04,350
Bom poklical velikost bistvu
je ista stvar kot rep,

228
00:11:04,350 --> 00:11:06,314
konec kjerkoli vaša čakalna vrsta je.

229
00:11:06,314 --> 00:11:07,730
Naj samo povem, velikost je tukaj.

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

231
00:11:14,380 --> 00:11:18,400
>> Torej, kako en izvedljiv
vstavite nekaj v čakalno vrsto?

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

233
00:11:21,000 --> 00:11:24,130
Kaj indeks želimo postaviti
kjer želimo vstaviti v.

234
00:11:24,130 --> 00:11:29,320
Če je to začetek vašega
čakalno vrsto in to je konec tega

235
00:11:29,320 --> 00:11:31,860
ali velikost njej, kjer počnemo
želite dodati naslednjo predmeta?

236
00:11:31,860 --> 00:11:32,920
>> OBČINSTVO: [neslišno]

237
00:11:32,920 --> 00:11:35,920
ANDI PENG: Točno, ki jih želite dodati
je odvisno od tega, ki ste ga napisali.

238
00:11:35,920 --> 00:11:37,840
Ali je to polje prazno ali da je prazen.

239
00:11:37,840 --> 00:11:42,630
Torej hočeš, da ga dodate verjetno
tukaj, ker če velikost is--

240
00:11:42,630 --> 00:11:50,540
če so ti vse polno, ki jih želite
da jo dodate tukaj, kajne?

241
00:11:50,540 --> 00:11:57,150
>> In tako, da je, medtem ko je zelo, zelo
preprosto, ne čisto vedno pravilna

242
00:11:57,150 --> 00:12:00,690
ker glavni razliki
med čakalno vrsto in dimnika

243
00:12:00,690 --> 00:12:04,350
je, da je čakalna vrsta
dejansko manipulira

244
00:12:04,350 --> 00:12:06,980
tako da so te spremembe glave
odvisno od tega, kje želite

245
00:12:06,980 --> 00:12:08,650
začetek vašega iztočnico za začetek.

246
00:12:08,650 --> 00:12:11,900
In kot rezultat, svoj rep
se tudi dogaja, da spremenite.

247
00:12:11,900 --> 00:12:14,770
In tako si oglejte
ta koda prav zdaj.

248
00:12:14,770 --> 00:12:18,620
Ker so fantje tudi zahteva, da se
izpišite na kvizu, enqueue.

249
00:12:18,620 --> 00:12:22,580
Mogoče bomo govorili skozi zakaj
odgovor je bil, kaj je bilo.

250
00:12:22,580 --> 00:12:26,790
>> Nisem mogel povsem fit to vrstico na eni,
ampak v bistvu je ta del kode

251
00:12:26,790 --> 00:12:29,030
mora biti v eni vrstici.

252
00:12:29,030 --> 00:12:30,140
Preživite kot 30 sekund.

253
00:12:30,140 --> 00:12:33,000
Oglejte si, in zakaj
to je način, da je.

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

255
00:12:50,030 --> 00:12:55,420
>> Zelo, zelo podobna struct, zelo zelo
podobno strukturo kot prejšnja

256
00:12:55,420 --> 00:12:58,090
kup razen morda
ena vrstica kode.

257
00:12:58,090 --> 00:13:01,190
In da eno vrstico kode
določa funkcionalnosti.

258
00:13:01,190 --> 00:13:03,900
In res razlikuje
čakalne vrste iz dimnika.

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

260
00:13:18,510 --> 00:13:22,010
>> Kdo želel vzeti stab
pri pojasnjevanju, zakaj ste

261
00:13:22,010 --> 00:13:24,980
dobil to zapleteno stvar tukaj?

262
00:13:24,980 --> 00:13:27,845
Vidimo vrnitev naših
čudovit prijatelj modul.

263
00:13:27,845 --> 00:13:31,020
Ker bo vidva kmalu
prepoznati v programiranju,

264
00:13:31,020 --> 00:13:34,910
skoraj kadarkoli boste potrebovali nekaj
da ovijte okoli nič,

265
00:13:34,910 --> 00:13:36,850
modul se bo pot, da to storite.

266
00:13:36,850 --> 00:13:40,510
Torej, vedoč, da se kdo hotel
da bi poskušali razložiti to vrstico kode?

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

268
00:13:44,060 --> 00:13:47,507
Ja, vsi odgovori so
sprejeta in dobrodošla.

269
00:13:47,507 --> 00:13:48,840
OBČINSTVO: Ali ste v pogovoru z mano?

270
00:13:48,840 --> 00:13:49,506
ANDI PENG: Ja.

271
00:13:49,506 --> 00:13:56,200
OBČINSTVO: Oh, ne opravičujem.

272
00:13:56,200 --> 00:14:00,250
ANDI PENG: OK, tako da je
sprehod skozi to oznako.

273
00:14:00,250 --> 00:14:03,642
Torej, ko ste poskušali
kaj dodati na čakalno vrsto,

274
00:14:03,642 --> 00:14:08,510
v lepem primeru, da glava zgodi
da je prav tukaj, je zelo enostaven za nas

275
00:14:08,510 --> 00:14:10,960
samo iti do konca
vstavite nekaj, kajne?

276
00:14:10,960 --> 00:14:14,690
Toda bistvo čakalno vrsto je
da vodja lahko dejansko dinamično

277
00:14:14,690 --> 00:14:17,280
spreminjajo glede na to, kje smo
želijo začetek našega q biti,

278
00:14:17,280 --> 00:14:19,880
in kot tak, repa
se tudi dogaja, da spremenite.

279
00:14:19,880 --> 00:14:31,100
>> In tako si predstavljam, da to ni bil
čakalne vrste, temveč je bila ta čakalna vrsta.

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

281
00:14:37,900 --> 00:14:39,330
Recimo, glava je tukaj.

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

283
00:14:54,900 --> 00:14:56,980
Recimo, da je naša čakalne videti takole.

284
00:14:56,980 --> 00:15:00,190
Če bi želeli preusmeriti, kjer
začetek liniji,

285
00:15:00,190 --> 00:15:03,400
recimo, da smo premaknilo glavo
Na ta način in velikosti tukaj.

286
00:15:03,400 --> 00:15:07,100
>> Sedaj želimo dodati nekaj
to čakalne vrste, ampak kot lahko vi vidite,

287
00:15:07,100 --> 00:15:11,150
to ni tako enostavno, kot da samo
dodamo kar je po velikosti

288
00:15:11,150 --> 00:15:13,630
ker potem mi zmanjka
Meje našega dejanskega paleto.

289
00:15:13,630 --> 00:15:16,190
Kjer želimo res dodati je tukaj.

290
00:15:16,190 --> 00:15:18,610
To je lepota čakalno vrsto
je, da je za nas, vizualno pa

291
00:15:18,610 --> 00:15:22,380
Izgleda, da je linija gre takole,
toda, če je shranjena v podatkovno strukturo,

292
00:15:22,380 --> 00:15:29,370
jim ga dal kot kot cikel.

293
00:15:29,370 --> 00:15:32,360
To nekako ovije
spredaj na enak način,

294
00:15:32,360 --> 00:15:34,780
da lahko črta tudi zaviti
okoli odvisno od kjerkoli vas

295
00:15:34,780 --> 00:15:36,279
želijo začetku vrstice biti.

296
00:15:36,279 --> 00:15:38,630
In tako, če vzamemo
poglej tukaj, dajmo

297
00:15:38,630 --> 00:15:40,880
rekli, da smo želeli ustvariti
Funkcija se imenuje enqueue.

298
00:15:40,880 --> 00:15:43,980
Želeli smo dodati int n v tem q.

299
00:15:43,980 --> 00:15:49,250
Če q.size -Q- bomo pokličem, da naše podatke
structure-- če naša queue.size ne

300
00:15:49,250 --> 00:15:52,520
enako kapaciteto ali če
to je manj kot zmogljivosti,

301
00:15:52,520 --> 00:15:55,120
q.strings je matrika v naši q.

302
00:15:55,120 --> 00:15:58,380
Gremo nastaviti
ki je enaka q.heads,

303
00:15:58,380 --> 00:16:02,730
ki je tukaj, plus q.size
modul s kapaciteto, ki je

304
00:16:02,730 --> 00:16:04,290
zaviti nas spet tukaj.

305
00:16:04,290 --> 00:16:08,040
>> Torej, v tem primeru, indeksa
glave je 1, kajne?

306
00:16:08,040 --> 00:16:11,480
Indeks velikosti 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Torej ne moremo storiti 1 plus 4 modul
jih naše zmogljivosti, ki je 5.

308
00:16:19,500 --> 00:16:20,920
Kaj nam daje?

309
00:16:20,920 --> 00:16:23,270
Kaj je indeks, ki
prihaja iz tega?

310
00:16:23,270 --> 00:16:24,080
>> OBČINSTVO: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI PENG: 0, kar
zgodi, da se prav tu,

312
00:16:27,870 --> 00:16:30,640
in zato želimo, da bi lahko
da vstavite tukaj.

313
00:16:30,640 --> 00:16:34,730
In zato je ta enačba tukaj vrsta
za preprosto deluje z vsemi številkami

314
00:16:34,730 --> 00:16:36,750
odvisno od tega, kje si
glava in vaše velikosti so.

315
00:16:36,750 --> 00:16:38,541
Če veste, kaj tisti,
so stvari, veste

316
00:16:38,541 --> 00:16:43,170
točno tam, kjer želite vstaviti
kar je po vašem čakalno vrsto.

317
00:16:43,170 --> 00:16:44,640
Ali, da je smiselno, da vse?

318
00:16:44,640 --> 00:16:48,560
>> Vem vrste možganov
teaser še posebej, ker je to

319
00:16:48,560 --> 00:16:50,512
prišel v odpravljanju posledic svojega kviza.

320
00:16:50,512 --> 00:16:52,220
Ampak upajmo, da vsakdo
Zdaj lahko razumemo,

321
00:16:52,220 --> 00:16:57,800
zakaj ta rešitev ali je to
funkcija je, da ga je.

322
00:16:57,800 --> 00:16:59,840
Vsakdo nekoliko nejasno o tem?

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

324
00:17:03,471 --> 00:17:03,970
V REDU.

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

326
00:17:07,109 --> 00:17:09,970
>> In zdaj, če vas
želel dequeue, to

327
00:17:09,970 --> 00:17:15,240
je, če bi bila naša glava premika
ker če bi dequeue,

328
00:17:15,240 --> 00:17:17,030
nimamo vzlet konec q.

329
00:17:17,030 --> 00:17:19,130
Želimo, da za vzlet glavo, kajne?

330
00:17:19,130 --> 00:17:24,260
Tako kot rezultat, glava se bo spremenilo,
in da je razlog, zakaj, ko ste enqueue,

331
00:17:24,260 --> 00:17:26,800
moraš slediti
kjer sta vaša glava in tvoja velikost

332
00:17:26,800 --> 00:17:29,450
morajo biti sposobni vstaviti
v pravilen položaj.

333
00:17:29,450 --> 00:17:32,740
>> In tako, ko dequeue,
Prav tako sem psevdokoda ven.

334
00:17:32,740 --> 00:17:35,480
Vas prosimo, da, če hočeš
poskus kodiranje to.

335
00:17:35,480 --> 00:17:36,980
Želite premakniti glavo, kajne?

336
00:17:36,980 --> 00:17:39,320
Če sem želel dequeue sem
bi se premaknite nad glavo.

337
00:17:39,320 --> 00:17:40,800
To bi bila glava.

338
00:17:40,800 --> 00:17:45,617
>> In bi naša sedanja velikost
odštejemo, ker ne bomo več

339
00:17:45,617 --> 00:17:46,950
ima štiri elemente v matriki.

340
00:17:46,950 --> 00:17:51,370
Imamo samo tri, nato pa želimo
vrniti, kar je bila shranjena v notranjosti

341
00:17:51,370 --> 00:17:56,260
glave, ker želimo, da bi to
Vrednost ven tako zelo podobna dimnika.

342
00:17:56,260 --> 00:17:58,010
Pravkar ste ob
iz druge destinacije,

343
00:17:58,010 --> 00:18:01,770
in boste morali znova dodelite kazalec
na drugo mesto, kot rezultat.

344
00:18:01,770 --> 00:18:03,890
Logično je, da vsi sledimo?

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

346
00:18:05,690 --> 00:18:10,156
>> OK, tako da bomo govorili malo
bolj poglobljeno o povezanih seznamih

347
00:18:10,156 --> 00:18:13,280
ker se bo zelo, zelo dragocen
za vas v teku ta teden je

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

349
00:18:14,964 --> 00:18:17,130
Povezani seznam, kot vidva
spomnim se, vsi so

350
00:18:17,130 --> 00:18:22,570
so vozlišča, ki so vozlišča nekaterih
Vrednosti obeh vrednost in kazalcem

351
00:18:22,570 --> 00:18:26,290
ki so med seboj povezani
s temi kazalci.

352
00:18:26,290 --> 00:18:29,880
In tako struct o tem, kako
smo ustvarili vozlišče tu smo

353
00:18:29,880 --> 00:18:33,569
imajo int n, ki je glede na
vrednost v trgovini ali niza n

354
00:18:33,569 --> 00:18:35,610
ali karkoli želite
pravijo, char zvezda n.

355
00:18:35,610 --> 00:18:41,482
Struct vozlišče zvezda, ki je kazalec
ki želite imeti v vsakem vozlišču,

356
00:18:41,482 --> 00:18:43,690
boste morali, da
kazalec točka v smeri naprej.

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

358
00:18:48,207 --> 00:18:50,040
Imeli boste glavo
iz povezanega seznama, ki je

359
00:18:50,040 --> 00:18:53,140
dogaja, da opozarjajo na preostalo
vrednosti tako naprej in tako naprej

360
00:18:53,140 --> 00:18:55,290
dokler ne boste sčasoma do konca.

361
00:18:55,290 --> 00:18:58,040
In to zadnje vozlišče je le
bo še kazalec.

362
00:18:58,040 --> 00:18:59,952
To se dogaja, da kažejo na
null, in da je, ko

363
00:18:59,952 --> 00:19:01,910
veste, da ste zadeli
konec vaše povezanega seznama

364
00:19:01,910 --> 00:19:04,076
je, ko tvoj zadnji kazalec
ne kaže na nič.

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

366
00:19:06,670 --> 00:19:10,990
>> Tako smo šli malo bolj v
Globina o tem, kako bi bila ena od možnosti

367
00:19:10,990 --> 00:19:12,400
iskati povezani seznam.

368
00:19:12,400 --> 00:19:15,460
Spomnite se, kaj so nekateri od
slabosti povezanih seznamov

369
00:19:15,460 --> 00:19:19,340
prehladna paleto zvezi iskanj.

370
00:19:19,340 --> 00:19:22,565
Matrika lahko binarno iskanje, vendar
zakaj ne morete storiti, da je v povezanem seznamu?

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

372
00:19:26,834 --> 00:19:30,320
>> OBČINSTVO: Ker oni so vsi povezani,
vendar ne povsem vedeli, kje

373
00:19:30,320 --> 00:19:31,330
[Neslišno].

374
00:19:31,330 --> 00:19:34,600
>> ANDI PENG: Ja, točno tako, ne pozabite
da sijaj array

375
00:19:34,600 --> 00:19:37,190
je dejstvo, da smo imeli
bralno-pisalnega pomnilnika, kjer

376
00:19:37,190 --> 00:19:41,580
če sem hotel vrednost iz indeksa
šest, jaz lahko samo rečem indeks šest,

377
00:19:41,580 --> 00:19:42,407
daj mi te vrednosti.

378
00:19:42,407 --> 00:19:45,240
In to zato, ker so nizi razporejene
v sosednjem prostoru pomnilnika

379
00:19:45,240 --> 00:19:48,020
na enem mestu, medtem ko je
vrsta povezanih seznamov

380
00:19:48,020 --> 00:19:52,820
so naključno posejani po vsem,
in edini način, boste lahko našli enega

381
00:19:52,820 --> 00:19:56,890
je s kazalcem, ki vam pove
naslov, kjer je ta dostavo vozlišče.

382
00:19:56,890 --> 00:20:00,290
>> In tako posledično edini način
iskanje po povezanem seznamu

383
00:20:00,290 --> 00:20:01,560
linearna iskanje.

384
00:20:01,560 --> 00:20:05,890
Ker mi ni točno vedel, kje
12. Vrednost v povezanem seznamu je,

385
00:20:05,890 --> 00:20:08,780
Moram prečkanje celoto
od tega povezanega z enim seznamom

386
00:20:08,780 --> 00:20:12,450
eden od glave do prvega vozla,
Na drugo vozlišče, na tretje vozlišče,

387
00:20:12,450 --> 00:20:17,690
vso pot navzdol, dokler sem končno dobil
da, kjer je to vozlišče iščem.

388
00:20:17,690 --> 00:20:22,110
In tako v tem smislu, iskanje
na povezane seznamu vedno n.

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

390
00:20:23,040 --> 00:20:25,690
To je vedno v linearnem času.

391
00:20:25,690 --> 00:20:28,470
>> In tako je koda, v katerem
izvajamo to, kar

392
00:20:28,470 --> 00:20:32,620
je malo novega za vas, saj ste
Fantje so se res ne govorili ali kdaj

393
00:20:32,620 --> 00:20:35,000
videl kazalci v tem, kako
iskanje po kazalci,

394
00:20:35,000 --> 00:20:37,670
tako da bomo sprehod skozi
To je zelo, zelo počasi.

395
00:20:37,670 --> 00:20:40,200
Torej iskanje bool, desno,
Predstavljajmo si želimo

396
00:20:40,200 --> 00:20:42,820
ustvariti funkcijo imenovano
Iskanje, ki vrne true

397
00:20:42,820 --> 00:20:46,820
Če ste našli vrednost znotraj povezano
seznam, in ga vrne false drugače.

398
00:20:46,820 --> 00:20:50,030
Seznam Node zvezdicami
Trenutno samo kazalec

399
00:20:50,030 --> 00:20:52,960
na prvi element v vašem povezani seznam.

400
00:20:52,960 --> 00:20:56,700
int n je vrednost, ki ste
išče na tem seznamu.

401
00:20:56,700 --> 00:20:58,770
>> Torej vozlišče zvezda kazalec enak seznam.

402
00:20:58,770 --> 00:21:00,970
To pomeni, da smo nastavitev
in ustvarjanje kazalec

403
00:21:00,970 --> 00:21:03,592
v tem prvim vozliščem znotraj seznama.

404
00:21:03,592 --> 00:21:04,300
Vsakdo z mano?

405
00:21:04,300 --> 00:21:06,530
Torej, če smo bili, da gredo
nazaj, bi moral

406
00:21:06,530 --> 00:21:13,850
inicializiran kazalec, ki kaže na
glava, kar je ta seznam.

407
00:21:13,850 --> 00:21:18,600
>> In potem, ko boste dobili tukaj,
medtem ko je kazalec ni enak null,

408
00:21:18,600 --> 00:21:22,160
tako, da je zanka, v kateri smo
bo nato prečkajo

409
00:21:22,160 --> 00:21:25,940
preostali del našega seznama ker tisto,
se zgodi, ko kazalec enaka null?

410
00:21:25,940 --> 00:21:27,550
Vemo, da smo have--

411
00:21:27,550 --> 00:21:28,450
>> OBČINSTVO: [neslišno]

412
00:21:28,450 --> 00:21:31,491
>> ANDI PENG: Točno, zato smo vedeli, da
smo prišli do konca seznama, kajne?

413
00:21:31,491 --> 00:21:34,470
Če greš nazaj, vsako vozlišče
Treba je poudariti, da drugo vozlišče

414
00:21:34,470 --> 00:21:36,550
in tako naprej in tako naprej
dokler si udaril na koncu

415
00:21:36,550 --> 00:21:41,589
rep vašega povezanega seznama,
ki ima kazalec, ki le

416
00:21:41,589 --> 00:21:43,130
ne kaže nikamor, razen št.

417
00:21:43,130 --> 00:21:47,510
In tako ste v bistvu vedeti, da
Vaš seznam je še vedno tam gor

418
00:21:47,510 --> 00:21:50,900
dokler se kazalec ne enaka
null, ker ko je enak null,

419
00:21:50,900 --> 00:21:53,310
saj veš, da ni več stvari.

420
00:21:53,310 --> 00:21:56,930
>> Tako, da je zanka, v kateri smo
dogaja, da imajo dejansko iskanje.

421
00:21:56,930 --> 00:22:01,690
In če pointer-- vidiš
da vrsta arrow funkcijo tam?

422
00:22:01,690 --> 00:22:06,930
Torej, če je kazalec točk, n, če
kazalec na n enako enako n,

423
00:22:06,930 --> 00:22:09,180
To pomeni, da če
kazalec, da ste

424
00:22:09,180 --> 00:22:13,420
iskanje na koncu vsakega
vozlišče dejansko enaka vrednosti

425
00:22:13,420 --> 00:22:15,990
iščete, potem
želite vrniti true.

426
00:22:15,990 --> 00:22:19,280
Torej v bistvu, če ste na vozlišču, ki
je vrednost, ki jo iščete,

427
00:22:19,280 --> 00:22:23,550
veste, da ste bili
uspešno iskanje.

428
00:22:23,550 --> 00:22:27,150
>> V nasprotnem primeru, da želite nastaviti
vaš kazalec na naslednje vozlišče.

429
00:22:27,150 --> 00:22:28,850
To je tisto, ki črta tu počne.

430
00:22:28,850 --> 00:22:31,750
Pointer enak kazalec zraven.

431
00:22:31,750 --> 00:22:33,360
Vsi videli, kako je to delovalo?

432
00:22:33,360 --> 00:22:36,580
>> In v bistvu boš samo
prečkanje celotne seznamu

433
00:22:36,580 --> 00:22:41,920
ponastavitev kazalec vsakič, dokler
sčasoma dvignil konec seznama.

434
00:22:41,920 --> 00:22:45,030
In veš, da ne obstajajo
več vozlišč za iskanje skozi,

435
00:22:45,030 --> 00:22:47,999
in potem se lahko vrnete false
saj veš, da, oh, no,

436
00:22:47,999 --> 00:22:50,540
če sem bil sposoben za iskanje
preko celotne seznama.

437
00:22:50,540 --> 00:22:54,530
Če se v tem primeru, če bi hotel
iskati vrednosti 10,

438
00:22:54,530 --> 00:22:57,250
in začnem na čelu, in
Iščem vso pot navzdol,

439
00:22:57,250 --> 00:23:00,550
in sem na koncu prišel do tega, kar
kazalec, ki kaže na ničlo,

440
00:23:00,550 --> 00:23:04,415
Vem, da je sranje, mislim, da 10 ni
ta seznam, ker nisem mogel najti.

441
00:23:04,415 --> 00:23:06,520
In jaz sem na koncu seznama.

442
00:23:06,520 --> 00:23:11,040
In v tem primeru veš
Bom vrnil false.

443
00:23:11,040 --> 00:23:12,900
>> Dovolite, da namakate v za malo.

444
00:23:12,900 --> 00:23:17,350
To bo lepa
pomembna za vašo pset.

445
00:23:17,350 --> 00:23:21,140
Logika je zelo preprosta, morda
skladenjsko le njeno izvajanje.

446
00:23:21,140 --> 00:23:23,365
Vidva želite
prepričani, da razumete.

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

448
00:23:25,870 --> 00:23:27,650
Cool.

449
00:23:27,650 --> 00:23:32,560
>> OK, tako, kako bi bili
vstavljanje vozlišč, desno,

450
00:23:32,560 --> 00:23:35,380
v seznam, saj se spomnite
kaj so, kaj koristi

451
00:23:35,380 --> 00:23:39,230
da imajo povezani seznam versus
niz v smislu skladiščenja?

452
00:23:39,230 --> 00:23:41,110
>> OBČINSTVO: To je dinamičen,
tako da je lažje to--

453
00:23:41,110 --> 00:23:43,180
>> ANDI PENG: Točno,
tako da je dinamičen, kar

454
00:23:43,180 --> 00:23:46,880
pomeni, da se lahko razširi in skrči
glede na potrebe uporabnika.

455
00:23:46,880 --> 00:23:56,570
In tako, v tem smislu, da ne potrebujemo
zapravljati nepotrebnih spomin, ker sem

456
00:23:56,570 --> 00:24:00,850
če ne vem, koliko vrednosti želim
za trgovino, pa nima smisla za mene

457
00:24:00,850 --> 00:24:04,310
ustvariti array, ker je
če želim shraniti 10 vrednosti

458
00:24:04,310 --> 00:24:08,380
in sem ustvaril niz 1.000, to je
veliko zapravlja spomina, dodeljen.

459
00:24:08,380 --> 00:24:11,180
Zato želimo, da uporabite povezan
seznam, da bi lahko dinamično

460
00:24:11,180 --> 00:24:13,860
spremeniti ali skrči svojo velikost.

461
00:24:13,860 --> 00:24:17,040
>> In tako, da omogoča vstavljanje
malo bolj zapletena.

462
00:24:17,040 --> 00:24:20,810
Ker ne moremo naključno dostop elemente
način, da bi iz nabora.

463
00:24:20,810 --> 00:24:24,270
Če želim vstaviti element
v sedmi indeksa,

464
00:24:24,270 --> 00:24:26,930
Jaz lahko samo vstavite
v sedmi indeks.

465
00:24:26,930 --> 00:24:30,020
Na povezanega seznama, le-ta ne
čisto delo tako enostavno,

466
00:24:30,020 --> 00:24:34,947
in tako, če smo želeli, da vstavite
ena tukaj v povezanem seznamu

467
00:24:34,947 --> 00:24:36,280
vizualno, to je zelo težko videti.

468
00:24:36,280 --> 00:24:39,363
Pravkar smo želeli, da ga vstavite tam,
takoj na začetku seznama,

469
00:24:39,363 --> 00:24:40,840
takoj po glavi.

470
00:24:40,840 --> 00:24:44,579
>> Ampak način, na katerega moramo prerazporediti
so kazalci je nekoliko zapletena

471
00:24:44,579 --> 00:24:47,620
ali, logično, je smiselno, ampak
želite poskrbite, da ga imate

472
00:24:47,620 --> 00:24:50,250
povsem dol, ker
zadnja stvar, ki jo želite

473
00:24:50,250 --> 00:24:52,990
se prerazporedijo kazalec
način, da delamo tukaj.

474
00:24:52,990 --> 00:24:58,170
Če vas dereference
kazalec od glave do 1,

475
00:24:58,170 --> 00:25:01,086
nato pa vse nenadoma
preostanek svojega povezanega seznama

476
00:25:01,086 --> 00:25:04,680
se izgubi, ker moraš dejansko ne
ustvaril začasno ničesar.

477
00:25:04,680 --> 00:25:06,220
Ki je opozoril na 2.

478
00:25:06,220 --> 00:25:10,080
Če znova kazalec, nato
Preostanek vašem seznamu je popolnoma izgubljen.

479
00:25:10,080 --> 00:25:13,310
Torej hočeš biti
zelo, zelo previdni tukaj

480
00:25:13,310 --> 00:25:17,010
najprej dodelite
pointer iz Karkoli

481
00:25:17,010 --> 00:25:20,150
želite vstaviti v kjerkoli
hočeš, nato pa vas

482
00:25:20,150 --> 00:25:22,710
lahko dereference preostanek svojega seznama.

483
00:25:22,710 --> 00:25:25,250
>> Torej to velja za kamorkoli
skušate vstavite.

484
00:25:25,250 --> 00:25:27,520
Če želite vstaviti Na
glava, če želite, da tu odgovoriti,

485
00:25:27,520 --> 00:25:29,455
Če želite vstaviti v
konec, no, na koncu sem

486
00:25:29,455 --> 00:25:30,910
Verjetno bi le
nimajo kazalec, vendar boste

487
00:25:30,910 --> 00:25:33,830
želite poskrbite, da ne boste
izgubijo preostanek svojega seznama.

488
00:25:33,830 --> 00:25:36,640
Vedno si želite zagotoviti
vaš novi vozlišče je obrnjena

489
00:25:36,640 --> 00:25:39,330
proti karkoli
želite vstaviti v,

490
00:25:39,330 --> 00:25:42,170
in potem si lahko dodate veriženje naprej.

491
00:25:42,170 --> 00:25:43,330
Vsakdo jasno?

492
00:25:43,330 --> 00:25:45,427
>> To se bo
eden izmed pravih vprašanj.

493
00:25:45,427 --> 00:25:48,010
Eden od najbolj pomembnih vprašanj
boste imeli na vašem pset

494
00:25:48,010 --> 00:25:51,340
je, da greš, da bi poskušali ustvariti
med sabo povezan seznam in vstavite stvari

495
00:25:51,340 --> 00:25:53,340
potem pa samo izgubili
preostanek svojega povezanega seznama.

496
00:25:53,340 --> 00:25:54,900
In ti bo všeč, sem
Ne vem, zakaj se to dogaja?

497
00:25:54,900 --> 00:25:58,040
In to je bolečina, da gredo skozi
in iskanje vseh vaših nasvetov.

498
00:25:58,040 --> 00:26:02,100
>> In zagotavljam vam na tem pset,
pisanje in risanje teh vozlišč ven

499
00:26:02,100 --> 00:26:03,344
bo zelo, zelo koristno.

500
00:26:03,344 --> 00:26:06,010
Tako boste lahko popolnoma spremljate
kje so vsi vaši kazalci,

501
00:26:06,010 --> 00:26:08,540
kaj je šlo narobe,
kjer so vsi vaši vozlišča,

502
00:26:08,540 --> 00:26:12,660
kaj morate storiti, da bi dostopali ali
vstavite ali izbrišete ali kateri koli od njih.

503
00:26:12,660 --> 00:26:14,550
Vsakdo dobro s tem?

504
00:26:14,550 --> 00:26:15,050
Cool.

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

506
00:26:19,300 --> 00:26:22,600
>> Torej, če smo želeli, da pogled na kodo?

507
00:26:22,600 --> 00:26:24,470
Oh, ne vem, če smo
lahko vidite the-- OK, tako

508
00:26:24,470 --> 00:26:27,940
Na vrhu vsega je funkcija
imenovan vložek, kjer želimo

509
00:26:27,940 --> 00:26:31,365
vstaviti int n v povezano seznamu.

510
00:26:31,365 --> 00:26:32,740
Gremo na sprehod skozi to.

511
00:26:32,740 --> 00:26:34,770
To je veliko kode, veliko novega sintakse.

512
00:26:34,770 --> 00:26:36,220
Mi bo v redu.

513
00:26:36,220 --> 00:26:39,120
>> Torej na vrhu, kadar
želimo ustvariti ničesar

514
00:26:39,120 --> 00:26:42,380
Kaj moramo storiti, še posebej, če vas
želim, da bi se ne shranjujejo na kupu

515
00:26:42,380 --> 00:26:43,920
vendar v kup?

516
00:26:43,920 --> 00:26:45,460
Gremo na knjižnične funkcije malloc, kajne?

517
00:26:45,460 --> 00:26:48,240
Tako bomo ustvarili kazalec.

518
00:26:48,240 --> 00:26:52,074
Vozlišče, kazalec, novi Ene
malloc velikosti vozlišču

519
00:26:52,074 --> 00:26:53,740
ker želimo, da je vozlišče, ki bo ustvaril.

520
00:26:53,740 --> 00:26:56,720
Želimo količino
spomin, da je vozlišče zavzame

521
00:26:56,720 --> 00:26:59,300
bodo dodeljene za
Ustanovitev novega vozlišča.

522
00:26:59,300 --> 00:27:02,270
>> In potem bomo preverite
vidim, če novi Ene enaka null.

523
00:27:02,270 --> 00:27:03,370
Spomni se, kaj smo rekli?

524
00:27:03,370 --> 00:27:06,470
Karkoli vam malloc,
Kaj morate vedno narediti?

525
00:27:06,470 --> 00:27:09,490
Morate vedno preverite,
ali je, da nič.

526
00:27:09,490 --> 00:27:13,620
>> Na primer, če je vaš operacijski
Sistem je bil povsem poln,

527
00:27:13,620 --> 00:27:17,060
če bi imeli nič več pomnilnika na
vse in poskusite knjižnične funkcije malloc,

528
00:27:17,060 --> 00:27:18,410
da bi se vrnil null zate.

529
00:27:18,410 --> 00:27:21,094
In tako, če boste poskušali uporabiti
ko je bila obrnjena na ničlo,

530
00:27:21,094 --> 00:27:23,260
ti ne boš mogel
za dostop do teh informacij.

531
00:27:23,260 --> 00:27:27,010
In tako, kot smo želeli, da bi
prepričani, da ko ste mallocing,

532
00:27:27,010 --> 00:27:30,500
ste vedno preverjanje, da vidim, če
da spomin dal je nična.

533
00:27:30,500 --> 00:27:33,670
In če je ni, potem lahko gremo
o s preostalim naše kode.

534
00:27:33,670 --> 00:27:36,140
>> Torej bomo
inicializacijo novo vozlišče.

535
00:27:36,140 --> 00:27:39,050
Bomo storili nov n enak n.

536
00:27:39,050 --> 00:27:42,390
In potem bomo storili
nastaviti nov kazalec na novo

537
00:27:42,390 --> 00:27:46,900
na nič, ker zdaj ne bomo
želim ničesar za to, da kaže.

538
00:27:46,900 --> 00:27:48,755
Nimamo pojma, kje
to se dogaja, da si dal,

539
00:27:48,755 --> 00:27:50,630
in potem, če želimo
ga vstavite na čelu,

540
00:27:50,630 --> 00:27:53,820
potem bomo lahko znova dodelite
kazalec z glavo.

541
00:27:53,820 --> 00:27:58,530
Ali vsi sledimo logiki
kje, da se dogaja?

542
00:27:58,530 --> 00:28:02,502
>> Vsi delamo ustvarja nova
vozlišče, ki določa kazalec na ničlo,

543
00:28:02,502 --> 00:28:04,210
in nato prerazporeditev
je v glavo, če bomo

544
00:28:04,210 --> 00:28:06,320
vem, želimo, da ga vstavite v glavo.

545
00:28:06,320 --> 00:28:09,420
In potem glava se bo
kažejo na to novo vozlišče.

546
00:28:09,420 --> 00:28:11,060
Vsakdo v redu s tem?

547
00:28:11,060 --> 00:28:12,380
>> Torej, to je dvostopenjski postopek.

548
00:28:12,380 --> 00:28:14,760
Imaš do prvega Dodeli
kar ste ustvarili.

549
00:28:14,760 --> 00:28:18,260
Nastavite, da kazalec na
reference, nato pa vas

550
00:28:18,260 --> 00:28:21,400
lahko vrsta ciljne datoteke
Prvi kazalec

551
00:28:21,400 --> 00:28:22,972
in kažejo na novo vozlišče.

552
00:28:22,972 --> 00:28:25,680
Kjerkoli jo želite vstaviti,
da logika se dogaja, da drži.

553
00:28:25,680 --> 00:28:27,530
>> To je nekako kot dodeljevanje
začasne spremenljivke.

554
00:28:27,530 --> 00:28:28,700
Zapomnite si, da imaš
se prepričajte, da vas

555
00:28:28,700 --> 00:28:30,346
ne bo zmanjkalo, če ste zamenjavo.

556
00:28:30,346 --> 00:28:33,470
Želite, da se prepričajte, da imate
začasna spremenljivka, ki nekako ohranja

557
00:28:33,470 --> 00:28:35,620
tir, kjer je to stvar
se shranijo, tako da boste

558
00:28:35,620 --> 00:28:41,190
ne izgubijo katerokoli vrednost med
podobnega mesijanski okrog z njim.

559
00:28:41,190 --> 00:28:42,710
>> OK, tako da koda bo tukaj.

560
00:28:42,710 --> 00:28:45,020
Vidva si oglejte po oddelku.

561
00:28:45,020 --> 00:28:48,060
To bo tam.

562
00:28:48,060 --> 00:28:50,280
>> Torej, mislim, kako deluje
To je drugačna, če smo želeli

563
00:28:50,280 --> 00:28:52,300
vstaviti v sredini ali na koncu?

564
00:28:52,300 --> 00:28:57,892
Ima kdo idejo, kaj je
psevdokoda kot logično referenca

565
00:28:57,892 --> 00:29:00,350
da bomo, če bomo želeli
da jo vstavite v sredini?

566
00:29:00,350 --> 00:29:03,391
Torej, če bi želeli, da ga vstavite Na
glava, vse moramo storiti, je ustvariti novo vozlišče.

567
00:29:03,391 --> 00:29:06,311
Postavili smo kazalec, ki
novo vozlišče na kakršnikoli glavo,

568
00:29:06,311 --> 00:29:08,310
in potem smo postavili glavo
na novo vozlišče, kajne?

569
00:29:08,310 --> 00:29:11,560
Če bomo želeli, da ga vstavite v sredini
seznama, kaj bi morali storiti?

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

571
00:29:14,108 --> 00:29:16,110
>> OBČINSTVO: To bi še vedno
Podobna Postopek

572
00:29:16,110 --> 00:29:19,114
podobnega dodeljevanje kazalec in
nato dodelite ta kazalec,

573
00:29:19,114 --> 00:29:20,530
vendar bi morali tam poiskati.

574
00:29:20,530 --> 00:29:23,560
>> ANDI PENG: Točno tako natanko
enak postopek, razen tebe

575
00:29:23,560 --> 00:29:27,820
morali poiskati, kje ste
želijo, da novi kazalec, da gredo v,

576
00:29:27,820 --> 00:29:44,790
tako da, če hočem, da vstavite
Sredi povezana list-- OK,

577
00:29:44,790 --> 00:29:46,370
recimo, da je naša povezani seznam.

578
00:29:46,370 --> 00:29:49,500
Če želimo, da jo vstavite tukaj,
bomo ustvarili novo vozlišče.

579
00:29:49,500 --> 00:29:50,520
Bomo knjižnične funkcije malloc.

580
00:29:50,520 --> 00:29:52,220
Bomo ustvarili novo vozlišče.

581
00:29:52,220 --> 00:29:55,940
Bomo dodelite
kazalec tega vozlišča tukaj.

582
00:29:55,940 --> 00:29:58,335
>> Vendar je problem, ki se razlikuje
od koder je glava

583
00:29:58,335 --> 00:30:00,490
je, da smo vedeli, točno
kjer je glava.

584
00:30:00,490 --> 00:30:01,930
Bilo je prav na prvi, kajne?

585
00:30:01,930 --> 00:30:04,870
Ampak tukaj imamo slediti
kje smo jo vstavite.

586
00:30:04,870 --> 00:30:07,930
Če smo vstavljanje naše
node tukaj, imamo

587
00:30:07,930 --> 00:30:12,270
se prepričajte, da
ena od prejšnjih za to vozlišče

588
00:30:12,270 --> 00:30:14,172
je tista, ki reassigns kazalec.

589
00:30:14,172 --> 00:30:16,380
Torej moraš nekako
spremljate dveh stvari.

590
00:30:16,380 --> 00:30:19,420
Če spremljate, kjer je to
vozlišče trenutno vstavite.

591
00:30:19,420 --> 00:30:23,280
Prav tako morajo slediti, kje
prejšnja vozlišče, da gledaš

592
00:30:23,280 --> 00:30:24,340
je tudi tam.

593
00:30:24,340 --> 00:30:25,830
Vsakdo dobro s tem?

594
00:30:25,830 --> 00:30:26,500
V REDU.

595
00:30:26,500 --> 00:30:28,000
>> Kako približno vstavite do konca?

596
00:30:28,000 --> 00:30:34,220
Če bi želel, da ga dodate here-- če sem hotel
dodati novo vozlišče na konec seznama,

597
00:30:34,220 --> 00:30:37,009
kako bi jaz šel o tem?

598
00:30:37,009 --> 00:30:39,300
OBČINSTVO: Torej, trenutno je
zadnja je opozoril na nič.

599
00:30:39,300 --> 00:30:40,960
ANDI PENG: Ja.

600
00:30:40,960 --> 00:30:43,560
Točno, tako da je to ena
Trenutno je poudaril, da vedo,

601
00:30:43,560 --> 00:30:46,720
in tako mislim, v tem smislu, da je
Zelo enostavno dodajanje na konec seznama.

602
00:30:46,720 --> 00:30:51,810
Vse kar morate storiti je, da jo nastavite
enaka NULL in potem bum.

603
00:30:51,810 --> 00:30:53,070
Prav tam, zelo enostavno.

604
00:30:53,070 --> 00:30:53,960
Zelo preprosto.

605
00:30:53,960 --> 00:30:56,430
>> Zelo podobna
glavo, vendar je logično vas

606
00:30:56,430 --> 00:30:59,690
želite zagotoviti, da ukrepi
jemljete proti delaš vse to,

607
00:30:59,690 --> 00:31:01,500
ste po skupaj.

608
00:31:01,500 --> 00:31:04,420
To je zelo enostavno, v sredini
vaše kode, ujeli na,

609
00:31:04,420 --> 00:31:05,671
oh, sem dobil toliko nasvetov.

610
00:31:05,671 --> 00:31:07,461
Ne vem, kje
vse kaže na.

611
00:31:07,461 --> 00:31:09,170
Sploh ne vem, katero vozlišče sem na.

612
00:31:09,170 --> 00:31:11,490
Kaj se dogaja?

613
00:31:11,490 --> 00:31:13,620
>> Pomiri se, pomiri se, globoko vdihni.

614
00:31:13,620 --> 00:31:15,530
Potegnili svoje povezani seznam.

615
00:31:15,530 --> 00:31:18,800
Če rečeš, vem, kje točno
Moram vstaviti to v

616
00:31:18,800 --> 00:31:22,970
in točno vem, kako prerazporediti my
kazalci, veliko, veliko lažje sliko

617
00:31:22,970 --> 00:31:27,200
out-- veliko, veliko lažje, da se ne
izgubijo v hroščev v kodi.

618
00:31:27,200 --> 00:31:29,410
Vsakdo v redu s tem?

619
00:31:29,410 --> 00:31:31,380
V REDU.

620
00:31:31,380 --> 00:31:35,120
>> Tako da mislim, koncept, ki ga imamo, ne
res govoril o pred zdaj,

621
00:31:35,120 --> 00:31:38,131
in ti veš verjetno
ne bodo imeli veliko yet--

622
00:31:38,131 --> 00:31:40,880
to je nekako napredno concept--
je, da smo dejansko imeli podatke

623
00:31:40,880 --> 00:31:43,900
struktura se imenuje dvojno povezani seznam.

624
00:31:43,900 --> 00:31:46,390
Tako da lahko vi vidite,
vse, kar počnete, je ustvarjanje

625
00:31:46,390 --> 00:31:50,400
dejanska vrednost, dodatno
kazalec na vsakega od naših vozlišč

626
00:31:50,400 --> 00:31:52,660
ki kaže tudi s predhodnim vozliščem.

627
00:31:52,660 --> 00:31:58,170
Torej, ne samo, da imamo
vozlišča kaže na naslednjega.

628
00:31:58,170 --> 00:32:01,430
Prav tako opozarjajo, da prejšnji.

629
00:32:01,430 --> 00:32:04,310
Grem prezreti teh dveh prav zdaj.

630
00:32:04,310 --> 00:32:06,740
>> Torej imate verigo
ki se lahko premika v obe smeri,

631
00:32:06,740 --> 00:32:09,630
in potem je nekoliko lažje
logično sledijo vzdolž.

632
00:32:09,630 --> 00:32:11,896
Kot tod namesto
sledenja, oh, jaz

633
00:32:11,896 --> 00:32:14,520
morali vedeti, da je to vozlišče
tisti, ki moram prerazporedijo,

634
00:32:14,520 --> 00:32:17,532
Jaz lahko samo iti tu in
samo potegnite prejšnji.

635
00:32:17,532 --> 00:32:19,490
Potem vem, kje
da je, nato pa vas

636
00:32:19,490 --> 00:32:21,130
nimajo za prečkanje
celota povezanega seznama.

637
00:32:21,130 --> 00:32:22,180
To je nekoliko lažje.

638
00:32:22,180 --> 00:32:24,960
>> Ampak kot taka, imate dvakrat
količina kazalcev,

639
00:32:24,960 --> 00:32:26,960
da je dvojna količina pomnilnika.

640
00:32:26,960 --> 00:32:28,950
To je veliko nasvetov za sledenje.

641
00:32:28,950 --> 00:32:32,140
To je malo bolj zapleteno, vendar je
malo bolj prijazen do uporabnika, odvisno

642
00:32:32,140 --> 00:32:34,080
o tem, kaj poskušate doseči.

643
00:32:34,080 --> 00:32:36,910
>> Tako da je ta vrsta podatkov
struktura povsem obstaja,

644
00:32:36,910 --> 00:32:40,280
in struktura je zelo, zelo
preprosta razen vse, kar imaš, je,

645
00:32:40,280 --> 00:32:43,850
namesto samo kazalec na naslednjo,
imate tudi kazalec na prejšnji.

646
00:32:43,850 --> 00:32:45,940
To je vse, kar je bila razlika.

647
00:32:45,940 --> 00:32:47,740
Vsakdo dobro s tem?

648
00:32:47,740 --> 00:32:48,240
Cool.

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

650
00:32:50,940 --> 00:32:53,280
>> Vse je v redu, tako da zdaj sem
res porabili verjetno

651
00:32:53,280 --> 00:32:56,870
kot 15 do 20 minut, ali pa bo večji
preostalega časa v oddelku

652
00:32:56,870 --> 00:32:58,360
govorimo o hash tabel.

653
00:32:58,360 --> 00:33:02,590
Koliko od vas fantov
Prebral pset5 spec?

654
00:33:02,590 --> 00:33:03,620
Dobro, dobro.

655
00:33:03,620 --> 00:33:06,160
To je višja od 50% normalno.

656
00:33:06,160 --> 00:33:07,560
To je v redu.

657
00:33:07,560 --> 00:33:10,345
>> Tako da bodo fantje videli,
ste izziv pset5

658
00:33:10,345 --> 00:33:16,790
bo izvajala slovar
kjer si naložiti preko 140.000 besed

659
00:33:16,790 --> 00:33:20,610
da smo vam in preverjanje črkovanja
je proti vsem besedilu.

660
00:33:20,610 --> 00:33:22,580
Mi vam bomo naključno
kosov literature.

661
00:33:22,580 --> 00:33:23,520
Mi vam bomo Odiseje.

662
00:33:23,520 --> 00:33:24,561
Mi vam bomo Iliadi.

663
00:33:24,561 --> 00:33:26,350
Mi vam bomo Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> In vaš izziv
bo preverjanje črkovanja

665
00:33:28,220 --> 00:33:31,760
vsak beseda v vseh
od teh slovarjev

666
00:33:31,760 --> 00:33:34,960
v bistvu z našo črkovalnik.

667
00:33:34,960 --> 00:33:38,620
In tako obstaja nekaj delov
ustvarjanja to pset,

668
00:33:38,620 --> 00:33:41,970
Prvi hočeš biti
lahko dejansko obremenitev

669
00:33:41,970 --> 00:33:43,970
vse besede v vašo
slovar, nato pa vas

670
00:33:43,970 --> 00:33:45,530
želijo biti sposobni
črkovati ček vse od njih.

671
00:33:45,530 --> 00:33:48,780
In tako, kot je na primer, da boš zahtevajo
podatkovna struktura, ki lahko to stori hitro

672
00:33:48,780 --> 00:33:50,790
ter učinkovito in dinamično.

673
00:33:50,790 --> 00:33:52,900
>> Torej, mislim, da je najlažje
način, da to storite, vas

674
00:33:52,900 --> 00:33:55,010
Verjetno bi ustvarili niz, kajne?

675
00:33:55,010 --> 00:33:58,910
Najlažji način shranjevanja je vas
lahko ustvarite niz 140.000 besed

676
00:33:58,910 --> 00:34:03,400
in jih vse samo mesto tam in
jih nato prečkala s binarnega iskanja

677
00:34:03,400 --> 00:34:06,780
ali z izborov ali not--
Žal mi je, da je razvrščanje.

678
00:34:06,780 --> 00:34:10,729
Lahko jih uredite in jih nato prečkala
s binarnega iskanja ali pa samo linearno iskanje

679
00:34:10,729 --> 00:34:13,730
in samo končne besede, temveč da
potrebnega ogromno pomnilnika,

680
00:34:13,730 --> 00:34:15,190
in to ni zelo učinkovito.

681
00:34:15,190 --> 00:34:18,350
>> In tako bomo za začetek
govorimo o načinih izdelave

682
00:34:18,350 --> 00:34:20,110
naš čas teče bolj učinkovito.

683
00:34:20,110 --> 00:34:23,190
In naš cilj je, da bi dobili
konstanten čas, kjer

684
00:34:23,190 --> 00:34:25,810
to je skoraj tako kot nizi, kjer
imate takojšen dostop.

685
00:34:25,810 --> 00:34:28,560
Če sem hotel iskati karkoli,
Želim, da bi lahko le,

686
00:34:28,560 --> 00:34:30,810
boom, da bi našli točno, in ga izvlecite.

687
00:34:30,810 --> 00:34:34,100
In tako strukturo, v kateri
bomo lahko postali zelo blizu

688
00:34:34,100 --> 00:34:37,569
da se lahko dostop konstantna
Tokrat je to sveti gral

689
00:34:37,569 --> 00:34:41,370
v programiranju konstanta
Čas se imenuje hash tabelo.

690
00:34:41,370 --> 00:34:45,370
In tako je David že prej omenjeno
[Neslišno] malo v predavanju,

691
00:34:45,370 --> 00:34:49,100
ampak bomo res
potop v globokem tem tednu

692
00:34:49,100 --> 00:34:51,780
na kos, ki je v zvezi s
kako hash tabela deluje.

693
00:34:51,780 --> 00:34:53,949
>> Torej, na način, da je hašiš
namizno dela, na primer,

694
00:34:53,949 --> 00:35:00,230
če sem hotel, da shranite kup besedami,
kup besed v angleškem jeziku,

695
00:35:00,230 --> 00:35:02,940
Jaz bi teoretično dal
banana, jabolko, kivi, mango, par,

696
00:35:02,940 --> 00:35:04,980
in melone vse na samo paleto.

697
00:35:04,980 --> 00:35:07,044
Lahko bi prilegajo in jih je najti.

698
00:35:07,044 --> 00:35:09,210
To bi bilo nekako v bolečinah
iskanje po in dostop,

699
00:35:09,210 --> 00:35:12,920
vendar je lažji način za to je,
da bomo lahko ustvarili dejansko strukturo

700
00:35:12,920 --> 00:35:15,680
imenuje hash tabele, kjer smo izbrskali.

701
00:35:15,680 --> 00:35:19,880
Vodimo vse naše ključev prek
funkcija hash, enačba,

702
00:35:19,880 --> 00:35:22,600
ki jih vse spremeni v
nekakšna vrednosti

703
00:35:22,600 --> 00:35:28,740
da potem bomo lahko shranite na
v bistvu paleto povezani seznam.

704
00:35:28,740 --> 00:35:32,570
>> In tako sem, če bomo želeli
za shranjevanje angleške besede,

705
00:35:32,570 --> 00:35:37,250
smo lahko potencialno samo, jaz ne
Veš, pa vse prve črke v

706
00:35:37,250 --> 00:35:39,630
v neke vrste številko.

707
00:35:39,630 --> 00:35:43,140
In tako, na primer, če sem hotel
A sinonim apple--

708
00:35:43,140 --> 00:35:47,460
ali z indeksom od 0, in
B sinonim z 1,

709
00:35:47,460 --> 00:35:51,030
imamo lahko 26 vnose
da lahko samo shranite

710
00:35:51,030 --> 00:35:53,610
vse črk
alphabet, da bomo začeli z.

711
00:35:53,610 --> 00:35:56,130
In potem bomo lahko imeli
jabolko na indeks 0.

712
00:35:56,130 --> 00:35:59,160
Imamo lahko banano na indeksu
1, melone na indeksu 2,

713
00:35:59,160 --> 00:36:00,540
in tako naprej in tako naprej.

714
00:36:00,540 --> 00:36:04,460
In zato, če sem hotel iskati
moj hash tabele in dostop jabolko,

715
00:36:04,460 --> 00:36:07,560
Vem, jabolko začne z
A, in točno vem,

716
00:36:07,560 --> 00:36:10,860
da mora biti in razpršitve
miza na indeksu 0 zato ker

717
00:36:10,860 --> 00:36:13,620
funkcije predhodno dodeljena.

718
00:36:13,620 --> 00:36:16,572
>> Torej, ne vem, mi smo
program uporabniški kadar

719
00:36:16,572 --> 00:36:18,780
vam bomo zaračunali z
arbitrarily-- ne samovoljno,

720
00:36:18,780 --> 00:36:22,530
s poskušajo premišljeno
mislim dobrih enačb

721
00:36:22,530 --> 00:36:25,460
da se lahko širi
iz vseh vaših vrednot

722
00:36:25,460 --> 00:36:29,370
na način, ki jih lahko enostavno dostopate
je kasneje s podobno enačbo

723
00:36:29,370 --> 00:36:31,130
da vas, sami, vem.

724
00:36:31,130 --> 00:36:35,210
Torej, v tem smislu, če sem hotel iti
mango, vem, oh, se začne z m.

725
00:36:35,210 --> 00:36:37,134
Mora biti v indeksu 12.

726
00:36:37,134 --> 00:36:38,800
Nimam iskati skozi karkoli.

727
00:36:38,800 --> 00:36:42,080
Vem exactly-- sem lahko samo iti
indeks 12 in potegnite, da ven.

728
00:36:42,080 --> 00:36:45,520
>> Vsakdo jasno, kako
Funkcija hash tabele se deluje?

729
00:36:45,520 --> 00:36:48,380
To je nekako le bolj kompleksno paleto.

730
00:36:48,380 --> 00:36:50,010
To je vse, kar je.

731
00:36:50,010 --> 00:36:51,630
V REDU.

732
00:36:51,630 --> 00:36:57,690
>> Torej, mislim, da smo zašli v
to vprašanje o tem, kaj

733
00:36:57,690 --> 00:37:06,390
se zgodi, če imate več stvari
da vam isti indeks?

734
00:37:06,390 --> 00:37:10,570
Tako pravijo naše delovanje, vse to
naredil je bilo to prvi dopis

735
00:37:10,570 --> 00:37:14,490
in nato da na A
Ustrezni 0 do 25 indeks.

736
00:37:14,490 --> 00:37:17,137
To je povsem v redu, če
ste le eden od vsakega.

737
00:37:17,137 --> 00:37:18,970
Ampak drugi začnete
ki imajo več, ste

738
00:37:18,970 --> 00:37:20,910
dogaja, da imajo, kaj se ti trčenja.

739
00:37:20,910 --> 00:37:25,580
>> Torej, če sem poskusil vstaviti pokopati v hash
tabela, ki ima že banano na njem,

740
00:37:25,580 --> 00:37:27,870
kaj se bo zgodilo, ko
poskusite vstaviti to?

741
00:37:27,870 --> 00:37:30,930
Slabe stvari, ker banana
že obstaja v indeksu

742
00:37:30,930 --> 00:37:33,800
ki jo želite shraniti v.

743
00:37:33,800 --> 00:37:35,560
Berry vrsta je všeč, ah, kaj naj storim?

744
00:37:35,560 --> 00:37:37,080
Ne vem, kam iti.

745
00:37:37,080 --> 00:37:38,410
Kako rešiti to?

746
00:37:38,410 --> 00:37:41,150
>> In tako bo vidva vrste
glej delamo to težavno stvar

747
00:37:41,150 --> 00:37:44,810
kjer bomo lahko nekako dejansko
ustvariti povezan seznam iz naših polj.

748
00:37:44,810 --> 00:37:46,840
In tako najlažje
razmišljati o tem,

749
00:37:46,840 --> 00:37:50,830
Vse hash tabela je
array povezanih seznamov.

750
00:37:50,830 --> 00:37:55,670
In tako, v tem smislu, imate
to lepo niz kazalcev,

751
00:37:55,670 --> 00:37:58,740
in nato vsak kazalec v
da vrednost, v tem indeksu,

752
00:37:58,740 --> 00:38:00,740
lahko dejansko kažejo na druge stvari.

753
00:38:00,740 --> 00:38:05,720
In tako imaš vse te ločene
verige prihajajo off enega velikega polja.

754
00:38:05,720 --> 00:38:07,960
>> In tako sem, če sem
želel vstaviti jagodami,

755
00:38:07,960 --> 00:38:11,220
Vem, OK, bom vhod
je po mojem hash funkcijo.

756
00:38:11,220 --> 00:38:15,070
Grem na koncu z indeksom
1, in potem bom lahko, da imajo

757
00:38:15,070 --> 00:38:20,410
le manjši podmnožica to
velikan 140.000 besedo slovar.

758
00:38:20,410 --> 00:38:24,220
In potem sem lahko samo pogled
skozi 1/26 tega.

759
00:38:24,220 --> 00:38:27,910
>> In tako potem bom lahko samo vstavite
berry bodisi pred ali po banana

760
00:38:27,910 --> 00:38:28,820
v tem primeru?

761
00:38:28,820 --> 00:38:29,700
Potem, kajne?

762
00:38:29,700 --> 00:38:33,920
In tako boste želeli
vstavite to vozlišče po banana,

763
00:38:33,920 --> 00:38:36,667
in tako boste, da vstavite
na repu tega povezanega seznama.

764
00:38:36,667 --> 00:38:38,500
Jaz bom šel nazaj
s tem prejšnjo prosojnico,

765
00:38:38,500 --> 00:38:40,680
tako da vidva lahko vidite, kako
hash funkcija deluje.

766
00:38:40,680 --> 00:38:43,980
>> Torej hash funkcija je ta enačba
da delate neke vrste vaš prispevek

767
00:38:43,980 --> 00:38:46,940
skozi, da bi dobili, kar indeks
Jo želite dodeliti smeri.

768
00:38:46,940 --> 00:38:51,130
In tako, v tem primeru, vse, kar smo želeli
storiti je vzeti prvo pismo,

769
00:38:51,130 --> 00:38:55,890
obrnejo, da v indeksu, nato pa smo
lahko shranite, da je v našem hash funkcijo.

770
00:38:55,890 --> 00:39:00,160
Vsi delamo tu smo
pretvorbo prvo pismo.

771
00:39:00,160 --> 00:39:04,770
Torej keykey [0], je le prva črka
ne glede na niz imava,

772
00:39:04,770 --> 00:39:05,720
smo poteka v.

773
00:39:05,720 --> 00:39:09,740
Mi smo pretvarjanje, da zgornji del, in
smo se odšteje s velikimi črkami A,

774
00:39:09,740 --> 00:39:11,740
zato vse, kar počne
nam daje številne

775
00:39:11,740 --> 00:39:13,670
v katerem bomo lahko izbrskali naše vrednote na.

776
00:39:13,670 --> 00:39:16,550
>> In potem bomo
vrne hash VELIKOST modul.

777
00:39:16,550 --> 00:39:19,340
Bodite zelo, zelo previdni
ker, teoretično, tu

778
00:39:19,340 --> 00:39:21,870
tvoj hash vrednost je lahko neskončno.

779
00:39:21,870 --> 00:39:23,660
To lahko samo pojdi naprej in naprej in naprej.

780
00:39:23,660 --> 00:39:26,080
To bi bilo nekaj res,
Res velika vrednost,

781
00:39:26,080 --> 00:39:29,849
ampak zato, ker vaše hash tabelo, ki
ki ste jo ustvarili ima samo 26 indeksov,

782
00:39:29,849 --> 00:39:31,890
želite, da vaš
modulusing tako da boste

783
00:39:31,890 --> 00:39:33,848
ne run-- je isto
stvar kot vaš queue--

784
00:39:33,848 --> 00:39:36,320
tako da vam ne zmanjka off
dno vašega hash funkcijo.

785
00:39:36,320 --> 00:39:39,210
>> Hočeš, da ga ovijte nazaj okoli
na enak način, v [neslišno], če

786
00:39:39,210 --> 00:39:41,750
ste imeli kot zelo,
zelo velika črka, ki jih

787
00:39:41,750 --> 00:39:43,740
niso želeli, da bi
Samo nogama konec.

788
00:39:43,740 --> 00:39:46,948
Ista stvar tukaj, boste želeli, da poskrbite,
ne nogama konec embaliranje

789
00:39:46,948 --> 00:39:48,330
približno na vrhu tabele.

790
00:39:48,330 --> 00:39:50,530
Torej, to je samo zelo
preprosto funkcijo razpršitve.

791
00:39:50,530 --> 00:39:56,570
Vse, kar si je vzeti prvi
pismo o kakršnikoli našega vhoda je

792
00:39:56,570 --> 00:40:01,660
in pa, da je v indeksu, ki
lahko bi dal v naše hash tabelo.

793
00:40:01,660 --> 00:40:05,450
>> Ja, tako kot sem rekel prej,
način, da bomo rešili trčenja

794
00:40:05,450 --> 00:40:09,330
v našem hash so mize, ki ima,
kaj pravimo, veriženje.

795
00:40:09,330 --> 00:40:13,860
Torej, če boste poskušali vstaviti multipla
Besede, ki se začnejo z isto stvar,

796
00:40:13,860 --> 00:40:16,145
boste morali en hash vrednost.

797
00:40:16,145 --> 00:40:18,770
Avokado in jabolko, če ste
ga vodijo skozi našo hash funkcijo,

798
00:40:18,770 --> 00:40:21,450
se dogaja, da bi vam
enako število, število 0.

799
00:40:21,450 --> 00:40:24,550
In tako način, kako rešiti, da je
da bomo lahko dejansko nekako povežejo

800
00:40:24,550 --> 00:40:27,010
skupaj preko povezanih seznamov.

801
00:40:27,010 --> 00:40:29,600
>> In tako v tem smislu,
vidva lahko vidite vrste

802
00:40:29,600 --> 00:40:32,640
kako podatkovne strukture, ki
smo bili predhodno nastavitev

803
00:40:32,640 --> 00:40:35,870
kot rozin povezan seznam naravi
za lahko pridejo skupaj v eno.

804
00:40:35,870 --> 00:40:38,860
In potem si lahko ustvarite daleč
bolj učinkovite podatkovne strukture

805
00:40:38,860 --> 00:40:43,350
da zmorem večje količine
Podatki, ki dinamično spreminjanje velikosti, odvisno

806
00:40:43,350 --> 00:40:44,870
na vaše potrebe.

807
00:40:44,870 --> 00:40:45,620
Vsakdo jasno?

808
00:40:45,620 --> 00:40:47,580
Vsakdo nekako jasno,
o tem, kaj se dogaja tukaj?

809
00:40:47,580 --> 00:40:52,110
>> Če sem želel insert-- kaj je
sadje, ki se začne z, ne vem,

810
00:40:52,110 --> 00:40:54,726
B, razen jagod, banana.

811
00:40:54,726 --> 00:40:55,710
>> OBČINSTVO: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI PENG: Blackberry, blackberry.

813
00:40:57,910 --> 00:41:00,530
Kje blackberry gre tukaj?

814
00:41:00,530 --> 00:41:04,251
No, pravzaprav niso razporejene
še to, vendar teoretično

815
00:41:04,251 --> 00:41:06,250
če bi želeli imeti to
po abecednem vrstnem redu,

816
00:41:06,250 --> 00:41:07,944
kje naj blackberry iti?

817
00:41:07,944 --> 00:41:09,210
>> OBČINSTVO: [neslišno]

818
00:41:09,210 --> 00:41:11,100
>> ANDI PENG: Točno, potem tukaj, kajne?

819
00:41:11,100 --> 00:41:14,950
Ampak, ker je zelo težko
reorder-- Mislim, da je do vas.

820
00:41:14,950 --> 00:41:17,920
Vidva lahko popolnoma
izvajati, kar hočeš.

821
00:41:17,920 --> 00:41:20,730
Bolj učinkovit način
to početje morda

822
00:41:20,730 --> 00:41:24,570
bi bilo razvrstiti vaše povezana
seznam v abecednem vrstnem redu,

823
00:41:24,570 --> 00:41:26,520
in tako, ko ste
vstavljanje stvari, ki jih želite

824
00:41:26,520 --> 00:41:28,632
biti prepričani, da jih vstavite
v abecednem vrstnem redu

825
00:41:28,632 --> 00:41:30,590
tako da potem, ko ste
poskušam jih iskati,

826
00:41:30,590 --> 00:41:32,410
nimate za prečkanje vse.

827
00:41:32,410 --> 00:41:35,290
Točno tam, kjer veš,
je, in to je lažje.

828
00:41:35,290 --> 00:41:39,100
>> Ampak, če boste nekako morali
Stvari vrinjeni naključno,

829
00:41:39,100 --> 00:41:41,420
ste še vedno dogaja, da imajo
da je prečkanje nekako.

830
00:41:41,420 --> 00:41:44,990
In zato, če sem hotel samo
vstavite blackberry tukaj

831
00:41:44,990 --> 00:41:47,470
in sem hotel iskati
da, vem, oh, blackberry

832
00:41:47,470 --> 00:41:52,012
se mora začeti z indeksom 1, tako da sem
vem, sprašuje samo iskanje na 1.

833
00:41:52,012 --> 00:41:53,970
In potem sem lahko nekako
prečkala povezan seznam

834
00:41:53,970 --> 00:41:56,120
dokler ne pridem do BlackBerry,
in then-- ja?

835
00:41:56,120 --> 00:41:59,550
>> OBČINSTVO: Če ste poskušali create--
Mislim, da, kot je to zelo preprost hash

836
00:41:59,550 --> 00:42:00,050
funkcija.

837
00:42:00,050 --> 00:42:02,835
In če smo želeli storiti
več plasti te všeč,

838
00:42:02,835 --> 00:42:05,870
OK, želimo ločiti v
kot vse abecedne črk na

839
00:42:05,870 --> 00:42:09,040
in potem spet rad še en niz
abecednih črk znotraj, da

840
00:42:09,040 --> 00:42:11,715
smo dajanje kot hash
miza v hash tabele,

841
00:42:11,715 --> 00:42:13,256
ali kot funkcije v odvisnosti?

842
00:42:13,256 --> 00:42:14,880
Ali je that--

843
00:42:14,880 --> 00:42:17,510
>> ANDI PENG: Torej vaš hash
function-- svoje razpršene tabele

844
00:42:17,510 --> 00:42:19,360
lahko tako velika, kot si želite, da bi.

845
00:42:19,360 --> 00:42:21,930
Torej, v tem smislu sem mislil
je bilo zelo enostavno, zelo

846
00:42:21,930 --> 00:42:25,320
enostavno za mene, da nekako temelji
na črkami prvo besedo.

847
00:42:25,320 --> 00:42:28,690
In tako da je le 26 možnosti.

848
00:42:28,690 --> 00:42:32,650
Lahko dobim samo 26 možnosti od
Od 0 do 25 let, saj lahko le

849
00:42:32,650 --> 00:42:36,510
začeti od A do Ž, ampak če si hotel
dodati, morda, več kompleksnosti

850
00:42:36,510 --> 00:42:39,260
ali hitreje teči čas, da vaš
hash tabele, morate nujno

851
00:42:39,260 --> 00:42:40,760
lahko storite vse vrste stvari.

852
00:42:40,760 --> 00:42:43,330
Lahko naredite sami
enačba, ki vam daje

853
00:42:43,330 --> 00:42:48,000
več distribucija v vašem
besede, potem ko iščete,

854
00:42:48,000 --> 00:42:49,300
to se dogaja, da se hitreje.

855
00:42:49,300 --> 00:42:52,100
>> To je povsem odvisno od vas fantje
kako želite izvesti to.

856
00:42:52,100 --> 00:42:55,140
Pomislite na to kot samo vedri.

857
00:42:55,140 --> 00:42:57,376
Če sem hotel imeti
26 žlice, jaz grem

858
00:42:57,376 --> 00:42:59,420
razvrstiti stvari v teh vedri.

859
00:42:59,420 --> 00:43:02,980
Ampak jaz grem, da imajo kup
stvari v posamezne segmente,

860
00:43:02,980 --> 00:43:05,890
tako da, če želite, da jo
hitrejše in učinkovitejše,

861
00:43:05,890 --> 00:43:07,190
Naj imajo sto veder.

862
00:43:07,190 --> 00:43:09,290
>> Ampak potem moraš razbrati
način, da razvrstite stvari, tako da so

863
00:43:09,290 --> 00:43:11,040
v ustrezno vedro morajo biti.

864
00:43:11,040 --> 00:43:13,331
Ampak potem, ko ste dejansko
želeli videti na tej vedro,

865
00:43:13,331 --> 00:43:16,410
to je veliko hitreje, ker obstaja
manj stvari v posamezne segmente.

866
00:43:16,410 --> 00:43:20,250
In tako, ja, to je dejansko
trik za vas v pset5

867
00:43:20,250 --> 00:43:22,360
je, da se boste
izzvani, da samo ustvariti

868
00:43:22,360 --> 00:43:26,170
karkoli je najučinkovitejši
Funkcija si lahko zamislite, da bi

869
00:43:26,170 --> 00:43:28,520
lahko shranite in preverite te vrednote.

870
00:43:28,520 --> 00:43:30,840
>> Popolnoma do vaju
pa hočeš to storiti,

871
00:43:30,840 --> 00:43:32,229
ampak to je res dobra točka.

872
00:43:32,229 --> 00:43:34,520
Ta vrsta logike
želim, da začnete razmišljati o

873
00:43:34,520 --> 00:43:37,236
je tudi, zakaj ne naredim več veder.

874
00:43:37,236 --> 00:43:39,527
In potem moram iskati
zmanjšane za stvari, in potem pa sem

875
00:43:39,527 --> 00:43:41,640
imajo drugačno funkcijo razpršitve.

876
00:43:41,640 --> 00:43:45,500
>> Ja, tam je veliko načinov, da to storijo
pset, nekateri so hitrejši od drugih.

877
00:43:45,500 --> 00:43:50,630
Jaz sem popolnoma bomo šele videli, kako
hiter je bil najhitrejši vidva bo

878
00:43:50,630 --> 00:43:55,170
lahko dobili svoje funkcije za delo.

879
00:43:55,170 --> 00:43:58,176
OK, vsi dobro na
veriženje in hash tabele?

880
00:43:58,176 --> 00:44:00,800
To je dejansko všeč zelo preprosta
koncept, če mislite o tem.

881
00:44:00,800 --> 00:44:05,160
Vse, kar je, je ločevanje karkoli
vaši vložki so v vedra,

882
00:44:05,160 --> 00:44:10,670
njihovo razvrščanje in preiskujejo
navaja, da je tam povezana s.

883
00:44:10,670 --> 00:44:11,852
>> Cool.

884
00:44:11,852 --> 00:44:18,160
V redu, sedaj imamo različne vrste
strukture podatkov, ki se imenuje drevo.

885
00:44:18,160 --> 00:44:20,850
Pojdimo naprej in govori o poskusih
ki so izrazito drugačen,

886
00:44:20,850 --> 00:44:22,330
vendar pa v isti kategoriji.

887
00:44:22,330 --> 00:44:29,010
V bistvu, vse je drevo namesto
organizacije podatkov v linearno

888
00:44:29,010 --> 00:44:32,560
da ste hash tabela does--
Veste, to je dobil top in dno

889
00:44:32,560 --> 00:44:37,900
in potem si nekako povezati off it-- a
Drevo ima top, ki ga imenujemo koren,

890
00:44:37,900 --> 00:44:40,220
in potem ima liste vse okoli njega.

891
00:44:40,220 --> 00:44:42,390
>> In tako vse, kar imamo tukaj
je samo vrh vozlišče

892
00:44:42,390 --> 00:44:45,980
ki kaže na drugih vozlišč, da točke
na več vozlišč, in tako naprej in tako naprej.

893
00:44:45,980 --> 00:44:48,130
In tako boste morali delitev vej.

894
00:44:48,130 --> 00:44:53,255
To je samo drugačen način organiziranja
podatkov, in ker smo to drevo klic,

895
00:44:53,255 --> 00:44:56,270
vidva just-- je samo
vzoru ven videti kot drevesa.

896
00:44:56,270 --> 00:44:57,670
To je razlog, zakaj ga imenujemo drevesa.

897
00:44:57,670 --> 00:44:59,370
>> Hash tabela izgleda mizo.

898
00:44:59,370 --> 00:45:01,310
Drevo samo izgleda kot drevo.

899
00:45:01,310 --> 00:45:03,300
Vse, kar je še posebna
način organiziranja vozlišč

900
00:45:03,300 --> 00:45:06,020
odvisno od tega, kakšne so vaše potrebe.

901
00:45:06,020 --> 00:45:11,810
>> Torej imate korenine in
potem imate liste.

902
00:45:11,810 --> 00:45:15,380
Tako, da smo lahko še posebej
pomislite, da je binarno drevo,

903
00:45:15,380 --> 00:45:18,150
binarno drevo je samo
posebna vrsta drevesa

904
00:45:18,150 --> 00:45:22,450
kjer vsako vozlišče le točke
da, na max, dva druga vozlišča.

905
00:45:22,450 --> 00:45:25,434
In tako da tukaj imate razlikuje
simetrija v drevo

906
00:45:25,434 --> 00:45:28,600
ki omogoča lažje nekako pogledati
po kakšni ceni ste, ker potem ste

907
00:45:28,600 --> 00:45:30,150
še vedno levo ali desno.

908
00:45:30,150 --> 00:45:33,150
Nikoli ni kot levi tretjina od
levo ali četrti z leve.

909
00:45:33,150 --> 00:45:36,358
To je samo imate levo in pravico
in lahko iščete eno od teh dveh.

910
00:45:36,358 --> 00:45:38,980
In zakaj je to koristno?

911
00:45:38,980 --> 00:45:40,980
Tako, da je to
koristno je, če iščete

912
00:45:40,980 --> 00:45:42,890
iskanje po vrednotah, kajne?

913
00:45:42,890 --> 00:45:45,640
Namesto izvajanju binarno
iskanje v vrsto napak,

914
00:45:45,640 --> 00:45:49,260
če boste želeli, da bi lahko vstavite vozlišč
in odnese vozlišč po svoji volji in tudi

915
00:45:49,260 --> 00:45:52,185
ohranitev iskanje
Zmogljivosti binarnega iskanja.

916
00:45:52,185 --> 00:45:54,560
Torej, na ta način, da smo nekako
tricking-- se spomniš, ko smo

917
00:45:54,560 --> 00:45:56,530
je dejal, povezani seznami ne more binarno iskanje?

918
00:45:56,530 --> 00:46:01,700
Mi smo nekako ustvariti podatkovno strukturo
da trikov, da v delovni.

919
00:46:01,700 --> 00:46:05,034
>> In zato, ker povezani seznami so linearne,
so le povezati eno za drugo.

920
00:46:05,034 --> 00:46:06,950
Lahko vrste imajo
drugačna vrsta kazalcev

921
00:46:06,950 --> 00:46:09,408
ki kažejo na različnih vozlišč
ki nam lahko pomaga pri iskanju.

922
00:46:09,408 --> 00:46:12,590
In tako sem, če sem hotel
imajo binarno iskalno drevo,

923
00:46:12,590 --> 00:46:14,090
Vem, da je moj sredini, če 55 let.

924
00:46:14,090 --> 00:46:18,280
Jaz sem le, da bo ustvaril, da
kot moj sredini, kot je moj koren,

925
00:46:18,280 --> 00:46:20,770
in potem bom imel
Vrednosti spin off od tega.

926
00:46:20,770 --> 00:46:25,610
>> Torej, tukaj, če grem za iskanje
vrednost 66, lahko začnem pri 55.

927
00:46:25,610 --> 00:46:27,310
To je 66 večja od 55?

928
00:46:27,310 --> 00:46:30,970
Ja je, zato sem vedel, da sem mus iskanje
i n pravica kazalec tega drevesa.

929
00:46:30,970 --> 00:46:32,440
Grem do 77.

930
00:46:32,440 --> 00:46:35,367
OK, je 66 manj kot ali večji od 77?

931
00:46:35,367 --> 00:46:37,950
To je manj kot, tako da boste vedeli, oh,
da mora biti v levo vozlišče.

932
00:46:37,950 --> 00:46:41,410
>> In tako da tukaj smo nekako ohranjanja
vse od velikih stvari o nizi,

933
00:46:41,410 --> 00:46:44,420
tako kot dinamično spreminjanje velikosti
predmetov, pri čemer je

934
00:46:44,420 --> 00:46:49,530
lahko vstavite in brisanje po svoji volji,
ne da bi morali skrbeti fiksni

935
00:46:49,530 --> 00:46:50,370
Količina prostora.

936
00:46:50,370 --> 00:46:52,820
Še vedno ohraniti vse
te čudovite stvari

937
00:46:52,820 --> 00:46:57,140
hkrati pa lahko, da se ohrani
log in iskanje čas binarnega iskanja

938
00:46:57,140 --> 00:47:00,450
da smo bili prej samo
lahko dobili besedno zvezo.

939
00:47:00,450 --> 00:47:06,310
>> Cool podatkovna struktura, vrsta
zapletene za izvajanje, vozlišče.

940
00:47:06,310 --> 00:47:08,311
Kot lahko vidite, vse to
je struct vozlišča

941
00:47:08,311 --> 00:47:10,143
je, da imate levo
in pravica kazalec.

942
00:47:10,143 --> 00:47:11,044
To je vse, kar je.

943
00:47:11,044 --> 00:47:12,960
Torej, ne samo
ima x ali prejšnja.

944
00:47:12,960 --> 00:47:15,920
Imate levo ali desno, in nato
jih lahko nekako povezati

945
00:47:15,920 --> 00:47:16,836
Vendar pa se tako odločijo.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, smo dejansko dogaja
vzemite nekaj minut.

948
00:47:24,270 --> 00:47:25,790
Tako smo šli nazaj.

949
00:47:25,790 --> 00:47:28,270
Kot sem že rekel,
Nekako sem razložil

950
00:47:28,270 --> 00:47:31,520
logika, kako smo
bi preiskava skozi to.

951
00:47:31,520 --> 00:47:33,860
Bomo poskušali
pseudocoding to gledat

952
00:47:33,860 --> 00:47:38,000
če bomo lahko nekako velja
Ista logika binarnega iskanja

953
00:47:38,000 --> 00:47:40,055
za drugačno vrsto podatkovne strukture.

954
00:47:40,055 --> 00:47:45,049
Če hočete, da bi kot par
minut, da le razmišljati o tem.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
V REDU.

957
00:48:46,925 --> 00:48:51,407
V redu, bom
dejansko samo vam the-- ne,

958
00:48:51,407 --> 00:48:52,990
bomo govorili o psevdokoda prvi.

959
00:48:52,990 --> 00:48:56,580
Torej, ali ima kdo rad
dati stab, kaj

960
00:48:56,580 --> 00:49:02,100
prva stvar, ki jo želite storiti, ko
ste začeli ven Iskanje je?

961
00:49:02,100 --> 00:49:04,460
Če iščemo
vrednost 66, kar je

962
00:49:04,460 --> 00:49:07,940
prva stvar, ki jo želite storiti, če
želimo binarno iskati to drevo?

963
00:49:07,940 --> 00:49:10,760
>> OBČINSTVO: Želite videti v redu
in poglej levo in videli [neslišno]

964
00:49:10,760 --> 00:49:11,230
večje število.

965
00:49:11,230 --> 00:49:12,271
>> ANDI PENG: Ja, točno.

966
00:49:12,271 --> 00:49:15,350
Torej boš pogled na vaše korenine.

967
00:49:15,350 --> 00:49:18,180
Obstaja veliko načinov, kako lahko kličete
to, vaši starša ljudje pravijo.

968
00:49:18,180 --> 00:49:21,317
Rad bi rekel, koren, ker
da je kot koren drevesa.

969
00:49:21,317 --> 00:49:23,400
Greš pogledati
svoj koren vozlišče, in vi ste

970
00:49:23,400 --> 00:49:26,940
bomo videli, je 66 večja
ali manjša od 55.

971
00:49:26,940 --> 00:49:30,360
In če je večji od, dobro, da je
večja kot, kjer ne želimo iskati?

972
00:49:30,360 --> 00:49:32,000
Kje želimo iskati zdaj, kajne?

973
00:49:32,000 --> 00:49:34,340
Želimo, da iskanje po
Desna polovica tega drevesa.

974
00:49:34,340 --> 00:49:38,390
>> Torej imamo priročno, A
kazalec, ki kaže na desno.

975
00:49:38,390 --> 00:49:44,325
In tako potem lahko nastavite
naš novi koren, da bo 77.

976
00:49:44,325 --> 00:49:46,450
Mi lahko samo iti kamorkoli
kazalec je obrnjena.

977
00:49:46,450 --> 00:49:49,100
No, oh, tu začenjamo
na 77, in bomo lahko samo

978
00:49:49,100 --> 00:49:51,172
To storite tako rekurzivno znova in znova.

979
00:49:51,172 --> 00:49:52,880
Na ta način se nekako
od imajo funkcijo.

980
00:49:52,880 --> 00:49:57,430
Imate način iskanja, ki vas
Lahko samo ponovim znova in znova in znova,

981
00:49:57,430 --> 00:50:02,720
odvisno od tega, kje želite iskati
dokler ne boste na koncu dobili z vrednostjo

982
00:50:02,720 --> 00:50:04,730
ki iščete.

983
00:50:04,730 --> 00:50:05,230
Ima smisel?

984
00:50:05,230 --> 00:50:07,800
>> Sem približno razkazati vi dejansko
kodo, in to je veliko kode.

985
00:50:07,800 --> 00:50:08,674
Ni potrebe, da znorela.

986
00:50:08,674 --> 00:50:09,910
Pogovorila se bova skozi to.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Pravzaprav ne.

989
00:50:14,020 --> 00:50:15,061
To je bila samo psevdokoda.

990
00:50:15,061 --> 00:50:17,860
OK, to je bil šele psevdokoda,
ki je nekoliko zapletena,

991
00:50:17,860 --> 00:50:19,751
ampak to je povsem v redu.

992
00:50:19,751 --> 00:50:21,000
Vsakdo po skupaj tukaj?

993
00:50:21,000 --> 00:50:24,260
Če je korenina je nična, vrnitev
false saj to pomeni

994
00:50:24,260 --> 00:50:26,850
nimate ničesar, tudi tam.

995
00:50:26,850 --> 00:50:31,376
>> Če koren je n vrednost, tako da, če je
zgodi, da je tista, ki jo gledaš,

996
00:50:31,376 --> 00:50:34,000
potem boš vrnil true
saj veste, da ste jo našli.

997
00:50:34,000 --> 00:50:36,250
Ampak, če je vrednost manjša
od korena n, ste

998
00:50:36,250 --> 00:50:38,332
gre za iskanje levo
otrok ali levo krilo,

999
00:50:38,332 --> 00:50:39,540
karkoli hočeš, da ga pokličete.

1000
00:50:39,540 --> 00:50:41,750
In če je vrednost večja od korena,
boš poiskati pravo drevo,

1001
00:50:41,750 --> 00:50:44,610
potem samo zaženite funkcijo
z iskanjem znova.

1002
00:50:44,610 --> 00:50:48,037
>> In če je korenina null, da je ta
pomeni, ko ste prišli do konca?

1003
00:50:48,037 --> 00:50:50,120
To pomeni, da nimate
več več listov za iskanje,

1004
00:50:50,120 --> 00:50:52,230
potem veste, oh, jaz
Verjetno je ni tukaj

1005
00:50:52,230 --> 00:50:55,063
ker ko sem pogledal skozi
cela stvar in je ni tukaj,

1006
00:50:55,063 --> 00:50:56,930
da le ne bi bilo tukaj.

1007
00:50:56,930 --> 00:50:58,350
>> Ali, da je smiselno, da vse?

1008
00:50:58,350 --> 00:51:03,230
Torej, to je kot binarnem iskanju ohranjanje
Zmogljivosti povezanih seznamov.

1009
00:51:03,230 --> 00:51:09,200
Ohladimo in tako drugi tip
od vas strukture podatkov fantje

1010
00:51:09,200 --> 00:51:13,180
Lahko poskusite izvajanju na vašem pset,
morate le izbrati eno metodo.

1011
00:51:13,180 --> 00:51:19,430
Toda morda alternativna metoda za
hash tabele je tisto, čemur pravimo trie.

1012
00:51:19,430 --> 00:51:24,080
>> Vse je trie je je
posebna vrsta drevesa, ki

1013
00:51:24,080 --> 00:51:28,600
ima vrednote, ki gredo do drugih vrednot.

1014
00:51:28,600 --> 00:51:31,450
Torej, namesto da binarna
drevo v smislu, da je samo eden

1015
00:51:31,450 --> 00:51:35,940
stvar, ki se lahko kaže na dvoje, lahko imate
ena stvar, ki kažejo na mnogo, mnogo stvari.

1016
00:51:35,940 --> 00:51:39,450
Vi v bistvu imajo nize
znotraj katerega shranite

1017
00:51:39,450 --> 00:51:41,790
kazalci, ki kažejo na druge nizi.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Torej vozlišče, kako smo
bi definirati Trie

1020
00:51:49,460 --> 00:51:52,590
se hočemo imeti
Boolean, c beseda, kajne?

1021
00:51:52,590 --> 00:51:54,920
Torej je vozlišče Boolean
kot resnična ali neresnična,

1022
00:51:54,920 --> 00:51:58,490
najprej na čelu
da matrika, je to beseda?

1023
00:51:58,490 --> 00:52:03,620
Drugič, želite imeti kazalce
da karkoli so ostali od njih.

1024
00:52:03,620 --> 00:52:07,470
Le malce zapleteno, malo abstraktno, ampak
Bom razložil, kaj to vse pomeni.

1025
00:52:07,470 --> 00:52:13,800
>> Torej tod na vrhu, če ti
imajo niz razglašena že,

1026
00:52:13,800 --> 00:52:17,040
vozlišče, kjer imate Boolean
Vrednost shranjene na prednjem

1027
00:52:17,040 --> 00:52:19,490
da vam pove, je to beseda?

1028
00:52:19,490 --> 00:52:20,520
Ali to ni beseda?

1029
00:52:20,520 --> 00:52:23,240
In potem imate
preostanek svojega polja, ki

1030
00:52:23,240 --> 00:52:26,040
dejansko shranjuje vse
možnosti, kaj bi lahko bilo.

1031
00:52:26,040 --> 00:52:28,660
Tako, na primer, kot
na vrhu imate

1032
00:52:28,660 --> 00:52:32,140
prva stvar, ki pravi, resnična ali
false, da ali ne, to je beseda.

1033
00:52:32,140 --> 00:52:38,130
>> In potem imate 0 do 26
pisma, ki jih lahko shranite.

1034
00:52:38,130 --> 00:52:42,790
Če bi želel, da tu iskanje
za bat, grem na vrh

1035
00:52:42,790 --> 00:52:49,200
in iščem B. najdem B v moji
matrika, in zato vem, OK, je B beseda?

1036
00:52:49,200 --> 00:52:53,010
B ni beseda, tako da s tem
Moram naprej iskati.

1037
00:52:53,010 --> 00:52:56,410
Grem od B, in gledam na
kazalec, da je B opozarja proti

1038
00:52:56,410 --> 00:53:00,900
in vidim še eno vrsto informacij,
enako strukturo, da smo imeli prej.

1039
00:53:00,900 --> 00:53:05,240
>> In here-- oh, naslednji
pismo, v [neslišno] je A.

1040
00:53:05,240 --> 00:53:07,210
Torej gledamo v tej matriki.

1041
00:53:07,210 --> 00:53:10,860
Najdemo osmo vrednost,
in potem pogledamo, da vidim, oh,

1042
00:53:10,860 --> 00:53:12,840
hej, je, da je beseda, B-A beseda?

1043
00:53:12,840 --> 00:53:13,807
To ni beseda.

1044
00:53:13,807 --> 00:53:14,890
Moramo ohraniti videti.

1045
00:53:14,890 --> 00:53:17,850
>> In tako potem pogledamo, kje
kazalec točk A,

1046
00:53:17,850 --> 00:53:21,130
in kaže na drug način v
ki imamo več vrednost shranjena.

1047
00:53:21,130 --> 00:53:24,150
In na koncu smo prišli do
B-A-T, ki je beseda.

1048
00:53:24,150 --> 00:53:25,970
In tako naslednjič, ko
pogledaš, boš

1049
00:53:25,970 --> 00:53:30,850
so, da je pregled, ja,
to Boolova funkcija je res.

1050
00:53:30,850 --> 00:53:35,450
In tako v tem smislu, da sva nekako
imajo drevo z nizi.

1051
00:53:35,450 --> 00:53:39,890
>> Torej potem lahko nekako iskanje navzdol.

1052
00:53:39,890 --> 00:53:43,650
Namesto razprševanja funkcijo in
pripisovanje vrednosti, ki jih povezani seznam,

1053
00:53:43,650 --> 00:53:49,190
lahko samo izvaja načrt
trie, ki išče downwords.

1054
00:53:49,190 --> 00:53:50,850
Res, res zapleteno stvari.

1055
00:53:50,850 --> 00:53:54,060
Ni enostavno, da razmišljajo o tem, ker sem kot
pljuvanje toliko podatkovne strukture ven

1056
00:53:54,060 --> 00:53:58,710
na vas, vendar ne vse vrste
razumeti, kako logika to deluje?

1057
00:53:58,710 --> 00:54:01,920
>> OK kul.

1058
00:54:01,920 --> 00:54:05,600
Torej B-A-T, in nato
boš iskati.

1059
00:54:05,600 --> 00:54:07,940
Naslednjič, ko boš
da vidim, oh, hej, to je res,

1060
00:54:07,940 --> 00:54:09,273
Tako vem, da to mora biti beseda.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Ista stvar za živalski vrt.

1063
00:54:13,770 --> 00:54:17,960
Torej, tukaj je stvar prav zdaj, če bomo
želel iskati živalskem vrtu, prav zdaj,

1064
00:54:17,960 --> 00:54:20,780
Trenutno zoo ni
Beseda v našem slovarju

1065
00:54:20,780 --> 00:54:25,300
saj, kot lahko vi vidite,
prvo mesto, da imamo Boolean

1066
00:54:25,300 --> 00:54:28,590
return true, je na koncu zoom.

1067
00:54:28,590 --> 00:54:30,430
Imamo Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> In zato je tu, ne bomo dejansko
beseda, živalski vrt, v našem slovarju

1069
00:54:33,900 --> 00:54:36,070
ker je to polje se ne preverja.

1070
00:54:36,070 --> 00:54:39,540
Torej računalnik ne
vemo, da je živalski vrt beseda

1071
00:54:39,540 --> 00:54:42,430
ker je način, ki smo jih
ga shranijo, le zoom tukaj

1072
00:54:42,430 --> 00:54:44,920
dejansko ima logično vrednost
ki je bila obrnil res.

1073
00:54:44,920 --> 00:54:49,380
Torej, če želimo, da vstavite
beseda, zoo, v našem slovarju,

1074
00:54:49,380 --> 00:54:51,770
Kako bi šel o tem?

1075
00:54:51,770 --> 00:54:55,960
Kaj moramo storiti, da poskrbite, da naši
Računalnik ve, da je Z-O-O beseda

1076
00:54:55,960 --> 00:54:58,130
in ne prva beseda je Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> OBČINSTVO: [neslišno]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI PENG: Točno, smo
želite zagotoviti, da ta

1079
00:55:01,450 --> 00:55:07,890
tukaj, da Boolova vrednost
odkljukali, da je res.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, potem bomo, da preveri,
tako da smo točno vedeli, hej, zoo je beseda.

1081
00:55:13,297 --> 00:55:15,380
Bom povedati
računalnik, da je beseda tako

1082
00:55:15,380 --> 00:55:18,000
da ko pregledi računalniške,
ve, da je živalski vrt beseda.

1083
00:55:18,000 --> 00:55:21,269
>> Ker se spomniš vseh teh podatkov
strukture, je zelo enostaven za nas

1084
00:55:21,269 --> 00:55:22,310
reči, oh, bat je beseda.

1085
00:55:22,310 --> 00:55:22,851
Zoo je beseda.

1086
00:55:22,851 --> 00:55:23,611
Zoom je beseda.

1087
00:55:23,611 --> 00:55:25,860
Toda, ko ste ga gradi,
računalnik nima pojma.

1088
00:55:25,860 --> 00:55:28,619
>> Tako da boste morali natančno povedati
v katerem trenutku je to beseda?

1089
00:55:28,619 --> 00:55:29,910
Na kateri točki je ni beseda?

1090
00:55:29,910 --> 00:55:31,784
In na kateri točki storiti I
morali iskati stvari,

1091
00:55:31,784 --> 00:55:34,000
in na kateri točki moram iti naprej?

1092
00:55:34,000 --> 00:55:37,010
Vsakdo jasno, da je?

1093
00:55:37,010 --> 00:55:39,540
Cool.

1094
00:55:39,540 --> 00:55:42,530
>> In tako potem pride
problem, kako bomo

1095
00:55:42,530 --> 00:55:45,560
iti okoli vstavljanje nekaj
da je dejansko ni tam?

1096
00:55:45,560 --> 00:55:49,090
Torej, kaj je pravkar rekel želimo vstaviti
beseda, kopel, v naši trie.

1097
00:55:49,090 --> 00:55:53,589
Kot lahko Vi vidite kot sedaj
vse, kar imamo zdaj, je B-A-T,

1098
00:55:53,589 --> 00:55:55,630
in ta nova struktura podatkov
tam imela vrček, ki

1099
00:55:55,630 --> 00:55:59,740
opozoril na nič, ker smo prevzeti
da, oh, ni besed po B-A-T,

1100
00:55:59,740 --> 00:56:02,530
zakaj moramo ohraniti
ob stvari po tem T.

1101
00:56:02,530 --> 00:56:06,581
>> Ampak problem nastane, če vas bomo storili
želijo imeti besedo, ki prihaja po

1102
00:56:06,581 --> 00:56:07,080
T-jev.

1103
00:56:07,080 --> 00:56:09,500
Če imate kopel, ste
dogaja, da želijo pravico H.

1104
00:56:09,500 --> 00:56:13,290
In tako pot bomo za to, da je
bomo ustvarili ločen vozlišče.

1105
00:56:13,290 --> 00:56:16,840
Nismo dodeli ne glede na količino
pomnilnika za to novo paleto,

1106
00:56:16,840 --> 00:56:20,720
in bomo prerazporedijo kazalce.

1107
00:56:20,720 --> 00:56:22,947
>> Bomo dodelite
H, First of all, to null,

1108
00:56:22,947 --> 00:56:24,030
bomo znebili.

1109
00:56:24,030 --> 00:56:26,590
Bomo imeli
navzdol, se točka H.

1110
00:56:26,590 --> 00:56:30,600
Če vidimo H, smo ga želeli
iti kam drugam.

1111
00:56:30,600 --> 00:56:33,910
>> In tukaj, lahko nato preverite off ja.

1112
00:56:33,910 --> 00:56:38,170
Če bomo zadeli H po T, oh,
potem vemo, da je ta beseda.

1113
00:56:38,170 --> 00:56:41,110
Boolean se bo vrnil res.

1114
00:56:41,110 --> 00:56:42,950
Vsakdo jasno, o tem, kako se je to zgodilo?

1115
00:56:42,950 --> 00:56:45,110
V REDU.

1116
00:56:45,110 --> 00:56:47,214
>> Torej v bistvu vse
Te podatkovne strukture

1117
00:56:47,214 --> 00:56:50,130
da smo šli čez danes, nimam
res, res hitro šli nad njimi

1118
00:56:50,130 --> 00:56:52,192
in ne za veliko
podrobnost, in to je v redu.

1119
00:56:52,192 --> 00:56:53,900
Ko začnete zajebavam
z njo, boste

1120
00:56:53,900 --> 00:56:55,733
sledenja, kjer
vsi kazalci so,

1121
00:56:55,733 --> 00:56:58,060
kaj se dogaja v vašem
podatkovne strukture, et cetera.

1122
00:56:58,060 --> 00:56:59,810
Ti bo zelo koristno,
in to je do vas,

1123
00:56:59,810 --> 00:57:03,890
fantje popolnoma ugotovimo, kako
želite izvajati stvari.

1124
00:57:03,890 --> 00:57:07,650
>> In tako pset4, od 5--, da je oh narobe.

1125
00:57:07,650 --> 00:57:10,140
Pset5 je pravopisne napake.

1126
00:57:10,140 --> 00:57:13,710
Kot sem že prej povedal, da boš, ko
spet prenesete izvorno kodo od nas.

1127
00:57:13,710 --> 00:57:16,210
Tam se dogaja, da so tri glavne
Stvari boste prenesli.

1128
00:57:16,210 --> 00:57:18,470
Boste prenos slovarjev,
lenih in besedil.

1129
00:57:18,470 --> 00:57:21,660
>> Vse te stvari so se
bodisi slovarji besed

1130
00:57:21,660 --> 00:57:25,190
da želimo, da preverite
ali testiranje informacij

1131
00:57:25,190 --> 00:57:26,930
da želimo, da preverjanje črkovanja.

1132
00:57:26,930 --> 00:57:29,670
In tako slovarji
smo vam gredo

1133
00:57:29,670 --> 00:57:34,870
da vam dejanske besede, ki jih želimo
da si nekako shranite na način, ki je

1134
00:57:34,870 --> 00:57:36,530
bolj učinkovita kot array.

1135
00:57:36,530 --> 00:57:38,470
In potem besedila so
bo tisto, kar smo

1136
00:57:38,470 --> 00:57:43,900
vas prosim, da natančno preverite,
vse besede so resnične besede.

1137
00:57:43,900 --> 00:57:47,970
>> In tako so trije bloki
programi, ki vam bomo dajejo

1138
00:57:47,970 --> 00:57:51,130
se imenujejo dictionary.c,
dictionary.h in speller.c.

1139
00:57:51,130 --> 00:57:56,500
In tako vse dictionary.c pa je
kaj ste morali izvajati.

1140
00:57:56,500 --> 00:57:57,880
To obilje besed.

1141
00:57:57,880 --> 00:58:02,000
To črkovati ček njih, in omogoča, da
da vse, kar je pravilno vstavljen.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h je le knjižnica datoteka
da izjavlja, vse te funkcije.

1143
00:58:05,180 --> 00:58:07,650
In speller.c, bomo, da vam.

1144
00:58:07,650 --> 00:58:09,290
Vam ni treba spremeniti katerega od njega.

1145
00:58:09,290 --> 00:58:14,290
Vse speller.c pa je vzel,
obremenitve je, nadzira hitrost njej,

1146
00:58:14,290 --> 00:58:19,190
testi merilo všeč, kako
hitro ste sposobni narediti stvari.

1147
00:58:19,190 --> 00:58:20,410
>> To je Speller.

1148
00:58:20,410 --> 00:58:23,920
Samo ne igraš z njim, vendar se
prepričani, da boste razumeli, kaj to počne.

1149
00:58:23,920 --> 00:58:28,090
Mi uporabljamo funkcijo imenovano getrusage da
testira učinkovitost vašega urok

1150
00:58:28,090 --> 00:58:28,590
skladiščnik.

1151
00:58:28,590 --> 00:58:32,200
Vse to pa je v bistvu preskusu z
Čas vsega v vašem slovarju,

1152
00:58:32,200 --> 00:58:33,680
zato poskrbite, da boste razumeli.

1153
00:58:33,680 --> 00:58:36,660
Bodite previdni, da se ne igraš z njim, ali
drugje stvari ne bo deloval pravilno.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> In večino tega izziva je za
vidva res spremeniti dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Bomo, da vam
140.000 besed v slovarju.

1157
00:58:48,526 --> 00:58:50,900
Bomo, da vam tekst
datoteka, ki ima te besede,

1158
00:58:50,900 --> 00:58:54,840
in želimo si, da bi lahko organizirali
jim v hash tabele ali trie

1159
00:58:54,840 --> 00:58:58,140
ker ko smo vas prosimo, da urok
check-- zamisliti, če ste urok

1160
00:58:58,140 --> 00:59:00,690
preverjanje, kot Homerjeve Odiseje.

1161
00:59:00,690 --> 00:59:03,010
To je kot ta velik, velik test.

1162
00:59:03,010 --> 00:59:05,190
>> Predstavljajte si, če vsak
beseda, ki jo je moral pogledati

1163
00:59:05,190 --> 00:59:08,100
skozi paleto 140.000 vrednot.

1164
00:59:08,100 --> 00:59:10,350
To bi trajalo celo večnost
za vaš stroj teči.

1165
00:59:10,350 --> 00:59:14,490
To je razlog, zakaj želimo organizirali
Podatki v bolj učinkovitih podatkovnih struktur

1166
00:59:14,490 --> 00:59:17,270
kot je hash tabele ali trie.

1167
00:59:17,270 --> 00:59:20,700
In potem vidva lahko nekako
kdaj iščete dostop

1168
00:59:20,700 --> 00:59:22,570
stvari lažje in hitreje.

1169
00:59:22,570 --> 00:59:24,934
>> In zato bodite previdni, da se odpravite trčenja.

1170
00:59:24,934 --> 00:59:27,350
Boš dobil kup
od besed, ki se začnejo z A.

1171
00:59:27,350 --> 00:59:29,957
Boš dobil kup besed
ki se začnejo z B. Do vas

1172
00:59:29,957 --> 00:59:31,290
Fantje, kako želite, da ga rešiti.

1173
00:59:31,290 --> 00:59:34,144
Morda je še več
učinkovite funkcije razpršitve

1174
00:59:34,144 --> 00:59:36,810
kot samo prvo črko
nekaj, in da je do vas

1175
00:59:36,810 --> 00:59:38,190
fantje nekako storiti karkoli hočeš.

1176
00:59:38,190 --> 00:59:40,148
>> Morda želite dodati
vse črke skupaj.

1177
00:59:40,148 --> 00:59:43,410
Morda boste želeli, da je všeč delati čudne stvari
da se upošteva število črk,

1178
00:59:43,410 --> 00:59:43,970
karkoli.

1179
00:59:43,970 --> 00:59:45,386
Do vaju kaj želite storiti.

1180
00:59:45,386 --> 00:59:49,262
Če želite narediti hash tabelo, če vas
želeli poskusiti Trie, povsem odvisno od vas.

1181
00:59:49,262 --> 00:59:52,470
Jaz vas bo opozoril pred časom, da je
trie je običajno nekoliko težje

1182
00:59:52,470 --> 00:59:54,520
samo zato, ker tam je veliko
več kazalci slediti.

1183
00:59:54,520 --> 00:59:55,645
Ampak popolnoma do vas.

1184
00:59:55,645 --> 00:59:58,742
To je veliko bolj učinkovito
v večini primerov.

1185
00:59:58,742 --> 01:00:01,450
Hočeš, da res lahko obdržali
Spremljajte vse vaše napotke.

1186
01:00:01,450 --> 01:00:03,850
Tako kot to isto stvar
da sem delal tu.

1187
01:00:03,850 --> 01:00:06,871
Ko poskušate vstaviti
Vrednosti v hash tabele ali izbrisati,

1188
01:00:06,871 --> 01:00:08,620
se prepričajte, da ste
Res sledenja

1189
01:00:08,620 --> 01:00:11,860
kje je vse, ker
to je res enostavno, če sem

1190
01:00:11,860 --> 01:00:14,727
poskušajo vriniti kot besede, Andy.

1191
01:00:14,727 --> 01:00:16,810
Naj samo povem, da je to
resnična beseda, beseda, andy,

1192
01:00:16,810 --> 01:00:19,640
v ogromen seznam A besed.

1193
01:00:19,640 --> 01:00:22,450
>> Če sem slučajno prerazporedijo
kazalec narobe, oops,

1194
01:00:22,450 --> 01:00:24,940
tam gre celoto
preostanek mojega povezani seznam.

1195
01:00:24,940 --> 01:00:26,897
Zdaj je edina beseda, I
imeti, je andy, in zdaj

1196
01:00:26,897 --> 01:00:29,230
vseh ostalih besed v
slovar je izgubila.

1197
01:00:29,230 --> 01:00:31,370
In tako želite poskrbite, da boste
slediti vse vaše napotke

1198
01:00:31,370 --> 01:00:33,661
ali pa boš dobil
velike težave v kodi.

1199
01:00:33,661 --> 01:00:35,840
Draw stvari previdno, korak za korakom.

1200
01:00:35,840 --> 01:00:37,870
To omogoča veliko lažje razmišljati.

1201
01:00:37,870 --> 01:00:40,910
>> In nenazadnje, želite, da bi lahko
preizkusite svoje delovanje vašega programa

1202
01:00:40,910 --> 01:00:41,618
na veliki plošči.

1203
01:00:41,618 --> 01:00:43,710
Če vidva traja
poglej CS50 prav zdaj,

1204
01:00:43,710 --> 01:00:45,210
imamo, kar se imenuje veliki svet.

1205
01:00:45,210 --> 01:00:50,200
To je ocena stanja najhitreje
črkovalnik krat čez vse CS50

1206
01:00:50,200 --> 01:00:55,720
zdaj, mislim, da je vrh 10
krat Mislim, osem od njih so zaposleni.

1207
01:00:55,720 --> 01:00:57,960
Res želimo vama, da nas premagati.

1208
01:00:57,960 --> 01:01:00,870
>> Vse nas so poskušali izvesti
najhitrejši kodo, kot je mogoče.

1209
01:01:00,870 --> 01:01:04,880
Želimo vama, da bi poskušali izzvati
nas in izvajati hitreje od vseh nas

1210
01:01:04,880 --> 01:01:05,550
lahko.

1211
01:01:05,550 --> 01:01:07,970
In zato je to res
prvič, da smo

1212
01:01:07,970 --> 01:01:12,680
vas prosi fantje narediti pset da
lahko res v kakršni koli metodo

1213
01:01:12,680 --> 01:01:13,760
ti hočeš.

1214
01:01:13,760 --> 01:01:17,730
>> Vedno pravim, da je to bolj podobno
k rešitvi resničnega življenja, kajne?

1215
01:01:17,730 --> 01:01:19,550
Sem rekel, hej, moraš to storiti.

1216
01:01:19,550 --> 01:01:21,380
Zgradite program, ki počne to za mene.

1217
01:01:21,380 --> 01:01:22,630
Ali jo pa hočeš.

1218
01:01:22,630 --> 01:01:24,271
Jaz samo vem, da želim na hitro.

1219
01:01:24,271 --> 01:01:25,770
To je vaš izziv za ta teden.

1220
01:01:25,770 --> 01:01:27,531
Vi fantje, gremo
da vam nalogo.

1221
01:01:27,531 --> 01:01:29,030
Bomo, da vam izziv.

1222
01:01:29,030 --> 01:01:31,559
In potem je do vaju
popolnoma samo ugotovimo,

1223
01:01:31,559 --> 01:01:34,100
kaj je najhitrejši in najbolj
učinkovit način za izvedbo tega.

1224
01:01:34,100 --> 01:01:34,600
Ja?

1225
01:01:34,600 --> 01:01:37,476
>> OBČINSTVO: Ali smo dovolili, da če
želel raziskovati hitrejše načine

1226
01:01:37,476 --> 01:01:40,821
narediti hash tabele na spletu, lahko storimo
da, in navajajo številko nekoga drugega?

1227
01:01:40,821 --> 01:01:42,070
ANDI PENG: Ja, popolnoma v redu.

1228
01:01:42,070 --> 01:01:44,320
Torej, če vi prebrati
spec, tam je linija

1229
01:01:44,320 --> 01:01:48,310
v spec, ki pravi, da fantje
so popolnoma brezplačno za raziskave hash

1230
01:01:48,310 --> 01:01:51,070
Funkcije o tem, kaj so nekateri
od hitrejše hash funkcij

1231
01:01:51,070 --> 01:01:54,720
teči stvari skozi kot
Dokler si citirati to kodo.

1232
01:01:54,720 --> 01:01:57,220
Torej imajo nekateri ljudje že
pogruntal hitre načine

1233
01:01:57,220 --> 01:02:00,250
početje črkovalniki, hitrega
načini shranjevanja podatkov.

1234
01:02:00,250 --> 01:02:02,750
Popolnoma odvisno od vas, fantje, če vas
želijo vzemite, kajne?

1235
01:02:02,750 --> 01:02:04,045
Prepričajte se, da ste navajanja.

1236
01:02:04,045 --> 01:02:06,170
Izziv tu res
da smo poskušali preizkusiti

1237
01:02:06,170 --> 01:02:09,750
je zagotoviti, da veste
svojo pot okoli kazalca.

1238
01:02:09,750 --> 01:02:12,700
Kolikor izvajanje
dejanska funkcija hash

1239
01:02:12,700 --> 01:02:15,070
in prihaja do podobnih
matematika za to,

1240
01:02:15,070 --> 01:02:17,570
vidva lahko raziskave karkoli
Načini spletu hočete.

1241
01:02:17,570 --> 01:02:17,996
Ja?

1242
01:02:17,996 --> 01:02:19,700
>> OBČINSTVO: Lahko navedemo samo
s pomočjo [neslišno]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI PENG: Ja.

1244
01:02:20,120 --> 01:02:22,328
Lahko samo v svoj komentar,
lahko navedemo, kot so, oh,

1245
01:02:22,328 --> 01:02:26,127
vzeta iz bla, bla,
bla, razpršilna funkcija.

1246
01:02:26,127 --> 01:02:27,210
Kdo še kakšna vprašanja?

1247
01:02:27,210 --> 01:02:29,694
Mi dejansko breezed
skozi odsek danes.

1248
01:02:29,694 --> 01:02:31,610
Bom tukaj do
odgovoriti na vprašanja, kot dobro.

1249
01:02:31,610 --> 01:02:36,570
>> Prav tako, kot sem rekel, za pisarne
ure nocoj in jutri.

1250
01:02:36,570 --> 01:02:40,307
Spec ta teden, je dejansko
super enostavno in zelo kratko, da se glasi.

1251
01:02:40,307 --> 01:02:43,140
Jaz bi predlagal ob poglej, samo
prebrati skozi celoto njo.

1252
01:02:43,140 --> 01:02:45,730
>> In Zamyla dejansko vas popelje
skozi vsako izmed funkcij

1253
01:02:45,730 --> 01:02:49,796
morate izvesti, in zato je
zelo, zelo jasno, kako narediti vse.

1254
01:02:49,796 --> 01:02:51,920
Samo se prepričajte, da ste
sledenja kazalcev.

1255
01:02:51,920 --> 01:02:53,650
To je zelo zahtevna pset.

1256
01:02:53,650 --> 01:02:56,744
>> To ni zahtevna, saj, kot so,
oh, koncepti so toliko bolj

1257
01:02:56,744 --> 01:02:59,160
težko, ali pa boste morali naučiti
toliko novih sintaksa pot

1258
01:02:59,160 --> 01:03:00,650
da si naredil za zadnje pset.

1259
01:03:00,650 --> 01:03:03,320
To pset je težko, ker
obstaja toliko kazalci,

1260
01:03:03,320 --> 01:03:06,980
in potem je to zelo, zelo enostaven za enkrat
imate napako v kodi ne bi mogli

1261
01:03:06,980 --> 01:03:08,315
najti, če je to bug.

1262
01:03:08,315 --> 01:03:13,200
>> In tako popolna in popolna vera v vas
fantje, da bi lahko premagal našo [neslišno]

1263
01:03:13,200 --> 01:03:13,700
člankih.

1264
01:03:13,700 --> 01:03:16,640
Pravzaprav nimam nobenega pisnega rudnik
še, ampak sem pisati mine.

1265
01:03:16,640 --> 01:03:19,070
Torej, medtem ko pišete
tvoja, bom pisal rudnik.

1266
01:03:19,070 --> 01:03:21,070
Bom poskusil, da bi
mine hitreje kot tvoje.

1267
01:03:21,070 --> 01:03:23,940
Bomo videli, kdo ima najhitrejši enega.

1268
01:03:23,940 --> 01:03:27,340
>> In ja, bom videl vse
vidva tukaj v torek.

1269
01:03:27,340 --> 01:03:29,510
Bom teči nekakšno podobnega delavnici pset.

1270
01:03:29,510 --> 01:03:32,640
Vse to odsekov
teden so pset delavnice,

1271
01:03:32,640 --> 01:03:36,690
tako da fantje imeli veliko priložnosti
za pomoč, uradne ure kot vedno,

1272
01:03:36,690 --> 01:03:41,330
in res se veselim
branje vseh kodo fantje.

1273
01:03:41,330 --> 01:03:44,160
Imam kvizi tukaj, če vas gor
fantje želijo, da pride tistim.

1274
01:03:44,160 --> 01:03:45,880
To je vse.

1275
01:03:45,880 --> 01:03:48,180