1
00:00:00,000 --> 00:00:03,423
>> [Glazbom]

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

3
00:00:05,380 --> 00:00:08,210
>> ANDI PENG: Dobrodošli u tjednu 6. poglavlju.

4
00:00:08,210 --> 00:00:11,620
Odstupili smo od našeg standarda
Odjeljak vrijeme utorak

5
00:00:11,620 --> 00:00:14,130
Poslijepodne na ovu lijepu nedjelju ujutro.

6
00:00:14,130 --> 00:00:17,330
Hvala vam svima koji
mi se pridružio i danas, ali ozbiljno,

7
00:00:17,330 --> 00:00:18,170
okrugli pljesak.

8
00:00:18,170 --> 00:00:20,600
>> To je prilično velika truda.

9
00:00:20,600 --> 00:00:23,600
Ja gotovo da nije ni to napraviti
na vrijeme, ali to je u redu.

10
00:00:23,600 --> 00:00:27,520
Dakle, znam da svi vi
Upravo to je napravio na kvizu.

11
00:00:27,520 --> 00:00:30,370
Prije svega, dobrodošli na
Druga strana toga.

12
00:00:30,370 --> 00:00:32,917
>> Drugo, mi ćemo govoriti o tome.

13
00:00:32,917 --> 00:00:34,000
Razgovarat ćemo o kvizu.

14
00:00:34,000 --> 00:00:35,700
Razgovarat ćemo o tome
radite u razredu.

15
00:00:35,700 --> 00:00:36,550
Vi ćete biti u redu.

16
00:00:36,550 --> 00:00:39,080
Imam svoje kvizova za
što na kraju ovdje

17
00:00:39,080 --> 00:00:42,120
pa ako ti dečki žele uzeti
pogledajte ga, potpuno u redu.

18
00:00:42,120 --> 00:00:46,590
>> Tako brzo prije nego što počnemo je
program za danas je kako slijedi.

19
00:00:46,590 --> 00:00:48,430
Kao što možete vidjeti, mi smo
osnovi brzo plamena

20
00:00:48,430 --> 00:00:52,120
kroz cijelu hrpa strukture podataka
jako, jako, jako brzo.

21
00:00:52,120 --> 00:00:54,380
Dakle, kao takva, ona neće biti
super interaktivne danas.

22
00:00:54,380 --> 00:00:59,620
To ću biti ja vrsta vikanje
stvari koje, i ako sam vas zbuniti,

23
00:00:59,620 --> 00:01:02,680
ako idem prebrzo, javite mi.

24
00:01:02,680 --> 00:01:05,200
Oni su samo različite podatke
strukture, a kao dio

25
00:01:05,200 --> 00:01:07,070
Vaše pset za to
nadolazeći tjedan, vi ćete

26
00:01:07,070 --> 00:01:10,340
biti zatraženo da provede jedan od njih,
možda dva them-- dvije od njih

27
00:01:10,340 --> 00:01:12,319
u svom pset.

28
00:01:12,319 --> 00:01:14,610
U redu, tako da sam samo ću
početi s nekim najavama.

29
00:01:14,610 --> 00:01:19,070
Mi ćemo ići preko dimnjaka i redovima više u
Dubina od onoga što smo učinili prije kvizu.

30
00:01:19,070 --> 00:01:20,990
Mi ćemo ići preko povezan
popis opet, još jednom,

31
00:01:20,990 --> 00:01:23,899
više u dubinu nego što
smo imali prije kvizu.

32
00:01:23,899 --> 00:01:26,440
A onda ćemo razgovarati o hash
stolovi, drveće i napad, koji se

33
00:01:26,440 --> 00:01:28,890
su svi prilično je potrebno za vaš pset.

34
00:01:28,890 --> 00:01:32,925
A onda ćemo ići preko neke
korisne savjete za pset5.

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

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

37
00:01:41,090 --> 00:01:45,370
To je bio vrlo nizak, pa vi svi
učinio jako, jako dobro u skladu

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

39
00:01:46,510 --> 00:01:49,970
>> Prilično mnogo, pravilo je, ako ste
unutar standardnog odstupanja od srednje vrijednosti

40
00:01:49,970 --> 00:01:52,990
pogotovo jer smo u manje
udoban poglavlje, ti si potpuno u redu.

41
00:01:52,990 --> 00:01:54,120
Vi ste na pravom putu.

42
00:01:54,120 --> 00:01:55,190
Život je dobar.

43
00:01:55,190 --> 00:01:58,952
>> Znam da je to zastrašujuće misliti da
Dobio sam kao 40% na ovom kvizu.

44
00:01:58,952 --> 00:02:00,160
Idem uspjeti ovaj razred.

45
00:02:00,160 --> 00:02:02,243
Obećavam ti, ti nisi
neće uspjeti razred.

46
00:02:02,243 --> 00:02:03,680
Ti si potpuno u redu.

47
00:02:03,680 --> 00:02:06,850
>> Za one od vas koji je dobio više
srednja, impresivna, impresivno,

48
00:02:06,850 --> 00:02:08,780
kao, ozbiljno i učinio.

49
00:02:08,780 --> 00:02:09,689
Ja ih imati sa mnom.

50
00:02:09,689 --> 00:02:11,730
Dodite ih dobiti
na kraju sekcije.

51
00:02:11,730 --> 00:02:14,520
Pustiti mene znati ako imate bilo
pitanja, pitanja s njima.

52
00:02:14,520 --> 00:02:17,204
Zbrojimo li vaš rezultat
krivo, javite nam.

53
00:02:17,204 --> 00:02:21,240
>> U redu, tako da pset5, ovo je stvarno
čudno tjedan za Yale u smislu

54
00:02:21,240 --> 00:02:24,240
da je naš pset je zbog
Srijeda u podne, uključujući

55
00:02:24,240 --> 00:02:27,317
pokojni dan, tako da je zapravo
teoretski zbog utorak u podne.

56
00:02:27,317 --> 00:02:29,150
Vjerojatno nitko nije završen
u utorak u podne.

57
00:02:29,150 --> 00:02:30,830
To je sasvim u redu.

58
00:02:30,830 --> 00:02:33,700
Mi ćemo imati radno vrijeme
Večeras, kao i ponedjeljak navečer.

59
00:02:33,700 --> 00:02:36,810
A sve dijelove ovog tjedna će
zapravo se pretvorio u radionicama,

60
00:02:36,810 --> 00:02:38,800
pa slobodno ubacite
bilo poglavlje želite,

61
00:02:38,800 --> 00:02:42,810
i oni će biti neka vrsta mini-pset
radionice za pomoć na to.

62
00:02:42,810 --> 00:02:45,620
Dakle, kao takav, to je jedini odjeljak
gdje smo gradivo.

63
00:02:45,620 --> 00:02:49,220
Svi ostali dijelovi će se usredotočiti
isključivo na pomoć za pset.

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

65
00:02:50,146 --> 00:02:52,000
>> PUBLIKA: Gdje su uredski vrijeme?

66
00:02:52,000 --> 00:02:56,120
>> ANDI PENG: Radno vrijeme
tonight-- oh, dobro pitanje.

67
00:02:56,120 --> 00:03:00,580
Mislim uredski večeras vrijeme
u Teal ili Commons.

68
00:03:00,580 --> 00:03:02,984
Ako ste provjerili online CS50
i idete na uredovno vrijeme,

69
00:03:02,984 --> 00:03:05,650
tamo bi trebao biti raspored koji
govori gdje su svi od njih su.

70
00:03:05,650 --> 00:03:07,954
>> Znam, bilo večeras
ili sutra je Teal,

71
00:03:07,954 --> 00:03:10,120
i mislim da možemo imati
zajednička za druge noći.

72
00:03:10,120 --> 00:03:11,020
Nisam siguran.

73
00:03:11,020 --> 00:03:11,700
Dobro pitanje.

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

75
00:03:14,430 --> 00:03:18,780
>> Cool, bilo kakvih pitanja u vezi s
raspored za sljedeća tri dana kao što je?

76
00:03:18,780 --> 00:03:21,690
Obećavam vam dečki poput Davida
rekao, ovo je vrh brda.

77
00:03:21,690 --> 00:03:23,050
Vi ste gotovo tamo.

78
00:03:23,050 --> 00:03:24,644
Samo još tri dana.

79
00:03:24,644 --> 00:03:26,310
Doći, a onda ćemo svi doći.

80
00:03:26,310 --> 00:03:28,114
Mi ćemo imati lijepo CS-slobodan pauzu.

81
00:03:28,114 --> 00:03:28,780
Dobrodosao natrag.

82
00:03:28,780 --> 00:03:30,779
Mi ćemo zaroniti u web
programiranje i razvoj,

83
00:03:30,779 --> 00:03:35,150
stvari koje su vrlo zabavna odnosu
na neke druge psets.

84
00:03:35,150 --> 00:03:37,974
I to će biti hladan, a
ćemo imati puno zabave.

85
00:03:37,974 --> 00:03:38,890
Imat ćemo više slatkiša.

86
00:03:38,890 --> 00:03:39,730
Žao nam je zbog slatkiša.

87
00:03:39,730 --> 00:03:40,945
Zaboravio sam slatkiše.

88
00:03:40,945 --> 00:03:43,310
Bilo je grubo jutro.

89
00:03:43,310 --> 00:03:46,340
Dakle, vi ste gotovo tamo,
i ja sam jako ponosna na vas momci.

90
00:03:46,340 --> 00:03:49,570
>> U redu, tako da gomila.

91
00:03:49,570 --> 00:03:53,331
Tko je ljubio pitanje o Jacku
i njegova odjeća na kvizu?

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

93
00:03:53,830 --> 00:03:56,500
U redu, to je u redu.

94
00:03:56,500 --> 00:04:00,200
>> Dakle, u biti kao što možete
slika Jack, ovaj tip ovdje,

95
00:04:00,200 --> 00:04:03,350
voli uzeti odjeću
iz vrha dimnjaka,

96
00:04:03,350 --> 00:04:05,750
i on ga stavlja natrag na
stog nakon što je učinio.

97
00:04:05,750 --> 00:04:07,600
Dakle, na ovaj način, on nikada
Čini se da je dobivanje

98
00:04:07,600 --> 00:04:10,090
na dnu od
stog u svojoj odjeći.

99
00:04:10,090 --> 00:04:12,600
Dakle, ova vrsta opisuje
osnovna struktura podataka

100
00:04:12,600 --> 00:04:16,610
kako stog se provodi.

101
00:04:16,610 --> 00:04:20,060
>> U biti, misliti na
stog kao bilo stog objekata

102
00:04:20,060 --> 00:04:24,900
gdje staviti stvari na vrhu, a
onda ih pop iz vrha.

103
00:04:24,900 --> 00:04:28,600
Dakle, LIFO je akronim volimo
da use-- posljednji u, prvi van.

104
00:04:28,600 --> 00:04:32,480
I tako trajati se na vrhu
stog je prvi onaj koji izlazi.

105
00:04:32,480 --> 00:04:34,260
I tako su dva pojma
smo željeli povezati

106
00:04:34,260 --> 00:04:36,190
s koje se zove guranje i pop.

107
00:04:36,190 --> 00:04:39,790
Kada gurnuti nešto na
stog, a ti ga pop natrag gore.

108
00:04:39,790 --> 00:04:43,422
>> I tako mislim da je ovo neka vrsta
apstraktan pojam za one od vas

109
00:04:43,422 --> 00:04:45,630
koji žele vidjeti se poput
stvarna provedba ovog

110
00:04:45,630 --> 00:04:46,740
u stvarnom svijetu.

111
00:04:46,740 --> 00:04:50,170
Koliko ste napisali esej
možda kao sat prije nego što je zbog,

112
00:04:50,170 --> 00:04:54,510
a ti slučajno izbrisane ogromna
komad od toga, kao što je slučajno?

113
00:04:54,510 --> 00:04:58,560
I što onda učiniti upravljač
koristimo ga vratiti?

114
00:04:58,560 --> 00:05:00,030
Kontrola-Z, zar ne?

115
00:05:00,030 --> 00:05:03,640
Kontrola-Z, tako da je količina vremena
da Control-Z je spasio moj život,

116
00:05:03,640 --> 00:05:08,820
je spasio moju guzicu, svaki put
koji je proveden kroz dimnjak.

117
00:05:08,820 --> 00:05:13,020
>> U suštini sve informacije
to je na svom Word dokument,

118
00:05:13,020 --> 00:05:15,080
to dobiva gurnuti i skinuti po volji.

119
00:05:15,080 --> 00:05:19,460
I tako u biti, kad god vas
izbrisati sve, što ga pop natrag gore.

120
00:05:19,460 --> 00:05:22,820
A onda, ako vam je potrebna leđa, te
gurnuti ga, što je ono što Control-C radi.

121
00:05:22,820 --> 00:05:26,770
I tako u stvarnom svijetu funkcija
koliko jednostavne strukture podataka

122
00:05:26,770 --> 00:05:28,690
može pomoći u svakodnevnom životu.

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

124
00:05:31,710 --> 00:05:40,150
>> Tako struct je način na koji
mi zapravo stvoriti hrpu.

125
00:05:40,150 --> 00:05:44,720
Mi upišite definirati struct, a zatim
zovemo ga stog na dnu.

126
00:05:44,720 --> 00:05:47,440
A unutar dimnjaka,
imamo dva parametra

127
00:05:47,440 --> 00:05:51,580
da smo u biti može manipulirati,
tako da imamo char kapacitet žice zvijezda.

128
00:05:51,580 --> 00:05:55,150
>> Sve što se radi
stvara niz

129
00:05:55,150 --> 00:05:58,835
da možemo pohraniti što god želite
koje možemo odrediti svoj kapacitet.

130
00:05:58,835 --> 00:06:01,990
Kapacitet je samo max iznos
Stavke možemo staviti u ovaj niz.

131
00:06:01,990 --> 00:06:05,660
Veličina int je brojač koji čuva
pjesma o tome kako mnoge stvari trenutno

132
00:06:05,660 --> 00:06:07,850
u snopu.

133
00:06:07,850 --> 00:06:11,860
Pa onda možemo pratiti, A,
i koliko je velika stvarna stog,

134
00:06:11,860 --> 00:06:14,850
a, B, koliko to stog
ispunjen smo jer ne želimo

135
00:06:14,850 --> 00:06:18,800
da se prelijevati preko onoga što je naš kapacitet je.

136
00:06:18,800 --> 00:06:24,340
>> Tako, na primjer, ovu lijepu
Pitanje je bilo na svom kvizu.

137
00:06:24,340 --> 00:06:28,160
U biti kako ćemo gurnuti
na vrhu dimnjaka.

138
00:06:28,160 --> 00:06:28,830
Prilično jednostavan.

139
00:06:28,830 --> 00:06:30,621
Ako na to gledate,
ćemo provesti kroz to.

140
00:06:30,621 --> 00:06:32,640
Ako [nečujan] size--
zapamtite, kad god

141
00:06:32,640 --> 00:06:35,300
želite pristupiti bilo
parametar unutar STRUCT,

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

143
00:06:40,320 --> 00:06:42,720
>> U tom slučaju, s je
naziv naše stog.

144
00:06:42,720 --> 00:06:46,230
Želimo pristupiti veličinu
od toga, pa mi s.size.

145
00:06:46,230 --> 00:06:50,280
Tako dugo dok je veličina nije
jednak kapacitet ili dok

146
00:06:50,280 --> 00:06:52,940
što je manje od kapaciteta,
bilo bi raditi ovdje.

147
00:06:52,940 --> 00:06:57,180
>> Želite pristupiti iznutra
Vaše stog, tako s.strings,

148
00:06:57,180 --> 00:07:00,790
i ti ćeš staviti da novi broj
koje želite umetnuti u tamo.

149
00:07:00,790 --> 00:07:05,030
Recimo samo da će htjeti
umetnite int n na stog,

150
00:07:05,030 --> 00:07:08,905
smo mogli učiniti s.strings,
zagrade, s.size jednak n.

151
00:07:08,905 --> 00:07:11,030
Budući da je veličina gdje smo
Trenutno u snopu

152
00:07:11,030 --> 00:07:14,590
ako ćemo gurati
što dalje, samo mi pristupiti

153
00:07:14,590 --> 00:07:17,370
gdje god je veličina je
trenutna punina stog,

154
00:07:17,370 --> 00:07:21,729
a mi gurnuti int n na njega.

155
00:07:21,729 --> 00:07:24,770
A onda želimo biti sigurni da
Mi smo također povećavati veličinu n,

156
00:07:24,770 --> 00:07:27,436
tako da možemo pratiti imamo
dodaje dodatni stvar na stog.

157
00:07:27,436 --> 00:07:29,660
Sada imamo veću veličinu.

158
00:07:29,660 --> 00:07:33,196
Je li ovo ovdje smisla
svatko, koliko je logično to radi?

159
00:07:33,196 --> 00:07:34,160
To je vrsta brzo.

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

161
00:07:39,535 --> 00:07:42,160
PUBLIKA: Možete li ići preko
su s.stringss.strings [s.size] opet?

162
00:07:42,160 --> 00:07:45,808
ANDI PENG: Naravno, tako što se
s.size trenutno nam dati?

163
00:07:45,808 --> 00:07:47,440
PUBLIKA: To je trenutna veličina.

164
00:07:47,440 --> 00:07:50,890
ANDI PENG: Točno, tako da je
Trenutni indeks da je naša veličina je u,

165
00:07:50,890 --> 00:07:57,780
pa želimo staviti novi cijeli broj
da želimo umetnuti u s.size.

166
00:07:57,780 --> 00:07:58,760
Ima li to smisla?

167
00:07:58,760 --> 00:08:01,110
Jer s.strings, sve što
je naziv polja.

168
00:08:01,110 --> 00:08:03,510
Sve to je pristup
Niz unutar naše STRUCT,

169
00:08:03,510 --> 00:08:06,030
pa ako želimo
stavite n u tom indeksu,

170
00:08:06,030 --> 00:08:09,651
mi samo može pristupiti
koriste zagrade 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
>> U redu, pop, to pseudokod sam
za vas momci, ali sličan koncept.

174
00:08:18,916 --> 00:08:19,790
Ima li to smisla?

175
00:08:19,790 --> 00:08:22,310
Ako je veličina veća
od nule, onda ste

176
00:08:22,310 --> 00:08:25,350
znam da želiš da se nešto
, jer ako se veličina nije

177
00:08:25,350 --> 00:08:27,620
veći od nule, onda ste
nemam ništa u dimnjaku.

178
00:08:27,620 --> 00:08:29,840
>> Dakle, želite samo izvršiti
ovaj kod, to može samo

179
00:08:29,840 --> 00:08:32,320
pop, ako postoji nešto za pop.

180
00:08:32,320 --> 00:08:35,830
Dakle, ako je veličina veća
od 0, što minus veličina.

181
00:08:35,830 --> 00:08:40,020
Dekrementirati smo veličinu, a zatim se vratiti
ono što je u njoj, jer

182
00:08:40,020 --> 00:08:42,710
iskakanje, želimo
Pristup god je pohranjena

183
00:08:42,710 --> 00:08:45,694
indeksa na vrhu dimnjaka.

184
00:08:45,694 --> 00:08:46,610
Sve smisla?

185
00:08:46,610 --> 00:08:49,693
Ako sam ti dečki napisati ovo,
bi ti dečki biti u mogućnosti to napisati?

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

187
00:08:52,029 --> 00:08:53,570
U redu, vi možete poigrati s njom.

188
00:08:53,570 --> 00:08:55,252
Bez brige, ako ga ne dobijete.

189
00:08:55,252 --> 00:08:57,460
Nemamo vremena za kodiranje
to se i danas, jer imamo

190
00:08:57,460 --> 00:08:59,959
ima puno tih struktura
proći, ali u suštini

191
00:08:59,959 --> 00:09:02,214
pseudokod, vrlo, vrlo slične gurnuti.

192
00:09:02,214 --> 00:09:03,380
Samo slijedite duž logike.

193
00:09:03,380 --> 00:09:06,092
Provjerite jeste li pristupate sve
značajke vašeg STRUCT ispravno.

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

195
00:09:06,574 --> 00:09:09,282
>> PUBLIKA: Hoće li ove slajdove i
ova cijela stvar bude još danas-ish?

196
00:09:09,282 --> 00:09:11,586
ANDI PENG: Uvijek, Yep.

197
00:09:11,586 --> 00:09:13,710
Ja ću pokušati staviti
ovo gore kao sat poslije.

198
00:09:13,710 --> 00:09:16,626
Ja ću e-mail Davida, David će pokušati
stavite ga kao sat nakon toga.

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

200
00:09:20,040 --> 00:09:25,470
>> OK, onda smo preseliti u taj drugi
Lijep struktura podataka se zove red.

201
00:09:25,470 --> 00:09:30,140
Kako vi vidite tu,
red, za Britance među nama,

202
00:09:30,140 --> 00:09:32,010
sve je to je linija.

203
00:09:32,010 --> 00:09:34,680
Dakle, suprotno onome što
mislite stog je,

204
00:09:34,680 --> 00:09:37,750
red je upravo ono što
logično mislite da je.

205
00:09:37,750 --> 00:09:41,914
To je održana po pravilima FIFO,
koji je prvi u, prvi van.

206
00:09:41,914 --> 00:09:43,705
Ako ste prvi
jedna u nizu, ti si

207
00:09:43,705 --> 00:09:46,230
prvi koji
dolazi iz linije.

208
00:09:46,230 --> 00:09:49,680
>> Dakle, ono što smo željeli nazvati to
je dequeueing i enqueueing.

209
00:09:49,680 --> 00:09:52,380
Ako želite dodati nešto
našem redu, enqueue smo.

210
00:09:52,380 --> 00:09:55,690
Ako želimo dequeue, ili se
nešto dalje, dequeue smo.

211
00:09:55,690 --> 00:10:03,350
>> Tako isto osjećaj da smo vrsta
stvaranje fiksne veličine elemenata koje

212
00:10:03,350 --> 00:10:06,500
može pohraniti sigurno
stvari, ali možemo

213
00:10:06,500 --> 00:10:10,100
promijeniti gdje smo stavljanje
Parametri unutar njih

214
00:10:10,100 --> 00:10:13,140
na temelju onoga što vrste
Funkcionalnost želimo.

215
00:10:13,140 --> 00:10:16,700
Dakle dimnjaka, htjeli smo posljednji
jedan, N biti prvi van.

216
00:10:16,700 --> 00:10:19,800
Red je želimo prva stvar
u biti prva stvar van.

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

218
00:10:22,510 --> 00:10:26,710
>> Tako je struct tipa
definirati, kao što možete vidjeti,

219
00:10:26,710 --> 00:10:29,470
to je malo drugačije
od onoga što je snop

220
00:10:29,470 --> 00:10:33,120
jer ne samo da moramo zadržati
trag gdje je veličina trenutačno je,

221
00:10:33,120 --> 00:10:37,420
želimo pratiti glave
kao i gdje smo trenutno.

222
00:10:37,420 --> 00:10:39,580
Zato mislim da je lakše
ako sam izraditi ovaj gore.

223
00:10:39,580 --> 00:10:53,270
Dakle, zamislimo da imamo red,
pa recimo glava je upravo ovdje.

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

225
00:10:55,811 --> 00:10:58,310
Čelnik linije, neka je
samo reći da je to trenutno postoji,

226
00:10:58,310 --> 00:11:01,809
i želimo umetnuti
nešto u redu.

227
00:11:01,809 --> 00:11:04,350
Idem zvati veličinu bitno
je ista stvar kao i rep,

228
00:11:04,350 --> 00:11:06,314
kraj gdje god je vaš red je.

229
00:11:06,314 --> 00:11:07,730
Recimo samo veličina je upravo ovdje.

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

231
00:11:14,380 --> 00:11:18,400
>> Pa kako se jedan feasibly
ubacite nešto u redu?

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

233
00:11:21,000 --> 00:11:24,130
Što Indeks želimo staviti
gdje želimo umetnuti u.

234
00:11:24,130 --> 00:11:29,320
Ako je ovo početak svoje
red i to je kraj nje

235
00:11:29,320 --> 00:11:31,860
ili veličina njega, u kojima radimo
Želite dodati sljedeći objekt?

236
00:11:31,860 --> 00:11:32,920
>> PUBLIKA: [nečujan]

237
00:11:32,920 --> 00:11:35,920
ANDI PENG: Točno, želite dodati
to ovisi o si ga napisao.

238
00:11:35,920 --> 00:11:37,840
Ili je to prazan ili da je prazno.

239
00:11:37,840 --> 00:11:42,630
Dakle, želite ga dodati vjerojatno
ovdje jer ako veličina is--

240
00:11:42,630 --> 00:11:50,540
ako su svi puni, što želite
to dodati ovdje, zar ne?

241
00:11:50,540 --> 00:11:57,150
>> I tako je to, a vrlo, vrlo
jednostavno, ne sasvim uvijek točno

242
00:11:57,150 --> 00:12:00,690
jer glavne razlike
između red i stog

243
00:12:00,690 --> 00:12:04,350
da je red može
zapravo se manipulira

244
00:12:04,350 --> 00:12:06,980
tako da su promjene glavu
ovisno o tome gdje želite

245
00:12:06,980 --> 00:12:08,650
početak vašeg znak za početak.

246
00:12:08,650 --> 00:12:11,900
I kao rezultat toga, vaš rep
također će se promijeniti.

247
00:12:11,900 --> 00:12:14,770
I tako pogledati
ovaj kod upravo sada.

248
00:12:14,770 --> 00:12:18,620
Kao što ti dečki su također zamoljeni da
pisati na kvizu, u red.

249
00:12:18,620 --> 00:12:22,580
Možda ćemo razgovarati kroz zašto
odgovor je bio ono što je bilo.

250
00:12:22,580 --> 00:12:26,790
>> Nisam mogao sasvim stane tu liniju na jedan,
ali u suštini to dio koda

251
00:12:26,790 --> 00:12:29,030
bi trebao biti na jednoj liniji.

252
00:12:29,030 --> 00:12:30,140
Provedite se kao 30 sekundi.

253
00:12:30,140 --> 00:12:33,000
Pogledajte i uvjerite se zašto
to je način na koji je to.

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

255
00:12:50,030 --> 00:12:55,420
>> Vrlo, vrlo sličan struct, vrlo, vrlo
Slična struktura kao prethodna

256
00:12:55,420 --> 00:12:58,090
stog osim možda
jedna linija koda.

257
00:12:58,090 --> 00:13:01,190
I to jedan redak koda
određuje funkcionalnost.

258
00:13:01,190 --> 00:13:03,900
I to stvarno razlikuje
red iz dimnjaka.

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

260
00:13:18,510 --> 00:13:22,010
>> Svatko želi uzeti ubod
na objašnjavanje zašto si

261
00:13:22,010 --> 00:13:24,980
nema tu kompliciranu stvar ovdje?

262
00:13:24,980 --> 00:13:27,845
Vidimo povratak naših
prekrasan prijatelj modul.

263
00:13:27,845 --> 00:13:31,020
Kao što ti dečki će uskoro doći
prepoznati u programiranju,

264
00:13:31,020 --> 00:13:34,910
gotovo bilo vam je potrebno nešto
omotati oko bilo čega,

265
00:13:34,910 --> 00:13:36,850
Modul će biti onako kako to učiniti.

266
00:13:36,850 --> 00:13:40,510
Dakle, znajući da, bilo tko želite
pokušati objašnjavajući da je linija koda?

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

268
00:13:44,060 --> 00:13:47,507
Da, svi su odgovori
prihvaćena i dobrodošla.

269
00:13:47,507 --> 00:13:48,840
PUBLIKA: Jeste li u razgovoru sa mnom?

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

271
00:13:49,506 --> 00:13:56,200
PUBLIKA: Oh, ne ispričavam.

272
00:13:56,200 --> 00:14:00,250
ANDI PENG: OK, neka je
hoda kroz ovaj kod.

273
00:14:00,250 --> 00:14:03,642
Dakle, kada pokušavate
dodati nešto na red,

274
00:14:03,642 --> 00:14:08,510
u lijepom slučaju da je glava događa
da se upravo ovdje, to je vrlo lako za nas

275
00:14:08,510 --> 00:14:10,960
samo otići do kraja
ubacite nešto, zar ne?

276
00:14:10,960 --> 00:14:14,690
No, cijela točka red je
da je glava zapravo može dinamički

277
00:14:14,690 --> 00:14:17,280
mijenjati ovisno o tome gdje smo
Želite početak naše q da bude,

278
00:14:17,280 --> 00:14:19,880
i kao takav, rep
također će se promijeniti.

279
00:14:19,880 --> 00:14:31,100
>> I tako zamisliti da to nije bilo
red, nego je to bio red.

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

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

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

283
00:14:54,900 --> 00:14:56,980
Recimo da je naš red izgledao ovako.

284
00:14:56,980 --> 00:15:00,190
Ako smo htjeli prebaciti u kojoj
početak linije,

285
00:15:00,190 --> 00:15:03,400
recimo mi pomaknuo glavu
na taj način i veličina ovdje.

286
00:15:03,400 --> 00:15:07,100
>> Sada želimo dodati nešto
ovaj red, ali kako vi vidite,

287
00:15:07,100 --> 00:15:11,150
to nije tako jednostavno kao samo
dodaj ono što je nakon veličini

288
00:15:11,150 --> 00:15:13,630
jer tada smo ponestane
granica našeg stvarnog polja.

289
00:15:13,630 --> 00:15:16,190
Gdje smo stvarno želite dodati ovdje.

290
00:15:16,190 --> 00:15:18,610
To je ljepota red
je da je za nas, vizualno

291
00:15:18,610 --> 00:15:22,380
Izgleda da je linija ide ovako,
a ako je pohranjena u strukture podataka,

292
00:15:22,380 --> 00:15:29,370
oni daju kao kao ciklus.

293
00:15:29,370 --> 00:15:32,360
To je vrsta omata
na prednjem isti način

294
00:15:32,360 --> 00:15:34,780
da linija može omotati
oko ovisno o gdje god vas

295
00:15:34,780 --> 00:15:36,279
želite početku retka biti.

296
00:15:36,279 --> 00:15:38,630
I tako, ako uzmemo
pogledajte ovdje, neka je

297
00:15:38,630 --> 00:15:40,880
reći da smo htjeli stvoriti
funkcija zove enqueue.

298
00:15:40,880 --> 00:15:43,980
Željeli smo dodali int n u taj q.

299
00:15:43,980 --> 00:15:49,250
Ako q.size q-- ćemo nazvati naše podatke
structure-- ako naš queue.size ne

300
00:15:49,250 --> 00:15:52,520
jednak kapacitet ili ako
to je manje od kapaciteta,

301
00:15:52,520 --> 00:15:55,120
q.strings je niz unutar naše q.

302
00:15:55,120 --> 00:15:58,380
Idemo postaviti
koja je jednaka q.heads,

303
00:15:58,380 --> 00:16:02,730
što je upravo ovdje, plus q.size
modul kapacitetom, koji

304
00:16:02,730 --> 00:16:04,290
zamotajte nas natrag ovdje.

305
00:16:04,290 --> 00:16:08,040
>> Dakle, u ovom primjeru, indeks
glave je 1, zar ne?

306
00:16:08,040 --> 00:16:11,480
Indeks veličine je 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Dakle, što možemo učiniti 1 plus 4 modul
naš kapacitet koji je 5.

308
00:16:19,500 --> 00:16:20,920
Što to nam dati?

309
00:16:20,920 --> 00:16:23,270
Što je indeks koji
dolazi iz toga?

310
00:16:23,270 --> 00:16:24,080
>> PUBLIKA: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI PENG: 0, koji
se događa da se upravo ovdje,

312
00:16:27,870 --> 00:16:30,640
i tako želimo biti u mogućnosti
umetnuti u ovdje.

313
00:16:30,640 --> 00:16:34,730
I tako ta jednadžba ovdje vrste
samo radi s bilo kojim brojevima

314
00:16:34,730 --> 00:16:36,750
ovisno o tome gdje svoje
Glava i tvoja veličina su.

315
00:16:36,750 --> 00:16:38,541
Ako znate što oni
stvari, znate

316
00:16:38,541 --> 00:16:43,170
točno gdje želite umetnuti
sve što je nakon čekanja.

317
00:16:43,170 --> 00:16:44,640
Znači li to da smisla svima?

318
00:16:44,640 --> 00:16:48,560
>> Znam kakve mozga
teaser pogotovo jer to

319
00:16:48,560 --> 00:16:50,512
došao je nakon kviza.

320
00:16:50,512 --> 00:16:52,220
No, nadamo se svi
Sada možete razumjeti

321
00:16:52,220 --> 00:16:57,800
zašto je to rješenje ili ovaj
Funkcija je način na koji je to.

322
00:16:57,800 --> 00:16:59,840
Svatko malo nejasno o tome?

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

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

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

326
00:17:07,109 --> 00:17:09,970
>> I tako sad, ako vas
htjela dequeue, ovaj

327
00:17:09,970 --> 00:17:15,240
gdje je naš voditelj će biti pomicanja
jer ako bismo dequeue,

328
00:17:15,240 --> 00:17:17,030
mi ne skinu kraj q.

329
00:17:17,030 --> 00:17:19,130
Želimo da skinu glavu, zar ne?

330
00:17:19,130 --> 00:17:24,260
Dakle, kao rezultat, glava će se promijeniti,
i zato kada enqueue,

331
00:17:24,260 --> 00:17:26,800
moraš pratiti
gdje vam je glava i tvoj veličina

332
00:17:26,800 --> 00:17:29,450
su da bi mogli umetnuti
u ispravan položaj.

333
00:17:29,450 --> 00:17:32,740
>> I tako kad dequeue,
Također sam ga pseudokod van.

334
00:17:32,740 --> 00:17:35,480
Slobodno ako želite
pokušati kodiranja ovo.

335
00:17:35,480 --> 00:17:36,980
Želite premjestiti glavu, zar ne?

336
00:17:36,980 --> 00:17:39,320
Ako sam htjela dequeue, ja
bi premjestiti nad glavom.

337
00:17:39,320 --> 00:17:40,800
To će biti glava.

338
00:17:40,800 --> 00:17:45,617
>> I naš sadašnji broj bi
oduzimati jer više ne

339
00:17:45,617 --> 00:17:46,950
imaju četiri elementa u nizu.

340
00:17:46,950 --> 00:17:51,370
Imamo samo tri, a onda želimo
da se vrati ono što je pohranjena u

341
00:17:51,370 --> 00:17:56,260
glave, jer želimo da se to
vrijednost se tako vrlo slična dimnjaka.

342
00:17:56,260 --> 00:17:58,010
Samo ste uzimajući
iz različitih mjesta,

343
00:17:58,010 --> 00:18:01,770
i morate preraspodijeliti pokazivač
na drugom mjestu kao rezultat.

344
00:18:01,770 --> 00:18:03,890
Logično, svi slijediti?

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

346
00:18:05,690 --> 00:18:10,156
>> U redu, pa ćemo razgovarati malo
više u dubinu o povezanim popisima

347
00:18:10,156 --> 00:18:13,280
jer će biti vrlo, vrlo vrijedan
za vas u toku ovog tjedna je

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

349
00:18:14,964 --> 00:18:17,130
Povezani popisi, kao što ste vi
sjećam se, svi su oni

350
00:18:17,130 --> 00:18:22,570
su čvorovi koji su čvorovi sigurno
vrijednosti obje vrijednosti i pokazivač

351
00:18:22,570 --> 00:18:26,290
koji su međusobno povezani
tim upućuje.

352
00:18:26,290 --> 00:18:29,880
I tako struct o tome
mi stvaramo čvor ovdje smo

353
00:18:29,880 --> 00:18:33,569
ima int n, što je bilo
vrijednost u trgovini ili string n

354
00:18:33,569 --> 00:18:35,610
ili što god želite
ga nazivaju, char zvijezda nje.

355
00:18:35,610 --> 00:18:41,482
Struct čvor zvijezda, što je pokazivač
koje želite imati u svakom čvoru,

356
00:18:41,482 --> 00:18:43,690
ti si idući u morati da
Pokazivač točka prema sljedećoj.

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

358
00:18:48,207 --> 00:18:50,040
Vi ćete imati glavu
popisa koji je povezan

359
00:18:50,040 --> 00:18:53,140
će ukazati na ostatak
tako dalje i tako dalje vrijednosti

360
00:18:53,140 --> 00:18:55,290
dok na kraju doći do kraja.

361
00:18:55,290 --> 00:18:58,040
A ovaj zadnji čvor je samo
će ne imati pokazivač.

362
00:18:58,040 --> 00:18:59,952
To će ukazati na
null, a to je kada

363
00:18:59,952 --> 00:19:01,910
znate da ste hit
kraj svog popisa povezan

364
00:19:01,910 --> 00:19:04,076
kada je vaša posljednja pokazivač
ne ukazuju na ništa.

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

366
00:19:06,670 --> 00:19:10,990
>> Tako ćemo ići malo više u
Dubina o tome kako jedan bi eventualno

367
00:19:10,990 --> 00:19:12,400
Pretražite popis povezane.

368
00:19:12,400 --> 00:19:15,460
Sjeti se što su neke od
Nedostaci povezanim popisima

369
00:19:15,460 --> 00:19:19,340
stihova niz vezi pretraživanja.

370
00:19:19,340 --> 00:19:22,565
Niz možete binarno pretraživanje, ali
zašto ne možete to učiniti na popisu povezane?

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

372
00:19:26,834 --> 00:19:30,320
>> PUBLIKA: Zato što su svi povezani,
ali ne znam točno gdje

373
00:19:30,320 --> 00:19:31,330
[NEČUJAN].

374
00:19:31,330 --> 00:19:34,600
>> ANDI PENG: Da, upravo tako zapamtiti
da sjaj niz

375
00:19:34,600 --> 00:19:37,190
bila je činjenica da smo imali
memorija s izravnim pristupom, gdje

376
00:19:37,190 --> 00:19:41,580
ako sam htjela vrijednost iz indeksa
šest, samo sam mogao reći indeks šest,

377
00:19:41,580 --> 00:19:42,407
daj mi tu vrijednost.

378
00:19:42,407 --> 00:19:45,240
A to je zato jer su nizovi razvrstani
u susjednom prostoru memorije

379
00:19:45,240 --> 00:19:48,020
na jednom mjestu, dok je
vrsta povezanih popisa

380
00:19:48,020 --> 00:19:52,820
su nasumično mjestimice diljem,
a jedini način na koji možete naći jedan

381
00:19:52,820 --> 00:19:56,890
je kroz pokazivač koji vam govori
adresu gdje da sljedeći čvor.

382
00:19:56,890 --> 00:20:00,290
>> Pa kao rezultat toga, jedini način
za pretraživanje kroz popis povezanih

383
00:20:00,290 --> 00:20:01,560
linearna pretraživanja.

384
00:20:01,560 --> 00:20:05,890
Jer ja ne znam točno gdje
12. Vrijednost na popisu povezan je,

385
00:20:05,890 --> 00:20:08,780
Moram proći u cijelosti
tog povezanog popisa jednom

386
00:20:08,780 --> 00:20:12,450
jedan od glave do prvog čvora,
na drugi čvor, do trećeg čvora,

387
00:20:12,450 --> 00:20:17,690
sve na putu prema dolje dok sam napokon dobiti
gdje da čvor tražim je.

388
00:20:17,690 --> 00:20:22,110
I tako u tom smislu, traži
na popisu povezan je uvijek n.

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

390
00:20:23,040 --> 00:20:25,690
To je uvijek u linearnom vremenu.

391
00:20:25,690 --> 00:20:28,470
>> I tako je broj na koji
implementiramo to, i to

392
00:20:28,470 --> 00:20:32,620
je malo novo za vas dečki Budući da
dečki nisu stvarno razgovarali o ili nikad

393
00:20:32,620 --> 00:20:35,000
vidi naputke u tome kako
pretraživanje pokazivače,

394
00:20:35,000 --> 00:20:37,670
pa ćemo šetati
Ovo je vrlo, vrlo sporo.

395
00:20:37,670 --> 00:20:40,200
Dakle bool pretraživanje, pravo,
neka je zamisliti da želimo

396
00:20:40,200 --> 00:20:42,820
stvoriti funkciju pod nazivom
traži da se vraća true

397
00:20:42,820 --> 00:20:46,820
Ako ste pronašli vrijednost unutar povezani
popis, a false inače.

398
00:20:46,820 --> 00:20:50,030
Popis Čvor zvijezda je
Trenutno samo pokazivač

399
00:20:50,030 --> 00:20:52,960
na prvu stavku na popisu povezane.

400
00:20:52,960 --> 00:20:56,700
int n vrijednost koju ste
traži u tom popisu.

401
00:20:56,700 --> 00:20:58,770
>> Dakle čvor zvijezda pokazivač jednaka popis.

402
00:20:58,770 --> 00:21:00,970
To znači da smo postavljanje
i stvaranje pokazivač

403
00:21:00,970 --> 00:21:03,592
na taj prvi čvor unutar popisa.

404
00:21:03,592 --> 00:21:04,300
Svatko sa mnom?

405
00:21:04,300 --> 00:21:06,530
Dakle, ako smo ići
ovamo, ja bi

406
00:21:06,530 --> 00:21:13,850
inicijalizira pokazivač koji ukazuje na
glava god da je popis.

407
00:21:13,850 --> 00:21:18,600
>> I onda jednom kada se ovdje,
dok pokazivač nije jednak null,

408
00:21:18,600 --> 00:21:22,160
tako da je petlja u kojoj smo
će biti naknadno poprijeko

409
00:21:22,160 --> 00:21:25,940
ostatak našeg popisa, jer ono što
događa kada pokazivač jednak null?

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

411
00:21:27,550 --> 00:21:28,450
>> PUBLIKA: [nečujan]

412
00:21:28,450 --> 00:21:31,491
>> ANDI PENG: Točno, tako da znamo da je
smo došli do kraja popisa, zar ne?

413
00:21:31,491 --> 00:21:34,470
Ako se vratite ovdje, svaki čvor
Treba ukazujući na drugi čvor

414
00:21:34,470 --> 00:21:36,550
i tako dalje i tako dalje
sve dok ne dosegnete kraju

415
00:21:36,550 --> 00:21:41,589
rep vašeg popisa povezani,
koja ima pokazivač koji samo

416
00:21:41,589 --> 00:21:43,130
ne pokazuje nigdje osim br.

417
00:21:43,130 --> 00:21:47,510
I tako vi zapravo znate da
Vaš popis je još uvijek tamo

418
00:21:47,510 --> 00:21:50,900
dok pokazivač nije jednak
null jer jednom je jednak null,

419
00:21:50,900 --> 00:21:53,310
znate da postoji više nema stvari.

420
00:21:53,310 --> 00:21:56,930
>> Tako da je petlja u kojoj smo
će imati stvarnu potragu.

421
00:21:56,930 --> 00:22:01,690
A ako pointer-- vidiš
koja vrsta strelice funkcije tamo?

422
00:22:01,690 --> 00:22:06,930
Dakle, ako pokazivač upućuje na n, ako je
pokazivač na n jednak jednak n,

423
00:22:06,930 --> 00:22:09,180
pa to znači da ako
pokazivač da ste

424
00:22:09,180 --> 00:22:13,420
traže na kraju svakog
Čvor je zapravo jednaka vrijednosti

425
00:22:13,420 --> 00:22:15,990
što tražite, a zatim
Želite li vratiti istinito.

426
00:22:15,990 --> 00:22:19,280
Tako je u osnovi, ako ste na čvoru koji
ima vrijednost koju tražite,

427
00:22:19,280 --> 00:22:23,550
znate da ste bili
mogli uspješno traženje.

428
00:22:23,550 --> 00:22:27,150
>> Inače, želite postaviti
pokazivač na sljedeći čvor.

429
00:22:27,150 --> 00:22:28,850
To je što to crta ovdje radi.

430
00:22:28,850 --> 00:22:31,750
Pointer jednak pokazivač sljedeći.

431
00:22:31,750 --> 00:22:33,360
Svatko vidi kako se to radi?

432
00:22:33,360 --> 00:22:36,580
>> A u biti da ćeš samo
proći cjelinu popisa,

433
00:22:36,580 --> 00:22:41,920
resetiranja pokazivač svaki put do
što na kraju pogodio kraj popisa.

434
00:22:41,920 --> 00:22:45,030
I znate da ne postoje
više čvorova za pretraživanje,

435
00:22:45,030 --> 00:22:47,999
a onda možete return false
jer znate da je, oh, dobro,

436
00:22:47,999 --> 00:22:50,540
ako sam bio u mogućnosti to traženje
kroz cijelosti popisa.

437
00:22:50,540 --> 00:22:54,530
Ako se u ovom primjeru, ako sam htjela
tražiti vrijednosti od 10,

438
00:22:54,530 --> 00:22:57,250
i ja početi na glavi, a
Tražim sve na putu prema dolje,

439
00:22:57,250 --> 00:23:00,550
i na kraju sam dobio za to, što
pokazivač koji ukazuje na null,

440
00:23:00,550 --> 00:23:04,415
Znam da, sranje, valjda 10 nije u
ovaj popis jer nisam mogao naći.

441
00:23:04,415 --> 00:23:06,520
I ja sam na kraju liste.

442
00:23:06,520 --> 00:23:11,040
I u tom slučaju znate
Idem return false.

443
00:23:11,040 --> 00:23:12,900
>> Neka to potopiti u za malo.

444
00:23:12,900 --> 00:23:17,350
To će biti prilično
važan za vaše pset.

445
00:23:17,350 --> 00:23:21,140
Logika je vrlo jednostavno, možda
sintaktički samo ga provoditi.

446
00:23:21,140 --> 00:23:23,365
Vi želite učiniti
sigurni da ste razumjeli.

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, pa kako ćemo biti
umetanje čvorova, pravo,

450
00:23:32,560 --> 00:23:35,380
u popisu, jer ne zaboravite
što su ono od prednosti

451
00:23:35,380 --> 00:23:39,230
vlasništvo povezana popis odnosu
niz u smislu čuvanja?

452
00:23:39,230 --> 00:23:41,110
>> PUBLIKA: To je dinamičan,
tako da je lakše to--

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

454
00:23:43,180 --> 00:23:46,880
znači da se može proširiti i smanjiti
ovisno o potrebama korisnika.

455
00:23:46,880 --> 00:23:56,570
I tako, u tom smislu, ne moramo
trošiti nepotrebno memorije jer sam

456
00:23:56,570 --> 00:24:00,850
ako ja ne znam koliko vrijednosti želim
do trgovine, to nema smisla za mene

457
00:24:00,850 --> 00:24:04,310
stvoriti niz, jer
ako želim pohraniti 10 vrijednosti

458
00:24:04,310 --> 00:24:08,380
i ja stvoriti niz 1000, to je
puno izgubljenog pamćenja, dodijelili.

459
00:24:08,380 --> 00:24:11,180
Zato želimo koristiti povezani
Popis se može dinamički

460
00:24:11,180 --> 00:24:13,860
promijeniti ili smanjiti našu veličinu.

461
00:24:13,860 --> 00:24:17,040
>> I tako to čini umetanje
malo više komplicirano.

462
00:24:17,040 --> 00:24:20,810
Budući da ne možemo nasumično pristupiti elemente
način na koji bismo od niza.

463
00:24:20,810 --> 00:24:24,270
Ako želim umetnuti element
u sedmom indeksa,

464
00:24:24,270 --> 00:24:26,930
Upravo sam ga možete umetnuti
u sedmom indeksa.

465
00:24:26,930 --> 00:24:30,020
Na popisu povezani, to ne
dosta raditi kao jednostavno,

466
00:24:30,020 --> 00:24:34,947
pa ako smo htjeli umetnuti
jedan ovdje u popisu povezane,

467
00:24:34,947 --> 00:24:36,280
vizualno, to je vrlo lako vidjeti.

468
00:24:36,280 --> 00:24:39,363
Mi samo želimo da ga ubacite pravo postoji,
odmah na početku popisa,

469
00:24:39,363 --> 00:24:40,840
odmah nakon glavu.

470
00:24:40,840 --> 00:24:44,579
>> No, način na koji moramo preraspodijeliti
se upućuje je malo savijen

471
00:24:44,579 --> 00:24:47,620
ili, logično, to ima smisla, ali
Želite li biti sigurni da ste ga

472
00:24:47,620 --> 00:24:50,250
sasvim dolje, jer
posljednja stvar koju želite

473
00:24:50,250 --> 00:24:52,990
je preraspodijeliti pokazivač
Način na koji radimo ovdje.

474
00:24:52,990 --> 00:24:58,170
Ako vas dereference
pokazivač od glave do 1,

475
00:24:58,170 --> 00:25:01,086
zatim sve iznenada
ostatak svog popisa povezan

476
00:25:01,086 --> 00:25:04,680
izgubljen jer niste zapravo
stvorio privremeni ništa.

477
00:25:04,680 --> 00:25:06,220
To je ukazao na 2.

478
00:25:06,220 --> 00:25:10,080
Ako preraspodijeliti pokazivač, a zatim
Ostatak svog popisa potpuno je izgubljen.

479
00:25:10,080 --> 00:25:13,310
Dakle, želite biti
vrlo, vrlo oprezni ovdje

480
00:25:13,310 --> 00:25:17,010
najprije dodijeliti
Pokazivač iz bilo kojeg vas

481
00:25:17,010 --> 00:25:20,150
želite umetnuti u gdje god
što želite, a zatim vas

482
00:25:20,150 --> 00:25:22,710
Možete dereference ostatak svog popisa.

483
00:25:22,710 --> 00:25:25,250
>> Dakle, to vrijedi i za gdje god
što pokušavate umetnuti u.

484
00:25:25,250 --> 00:25:27,520
Ako želite umetnuti Na
glava, ako želite odgovoriti ovdje,

485
00:25:27,520 --> 00:25:29,455
Ako želite umetnuti u
kraj, dobro, na kraju sam

486
00:25:29,455 --> 00:25:30,910
Pretpostavljam da bi samo
nemaju pokazivač, ali

487
00:25:30,910 --> 00:25:33,830
želite biti sigurni da ne
izgubiti ostatak svog popisa.

488
00:25:33,830 --> 00:25:36,640
Vi uvijek želite biti sigurni
Vaš novi čvor ukazuje

489
00:25:36,640 --> 00:25:39,330
prema god
želite umetnuti u,

490
00:25:39,330 --> 00:25:42,170
a zatim možete dodati ulančavanje dalje.

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

492
00:25:43,330 --> 00:25:45,427
>> To će biti
jedan od stvarnih problema.

493
00:25:45,427 --> 00:25:48,010
Jedan od najvažnijih glavnih pitanja
ti si idući u imati na svom pset

494
00:25:48,010 --> 00:25:51,340
je da ćeš pokušati stvoriti
je povezani popis i stavite stvari

495
00:25:51,340 --> 00:25:53,340
ali onda samo izgubiti
ostatak svog popisa povezane.

496
00:25:53,340 --> 00:25:54,900
I vi ćete biti kao ja
ne znam zašto se to događa?

497
00:25:54,900 --> 00:25:58,040
I to je bol proći
i traži sve svoje pokazivače.

498
00:25:58,040 --> 00:26:02,100
>> A ja vam jamčim ovaj pset,
pisanje i crtanje te čvorova iz

499
00:26:02,100 --> 00:26:03,344
će biti vrlo, vrlo korisno.

500
00:26:03,344 --> 00:26:06,010
Tako da u potpunosti možete pratiti
gdje sve svoje pokazivače su,

501
00:26:06,010 --> 00:26:08,540
što se događa u krivu,
gdje su svi vaši čvorovi,

502
00:26:08,540 --> 00:26:12,660
ono što trebate učiniti za pristup ili
umetnuti ili izbrisati ili bilo koji od njih.

503
00:26:12,660 --> 00:26:14,550
Svatko dobro s tim?

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
>> Dakle, ako smo htjeli pogledati šifru?

507
00:26:22,600 --> 00:26:24,470
Oh, ja ne znam da li smo
možete vidjeti the-- redu, tako da

508
00:26:24,470 --> 00:26:27,940
na vrhu sve što je funkcija
nazvana umetak gdje želimo

509
00:26:27,940 --> 00:26:31,365
umetnuti int n u popisu povezane.

510
00:26:31,365 --> 00:26:32,740
Idemo u šetnju kroz ovo.

511
00:26:32,740 --> 00:26:34,770
To je puno koda, puno novih sintakse.

512
00:26:34,770 --> 00:26:36,220
Mi ćemo biti u redu.

513
00:26:36,220 --> 00:26:39,120
>> Tako se na vrhu, kad god
želimo stvoriti nešto

514
00:26:39,120 --> 00:26:42,380
Što trebamo učiniti, osobito ako vas
žele da neće biti pohranjeni na stogu

515
00:26:42,380 --> 00:26:43,920
ali u hrpi?

516
00:26:43,920 --> 00:26:45,460
Idemo na malloc, zar ne?

517
00:26:45,460 --> 00:26:48,240
Tako ćemo stvoriti pokazivač.

518
00:26:48,240 --> 00:26:52,074
Čvor, pokazivač, novi jednaki
malloc veličine čvora

519
00:26:52,074 --> 00:26:53,740
jer želimo da se čvor biti stvoren.

520
00:26:53,740 --> 00:26:56,720
Želimo količinu
memorije koja čvor zauzima

521
00:26:56,720 --> 00:26:59,300
se dodjeljuju za
Stvaranje novog čvora.

522
00:26:59,300 --> 00:27:02,270
>> A onda ćemo provjeriti
je li nova jednaki jednaka nuli.

523
00:27:02,270 --> 00:27:03,370
Sjećaš se što smo rekli?

524
00:27:03,370 --> 00:27:06,470
Što god vam malloc,
što moraš uvijek raditi?

525
00:27:06,470 --> 00:27:09,490
Uvijek morate provjeriti da se vidi
da li ili ne to je null.

526
00:27:09,490 --> 00:27:13,620
>> Na primjer, ako vaš operativni
Sustav je potpuno pun,

527
00:27:13,620 --> 00:27:17,060
ako je nema više memorije na
sve i pokušate malloc,

528
00:27:17,060 --> 00:27:18,410
to bi se vratiti null za vas.

529
00:27:18,410 --> 00:27:21,094
I tako, ako pokušate ga koristiti
kada je pokazujući na null,

530
00:27:21,094 --> 00:27:23,260
ti nećeš moći
pristupiti te podatke.

531
00:27:23,260 --> 00:27:27,010
I tako, kao što smo htjeli napraviti
jeste da kad god ste mallocing,

532
00:27:27,010 --> 00:27:30,500
ti si uvijek provjeru je li
da memorija tebi je null.

533
00:27:30,500 --> 00:27:33,670
A ako nije, onda možemo pomaknuti
na sa ostatkom našeg koda.

534
00:27:33,670 --> 00:27:36,140
>> Tako ćemo
inicijalizirati novi čvor.

535
00:27:36,140 --> 00:27:39,050
Idemo napraviti novi je n = n.

536
00:27:39,050 --> 00:27:42,390
A onda ćemo napraviti
postaviti novi pokazivač na novo

537
00:27:42,390 --> 00:27:46,900
na nulu, jer sada mi ne
Želite ništa za to ukazati.

538
00:27:46,900 --> 00:27:48,755
Mi nemamo pojma gdje
to će vas,

539
00:27:48,755 --> 00:27:50,630
a onda, ako želimo
umetnite ga u glavu,

540
00:27:50,630 --> 00:27:53,820
onda možemo dodijeliti
pokazivač na glavu.

541
00:27:53,820 --> 00:27:58,530
Da li su svi slijede logiku
gdje to događa?

542
00:27:58,530 --> 00:28:02,502
>> Sve što radite stvara novi
čvor, postavljanje pokazivača na nulu,

543
00:28:02,502 --> 00:28:04,210
a zatim prenamjene
je u glavu ako mi

544
00:28:04,210 --> 00:28:06,320
znate što želite umetnuti u glavi.

545
00:28:06,320 --> 00:28:09,420
A onda je glava ide
usmjerite prema tom novom čvor.

546
00:28:09,420 --> 00:28:11,060
Svatko u redu s tim?

547
00:28:11,060 --> 00:28:12,380
>> Dakle, to je proces u dva koraka.

548
00:28:12,380 --> 00:28:14,760
Moraš prvo Dodijeli
sve što stvarate.

549
00:28:14,760 --> 00:28:18,260
Postavite pokazivač na taj
referenca, a onda vam

550
00:28:18,260 --> 00:28:21,400
Možete vrsta dereference
prvi pokazivač

551
00:28:21,400 --> 00:28:22,972
i usmjerite prema novom čvor.

552
00:28:22,972 --> 00:28:25,680
Gdje god ga želite umetnuti,
da logika ide vrijede.

553
00:28:25,680 --> 00:28:27,530
>> To je vrsta kao dodjeljivanje
privremene varijable.

554
00:28:27,530 --> 00:28:28,700
Sjeti se, imaš
kako bi bili sigurni da vas

555
00:28:28,700 --> 00:28:30,346
nemojte izgubiti trag ako ste zamjene.

556
00:28:30,346 --> 00:28:33,470
Vi želite biti sigurni da imate
privremena varijabla koja vrsta čuva

557
00:28:33,470 --> 00:28:35,620
Staza gdje tu stvar
se pohranjuje tako da

558
00:28:35,620 --> 00:28:41,190
ne izgubiti bilo koju vrijednost u tijeku
poput messing oko s njom.

559
00:28:41,190 --> 00:28:42,710
>> U redu, tako da kod će biti ovdje.

560
00:28:42,710 --> 00:28:45,020
Vi pogledati nakon dijelu.

561
00:28:45,020 --> 00:28:48,060
To će biti tamo.

562
00:28:48,060 --> 00:28:50,280
>> Pa valjda kako se
to razlikuje ako smo htjeli

563
00:28:50,280 --> 00:28:52,300
umetnuti u sredini ili na kraju?

564
00:28:52,300 --> 00:28:57,892
Se bilo tko imati ideju o tome što je
pseudokod kao logičan referenca

565
00:28:57,892 --> 00:29:00,350
da bi se, ako smo htjeli
umetnite ga u sredini?

566
00:29:00,350 --> 00:29:03,391
Dakle, ako smo htjeli da ga ubacite Na
Glava, sve što radimo je stvoriti novi čvor.

567
00:29:03,391 --> 00:29:06,311
Postavili smo pokazivač toga
novi čvor na bilo glave,

568
00:29:06,311 --> 00:29:08,310
a zatim smo postavili glavu
na novi čvor, zar ne?

569
00:29:08,310 --> 00:29:11,560
Ako smo htjeli da ga ubacite u sredini
popisa, što bi mi moramo učiniti?

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

571
00:29:14,108 --> 00:29:16,110
>> PUBLIKA: on će i dalje
biti sličan proces

572
00:29:16,110 --> 00:29:19,114
poput dodjele pokazivač i
onda dodjeljivanje da pokazivač,

573
00:29:19,114 --> 00:29:20,530
ali će morati pronaći tamo.

574
00:29:20,530 --> 00:29:23,560
>> ANDI PENG: Točno, tako da je točno
isti proces, osim tebe

575
00:29:23,560 --> 00:29:27,820
moraju pronaći gdje točno
Želite da novi pokazivač ići u,

576
00:29:27,820 --> 00:29:44,790
pa ako želim umetnuti u
sredina povezani list-- redu,

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

578
00:29:46,370 --> 00:29:49,500
Ako želite umetnuti ovdje,
ćemo stvoriti novi čvor.

579
00:29:49,500 --> 00:29:50,520
Idemo malloc.

580
00:29:50,520 --> 00:29:52,220
Ćemo stvoriti novi čvor.

581
00:29:52,220 --> 00:29:55,940
Idemo dodijeliti
pokazivač ovog čvora ovdje.

582
00:29:55,940 --> 00:29:58,335
>> No, problem koji se razlikuje
odakle je glava

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

584
00:30:00,490 --> 00:30:01,930
Bilo je to pravo na prvi, zar ne?

585
00:30:01,930 --> 00:30:04,870
No, ovdje moramo pratiti
gdje smo ubacivanja u.

586
00:30:04,870 --> 00:30:07,930
Ako se umetanjem naš
čvor ovdje imamo

587
00:30:07,930 --> 00:30:12,270
kako bi bili sigurni da je
jedan prethodni ovom čvoru

588
00:30:12,270 --> 00:30:14,172
je onaj koji reassigns pokazivač.

589
00:30:14,172 --> 00:30:16,380
Pa onda morate vrsta
pratiti dvije stvari.

590
00:30:16,380 --> 00:30:19,420
Ako vam pratiti gdje se to
čvor trenutno umetanja.

591
00:30:19,420 --> 00:30:23,280
Također morate pratiti gdje
prethodna čvor koji gledate

592
00:30:23,280 --> 00:30:24,340
je također bio tamo.

593
00:30:24,340 --> 00:30:25,830
Svatko dobro s tim?

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

595
00:30:26,500 --> 00:30:28,000
>> Kako o umetanja u kraj?

596
00:30:28,000 --> 00:30:34,220
Ako sam htjela dodati here-- ako sam htjela
dodati novi čvor na kraj popisa,

597
00:30:34,220 --> 00:30:37,009
kako bih mogao ići oko radiš to?

598
00:30:37,009 --> 00:30:39,300
PUBLIKA: Pa trenutno je
Posljednji je ukazao na nulu.

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

600
00:30:40,960 --> 00:30:43,560
Točno, tako da je ovo jedan
Trenutno je istakao da zna,

601
00:30:43,560 --> 00:30:46,720
pa mislim, u tom smislu, to je
vrlo lako dodati na kraj popisa.

602
00:30:46,720 --> 00:30:51,810
Sve što trebate učiniti je postaviti
jednak null a onda bum.

603
00:30:51,810 --> 00:30:53,070
Upravo tamo, vrlo jednostavno.

604
00:30:53,070 --> 00:30:53,960
Vrlo jednostavno.

605
00:30:53,960 --> 00:30:56,430
>> Vrlo sličan
glavu, ali logično vas

606
00:30:56,430 --> 00:30:59,690
želite biti sigurni da su koraci
što se prema radili bilo što od toga,

607
00:30:59,690 --> 00:31:01,500
ste sljedeće zajedno.

608
00:31:01,500 --> 00:31:04,420
To je vrlo lako, u sredini
vašeg koda, dobiti uhvaćen na,

609
00:31:04,420 --> 00:31:05,671
oh, imam toliko naputke.

610
00:31:05,671 --> 00:31:07,461
Ne znam gdje
sve ukazuje na.

611
00:31:07,461 --> 00:31:09,170
Ne znam ni što čvor sam na.

612
00:31:09,170 --> 00:31:11,490
Što se događa?

613
00:31:11,490 --> 00:31:13,620
>> Opustite se, smiri se, duboko udahnite.

614
00:31:13,620 --> 00:31:15,530
Nacrtaj svoj popis povezane.

615
00:31:15,530 --> 00:31:18,800
Ako kažem, ja znam gdje je točno
Moram umetnuti to u

616
00:31:18,800 --> 00:31:22,970
i znam točno kako preraspodijeliti moj
pokazivače, mnogo, mnogo lakše zamisliti

617
00:31:22,970 --> 00:31:27,200
out-- mnogo, mnogo lakše ne
izgubiti u bugova vašeg koda.

618
00:31:27,200 --> 00:31:29,410
Svatko u redu s tim?

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

620
00:31:31,380 --> 00:31:35,120
>> Pa valjda koncept koji nemamo
stvarno razgovarali o do sada,

621
00:31:35,120 --> 00:31:38,131
i ja ti valjda vjerojatno
neće naići na mnogo yet--

622
00:31:38,131 --> 00:31:40,880
to je vrsta naprednog concept--
je da mi zapravo imaju podatke

623
00:31:40,880 --> 00:31:43,900
Struktura naziva popisa za dvostruko povezani.

624
00:31:43,900 --> 00:31:46,390
Dakle, kao što vi vidite,
sve što radite je da stvarate

625
00:31:46,390 --> 00:31:50,400
stvarna vrijednost, dodatni
pokazivač na svaki od naših čvorova

626
00:31:50,400 --> 00:31:52,660
koja također ukazuje na prethodni čvor.

627
00:31:52,660 --> 00:31:58,170
Dakle, ne samo da mi imamo
čvorovi upućuju na sljedeću.

628
00:31:58,170 --> 00:32:01,430
Oni također ukazuju na prethodni.

629
00:32:01,430 --> 00:32:04,310
Idem ignorirati ta dva sada.

630
00:32:04,310 --> 00:32:06,740
>> Pa onda imate lanac
koji može kretati u oba smjera,

631
00:32:06,740 --> 00:32:09,630
a onda je malo lakše
logički slijediti zajedno.

632
00:32:09,630 --> 00:32:11,896
Kao i ovdje, umjesto
praćenje, oh,

633
00:32:11,896 --> 00:32:14,520
moraju znati da je ovaj čvor
onaj koji moram preraspodijeliti,

634
00:32:14,520 --> 00:32:17,532
Ja samo mogu ići ovdje i
Samo povucite prethodni.

635
00:32:17,532 --> 00:32:19,490
Tada znam točno gdje
da je, a onda vam

636
00:32:19,490 --> 00:32:21,130
ne moraju proći
cjelokupnost popisa povezane.

637
00:32:21,130 --> 00:32:22,180
To je malo lakše.

638
00:32:22,180 --> 00:32:24,960
>> Ali kao takva, imate dvostruko
iznos pokazivača,

639
00:32:24,960 --> 00:32:26,960
to je dvostruka količina memorije.

640
00:32:26,960 --> 00:32:28,950
To je puno naputke za praćenje.

641
00:32:28,950 --> 00:32:32,140
To je malo složeniji, ali to je
malo više user friendly, ovisno

642
00:32:32,140 --> 00:32:34,080
na ono što pokušavate postići.

643
00:32:34,080 --> 00:32:36,910
>> Dakle, ova vrsta podataka
Struktura totalno postoji,

644
00:32:36,910 --> 00:32:40,280
a struktura je vrlo, vrlo
Jednostavan osim sve što imate je,

645
00:32:40,280 --> 00:32:43,850
umjesto samo pokazivač na sljedeći,
imate i pokazivač na prethodni.

646
00:32:43,850 --> 00:32:45,940
To je sve što je razlika je.

647
00:32:45,940 --> 00:32:47,740
Svatko dobro s tim?

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
>> U redu, sada sam
stvarno provesti vjerojatno

651
00:32:53,280 --> 00:32:56,870
kao i 15 do 20 minuta ili skupno
ostatka vremena u dijelu

652
00:32:56,870 --> 00:32:58,360
govori o hash tablica.

653
00:32:58,360 --> 00:33:02,590
Koliko od vas
Pročitao pset5 spec?

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

655
00:33:03,620 --> 00:33:06,160
To je veći od 50% normalno.

656
00:33:06,160 --> 00:33:07,560
Uredu je.

657
00:33:07,560 --> 00:33:10,345
>> Dakle, kao što će ti dečki vide,
ti si izazov u pset5

658
00:33:10,345 --> 00:33:16,790
će provesti rječnik
gdje se učitati preko 140.000 riječi

659
00:33:16,790 --> 00:33:20,610
da ćemo vam dati i provjere pravopisa
je protiv svih teksta.

660
00:33:20,610 --> 00:33:22,580
Mi ćemo vam dati slučajni
komada književnosti.

661
00:33:22,580 --> 00:33:23,520
Mi ćemo vam dati Odiseji.

662
00:33:23,520 --> 00:33:24,561
Mi ćemo vam dati Ilijadi.

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

664
00:33:26,350 --> 00:33:28,220
>> I vaš izazov
bit će da provjere pravopisa

665
00:33:28,220 --> 00:33:31,760
svaka riječ u svemu
od onih rječnika

666
00:33:31,760 --> 00:33:34,960
u biti s našim provjeru pravopisa.

667
00:33:34,960 --> 00:33:38,620
I tako postoji nekoliko dijelova
stvaranja ovog pset,

668
00:33:38,620 --> 00:33:41,970
Prvi želite biti
mogućnosti da se zapravo učitavanje

669
00:33:41,970 --> 00:33:43,970
sve riječi u svoj
rječnik, a onda vam

670
00:33:43,970 --> 00:33:45,530
želite biti u mogućnosti
provjeru pravopisa sve njih.

671
00:33:45,530 --> 00:33:48,780
I tako kao takva, ti si idući u zahtijevaju
data struktura koja može učiniti brzo

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

673
00:33:50,790 --> 00:33:52,900
>> Pa valjda najlakše
način da to učinite, te

674
00:33:52,900 --> 00:33:55,010
vjerojatno stvoriti niz, zar ne?

675
00:33:55,010 --> 00:33:58,910
Najlakši način za pohranu je vas
može stvoriti niz 140.000 riječi

676
00:33:58,910 --> 00:34:03,400
i samo ih stavite tamo i
zatim ih poprijeko po binarnom pretraživanje

677
00:34:03,400 --> 00:34:06,780
ili selekcija ili not--
žao da je razvrstavanje.

678
00:34:06,780 --> 00:34:10,729
Možete ih sortirati, a zatim ih poprijeko
binarnim pretraživanje ili jednostavno linearno pretraživanje

679
00:34:10,729 --> 00:34:13,730
i samo završne riječi, no to
ima veliku količinu memorije,

680
00:34:13,730 --> 00:34:15,190
i to ne jako učinkovit.

681
00:34:15,190 --> 00:34:18,350
>> I tako ćemo početi
govorimo o načinima izrade

682
00:34:18,350 --> 00:34:20,110
naša trčanje vrijeme učinkovitije.

683
00:34:20,110 --> 00:34:23,190
A naš cilj je dobiti
konstanta vrijeme u kojem

684
00:34:23,190 --> 00:34:25,810
to je gotovo kao polja, gdje
imate trenutačan pristup.

685
00:34:25,810 --> 00:34:28,560
Da sam htio tražiti bilo što,
Želim biti u mogućnosti jednostavno,

686
00:34:28,560 --> 00:34:30,810
bum, pronašli ga baš i izvucite ga.

687
00:34:30,810 --> 00:34:34,100
I tako je struktura u kojoj
ćemo postati vrlo blizu

688
00:34:34,100 --> 00:34:37,569
da bi mogli pristupiti konstanta
Vrijeme, taj sveti gral

689
00:34:37,569 --> 00:34:41,370
u programiranju konstanta
Vrijeme se naziva hash tablicu.

690
00:34:41,370 --> 00:34:45,370
I tako David ranije spomenuo
[Nečujan] malo u predavanju,

691
00:34:45,370 --> 00:34:49,100
ali ćemo stvarno
zaronite duboko u ovom tjednu

692
00:34:49,100 --> 00:34:51,780
na komad koji je u vezi
kako hash tablicu radi.

693
00:34:51,780 --> 00:34:53,949
>> Dakle, na način da se rasprsne
stol djela, primjerice,

694
00:34:53,949 --> 00:35:00,230
ako sam htjela spremiti hrpa riječima,
hrpa riječi na engleskom jeziku,

695
00:35:00,230 --> 00:35:02,940
Ja teoretski mogao staviti
banane, jabuke, kivi, mango, par,

696
00:35:02,940 --> 00:35:04,980
i dinja sve na samo polje.

697
00:35:04,980 --> 00:35:07,044
Svi su mogli uklopiti i biti pronaći.

698
00:35:07,044 --> 00:35:09,210
Bilo bi vrsta boli
pretraživanje i pristup,

699
00:35:09,210 --> 00:35:12,920
ali lakši način za to je
da možemo stvoriti zapravo struktura

700
00:35:12,920 --> 00:35:15,680
naziva hash tablicu gdje smo razmotrili.

701
00:35:15,680 --> 00:35:19,880
Mi pokrenuti sve naše tipke kroz
hash funkcija, jednadžba,

702
00:35:19,880 --> 00:35:22,600
da ih sve pretvara u
nekakva vrijednost

703
00:35:22,600 --> 00:35:28,740
kako onda možemo pohraniti na
u biti niz povezanih popisa.

704
00:35:28,740 --> 00:35:32,570
>> I tako ovdje, ako smo htjeli
pohraniti engleske riječi,

705
00:35:32,570 --> 00:35:37,250
smo mogli potencijalno jednostavno, ja ne
Znaš, uključiti sve prva slova

706
00:35:37,250 --> 00:35:39,630
u nekakvu nizu.

707
00:35:39,630 --> 00:35:43,140
I tako, na primjer, ako želim
A do sinonim apple--

708
00:35:43,140 --> 00:35:47,460
ili s indeksom od 0, i
B sinonim 1,

709
00:35:47,460 --> 00:35:51,030
možemo imati 26 unose
samo da može pohraniti

710
00:35:51,030 --> 00:35:53,610
sva slova
abeceda da ćemo početi s.

711
00:35:53,610 --> 00:35:56,130
A onda možemo imati
Apple na indeks 0.

712
00:35:56,130 --> 00:35:59,160
Možemo imati bananu na indeks
1, dinja na indeks 2,

713
00:35:59,160 --> 00:36:00,540
i tako dalje i tako dalje.

714
00:36:00,540 --> 00:36:04,460
I tako, ako sam htjela za pretraživanje
moj hash tablicu i pristup jabuka,

715
00:36:04,460 --> 00:36:07,560
Znam Apple počinje s
A klase, i znam točno

716
00:36:07,560 --> 00:36:10,860
da to mora biti i ljestve
stol u indeksu 0 zato

717
00:36:10,860 --> 00:36:13,620
funkcije prethodno dodijeljen.

718
00:36:13,620 --> 00:36:16,572
>> Pa ne znam, mi smo
user program u kojem

719
00:36:16,572 --> 00:36:18,780
ćete biti optužen
arbitrarily-- ne proizvoljno,

720
00:36:18,780 --> 00:36:22,530
pokušaj zamišljeno
mislim dobrih jednadžbi

721
00:36:22,530 --> 00:36:25,460
se moći širiti
iz sve svoje vrijednosti

722
00:36:25,460 --> 00:36:29,370
na način da se lako može pristupiti
što kasnije s poput jednadžbe

723
00:36:29,370 --> 00:36:31,130
da tebe, sebe, znate.

724
00:36:31,130 --> 00:36:35,210
Dakle, u tom smislu, ako sam htjela ići
mango, znam, oh, to počinje s m.

725
00:36:35,210 --> 00:36:37,134
To mora biti u indeksu od 12 godina.

726
00:36:37,134 --> 00:36:38,800
Ja ne moram tražiti kroz sve.

727
00:36:38,800 --> 00:36:42,080
Znam exactly-- samo sam mogao ići na
indeks 12 i povucite da van.

728
00:36:42,080 --> 00:36:45,520
>> Svatko jasno kako
Funkcija hash tablicu djela?

729
00:36:45,520 --> 00:36:48,380
To je vrsta samo složenije polje.

730
00:36:48,380 --> 00:36:50,010
To je sve što je.

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

732
00:36:51,630 --> 00:36:57,690
>> Dakle, mislim da naletimo
ovo pitanje o tome što

733
00:36:57,690 --> 00:37:06,390
dogoditi ako imate više stvari
da vam dati isti indeks?

734
00:37:06,390 --> 00:37:10,570
Tako kažu naše djelovanje, a sve to
učinio je poduzeti prvi pismo

735
00:37:10,570 --> 00:37:14,490
i da se uključite u
Dotični 0 do 25 indeks.

736
00:37:14,490 --> 00:37:17,137
To je sasvim u redu, ako
imate samo jedan od svakog.

737
00:37:17,137 --> 00:37:18,970
Ali drugi počnete
ima više, ti si

738
00:37:18,970 --> 00:37:20,910
će imati ono što se zove sudara.

739
00:37:20,910 --> 00:37:25,580
>> Dakle, ako ja pokušati umetnuti zakopati u hash
Tablica koja već ima bananu na njega,

740
00:37:25,580 --> 00:37:27,870
što će se dogoditi kada
pokušate umetnuti to?

741
00:37:27,870 --> 00:37:30,930
Loše stvari jer banane
već postoji u indeksu

742
00:37:30,930 --> 00:37:33,800
da želite ga pohraniti u.

743
00:37:33,800 --> 00:37:35,560
Berry vrsta je kao, ah, što da radim?

744
00:37:35,560 --> 00:37:37,080
Ne znam gdje da ide.

745
00:37:37,080 --> 00:37:38,410
Kako riješiti ovo?

746
00:37:38,410 --> 00:37:41,150
>> I tako vi vrsta volje
vidjet ćemo učiniti škakljivo

747
00:37:41,150 --> 00:37:44,810
Gdje možemo vrsta zapravo
stvoriti povezani popis u našim poljima.

748
00:37:44,810 --> 00:37:46,840
I tako je najlakše
razmišljati o tome,

749
00:37:46,840 --> 00:37:50,830
Sve hash tablica je
niz povezanih liste.

750
00:37:50,830 --> 00:37:55,670
I tako, u tom smislu, imate
ovaj lijepi niz pokazivača,

751
00:37:55,670 --> 00:37:58,740
i onda svaki pokazivač u
da se vrijednost, u tom indeksu,

752
00:37:58,740 --> 00:38:00,740
zapravo može ukazati na druge stvari.

753
00:38:00,740 --> 00:38:05,720
I tako imate sve ove odvojene
lanci dolaze izvan jedan veliki niz.

754
00:38:05,720 --> 00:38:07,960
>> I tako ovdje, ako sam
htjela umetnuti bobica,

755
00:38:07,960 --> 00:38:11,220
Znam, u redu, ja idem za unos
je kroz moje hash funkcije.

756
00:38:11,220 --> 00:38:15,070
Idem završiti s indeksom
1, a onda ću biti u mogućnosti da imaju

757
00:38:15,070 --> 00:38:20,410
samo manji podskup toga
div rječnik 140.000-riječ.

758
00:38:20,410 --> 00:38:24,220
A onda ja samo mogu gledati
kroz 1/26 toga.

759
00:38:24,220 --> 00:38:27,910
>> I tako onda sam jednostavno možete umetnuti
bobica bilo prije ili poslije banana

760
00:38:27,910 --> 00:38:28,820
u ovom slučaju?

761
00:38:28,820 --> 00:38:29,700
Nakon, zar ne?

762
00:38:29,700 --> 00:38:33,920
I tako idete želite
umetnite ovaj čvor nakon banani,

763
00:38:33,920 --> 00:38:36,667
pa ti si idući umetnuti
na repu tog vezanog popisa.

764
00:38:36,667 --> 00:38:38,500
Idem se vratiti
ovaj prethodni slajd,

765
00:38:38,500 --> 00:38:40,680
tako da vi možete vidjeti kako
hash funkcija radi.

766
00:38:40,680 --> 00:38:43,980
>> Dakle hash funkcija je ova jednadžba
da radite kakve vašeg unosa

767
00:38:43,980 --> 00:38:46,940
do dobiti sve što indeksa
Želite li ga dodijeliti prema.

768
00:38:46,940 --> 00:38:51,130
I tako, u ovom primjeru, sve što smo htjeli
učiniti je uzeti prvo pismo,

769
00:38:51,130 --> 00:38:55,890
da se uključite u indeks, onda smo
može pohraniti da u našem hash funkcije.

770
00:38:55,890 --> 00:39:00,160
Sve što radite ovdje smo
pretvaranje prvo slovo.

771
00:39:00,160 --> 00:39:04,770
Dakle keykey [0] je samo prvo slovo
bez obzira na niz koju smo ima,

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

773
00:39:05,720 --> 00:39:09,740
Mi smo pretvaranja da se gornji i
mi smo oduzimanjem od verzalnog A,

774
00:39:09,740 --> 00:39:11,740
tako da sve što radi
daje nam broj

775
00:39:11,740 --> 00:39:13,670
u kojem možemo hash naše vrijednosti na.

776
00:39:13,670 --> 00:39:16,550
>> A onda ćemo
povratak hash modul čvrstoće veličine.

777
00:39:16,550 --> 00:39:19,340
Budite vrlo, vrlo oprezni
jer, teoretski, ovdje

778
00:39:19,340 --> 00:39:21,870
Vaš hash vrijednost može biti beskonačan.

779
00:39:21,870 --> 00:39:23,660
To može samo ići na i na i na.

780
00:39:23,660 --> 00:39:26,080
To bi mogao biti neki jako,
stvarno velika vrijednost,

781
00:39:26,080 --> 00:39:29,849
ali zbog vaše hash tablicu koja
ste stvorili ima samo 26 indeksa,

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

783
00:39:31,890 --> 00:39:33,848
ne run-- to isto
stvar kao queue--

784
00:39:33,848 --> 00:39:36,320
tako da ne pokrenuti off
Dno vašeg hash funkcije.

785
00:39:36,320 --> 00:39:39,210
>> Želite zamotati natrag oko
na isti način u [nečujan] kada

786
00:39:39,210 --> 00:39:41,750
ste imali kao vrlo,
vrlo velika slova, što

787
00:39:41,750 --> 00:39:43,740
nije želio da se
samo pokrenuti off kraj.

788
00:39:43,740 --> 00:39:46,948
Ista stvar ovdje, želite da biste bili sigurni
ne trude kraj omatanje

789
00:39:46,948 --> 00:39:48,330
oko vrha stola.

790
00:39:48,330 --> 00:39:50,530
Dakle, ovo je samo vrlo
Jednostavan hash funkcija.

791
00:39:50,530 --> 00:39:56,570
Sve što je učinio je poduzeti prvi
pismo bilo naše ulaz je

792
00:39:56,570 --> 00:40:01,660
i da se uključite u indeksu koji
možemo staviti u našem hash tablicu.

793
00:40:01,660 --> 00:40:05,450
>> Da, pa kao što sam rekao prije,
način na koji smo riješili sudara

794
00:40:05,450 --> 00:40:09,330
u našem hash su tablice s,
Ono što mi zovemo, ulančavanje.

795
00:40:09,330 --> 00:40:13,860
Dakle, ako pokušate umetnuti višestruki
Riječi koje počinju s iste stvari,

796
00:40:13,860 --> 00:40:16,145
ti si idući u imati jedan hash vrijednosti.

797
00:40:16,145 --> 00:40:18,770
Avokado i jabuke, ako ste
pokrenite ga kroz naše hash funkcija,

798
00:40:18,770 --> 00:40:21,450
će vam dati
Isti broj, broj 0.

799
00:40:21,450 --> 00:40:24,550
I tako je način na koji smo riješili da je
da zapravo možemo vrsta ih povezati

800
00:40:24,550 --> 00:40:27,010
zajedno preko povezanih liste.

801
00:40:27,010 --> 00:40:29,600
>> I tako u tom smislu,
vi možete vidjeti kakav

802
00:40:29,600 --> 00:40:32,640
kako strukture podataka koje
smo postavljanje prethodno

803
00:40:32,640 --> 00:40:35,870
poput grožđica povezani popis vrsta
od mogu udružiti u jedan.

804
00:40:35,870 --> 00:40:38,860
A onda možete stvoriti daleko
učinkovitije strukture podataka

805
00:40:38,860 --> 00:40:43,350
koja se može nositi veće količine
podataka, koja dinamički promijeniti veličinu ovisno

806
00:40:43,350 --> 00:40:44,870
o Vašim potrebama.

807
00:40:44,870 --> 00:40:45,620
Svatko jasno?

808
00:40:45,620 --> 00:40:47,580
Svatko vrsta jasan
na ono što se događa ovdje?

809
00:40:47,580 --> 00:40:52,110
>> Ako sam htjela insert-- što je
voće koje počinje s, ne znam,

810
00:40:52,110 --> 00:40:54,726
B, osim bobica, banane.

811
00:40:54,726 --> 00:40:55,710
>> PUBLIKA: BlackBerry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI PENG: BlackBerry, BlackBerry.

813
00:40:57,910 --> 00:41:00,530
Gdje kupina ide ovdje?

814
00:41:00,530 --> 00:41:04,251
Pa, mi zapravo nisu razvrstani
to još, ali teoretski

815
00:41:04,251 --> 00:41:06,250
ako smo htjeli da se ovaj
abecednim redom,

816
00:41:06,250 --> 00:41:07,944
gdje bi BLACKBERRY ići?

817
00:41:07,944 --> 00:41:09,210
>> PUBLIKA: [nečujan]

818
00:41:09,210 --> 00:41:11,100
>> ANDI PENG: Točno, nakon što se ovdje, zar ne?

819
00:41:11,100 --> 00:41:14,950
No, budući da je vrlo teško
reorder-- Mislim da je do vas dečki.

820
00:41:14,950 --> 00:41:17,920
Vi možete u potpunosti
provesti što god želite.

821
00:41:17,920 --> 00:41:20,730
Učinkovitiji način
za to možda

822
00:41:20,730 --> 00:41:24,570
bi se razvrstati vaš povezani
popis u abecednom redu,

823
00:41:24,570 --> 00:41:26,520
pa kad si
umetanja stvari, što želite

824
00:41:26,520 --> 00:41:28,632
biti sigurni da ih stavite
u abecednom redu

825
00:41:28,632 --> 00:41:30,590
pa onda kada ste
pokušavajući ih traži,

826
00:41:30,590 --> 00:41:32,410
ne morate proći sve.

827
00:41:32,410 --> 00:41:35,290
Znaš točno gdje
je, i to je lakše.

828
00:41:35,290 --> 00:41:39,100
>> Ali, ako ste vrsta ima
stvari mjestimice slučajno,

829
00:41:39,100 --> 00:41:41,420
i dalje ćeš imati
to proći ionako.

830
00:41:41,420 --> 00:41:44,990
I tako, ako sam htjela samo
umetnite kupina ovdje

831
00:41:44,990 --> 00:41:47,470
i ja sam htjela za pretragu
da, znam, oh, kupina

832
00:41:47,470 --> 00:41:52,012
mora započeti s indeksom 1, pa sam
znam trenutačno samo traži na 1.

833
00:41:52,012 --> 00:41:53,970
I onda ja mogu nekako
prošli popis povezan

834
00:41:53,970 --> 00:41:56,120
dok sam se na BlackBerry,
i then-- da?

835
00:41:56,120 --> 00:41:59,550
>> PUBLIKA: Ako pokušavate create--
Mislim da kao što je to vrlo jednostavna hash

836
00:41:59,550 --> 00:42:00,050
funkcija.

837
00:42:00,050 --> 00:42:02,835
A ako smo htjeli napraviti
višestruke razine da kao,

838
00:42:02,835 --> 00:42:05,870
U redu, želimo odvojiti u
kao i svi znakovi abecede

839
00:42:05,870 --> 00:42:09,040
a onda opet voljeti drugu set
od abecednom slova unutar koje,

840
00:42:09,040 --> 00:42:11,715
smo stavljajući se kao hash
Tablica u hash tablici,

841
00:42:11,715 --> 00:42:13,256
ili poput funkcije u funkciju?

842
00:42:13,256 --> 00:42:14,880
Ili je that--

843
00:42:14,880 --> 00:42:17,510
>> ANDI PENG: Pa vašem hash
function-- svoj hash tablicu

844
00:42:17,510 --> 00:42:19,360
može biti tako velika kao što želite da.

845
00:42:19,360 --> 00:42:21,930
Dakle, u tom smislu, mislio sam
to je vrlo jednostavno, vrlo

846
00:42:21,930 --> 00:42:25,320
jednostavno mi se samo vrsta temelji
na slova prve riječi.

847
00:42:25,320 --> 00:42:28,690
I tako postoji samo 26 opcija.

848
00:42:28,690 --> 00:42:32,650
Ja mogu samo dobiti 26 opcija
0 do 25, jer oni mogu samo

849
00:42:32,650 --> 00:42:36,510
početi od A do Z. Ali ako ste željeli
dodati, možda, više složenosti

850
00:42:36,510 --> 00:42:39,260
ili brži trčanje vremena da svoje
hash tablicu, apsolutno

851
00:42:39,260 --> 00:42:40,760
mogu učiniti sve i svašta.

852
00:42:40,760 --> 00:42:43,330
Možete napraviti svoj vlastiti
jednadžba koja vam daje

853
00:42:43,330 --> 00:42:48,000
više distribucija u svom
Riječi, onda kada se traži,

854
00:42:48,000 --> 00:42:49,300
to će biti brže.

855
00:42:49,300 --> 00:42:52,100
>> To je totalno do vas dečki
kako želite provesti to.

856
00:42:52,100 --> 00:42:55,140
Razmislite o tome kako je samo kante.

857
00:42:55,140 --> 00:42:57,376
Da sam htio imati
26 kante, idem

858
00:42:57,376 --> 00:42:59,420
sortiranje stvari u te kante.

859
00:42:59,420 --> 00:43:02,980
Ali ja ću imati hrpu
stvari u svakoj ćeliji,

860
00:43:02,980 --> 00:43:05,890
pa ako želite to učiniti
brže i učinkovitije,

861
00:43:05,890 --> 00:43:07,190
neka mi se sto kante.

862
00:43:07,190 --> 00:43:09,290
>> Ali onda morate shvatiti
način za sortiranje stvari, tako da su

863
00:43:09,290 --> 00:43:11,040
u pravilnom kantu oni bi trebali biti u.

864
00:43:11,040 --> 00:43:13,331
Ali onda zapravo kada
želite pogledati tu kantu,

865
00:43:13,331 --> 00:43:16,410
to je puno brže, jer postoji
manje stvari u svakoj ćeliji.

866
00:43:16,410 --> 00:43:20,250
I tako, da, to je zapravo
trik za vas dečki u pset5

867
00:43:20,250 --> 00:43:22,360
je da ćete biti
izazov da samo stvoriti

868
00:43:22,360 --> 00:43:26,170
bilo je najučinkovitiji
Funkcija možete sjetiti da se

869
00:43:26,170 --> 00:43:28,520
mogli pohraniti i provjeriti te vrijednosti.

870
00:43:28,520 --> 00:43:30,840
>> Totalno do vas dečki
Međutim želite to učiniti,

871
00:43:30,840 --> 00:43:32,229
ali to je stvarno dobra stvar.

872
00:43:32,229 --> 00:43:34,520
To je vrsta logike koju
želim početi razmišljati o

873
00:43:34,520 --> 00:43:37,236
je, dobro, zašto ne bih napraviti još kante.

874
00:43:37,236 --> 00:43:39,527
I onda moram tražiti
manje stvari, a onda možda sam

875
00:43:39,527 --> 00:43:41,640
imaju različite hash funkcije.

876
00:43:41,640 --> 00:43:45,500
>> Da, postoji mnogo načina za to
pset, neki su brži od drugih.

877
00:43:45,500 --> 00:43:50,630
Ja sam totalno ću samo vidjeti kako
brzo je bio najbrži vi ćete

878
00:43:50,630 --> 00:43:55,170
biti u mogućnosti da biste dobili vaše funkcionira na posao.

879
00:43:55,170 --> 00:43:58,176
U redu, svi dobro na
ulančavanje i hash tablice?

880
00:43:58,176 --> 00:44:00,800
To je zapravo kao vrlo jednostavan
koncept ako mislite o tome.

881
00:44:00,800 --> 00:44:05,160
Sve to je odvajanje bilo
Vaši ulaza u kante,

882
00:44:05,160 --> 00:44:10,670
ih sortiranje, a zatim u potrazi
navodi da je povezana s.

883
00:44:10,670 --> 00:44:11,852
>> Cool.

884
00:44:11,852 --> 00:44:18,160
U redu, sada imamo različite vrste
strukture podataka koji se zove stablo.

885
00:44:18,160 --> 00:44:20,850
Idemo dalje i pričati o pokušaja
koji su izrazito različiti,

886
00:44:20,850 --> 00:44:22,330
ali u istoj kategoriji.

887
00:44:22,330 --> 00:44:29,010
U suštini, sve drvo je umjesto
organiziranja podataka na linearni način

888
00:44:29,010 --> 00:44:32,560
da hash tablicu vas does--
Znate, to je dobio vrh i dno

889
00:44:32,560 --> 00:44:37,900
i onda nekako povezati off it-- u
Stablo ima top koji nazoveš korijen,

890
00:44:37,900 --> 00:44:40,220
a onda je sve lišće oko njega.

891
00:44:40,220 --> 00:44:42,390
>> I tako sve što imamo ovdje
je samo vrh čvor

892
00:44:42,390 --> 00:44:45,980
koji ukazuje na druge čvorove, koji ukazuje
na više čvorova, i tako dalje i tako dalje.

893
00:44:45,980 --> 00:44:48,130
I tako ste upravo cijepanje grane.

894
00:44:48,130 --> 00:44:53,255
To je samo drugačiji način organiziranja
podataka, i zato što je to stablo poziv,

895
00:44:53,255 --> 00:44:56,270
vi just-- to je samo
po uzoru na izgleda kao drvo.

896
00:44:56,270 --> 00:44:57,670
Zato smo ga nazvati stabala.

897
00:44:57,670 --> 00:44:59,370
>> Hash tablicu izgleda kao stol.

898
00:44:59,370 --> 00:45:01,310
Stablo samo izgleda kao drvo.

899
00:45:01,310 --> 00:45:03,300
Sve je to je zasebna
način organiziranja čvorova

900
00:45:03,300 --> 00:45:06,020
ovisno o tome što su vaše potrebe.

901
00:45:06,020 --> 00:45:11,810
>> Dakle, imate korijen i
onda imate lišće.

902
00:45:11,810 --> 00:45:15,380
Način na koji možemo posebno
mislim o tome je binarno stablo,

903
00:45:15,380 --> 00:45:18,150
binarno stablo je samo
specifična vrsta drveta

904
00:45:18,150 --> 00:45:22,450
gdje svaki čvor samo točke
da, na max, druga dva čvora.

905
00:45:22,450 --> 00:45:25,434
I tako ovdje imate različita
simetrija u vašem stablo

906
00:45:25,434 --> 00:45:28,600
koji olakšava vrsta izgleda
na ono vrijednosti ste jer onda

907
00:45:28,600 --> 00:45:30,150
ima uvijek lijevo ili desno.

908
00:45:30,150 --> 00:45:33,150
Tu je nikad kao lijevoj trećini od
lijevi ili četvrti s lijeva.

909
00:45:33,150 --> 00:45:36,358
To je samo imate lijevo i pravo
i možete tražiti bilo koji od ta dva.

910
00:45:36,358 --> 00:45:38,980
A zašto je to korisno?

911
00:45:38,980 --> 00:45:40,980
Način na koji je to
korisno je ako ste u potrazi

912
00:45:40,980 --> 00:45:42,890
pretraživati ​​vrijednosti, zar ne?

913
00:45:42,890 --> 00:45:45,640
Umjesto provedbe binarni
traži u polje pogreške,

914
00:45:45,640 --> 00:45:49,260
ako ste htjeli biti u mogućnosti da ubacite čvorova
i oduzeti čvorova po volji i

915
00:45:49,260 --> 00:45:52,185
sačuvati pretraživanje
Kapaciteti binarnog pretraživanja.

916
00:45:52,185 --> 00:45:54,560
Dakle, na ovaj način, mi smo vrsta
tricking-- sjećam se kad smo

917
00:45:54,560 --> 00:45:56,530
rekao povezani popisi ne mogu binarno pretraživanje?

918
00:45:56,530 --> 00:46:01,700
Mi smo vrsta stvarajući strukturu podataka
da imate to u radi.

919
00:46:01,700 --> 00:46:05,034
>> I zato povezani popisi su linearni,
oni povezuju samo jedan za drugim.

920
00:46:05,034 --> 00:46:06,950
Možemo vrsta ima
različita vrsta pokazivača

921
00:46:06,950 --> 00:46:09,408
koji ukazuju na različitim čvorovima
koji nam mogu pomoći u traženju.

922
00:46:09,408 --> 00:46:12,590
I tako ovdje, ako sam htjela
imaju pretraživanje po binarnom stablu,

923
00:46:12,590 --> 00:46:14,090
Znam da moje sredine, ako 55.

924
00:46:14,090 --> 00:46:18,280
Samo ću napraviti da
kao moj sredini, kao moj korijen,

925
00:46:18,280 --> 00:46:20,770
a onda ću imati
Vrijednosti spin off od njega.

926
00:46:20,770 --> 00:46:25,610
>> Dakle ovdje, ako ću tražiti
vrijednost od 66, mogu započeti u 55.

927
00:46:25,610 --> 00:46:27,310
To je 66 veći od 55?

928
00:46:27,310 --> 00:46:30,970
Da je to tako znam da mus pretragu
ja n pravo pokazivač ovog stabla.

929
00:46:30,970 --> 00:46:32,440
Idem na 77.

930
00:46:32,440 --> 00:46:35,367
Dobro je manji od 66 ili više od 77?

931
00:46:35,367 --> 00:46:37,950
To je manje nego, tako da znate, oh,
to mora biti lijevo čvor.

932
00:46:37,950 --> 00:46:41,410
>> I tako ovdje smo vrsta očuvanja
sve velike stvari o polja,

933
00:46:41,410 --> 00:46:44,420
pa kao dinamičke promjene veličine
objekata, što

934
00:46:44,420 --> 00:46:49,530
mogućnosti za umetanje i brisanje po volji,
bez brige o fiksnoj

935
00:46:49,530 --> 00:46:50,370
Količina prostora.

936
00:46:50,370 --> 00:46:52,820
Još uvijek čuvaju sve
one čudesa

937
00:46:52,820 --> 00:46:57,140
a također je u mogućnosti sačuvati
prijavite i traži vrijeme binarnog pretraživanja

938
00:46:57,140 --> 00:47:00,450
da mi je samo prije
mogućnosti da biste dobili izraz.

939
00:47:00,450 --> 00:47:06,310
>> Cool struktura podataka, vrsta
Kompleks provesti, čvor.

940
00:47:06,310 --> 00:47:08,311
Kao što možete vidjeti, sve to
je struct čvora

941
00:47:08,311 --> 00:47:10,143
je da imate lijevo
i pravo pokazivač.

942
00:47:10,143 --> 00:47:11,044
To je sve što je.

943
00:47:11,044 --> 00:47:12,960
Dakle, umjesto da samo
ima x ili prethodni.

944
00:47:12,960 --> 00:47:15,920
Imate lijevu ili pravo, a zatim
što vrste ih može povezati zajedno

945
00:47:15,920 --> 00:47:16,836
No tako odlučite.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> U redu, mi zapravo ide
samo potrajati nekoliko minuta.

948
00:47:24,270 --> 00:47:25,790
Tako ćemo se vratiti ovdje.

949
00:47:25,790 --> 00:47:28,270
Kao što sam rekao ranije,
Nekako sam objasnio

950
00:47:28,270 --> 00:47:31,520
logika iza kako smo
će tražiti kroz to.

951
00:47:31,520 --> 00:47:33,860
Idemo pokušati
pseudocoding ovo vidjeti

952
00:47:33,860 --> 00:47:38,000
ako možemo vrsta vrijedi
Ista logika binarnog pretraživanja

953
00:47:38,000 --> 00:47:40,055
na drugu vrstu strukture podataka.

954
00:47:40,055 --> 00:47:45,049
Ako vi želite uzeti kao par
minuta da samo razmišljam o tome.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
U REDU.

957
00:48:46,925 --> 00:48:51,407
U redu, ja ću
zapravo samo dati the-- ne,

958
00:48:51,407 --> 00:48:52,990
ćemo razgovarati o pseudokod prvi.

959
00:48:52,990 --> 00:48:56,580
Tako se bilo tko želite
dati ubosti na ono što

960
00:48:56,580 --> 00:49:02,100
prva stvar koju želite učiniti kada
ste početku potrazi je?

961
00:49:02,100 --> 00:49:04,460
Ako ste se u potrazi za
vrijednost od 66, što je

962
00:49:04,460 --> 00:49:07,940
prva stvar koju želite učiniti ako
želimo binarnog pretraživanja ovo drvo?

963
00:49:07,940 --> 00:49:10,760
>> PUBLIKA: Želite izgleda dobro
i gledati lijevo i vidjet [nečujan]

964
00:49:10,760 --> 00:49:11,230
veći broj.

965
00:49:11,230 --> 00:49:12,271
>> ANDI PENG: Da, točno.

966
00:49:12,271 --> 00:49:15,350
Dakle, ti ćeš gledati na korijenu.

967
00:49:15,350 --> 00:49:18,180
Postoji mnogo načina na koje možete nazvati
da, tvoj roditelj čvor ljudi kažu.

968
00:49:18,180 --> 00:49:21,317
Volim reći, jer korijen
to je kao korijen stabla.

969
00:49:21,317 --> 00:49:23,400
Ideš pogledati
vaša root čvor, a vi ste

970
00:49:23,400 --> 00:49:26,940
idući u vidjeti je 66 veći
od ili manje od 55.

971
00:49:26,940 --> 00:49:30,360
A ako je veći od, dobro, to je
veći od, na kojem želimo gledati?

972
00:49:30,360 --> 00:49:32,000
Gdje želimo tražiti, zar ne?

973
00:49:32,000 --> 00:49:34,340
Želimo za pretraživanje
Pravo polovica tog stabla.

974
00:49:34,340 --> 00:49:38,390
>> Tako smo, jednostavno, A
pokazivač koji pokazuje na desno.

975
00:49:38,390 --> 00:49:44,325
I tako onda možemo postaviti
naš novi korijen se 77.

976
00:49:44,325 --> 00:49:46,450
Mi samo možemo ići gdje god
pokazivač pokazuje.

977
00:49:46,450 --> 00:49:49,100
Pa, oh, ovdje mi počinjemo
na 77, a možemo samo

978
00:49:49,100 --> 00:49:51,172
to rekurzivno opet i opet.

979
00:49:51,172 --> 00:49:52,880
Na ovaj način, možete vrsta
od imati funkciju.

980
00:49:52,880 --> 00:49:57,430
Imate način traži da ti
mogu samo ponoviti iznova i iznova i iznova,

981
00:49:57,430 --> 00:50:02,720
ovisno o tome gdje želite pogledati
dok na kraju dobiti na vrijednosti

982
00:50:02,720 --> 00:50:04,730
da ste u potrazi za.

983
00:50:04,730 --> 00:50:05,230
Ima smisla?

984
00:50:05,230 --> 00:50:07,800
>> Ja sam o to pokazivanje stvarni
broj, a to je puno koda.

985
00:50:07,800 --> 00:50:08,674
Nema potrebe da se paliti.

986
00:50:08,674 --> 00:50:09,910
Razgovarat ćemo kroz njega.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Zapravo, ne.

989
00:50:14,020 --> 00:50:15,061
To je bio samo pseudokod.

990
00:50:15,061 --> 00:50:17,860
U redu, to je bio samo pseudokod,
što je malo složen,

991
00:50:17,860 --> 00:50:19,751
ali to je potpuno u redu.

992
00:50:19,751 --> 00:50:21,000
Svatko slijedi ovdje zajedno?

993
00:50:21,000 --> 00:50:24,260
Ako je korijen je null, povratak
netočno, jer to znači

994
00:50:24,260 --> 00:50:26,850
vi ne morate ništa tamo.

995
00:50:26,850 --> 00:50:31,376
>> Ako korijen n vrijednost, pa ako je to
se događa da se jedan gledaš,

996
00:50:31,376 --> 00:50:34,000
onda ćeš se vratiti istina
jer vi znate da ga pronašli.

997
00:50:34,000 --> 00:50:36,250
No, ako je vrijednost manja
od korijena n, ti si

998
00:50:36,250 --> 00:50:38,332
idući za pretraživanje lijevu
dijete ili lijevi list,

999
00:50:38,332 --> 00:50:39,540
što god želite nazvati.

1000
00:50:39,540 --> 00:50:41,750
A ako je vrijednost veća od korijena,
idete tražiti pravo drvo,

1001
00:50:41,750 --> 00:50:44,610
onda samo pokrenuti funkciju
kroz potragu opet.

1002
00:50:44,610 --> 00:50:48,037
>> I ako je korijen null, da je
znači što ste došli do kraja?

1003
00:50:48,037 --> 00:50:50,120
To znači da nemaju
više više listova za pretraživanje,

1004
00:50:50,120 --> 00:50:52,230
onda znate, oh,
Pretpostavljam da nije ovdje

1005
00:50:52,230 --> 00:50:55,063
jer nakon što sam pogledao kroz
cijela stvar i nije ovdje,

1006
00:50:55,063 --> 00:50:56,930
to jednostavno ne može biti ovdje.

1007
00:50:56,930 --> 00:50:58,350
>> Znači li to da smisla svima?

1008
00:50:58,350 --> 00:51:03,230
Dakle, to je kao binarnog pretraživanja konzerviranje
sposobnosti povezanih popisa.

1009
00:51:03,230 --> 00:51:09,200
Cool, pa drugi tip
Strukture podataka što dečki

1010
00:51:09,200 --> 00:51:13,180
možete pokušati provedbu na svom pset,
imate samo odabrati jedan način.

1011
00:51:13,180 --> 00:51:19,430
No, možda alternativna metoda za
hash tablicu je ono što mi nazivamo Trie.

1012
00:51:19,430 --> 00:51:24,080
>> Sve što je Trie je
specifična vrsta drveta koje

1013
00:51:24,080 --> 00:51:28,600
ima vrijednosti koje idu na drugim vrijednostima.

1014
00:51:28,600 --> 00:51:31,450
Dakle, umjesto da binarni
stablo u smislu da je samo jedan

1015
00:51:31,450 --> 00:51:35,940
što može ukazati na dva, možete imati
jedna stvar točka za mnoge, mnoge stvari.

1016
00:51:35,940 --> 00:51:39,450
Vi zapravo imate nizove
unutar koje pohranjujete

1017
00:51:39,450 --> 00:51:41,790
upućuje da ukazuju na druge polja.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Tako je čvor kako smo
će definirati Trie

1020
00:51:49,460 --> 00:51:52,590
je želimo imati
Boolean, c riječ, zar ne?

1021
00:51:52,590 --> 00:51:54,920
Dakle, čvor je Booleova
kao istinite ili lažne,

1022
00:51:54,920 --> 00:51:58,490
prije svega na čelu
to polje, je li to riječ?

1023
00:51:58,490 --> 00:52:03,620
Drugo, želite imati pokazivače
na ono što od njih su.

1024
00:52:03,620 --> 00:52:07,470
Malo kompleks, malo apstraktno, ali
Ja ću objasniti što to sve znači.

1025
00:52:07,470 --> 00:52:13,800
>> Dakle, ovdje, na vrhu, ako vas
ima niz proglasio je već,

1026
00:52:13,800 --> 00:52:17,040
čvor u kojoj imate Boolean
vrijednost spremljena na prednjem

1027
00:52:17,040 --> 00:52:19,490
koji kaže da je to riječ?

1028
00:52:19,490 --> 00:52:20,520
Nije li to riječ?

1029
00:52:20,520 --> 00:52:23,240
I onda imate
ostatak svog polja koja

1030
00:52:23,240 --> 00:52:26,040
zapravo pohranjuje sve
mogućnosti što bi to moglo biti.

1031
00:52:26,040 --> 00:52:28,660
Tako je, na primjer, kao što je
na vrhu imate

1032
00:52:28,660 --> 00:52:32,140
prva stvar koja govori istina ili
lažna, da ili ne, to je riječ.

1033
00:52:32,140 --> 00:52:38,130
>> I onda imate 0 do 26.
slova koje možete pohraniti.

1034
00:52:38,130 --> 00:52:42,790
Ako sam htjela potražiti ovdje
za šišmiša, idem na vrh

1035
00:52:42,790 --> 00:52:49,200
i ja tražiti B. nađem B u mom
niz, pa znam, u redu je B riječ?

1036
00:52:49,200 --> 00:52:53,010
B nije riječ, pa time i
Moram nastaviti pretraživanje.

1037
00:52:53,010 --> 00:52:56,410
Idem iz B, a sam pogled na
Pokazivač da B upućuje

1038
00:52:56,410 --> 00:53:00,900
i vidim još niz podataka,
ista struktura koje smo imali prije.

1039
00:53:00,900 --> 00:53:05,240
>> I here-- oh, sljedeći
pismo u [nečujan] je A.

1040
00:53:05,240 --> 00:53:07,210
Tako gledamo u tom nizu.

1041
00:53:07,210 --> 00:53:10,860
Nalazimo osmi vrijednosti,
a onda gledamo vidjeti, oh,

1042
00:53:10,860 --> 00:53:12,840
hej, je da je riječ je B-A riječ?

1043
00:53:12,840 --> 00:53:13,807
Nije riječ.

1044
00:53:13,807 --> 00:53:14,890
Moramo se držati obličje.

1045
00:53:14,890 --> 00:53:17,850
>> I tako onda gledamo gdje
kazaljka A točaka,

1046
00:53:17,850 --> 00:53:21,130
a to ukazuje na neki drugi način u
što imamo više vrijednost pohranjena.

1047
00:53:21,130 --> 00:53:24,150
I na kraju, možemo doći do
B-A-T, što je riječ.

1048
00:53:24,150 --> 00:53:25,970
I tako sljedeći put
pogledate, idete

1049
00:53:25,970 --> 00:53:30,850
da se taj ček od, da,
ovo Booleova funkcija je istina.

1050
00:53:30,850 --> 00:53:35,450
I tako, u smislu da smo ljubazni
vlasništvo stablo s polja.

1051
00:53:35,450 --> 00:53:39,890
>> Pa onda možete vrsta pretraživati ​​prema dolje.

1052
00:53:39,890 --> 00:53:43,650
Umjesto raspršivanja funkcije i
dodjeljivanje vrijednosti od povezanog popisa,

1053
00:53:43,650 --> 00:53:49,190
možete jednostavno implementirati
Trie koji pretražuje downwords.

1054
00:53:49,190 --> 00:53:50,850
Stvarno, stvarno komplicirano stvari.

1055
00:53:50,850 --> 00:53:54,060
Nije lako razmišljati jer sam se kao
pljuvanje toliko strukture podataka iz

1056
00:53:54,060 --> 00:53:58,710
na vas, ali ne sve vrste
razumjeti kako logika ovo radi?

1057
00:53:58,710 --> 00:54:01,920
>> OK super.

1058
00:54:01,920 --> 00:54:05,600
Tako B-A-T, te
ideš tražiti.

1059
00:54:05,600 --> 00:54:07,940
Sljedeći put kad idete
vidjeti, oh, hej, to je istina,

1060
00:54:07,940 --> 00:54:09,273
Tako znam da to mora biti riječ.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Ista stvar za zoološki vrt.

1063
00:54:13,770 --> 00:54:17,960
Dakle ovdje je stvar sada, ako smo
htio tražiti zoološkom vrtu, upravo sada,

1064
00:54:17,960 --> 00:54:20,780
Trenutno zoo nije
Riječ u našem rječniku

1065
00:54:20,780 --> 00:54:25,300
jer, kao što vi vidite,
Prvo mjesto koje imamo Boolean

1066
00:54:25,300 --> 00:54:28,590
povratak istina je na kraju zoom.

1067
00:54:28,590 --> 00:54:30,430
Imamo Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> I tako ovdje, ne zapravo imaju
riječ, zoološki vrt, u našem rječniku

1069
00:54:33,900 --> 00:54:36,070
jer ovaj potvrdni okvir nije označen.

1070
00:54:36,070 --> 00:54:39,540
Tako se računalo ne
znam da zoološki vrt je riječ

1071
00:54:39,540 --> 00:54:42,430
jer način na koji smo
spremio, samo zoom ovdje

1072
00:54:42,430 --> 00:54:44,920
zapravo ima Boolean vrijednost
koji je bio uključen istina.

1073
00:54:44,920 --> 00:54:49,380
Dakle, ako želimo umetnuti
Riječ, zoološki vrt, u naš rječnik,

1074
00:54:49,380 --> 00:54:51,770
kako bi smo ići oko radiš to?

1075
00:54:51,770 --> 00:54:55,960
Što moramo učiniti kako bi bili sigurni da naš
Računalo zna da je Z-O-O je riječ

1076
00:54:55,960 --> 00:54:58,130
a ne prva riječ Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> PUBLIKA: [nečujan]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI PENG: Točno, mi
želite biti sigurni da je to

1079
00:55:01,450 --> 00:55:07,890
ovdje, da Boolean vrijednost
provjeriti off da je to istina.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, tada ćemo provjeriti da je,
tako da točno znamo, hej, zoološki vrt je riječ.

1081
00:55:13,297 --> 00:55:15,380
Idem reći
Računalo koje je riječ, tako

1082
00:55:15,380 --> 00:55:18,000
je li računalo provjerava,
ona zna da zoološki vrt je riječ.

1083
00:55:18,000 --> 00:55:21,269
>> Zato ne zaboravite sve ove podatke
strukture, to je vrlo lako za nas

1084
00:55:21,269 --> 00:55:22,310
reći, oh, šišmiš je riječ.

1085
00:55:22,310 --> 00:55:22,851
Zoo je riječ.

1086
00:55:22,851 --> 00:55:23,611
Zoom je riječ.

1087
00:55:23,611 --> 00:55:25,860
Ali kad ste ga zgrada,
računalo nema pojma.

1088
00:55:25,860 --> 00:55:28,619
>> Dakle, morate ga točno reći
U kojem trenutku je to riječ?

1089
00:55:28,619 --> 00:55:29,910
U kojem trenutku je da nije riječ?

1090
00:55:29,910 --> 00:55:31,784
I na kojoj točki ne ja
morati tražiti stvari,

1091
00:55:31,784 --> 00:55:34,000
i na kojoj točki trebam ići dalje?

1092
00:55:34,000 --> 00:55:37,010
Svatko jasno kako?

1093
00:55:37,010 --> 00:55:39,540
Cool.

1094
00:55:39,540 --> 00:55:42,530
>> I tako onda dolazi
problem kako bi mi

1095
00:55:42,530 --> 00:55:45,560
ići oko umetanja nešto
to je zapravo ne postoji?

1096
00:55:45,560 --> 00:55:49,090
Pa recimo samo želimo umetnuti
riječ, kada, u našu Trie.

1097
00:55:49,090 --> 00:55:53,589
Kao što dečki mogu vidjeti kao trenutno
sve što imamo je B-A-T,

1098
00:55:53,589 --> 00:55:55,630
i ovaj novi struktura podataka
Postoji imao pivo koje

1099
00:55:55,630 --> 00:55:59,740
ukazao na nulu, jer pretpostavljamo
da, oh, nema riječi nakon B-A-T,

1100
00:55:59,740 --> 00:56:02,530
zašto nam je potrebna da bi
ima stvari nakon toga T.

1101
00:56:02,530 --> 00:56:06,581
>> No, problem nastaje ako vam se
Želite imati riječ koja dolazi nakon

1102
00:56:06,581 --> 00:56:07,080
T-a.

1103
00:56:07,080 --> 00:56:09,500
Ako imate kadu, ti si
ide žele H pravo.

1104
00:56:09,500 --> 00:56:13,290
I tako je način na koji ćemo učiniti da je
ćemo stvoriti zaseban čvor.

1105
00:56:13,290 --> 00:56:16,840
Nećemo dodijeliti bilo koji iznos
memorije za ovaj novi niz,

1106
00:56:16,840 --> 00:56:20,720
i mi ćemo preraspodijeliti naputke.

1107
00:56:20,720 --> 00:56:22,947
>> Idemo dodijeliti
H, Prije svega, to null,

1108
00:56:22,947 --> 00:56:24,030
ćemo riješiti.

1109
00:56:24,030 --> 00:56:26,590
Mi ćemo imati
je H točke prema dolje.

1110
00:56:26,590 --> 00:56:30,600
Ako vidimo H, želimo ga
ići na neko drugo mjesto.

1111
00:56:30,600 --> 00:56:33,910
>> Ovdje, možemo onda prekrižite da.

1112
00:56:33,910 --> 00:56:38,170
Ako udario H nakon T, oh,
onda znamo da je to riječ.

1113
00:56:38,170 --> 00:56:41,110
Logički će vratiti istinito.

1114
00:56:41,110 --> 00:56:42,950
Svatko jasno kako se to dogodilo?

1115
00:56:42,950 --> 00:56:45,110
U REDU.

1116
00:56:45,110 --> 00:56:47,214
>> Pa u biti, sve
ove strukture podataka

1117
00:56:47,214 --> 00:56:50,130
da smo otišli preko danas, imam
otišao preko njih jako, jako brzo

1118
00:56:50,130 --> 00:56:52,192
i ne previše
detalj, a to je u redu.

1119
00:56:52,192 --> 00:56:53,900
Jednom kada počnete petljaju
s njim, vi ćete biti

1120
00:56:53,900 --> 00:56:55,733
praćenje gdje
sve pokazivače su,

1121
00:56:55,733 --> 00:56:58,060
što se događa u vašem
strukture podataka, i tako dalje.

1122
00:56:58,060 --> 00:56:59,810
Oni će biti vrlo korisno,
i to je do vas

1123
00:56:59,810 --> 00:57:03,890
Dečki potpuno shvatiti kako
Želite li provesti stvari.

1124
00:57:03,890 --> 00:57:07,650
>> I tako pset4, od 5-- oh, to je u redu.

1125
00:57:07,650 --> 00:57:10,140
Pset5 je pravopisne pogreške.

1126
00:57:10,140 --> 00:57:13,710
Kao što sam rekao prije, ti si idući u jednom
opet preuzeti izvorni kod od nas.

1127
00:57:13,710 --> 00:57:16,210
Tu će biti tri glavna
stvari koje će biti preuzimanje.

1128
00:57:16,210 --> 00:57:18,470
Vi ćete preuzeti rječnike,
cima i tekstovi.

1129
00:57:18,470 --> 00:57:21,660
>> Sve te stvari su se
bilo rječnici riječi

1130
00:57:21,660 --> 00:57:25,190
da želimo da provjerite
ili test podataka

1131
00:57:25,190 --> 00:57:26,930
da želimo da provjere pravopisa.

1132
00:57:26,930 --> 00:57:29,670
I tako rječnici
dajemo idete

1133
00:57:29,670 --> 00:57:34,870
vam dati stvarne riječi koje želimo
možete pohraniti nekako na način koji je

1134
00:57:34,870 --> 00:57:36,530
učinkovitiji od niza.

1135
00:57:36,530 --> 00:57:38,470
A onda se tekstovi
će biti ono što smo

1136
00:57:38,470 --> 00:57:43,900
vas da čarolija provjerite je li
sve riječi postoje stvarne riječi.

1137
00:57:43,900 --> 00:57:47,970
>> I tako tri bloka
programi koji ćemo vam dati

1138
00:57:47,970 --> 00:57:51,130
nazivaju dictionary.c,
dictionary.h i speller.c.

1139
00:57:51,130 --> 00:57:56,500
I tako sve dictionary.c čini se
što ste pitali za provedbu.

1140
00:57:56,500 --> 00:57:57,880
To učitava riječi.

1141
00:57:57,880 --> 00:58:02,000
To čarolija provjerava ih, i to čini da
da je sve ispravno umetnut.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h je samo knjižnica datoteke
da proglasi sve te funkcije.

1143
00:58:05,180 --> 00:58:07,650
I speller.c, ćemo vam dati.

1144
00:58:07,650 --> 00:58:09,290
Ne morate mijenjati ništa od toga.

1145
00:58:09,290 --> 00:58:14,290
Sve speller.c se je uzeti,
opterećenja, provjerava brzinu njega,

1146
00:58:14,290 --> 00:58:19,190
ispituje mjerilo poput kako
brzo ste u mogućnosti to učiniti stvari.

1147
00:58:19,190 --> 00:58:20,410
>> To je bukvar.

1148
00:58:20,410 --> 00:58:23,920
Samo nemojte igrati s njim, ali bi
jeste li razumjeli što to radiš.

1149
00:58:23,920 --> 00:58:28,090
Mi koristimo funkciju zove getrusage da
testovi performanse vašeg čarolija

1150
00:58:28,090 --> 00:58:28,590
provjeru.

1151
00:58:28,590 --> 00:58:32,200
Sve je to ipak u osnovi testirati
Vrijeme svega u svom rječniku,

1152
00:58:32,200 --> 00:58:33,680
tako da bi bili sigurni da ga razumijemo.

1153
00:58:33,680 --> 00:58:36,660
Budite oprezni da ne igrati s njim ili
drugo stvari neće raditi ispravno.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> I većina ovog izazov je za
ti dečki stvarno izmijeniti dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Mi ćemo vam dati
140.000 riječi u rječniku.

1157
00:58:48,526 --> 00:58:50,900
Mi ćemo vam dati tekst
datoteku koja ima te riječi,

1158
00:58:50,900 --> 00:58:54,840
i želimo da budete u mogućnosti organizirati
ih u hash tablicu ili Trie

1159
00:58:54,840 --> 00:58:58,140
jer kad smo vas da čarolija
check-- zamislite ako ste čarolija

1160
00:58:58,140 --> 00:59:00,690
provjeru poput Homerovih Odyssey.

1161
00:59:00,690 --> 00:59:03,010
To je kao što je ovaj ogroman, ogroman test.

1162
00:59:03,010 --> 00:59:05,190
>> Zamislite da svaki
riječ koju je morao gledati

1163
00:59:05,190 --> 00:59:08,100
kroz niz 140.000 vrijednosti.

1164
00:59:08,100 --> 00:59:10,350
To bi se zauvijek
za vaš stroj radi.

1165
00:59:10,350 --> 00:59:14,490
Zato želimo organizirati naše
podataka u učinkovitijih struktura podataka

1166
00:59:14,490 --> 00:59:17,270
kao što je hash tablicu ili Trie.

1167
00:59:17,270 --> 00:59:20,700
I onda vi možete vrsta
kada se traži pristup

1168
00:59:20,700 --> 00:59:22,570
stvari lakše i brže.

1169
00:59:22,570 --> 00:59:24,934
>> I stoga budite oprezni u rješavanju sudara.

1170
00:59:24,934 --> 00:59:27,350
Ti si idući u dobiti hrpu
riječi tog starta s A.

1171
00:59:27,350 --> 00:59:29,957
Ti si idući u dobiti hrpu riječi
kako početi s B. Do tebe

1172
00:59:29,957 --> 00:59:31,290
Dečki kako želite to riješiti.

1173
00:59:31,290 --> 00:59:34,144
Možda ima još
učinkovita funkcija mljeveno meso

1174
00:59:34,144 --> 00:59:36,810
nego samo prvo slovo
nešto, i to tako da je na vama

1175
00:59:36,810 --> 00:59:38,190
dečki vrsta učiniti što god želite.

1176
00:59:38,190 --> 00:59:40,148
>> Možda želite dodati
sva slova zajedno.

1177
00:59:40,148 --> 00:59:43,410
Možda želite željeli raditi čudne stvari
na račun broj slova,

1178
00:59:43,410 --> 00:59:43,970
kako god.

1179
00:59:43,970 --> 00:59:45,386
Do vama kako želite raditi.

1180
00:59:45,386 --> 00:59:49,262
Ako želite napraviti hash tablicu, ako ste
želite probati Trie, potpuno na vama.

1181
00:59:49,262 --> 00:59:52,470
Ja ću vas upozoriti ispred vremena koje je
Trie je obično malo teže

1182
00:59:52,470 --> 00:59:54,520
samo zato što je puno
više upućuje pratiti.

1183
00:59:54,520 --> 00:59:55,645
Ali totalno do vas dečki.

1184
00:59:55,645 --> 00:59:58,742
To je daleko učinkovitiji
u većini slučajeva.

1185
00:59:58,742 --> 01:00:01,450
Vi stvarno želite biti u mogućnosti to držati
praćenje svih vaših upućuje.

1186
01:00:01,450 --> 01:00:03,850
Kao učiniti istu stvar
da radim ovdje.

1187
01:00:03,850 --> 01:00:06,871
Kada pokušavate umetnuti
vrijednosti u hash tablicu ili izbrisati,

1188
01:00:06,871 --> 01:00:08,620
pobrinite se da ste
stvarno praćenje

1189
01:00:08,620 --> 01:00:11,860
gdje je sve jer je
to je stvarno lako za ako sam

1190
01:00:11,860 --> 01:00:14,727
pokušavate umetnuti poput riječi, Andy.

1191
01:00:14,727 --> 01:00:16,810
Recimo samo da je
Pravi riječ, riječ, Andy,

1192
01:00:16,810 --> 01:00:19,640
u diva popis A riječi.

1193
01:00:19,640 --> 01:00:22,450
>> Ako sam slučajno preraspodijeliti
pokazivač krivo, ups,

1194
01:00:22,450 --> 01:00:24,940
tu ide cjelokupnost
ostatak mog popisa povezane.

1195
01:00:24,940 --> 01:00:26,897
Sada je samo riječ koju
imam je Andy, a sada

1196
01:00:26,897 --> 01:00:29,230
sve ostale riječi u
rječnik su izgubljeni.

1197
01:00:29,230 --> 01:00:31,370
I tako želite biti sigurni da
pratiti sve svoje pokazivače

1198
01:00:31,370 --> 01:00:33,661
inače si idući u dobiti
veliki problemi u kodu.

1199
01:00:33,661 --> 01:00:35,840
Nacrtaj stvari pažljivo korak po korak.

1200
01:00:35,840 --> 01:00:37,870
To ga čini mnogo lakše misliti.

1201
01:00:37,870 --> 01:00:40,910
>> I na kraju, želite biti u mogućnosti
testirati svoje performanse vašeg programa

1202
01:00:40,910 --> 01:00:41,618
na velikom brodu.

1203
01:00:41,618 --> 01:00:43,710
Ako vi uzeti
pogledajte CS50 upravo sada,

1204
01:00:43,710 --> 01:00:45,210
imamo ono što se zove velika odbora.

1205
01:00:45,210 --> 01:00:50,200
To je rezultat list najbrže
Provjera pravopisa puta u svim CS50

1206
01:00:50,200 --> 01:00:55,720
upravo sada, mislim da je vrh kao 10
puta mislim osam ih je osoblje.

1207
01:00:55,720 --> 01:00:57,960
Mi doista želite li vi da nas tuku.

1208
01:00:57,960 --> 01:01:00,870
>> Svi od nas su pokušali provesti
najbrži kod moguće.

1209
01:01:00,870 --> 01:01:04,880
Želimo ti dečki pokušati osporiti
nas i provesti brže od svih nas

1210
01:01:04,880 --> 01:01:05,550
može.

1211
01:01:05,550 --> 01:01:07,970
I tako je to stvarno
prvi put da smo

1212
01:01:07,970 --> 01:01:12,680
traži dečki napraviti pset da
zaista možete učiniti u bilo kojoj metodi

1213
01:01:12,680 --> 01:01:13,760
ti želiš.

1214
01:01:13,760 --> 01:01:17,730
>> Uvijek kažem, to je više moj
u stvarnom životu rješenje, zar ne?

1215
01:01:17,730 --> 01:01:19,550
Kažem, hej, moram li to učiniti.

1216
01:01:19,550 --> 01:01:21,380
Graditi program koji radi ovo za mene.

1217
01:01:21,380 --> 01:01:22,630
Učinite to kako god želite.

1218
01:01:22,630 --> 01:01:24,271
Ja samo znam da želim postiti.

1219
01:01:24,271 --> 01:01:25,770
To je tvoj izazov za ovaj tjedan.

1220
01:01:25,770 --> 01:01:27,531
Vi, idemo
vam dati zadatak.

1221
01:01:27,531 --> 01:01:29,030
Mi ćemo vam dati izazov.

1222
01:01:29,030 --> 01:01:31,559
A onda je na vama
potpuno jednostavno shvatiti

1223
01:01:31,559 --> 01:01:34,100
što je najbrži i najviše
učinkovit način za provedbu ovoga.

1224
01:01:34,100 --> 01:01:34,600
Da?

1225
01:01:34,600 --> 01:01:37,476
>> PUBLIKA: Jesmo li dopušteno
htio istražiti brže načine

1226
01:01:37,476 --> 01:01:40,821
učiniti hash tablice line, možemo učiniti
to i navode tuđe šifru?

1227
01:01:40,821 --> 01:01:42,070
ANDI PENG: Da, potpuno u redu.

1228
01:01:42,070 --> 01:01:44,320
Dakle, ako vi pročitali
spec, postoji linija

1229
01:01:44,320 --> 01:01:48,310
u spec koji kaže da dečki
su potpuno besplatni za istraživanje mljeveno meso

1230
01:01:48,310 --> 01:01:51,070
funkcionira na ono što su neki
od brže hash funkcija

1231
01:01:51,070 --> 01:01:54,720
pokrenuti stvari kroz što
dok vam citirati taj kod.

1232
01:01:54,720 --> 01:01:57,220
Dakle, neki ljudi su već
shvatio brze načine

1233
01:01:57,220 --> 01:02:00,250
radiš za provjeru pravopisa, brzim
načini pohrane podataka.

1234
01:02:00,250 --> 01:02:02,750
Totalno do vas dečki, ako vas
žele samo uzeti to, zar ne?

1235
01:02:02,750 --> 01:02:04,045
Provjerite jeste li navodeći.

1236
01:02:04,045 --> 01:02:06,170
Izazov ovdje stvarno
da smo pokušava testirati

1237
01:02:06,170 --> 01:02:09,750
biti sigurni da znate
svoj put okolo naputke.

1238
01:02:09,750 --> 01:02:12,700
Koliko provedbi
stvarna hash funkcija

1239
01:02:12,700 --> 01:02:15,070
i dolaze s kao
math to učiniti,

1240
01:02:15,070 --> 01:02:17,570
vi možete istražiti sve što
Metode online dečki žele.

1241
01:02:17,570 --> 01:02:17,996
Da?

1242
01:02:17,996 --> 01:02:19,700
>> PUBLIKA: Možemo citirati samo
pomoću [nečujan]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI PENG: Da.

1244
01:02:20,120 --> 01:02:22,328
Možete samo u svoj komentar,
možete navesti kao, oh,

1245
01:02:22,328 --> 01:02:26,127
preuzet iz BLA, Yada,
Yada, hash funkcija.

1246
01:02:26,127 --> 01:02:27,210
Bilo tko imati bilo kakvih pitanja?

1247
01:02:27,210 --> 01:02:29,694
Mi zapravo breezed
kroz sekcije danas.

1248
01:02:29,694 --> 01:02:31,610
Ja ću biti ovdje da se
odgovoriti na pitanja kao dobro.

1249
01:02:31,610 --> 01:02:36,570
>> Također, kao što sam rekao, uredski
sati večeras i sutra.

1250
01:02:36,570 --> 01:02:40,307
Spec ovaj tjedan je zapravo
super jednostavno i super kratke čitati.

1251
01:02:40,307 --> 01:02:43,140
JA će predlagati uzimanje pogledati, samo
pročitajte cjelinu njega.

1252
01:02:43,140 --> 01:02:45,730
>> I Zamyla zapravo šetnje
preko svake funkcije

1253
01:02:45,730 --> 01:02:49,796
morate provesti, pa je
vrlo, vrlo jasno kako to učiniti sve.

1254
01:02:49,796 --> 01:02:51,920
Samo kako bi bili sigurni da ste
praćenje upućuje.

1255
01:02:51,920 --> 01:02:53,650
To je vrlo izazovna pset.

1256
01:02:53,650 --> 01:02:56,744
>> Nije zahtjevna, jer kao što je,
oh, pojmovi su mnogo

1257
01:02:56,744 --> 01:02:59,160
teško, ili morate naučiti
toliko Novi sintaksa način

1258
01:02:59,160 --> 01:03:00,650
što si učinio za posljednji pset.

1259
01:03:00,650 --> 01:03:03,320
To je teško jer pset
ima toliko naputke,

1260
01:03:03,320 --> 01:03:06,980
a onda je vrlo, vrlo lako jednom
imate bug u kodu neće moći

1261
01:03:06,980 --> 01:03:08,315
pronaći gdje da bug.

1262
01:03:08,315 --> 01:03:13,200
>> I tako potpuni i izustiti vjera u vama
dečki biti u mogućnosti da tuku naše [nečujan]

1263
01:03:13,200 --> 01:03:13,700
pravopisa.

1264
01:03:13,700 --> 01:03:16,640
Ja zapravo nemam nikakav pisani mina
još, ali ću pisati moje.

1265
01:03:16,640 --> 01:03:19,070
Dakle, dok ste pisanja
tvoje, ja ću pisati moje.

1266
01:03:19,070 --> 01:03:21,070
Idem probati napraviti
moja brže od tvoje.

1267
01:03:21,070 --> 01:03:23,940
Vidjet ćemo tko ima najbrži jedan.

1268
01:03:23,940 --> 01:03:27,340
>> I da, ja ću vidjeti sve
vi ovdje u utorak.

1269
01:03:27,340 --> 01:03:29,510
Ja ću pokrenuti vrste poput pset radionici.

1270
01:03:29,510 --> 01:03:32,640
Sve ove sekcije
tjedan su pset radionice,

1271
01:03:32,640 --> 01:03:36,690
tako da dečki imaju puno mogućnosti
za pomoć, radno vrijeme, kao i uvijek,

1272
01:03:36,690 --> 01:03:41,330
i ja stvarno gledati prema naprijed
čitajući sve vaše momci 'kod.

1273
01:03:41,330 --> 01:03:44,160
Imam kvizovi ovdje ako vas
dečki žele doći po njih.

1274
01:03:44,160 --> 01:03:45,880
To je sve.

1275
01:03:45,880 --> 01:03:48,180