1
00:00:00,000 --> 00:00:03,423
>> [MUSIC JOC]

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

3
00:00:05,380 --> 00:00:08,210
>> ANDI Peng: Bine ati venit la saptamana 6 de secțiune.

4
00:00:08,210 --> 00:00:11,620
Am deviat de la standardul nostru
timp de marți secțiune

5
00:00:11,620 --> 00:00:14,130
după-amiază la această duminica dimineata minunat.

6
00:00:14,130 --> 00:00:17,330
Vă mulțumim pentru toată lumea că
mi s-au alăturat astăzi, dar serios,

7
00:00:17,330 --> 00:00:18,170
o rundă de aplauze.

8
00:00:18,170 --> 00:00:20,600
>> Asta e un efort destul de mare.

9
00:00:20,600 --> 00:00:23,600
Eu aproape că nu am chiar face
în timp, dar a fost ok.

10
00:00:23,600 --> 00:00:27,520
Așa că știu că voi toți
tocmai ajuns la testul.

11
00:00:27,520 --> 00:00:30,370
Mai întâi de toate, bun venit pentru a
de cealalta parte de asta.

12
00:00:30,370 --> 00:00:32,917
>> În al doilea rând, vom vorbi despre asta.

13
00:00:32,917 --> 00:00:34,000
Vom vorbi despre testul.

14
00:00:34,000 --> 00:00:35,700
Vom vorbi despre modul în care
faci in clasa.

15
00:00:35,700 --> 00:00:36,550
O sa fii bine.

16
00:00:36,550 --> 00:00:39,080
Am teste tale pentru
te la sfârșitul aici,

17
00:00:39,080 --> 00:00:42,120
Deci, dacă vreți să luați
o privire la ea, totul bine.

18
00:00:42,120 --> 00:00:46,590
>> Atât de repede înainte de a începe, The
agenda pentru astăzi este după cum urmează.

19
00:00:46,590 --> 00:00:48,430
După cum puteți vedea, suntem
ardere practic rapid

20
00:00:48,430 --> 00:00:52,120
printr-o grămadă de structuri de date
într-adevăr, într-adevăr, foarte repede.

21
00:00:52,120 --> 00:00:54,380
Deci, ca atare, acesta nu va fi
azi super-interactiv.

22
00:00:54,380 --> 00:00:59,620
Va fi doar eu un fel de strigând
lucrurile pe care le, și dacă te confunda,

23
00:00:59,620 --> 00:01:02,680
dacă am de gând prea repede, lasă-mă să știu.

24
00:01:02,680 --> 00:01:05,200
Sunt doar diferite date
structuri, precum și în cadrul

25
00:01:05,200 --> 00:01:07,070
de PSET pentru acest
Săptămâna viitoare, veți

26
00:01:07,070 --> 00:01:10,340
va cere să pună în aplicare una dintre ele,
probabil, două din them-- două dintre ele

27
00:01:10,340 --> 00:01:12,319
în PSET dumneavoastră.

28
00:01:12,319 --> 00:01:14,610
OK, așa că doar de gând să
începe cu câteva anunțuri.

29
00:01:14,610 --> 00:01:19,070
Vom trece peste stive și cozi mai multe în
adâncime decât ceea ce am făcut înainte de testul.

30
00:01:19,070 --> 00:01:20,990
Vom trece peste legată
lista nou, încă o dată,

31
00:01:20,990 --> 00:01:23,899
mai în profunzime decât ceea ce
am avut înainte de testul.

32
00:01:23,899 --> 00:01:26,440
Și apoi vom vorbi despre hash
tabele, copaci și încearcă, care

33
00:01:26,440 --> 00:01:28,890
sunt destul de necesare pentru PSET ta.

34
00:01:28,890 --> 00:01:32,925
Și apoi vom trece peste unele
sfaturi utile pentru pset5.

35
00:01:32,925 --> 00:01:37,360
>> OK, așa test 0.

36
00:01:37,360 --> 00:01:41,090
Media a fost un 58%.

37
00:01:41,090 --> 00:01:45,370
A fost foarte scăzută, și așa voi toți
a făcut foarte, foarte bine, în conformitate

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

39
00:01:46,510 --> 00:01:49,970
>> Destul de mult, regula de degetul mare este daca esti
într-un deviație standard a mediei

40
00:01:49,970 --> 00:01:52,990
mai ales că suntem într-o mai mică
secțiune confortabil, ești în regulă.

41
00:01:52,990 --> 00:01:54,120
Ești pe drumul cel bun.

42
00:01:54,120 --> 00:01:55,190
Viata e buna.

43
00:01:55,190 --> 00:01:58,952
>> Știu că e înfricoșător să cred că
Am ca un 40% pe acest test.

44
00:01:58,952 --> 00:02:00,160
Am de gând să nu reușească această clasă.

45
00:02:00,160 --> 00:02:02,243
Îți promit, nu ești
O să reușesc clasa.

46
00:02:02,243 --> 00:02:03,680
Ești în regulă.

47
00:02:03,680 --> 00:02:06,850
>> Pentru cei dintre voi care au primit peste
media, impresionant, impresionant,

48
00:02:06,850 --> 00:02:08,780
cum ar fi, serios bine făcut.

49
00:02:08,780 --> 00:02:09,689
Le am cu mine.

50
00:02:09,689 --> 00:02:11,730
Simțiți-vă liber pentru a veni le obține
la sfârșitul secțiunii.

51
00:02:11,730 --> 00:02:14,520
Lasă-mă să știu dacă aveți orice
probleme, întrebări cu ei.

52
00:02:14,520 --> 00:02:17,204
Dacă adăugăm la scorul
greșit, să ne anunțați.

53
00:02:17,204 --> 00:02:21,240
>> OK, deci pset5, aceasta este într-adevăr o
săptămână ciudat pentru Yale, în sensul

54
00:02:21,240 --> 00:02:24,240
că PSET noastră se datorează
Miercuri la prânz, inclusiv

55
00:02:24,240 --> 00:02:27,317
târziu ziua, așa că de fapt
din cauza teoretic marți la prânz.

56
00:02:27,317 --> 00:02:29,150
Probabil nimeni nu a terminat
la marți la prânz.

57
00:02:29,150 --> 00:02:30,830
Asta e cu totul în regulă.

58
00:02:30,830 --> 00:02:33,700
Vom avea de ore de birou
in seara asta la fel de bine ca luni noaptea.

59
00:02:33,700 --> 00:02:36,810
Și toate secțiunile săptămâni acest lucru va
de fapt, să fie transformat în ateliere de lucru,

60
00:02:36,810 --> 00:02:38,800
deci nu ezitați să pop în
orice secțiune vrei,

61
00:02:38,800 --> 00:02:42,810
și vor fi un fel de mini-PSET
ateliere de lucru pentru ajutor pe care.

62
00:02:42,810 --> 00:02:45,620
Deci, ca atare, aceasta este singura secțiune
în cazul în care ne material didactic.

63
00:02:45,620 --> 00:02:49,220
Toate celelalte secțiuni se va concentra
exclusiv pe de ajutor pentru PSET.

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

65
00:02:50,146 --> 00:02:52,000
>> Audiența: Unde sunt orelor de program?

66
00:02:52,000 --> 00:02:56,120
>> ANDI Peng: ore de birou
seara asta oh, bine întrebarea.

67
00:02:56,120 --> 00:03:00,580
Cred orelor seara asta
sunt în Teal sau la Commons.

68
00:03:00,580 --> 00:03:02,984
Dacă tu a verifica on-line CS50
și te duci la ore de birou,

69
00:03:02,984 --> 00:03:05,650
ar trebui să existe un program care
tu unde toate acestea sunt spune.

70
00:03:05,650 --> 00:03:07,954
>> Știu fie in seara asta
sau mâine este Teal,

71
00:03:07,954 --> 00:03:10,120
și cred că am putea avea
Commons pentru noaptea trecută.

72
00:03:10,120 --> 00:03:11,020
Nu sunt sigur.

73
00:03:11,020 --> 00:03:11,700
Buna intrebare.

74
00:03:11,700 --> 00:03:14,430
Verificați pe CS50.

75
00:03:14,430 --> 00:03:18,780
>> Rece, orice întrebare privind
programul pentru următoarea ca de trei zile?

76
00:03:18,780 --> 00:03:21,690
Promit ca voi ca David
a spus, aceasta este partea de sus a dealului.

77
00:03:21,690 --> 00:03:23,050
Voi sunteți aproape acolo.

78
00:03:23,050 --> 00:03:24,644
Doar trei zile.

79
00:03:24,644 --> 00:03:26,310
Ajunge acolo, și apoi vom veni toți în jos.

80
00:03:26,310 --> 00:03:28,114
Vom avea o pauză CS-free frumos.

81
00:03:28,114 --> 00:03:28,780
Bine ai revenit.

82
00:03:28,780 --> 00:03:30,779
Vom arunca cu capul în web
programare și dezvoltare,

83
00:03:30,779 --> 00:03:35,150
lucruri care sunt foarte distractiv, comparativ
la unele dintre celelalte psets.

84
00:03:35,150 --> 00:03:37,974
Și va fi rece, și
vom avea o mulțime de distracție.

85
00:03:37,974 --> 00:03:38,890
Vom avea mai multe bomboane.

86
00:03:38,890 --> 00:03:39,730
Ne pare rău pentru bomboane.

87
00:03:39,730 --> 00:03:40,945
Am uitat bomboane.

88
00:03:40,945 --> 00:03:43,310
Era o dimineață dur.

89
00:03:43,310 --> 00:03:46,340
Deci voi sunteți aproape acolo,
și eu sunt foarte mândru de voi.

90
00:03:46,340 --> 00:03:49,570
>> OK, așa stive.

91
00:03:49,570 --> 00:03:53,331
Care a iubit la întrebarea despre Jack
și hainele de pe testul?

92
00:03:53,331 --> 00:03:53,830
Nici unul?

93
00:03:53,830 --> 00:03:56,500
OK, e in regula.

94
00:03:56,500 --> 00:04:00,200
>> Deci, în esență, după cum puteți
Jack, tipul ăsta de aici,

95
00:04:00,200 --> 00:04:03,350
îi place să ia hainele
din partea de sus a stivei,

96
00:04:03,350 --> 00:04:05,750
și el pune din nou pe
stiva după ce a făcut.

97
00:04:05,750 --> 00:04:07,600
Deci, în acest fel, el nu
pare să se

98
00:04:07,600 --> 00:04:10,090
la partea de jos a
stivă în hainele.

99
00:04:10,090 --> 00:04:12,600
Deci, acest tip de descrie
structura de date de bază

100
00:04:12,600 --> 00:04:16,610
de modul în care este pusă în aplicare o stivă.

101
00:04:16,610 --> 00:04:20,060
>> În esență, cred că de o
stiva ca orice stivă de obiecte

102
00:04:20,060 --> 00:04:24,900
în cazul în care ați pus lucrurile pe partea de sus, și
apoi le pop din partea de sus.

103
00:04:24,900 --> 00:04:28,600
Deci LIFO este acronimul ne place
la use-- Last In, First Out.

104
00:04:28,600 --> 00:04:32,480
Și astfel, în ultimul în partea de sus
stiva este primul care iese.

105
00:04:32,480 --> 00:04:34,260
Și astfel cei doi termeni
ne place să se asocieze

106
00:04:34,260 --> 00:04:36,190
cu care sunt numite împinge și pop.

107
00:04:36,190 --> 00:04:39,790
Când împinge ceva pe produsul
stiva, și îl pop înapoi.

108
00:04:39,790 --> 00:04:43,422
>> Și așa cred că acest lucru este un fel de
concept abstract pentru cei dintre voi

109
00:04:43,422 --> 00:04:45,630
care doresc să vadă ca un
punerea în aplicare efectivă a acestei

110
00:04:45,630 --> 00:04:46,740
în lumea reală.

111
00:04:46,740 --> 00:04:50,170
Câți dintre voi au scris un eseu
Poate ca o oră înainte de a fi datorat,

112
00:04:50,170 --> 00:04:54,510
și ați șters accidental un imens
bucată din ea, ca din greșeală?

113
00:04:54,510 --> 00:04:58,560
Și apoi ce face de control
vom folosi să-l puneți înapoi?

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

115
00:05:00,030 --> 00:05:03,640
Control-Z, astfel încât cantitatea de ori
că control-Z a salvat viața,

116
00:05:03,640 --> 00:05:08,820
a salvat fundul meu, de fiecare dată
care este pus în aplicare printr-un coș.

117
00:05:08,820 --> 00:05:13,020
>> În esență toate informațiile
asta e pe document Word,

118
00:05:13,020 --> 00:05:15,080
devine împins și mi-a venit în voie.

119
00:05:15,080 --> 00:05:19,460
Și astfel, în esență, ori de câte ori
șterge nimic, îl pop înapoi.

120
00:05:19,460 --> 00:05:22,820
Și apoi, dacă aveți nevoie de ea din nou, tu
împingeți-l, care este ceea ce face de control-C.

121
00:05:22,820 --> 00:05:26,770
Și funcția lumea atat de real
de structură de date cât de simplu

122
00:05:26,770 --> 00:05:28,690
poate ajuta cu viata de zi cu zi.

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

124
00:05:31,710 --> 00:05:40,150
>> Deci, o struct este modul în care
vom crea de fapt o stivă.

125
00:05:40,150 --> 00:05:44,720
Noi definim tip struct, și apoi
noi numim stivă în partea de jos.

126
00:05:44,720 --> 00:05:47,440
Și în cadrul stivei,
avem doi parametri

127
00:05:47,440 --> 00:05:51,580
pe care le putem manipula în esență,
așa că avem capacitatea de siruri de caractere char stele.

128
00:05:51,580 --> 00:05:55,150
>> Tot ce este de a face
este de a crea un tablou

129
00:05:55,150 --> 00:05:58,835
pe care le poate stoca tot ce vrei
care putem determina capacitatea sa.

130
00:05:58,835 --> 00:06:01,990
Capacitatea este doar cantitatea de max
articole putem pune în această matrice.

131
00:06:01,990 --> 00:06:05,660
int size este contorul care ține
urmări cât de multe elemente sunt în prezent

132
00:06:05,660 --> 00:06:07,850
în stivă.

133
00:06:07,850 --> 00:06:11,860
Deci, atunci putem urmări, A,
atât cât de mare stiva reală este,

134
00:06:11,860 --> 00:06:14,850
si, B, cât de mult din care stivă
am umplut pentru că nu vrem

135
00:06:14,850 --> 00:06:18,800
să se reverse asupra a ceea ce capacitatea noastră este.

136
00:06:18,800 --> 00:06:24,340
>> Deci, de exemplu, acest minunat
Întrebarea a fost pe testul tău.

137
00:06:24,340 --> 00:06:28,160
În esență cum putem împinge
pe partea de sus a unei stive.

138
00:06:28,160 --> 00:06:28,830
Destul de simplu.

139
00:06:28,830 --> 00:06:30,621
Dacă te uiți la el,
vom trece prin asta.

140
00:06:30,621 --> 00:06:32,640
Dacă [Inaudibil] size--
amintiți-vă, ori de câte ori

141
00:06:32,640 --> 00:06:35,300
doresc să acceseze orice
parametru într-un struct,

142
00:06:35,300 --> 00:06:40,320
faci numele struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> In acest caz, s este
numele stivă noastre.

144
00:06:42,720 --> 00:06:46,230
Vrem pentru a accesa dimensiunea
de ea, așa că vom face s.size.

145
00:06:46,230 --> 00:06:50,280
Deci, atâta timp cât dimensiunea nu este
egală cu capacitatea sau, atâta timp

146
00:06:50,280 --> 00:06:52,940
ca este mai mică de capacitate,
fie ar lucra aici.

147
00:06:52,940 --> 00:06:57,180
>> Vrei pentru a accesa interior
din stack, așa s.strings,

148
00:06:57,180 --> 00:07:00,790
și ai de gând să pună acest număr nou
pe care doriți să introduceți în acolo.

149
00:07:00,790 --> 00:07:05,030
Să spunem că va dori să
introduceți int n pe stiva,

150
00:07:05,030 --> 00:07:08,905
am putea face s.strings,
paranteze, s.size egal n.

151
00:07:08,905 --> 00:07:11,030
Deoarece dimensiunea este în cazul în care ne-am
în prezent se află în stivă

152
00:07:11,030 --> 00:07:14,590
dacă vom împinge
l pe, ne-am acces

153
00:07:14,590 --> 00:07:17,370
oriunde dimensiunea, cu atât
plinătatea curent al stivei,

154
00:07:17,370 --> 00:07:21,729
și ne-am împinge int n pe ea.

155
00:07:21,729 --> 00:07:24,770
Și apoi ne-am dori să vă asigurați că
suntem, de asemenea, incrementare dimensiunea n,

156
00:07:24,770 --> 00:07:27,436
astfel încât să putem urmări ne-am
adăugat un lucru suplimentar pentru stiva.

157
00:07:27,436 --> 00:07:29,660
Acum avem o dimensiune mai mare.

158
00:07:29,660 --> 00:07:33,196
Are acest sens să aici
toată lumea, cum în mod logic funcționează?

159
00:07:33,196 --> 00:07:34,160
A fost un fel de rapid.

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

161
00:07:39,535 --> 00:07:42,160
Audiența: Poți trece peste
de s.stringss.strings [s.size] din nou?

162
00:07:42,160 --> 00:07:45,808
ANDI Peng: Sigur, asa ca ce face
s.size prezent ne dea?

163
00:07:45,808 --> 00:07:47,440
Audiența: E dimensiunea actuală.

164
00:07:47,440 --> 00:07:50,890
ANDI Peng: Exact, așa că
Indicele curent că dimensiunea noastră este la,

165
00:07:50,890 --> 00:07:57,780
și așa ne-o dorim pentru a pune în noul număr întreg
care ne-o dorim pentru a insera în s.size.

166
00:07:57,780 --> 00:07:58,760
Are sens?

167
00:07:58,760 --> 00:08:01,110
Deoarece s.strings, tot ceea ce
este este numele de matrice.

168
00:08:01,110 --> 00:08:03,510
Tot ce este este accesarea
matrice în struct nostru,

169
00:08:03,510 --> 00:08:06,030
și așa, dacă vrem să
plasa n în care indicele,

170
00:08:06,030 --> 00:08:09,651
putem accesa doar
utilizând paranteze s.size.

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

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

173
00:08:13,580 --> 00:08:18,916
>> Bine, pop, am pseudocod afară
pentru voi, dar concept similar.

174
00:08:18,916 --> 00:08:19,790
Are sens?

175
00:08:19,790 --> 00:08:22,310
Dacă dimensiunea este mai mare
decât zero, atunci

176
00:08:22,310 --> 00:08:25,350
Știu că vrei să iei ceva
din cauza dacă mărimea nu este

177
00:08:25,350 --> 00:08:27,620
mai mare decât zero, atunci
nu au nimic în stivă.

178
00:08:27,620 --> 00:08:29,840
>> Deci, vrei doar să execute
acest cod, se poate doar

179
00:08:29,840 --> 00:08:32,320
pop dacă există ceva la pop.

180
00:08:32,320 --> 00:08:35,830
Deci, în cazul în care dimensiunea este mai mare
decât 0, am minus dimensiunea.

181
00:08:35,830 --> 00:08:40,020
Am decrement mărimea și apoi să se întoarcă
ceea ce este în interiorul pentru că

182
00:08:40,020 --> 00:08:42,710
de popping, dorim să
acces indiferent de este stocat

183
00:08:42,710 --> 00:08:45,694
în indicele de sus a stivei.

184
00:08:45,694 --> 00:08:46,610
Totul face sens?

185
00:08:46,610 --> 00:08:49,693
Dacă am făcut voi scrie acest lucru,
ar putea să-l scrie voi?

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

187
00:08:52,029 --> 00:08:53,570
OK, voi poate juca în jurul cu ea.

188
00:08:53,570 --> 00:08:55,252
Nu vă faceți griji dacă nu înțelegi.

189
00:08:55,252 --> 00:08:57,460
Nu avem timp să cod
l astăzi pentru că ne-am

190
00:08:57,460 --> 00:08:59,959
a primit o mulțime de aceste structuri
pentru a merge prin, dar, în esență

191
00:08:59,959 --> 00:09:02,214
pseudocod, foarte, foarte asemănătoare pentru a împinge.

192
00:09:02,214 --> 00:09:03,380
Doar urmați de-a lungul logica.

193
00:09:03,380 --> 00:09:06,092
Asigurați-vă că accesați toate
caracteristici ale struct corect.

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

195
00:09:06,574 --> 00:09:09,282
>> Audiența: Va aceste slide-uri și
toată chestia asta să fie up-ish azi?

196
00:09:09,282 --> 00:09:11,586
ANDI Peng: Întotdeauna, da.

197
00:09:11,586 --> 00:09:13,710
Am de gând să încerce să pună
asta ca o oră după.

198
00:09:13,710 --> 00:09:16,626
Voi trimite un email pentru David, David va încerca să
pune-l ca o oră după asta.

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

200
00:09:20,040 --> 00:09:25,470
>> OK, astfel încât atunci vom trece în acest alt
structură de date minunat numit-o coadă.

201
00:09:25,470 --> 00:09:30,140
Ca voi puteti vedea aici, o
coadă, pentru britanici printre noi,

202
00:09:30,140 --> 00:09:32,010
tot ce este este o linie.

203
00:09:32,010 --> 00:09:34,680
Deci, contrar a ceea ce
crezi ca o stivă este,

204
00:09:34,680 --> 00:09:37,750
o coadă este exact ceea ce
logic credeți că este.

205
00:09:37,750 --> 00:09:41,914
Este deținut de regulile FIFO,
care este în primul intrat, primul ieșit.

206
00:09:41,914 --> 00:09:43,705
Dacă sunteți primul
unul în linie, ești

207
00:09:43,705 --> 00:09:46,230
prima care
iese din linia.

208
00:09:46,230 --> 00:09:49,680
>> Deci, ceea ce ne place să numim această
este dequeueing și enqueueing.

209
00:09:49,680 --> 00:09:52,380
Dacă vrem să adăugați ceva
la coada noastră, ne-am Puneți în coadă.

210
00:09:52,380 --> 00:09:55,690
Dacă vrem să dequeue, sau de a lua
ceva departe, ne-am dequeue.

211
00:09:55,690 --> 00:10:03,350
>> Deci același sens în care suntem un fel de
crearea de elemente de dimensiuni fixe pe care le

212
00:10:03,350 --> 00:10:06,500
poate stoca anumite
lucruri, dar putem, de asemenea

213
00:10:06,500 --> 00:10:10,100
schimba în cazul în care ne plasarea
Parametrii interiorul ei

214
00:10:10,100 --> 00:10:13,140
bazat pe ce tip de
funcționalitate vrem.

215
00:10:13,140 --> 00:10:16,700
Deci stive, am vrut ultimul
o, N pentru a fi primul unul.

216
00:10:16,700 --> 00:10:19,800
Coada este dorim primul lucru
în a fi primul lucru pe.

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

218
00:10:22,510 --> 00:10:26,710
>> Deci de tip struct
definesc, după cum puteți vedea,

219
00:10:26,710 --> 00:10:29,470
e un pic diferit
din ceea ce a fost stivă

220
00:10:29,470 --> 00:10:33,120
pentru că nu numai că trebuie să țină
urmări în cazul în care dimensiunea este, în prezent,

221
00:10:33,120 --> 00:10:37,420
am dori, de asemenea pentru a urmări a capului
precum și în cazul în care suntem în prezent sunt.

222
00:10:37,420 --> 00:10:39,580
Deci, cred că este mai ușor
dacă trag asta.

223
00:10:39,580 --> 00:10:53,270
Așa că haideți să ne imaginăm că avem o coadă,
Să spunem capul este chiar aici.

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

225
00:10:55,811 --> 00:10:58,310
Șeful de linie, să
doar spun că e prezent acolo,

226
00:10:58,310 --> 00:11:01,809
și vrem să introduceți
ceva în coada de așteptare.

227
00:11:01,809 --> 00:11:04,350
Am de gând pentru a apela, în esență, dimensiunea
este același lucru ca și coada,

228
00:11:04,350 --> 00:11:06,314
la sfârșitul anului oriunde coada este.

229
00:11:06,314 --> 00:11:07,730
Să spunem doar că dimensiunea este chiar aici.

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

231
00:11:14,380 --> 00:11:18,400
>> Deci, cum face un practic
introduce ceva într-o coadă?

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

233
00:11:21,000 --> 00:11:24,130
Ce index vrem să plasați
în cazul în care ne-o dorim pentru a introduce în.

234
00:11:24,130 --> 00:11:29,320
Dacă acesta este începutul tău
coadă și acesta este sfârșitul anului acesta

235
00:11:29,320 --> 00:11:31,860
sau dimensiunea acesteia, în cazul în care facem
doriți să adăugați următorul obiect?

236
00:11:31,860 --> 00:11:32,920
>> Audiența: [inaudibil]

237
00:11:32,920 --> 00:11:35,920
ANDI Peng: Exact, doriți să adăugați
l în funcție de ai scris.

238
00:11:35,920 --> 00:11:37,840
Fie acest este necompletat sau că este necompletat.

239
00:11:37,840 --> 00:11:42,630
Deci vrei să adauga, probabil,
aici, pentru că în cazul în care dimensiunea este--

240
00:11:42,630 --> 00:11:50,540
dacă acestea sunt pline, pe care doriți
adauga aici, nu?

241
00:11:50,540 --> 00:11:57,150
>> Și astfel că, în timp ce foarte, foarte
simplu, nu destul de corect întotdeauna

242
00:11:57,150 --> 00:12:00,690
pentru că principala diferență
între o coada si o stivă

243
00:12:00,690 --> 00:12:04,350
este faptul că coada poate
de fapt fi manipulat

244
00:12:04,350 --> 00:12:06,980
astfel încât modificările cap
în funcție de locul în care doriți

245
00:12:06,980 --> 00:12:08,650
începutul tac dumneavoastră pentru a începe.

246
00:12:08,650 --> 00:12:11,900
Și, ca rezultat, coada
este, de asemenea, va schimba.

247
00:12:11,900 --> 00:12:14,770
Și astfel încât să ia o privire la
acest cod acum.

248
00:12:14,770 --> 00:12:18,620
Ca voi, de asemenea, au fost rugati sa
scrie pe testul, Puneți în coadă.

249
00:12:18,620 --> 00:12:22,580
Poate vom vorbi prin ce
răspunsul a fost ceea ce a fost.

250
00:12:22,580 --> 00:12:26,790
>> Nu am putut potrivi destul de această linie pe una,
dar, în esență această bucată de cod

251
00:12:26,790 --> 00:12:29,030
ar trebui să fie pe o linie.

252
00:12:29,030 --> 00:12:30,140
Petreceți ca 30 de secunde.

253
00:12:30,140 --> 00:12:33,000
Aruncati o privire, și a vedea de ce
acesta este modul în care aceasta este.

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

255
00:12:50,030 --> 00:12:55,420
>> Foarte, foarte asemănătoare struct, foarte, foarte
structură similară ca în cazul precedent

256
00:12:55,420 --> 00:12:58,090
stiva cu excepția, poate, pentru
o linie de cod.

257
00:12:58,090 --> 00:13:01,190
Și că o linie de cod
determină funcționalitatea.

258
00:13:01,190 --> 00:13:03,900
Și-l diferențiază într-adevăr
o coadă dintr-o stivă.

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

260
00:13:18,510 --> 00:13:22,010
>> Oricine vrea să ia o lovitură de cuțit
la explica de ce ai

261
00:13:22,010 --> 00:13:24,980
luat acest lucru complicat aici?

262
00:13:24,980 --> 00:13:27,845
Vedem revenirea nostru
minunat prieten modul.

263
00:13:27,845 --> 00:13:31,020
Ca voi va veni în curând
să recunoască în programare,

264
00:13:31,020 --> 00:13:34,910
aproape oricand ai nevoie de ceva
să-și încheie în jurul valorii de nimic,

265
00:13:34,910 --> 00:13:36,850
modul va fi modul de a face acest lucru.

266
00:13:36,850 --> 00:13:40,510
Deci, știind că, nimeni nu vrea
pentru a încerca să explice că linie de cod?

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

268
00:13:44,060 --> 00:13:47,507
Da, toate răspunsurile sunt
acceptat și bun venit.

269
00:13:47,507 --> 00:13:48,840
Audiența: Vorbești cu mine?

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

271
00:13:49,506 --> 00:13:56,200
Audiența: Oh, nu îmi pare rău.

272
00:13:56,200 --> 00:14:00,250
ANDI Peng: OK, așa că hai să
plimbare prin acest cod.

273
00:14:00,250 --> 00:14:03,642
Deci, atunci când sunteți încercarea de a
adăugați ceva pe-o coadă,

274
00:14:03,642 --> 00:14:08,510
în cazul în care se întâmplă minunat cap
să fie aici, e foarte ușor pentru noi

275
00:14:08,510 --> 00:14:10,960
pentru a merge doar până la capăt
introduce ceva, nu?

276
00:14:10,960 --> 00:14:14,690
Dar ideea de o coadă este
că șeful de fapt, poate dinamic

277
00:14:14,690 --> 00:14:17,280
modifica în funcție de cazul în care ne-am
doresc începerea Q nostru de a fi,

278
00:14:17,280 --> 00:14:19,880
și, ca atare, coada
este, de asemenea, va schimba.

279
00:14:19,880 --> 00:14:31,100
>> Și așa ne imaginăm că nu acesta este fost
coadă, ci mai degrabă aceasta a fost coada.

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

281
00:14:37,900 --> 00:14:39,330
Să spunem că capul este chiar aici.

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

283
00:14:54,900 --> 00:14:56,980
Să spunem coadă nostru arata ca aceasta.

284
00:14:56,980 --> 00:15:00,190
Dacă ne-am dorit pentru a schimba în cazul în care
începutul liniei este,

285
00:15:00,190 --> 00:15:03,400
să spunem că ne-am mutat capul
în acest fel și dimensiuni de aici.

286
00:15:03,400 --> 00:15:07,100
>> Acum dorim să adăugăm ceva la
această coadă, dar voi poate vedea,

287
00:15:07,100 --> 00:15:11,150
nu este atât de simplu ca doar la
adauga tot ceea ce este după mărimea

288
00:15:11,150 --> 00:15:13,630
pentru că atunci ne-am alerga afară de
limite de oferta noastră reală.

289
00:15:13,630 --> 00:15:16,190
În cazul în care dorim să adăugați într-adevăr este aici.

290
00:15:16,190 --> 00:15:18,610
Asta e frumusetea de o coadă
este că pentru noi, vizual se

291
00:15:18,610 --> 00:15:22,380
arata ca linia merge ca aceasta,
dar atunci când este păstrat într-o structură de date,

292
00:15:22,380 --> 00:15:29,370
ei da ca ca un ciclu.

293
00:15:29,370 --> 00:15:32,360
Un fel de se încadrează în jurul
în față la fel

294
00:15:32,360 --> 00:15:34,780
că o linie poate, de asemenea încheia
în jurul valorii de în funcție de oriunde te-ai

295
00:15:34,780 --> 00:15:36,279
doresc să începutul liniei de a fi.

296
00:15:36,279 --> 00:15:38,630
Și așa, dacă vom lua o
uite aici, să

297
00:15:38,630 --> 00:15:40,880
spune am vrut să creeze un
functie numita Puneți în coadă.

298
00:15:40,880 --> 00:15:43,980
Ne-am dorit pentru a adăuga int n în care q.

299
00:15:43,980 --> 00:15:49,250
Dacă q.size q-- vom suna ca datele noastre
structure-- dacă queue.size nostru nu

300
00:15:49,250 --> 00:15:52,520
egală cu capacitatea sau dacă
este mai puțin decât capacitatea,

301
00:15:52,520 --> 00:15:55,120
q.strings este matrice în q nostru.

302
00:15:55,120 --> 00:15:58,380
Vom stabili
care egal cu q.heads,

303
00:15:58,380 --> 00:16:02,730
care este chiar aici, plus q.size
Modulul de capacitatea, care

304
00:16:02,730 --> 00:16:04,290
înfășurați-ne înapoi pe aici.

305
00:16:04,290 --> 00:16:08,040
>> Deci, în acest exemplu, indicele
de cap este de 1, nu?

306
00:16:08,040 --> 00:16:11,480
Indicele de mărime este 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Deci, putem face un plus 4 modul
prin capacitatea noastră, care este de 5.

308
00:16:19,500 --> 00:16:20,920
Ce ne dea?

309
00:16:20,920 --> 00:16:23,270
Care este indicele care
iese din asta?

310
00:16:23,270 --> 00:16:24,080
>> Audiența: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI Peng: 0, care
se întâmplă să fie chiar aici,

312
00:16:27,870 --> 00:16:30,640
și așa ne-o dorim să fie în măsură
pentru a introduce în chiar aici.

313
00:16:30,640 --> 00:16:34,730
Și astfel această ecuație aici gen
de doar funcționează cu orice numere

314
00:16:34,730 --> 00:16:36,750
în funcție de locul dvs.
cap și dimensiunea sunt.

315
00:16:36,750 --> 00:16:38,541
Dacă știi ce cei
lucrurile sunt, știi

316
00:16:38,541 --> 00:16:43,170
exact unde doriți să inserați
tot ce este dupa coada ta.

317
00:16:43,170 --> 00:16:44,640
Asta face sens pentru toată lumea?

318
00:16:44,640 --> 00:16:48,560
>> Știu un fel de creier
teaser mai ales că acest

319
00:16:48,560 --> 00:16:50,512
a venit în urma test dumneavoastră.

320
00:16:50,512 --> 00:16:52,220
Dar sperăm că toată lumea
acum se poate înțelege

321
00:16:52,220 --> 00:16:57,800
de ce această soluție sau acest
funcție este modul în care aceasta este.

322
00:16:57,800 --> 00:16:59,840
Oricine un pic neclar cu privire la acest?

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

324
00:17:03,471 --> 00:17:03,970
BINE.

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

326
00:17:07,109 --> 00:17:09,970
>> Și așa acum, dacă
a vrut să dequeue, acest

327
00:17:09,970 --> 00:17:15,240
este în cazul în care capul nostru ar fi trecerea
pentru că dacă ar fi să dequeue,

328
00:17:15,240 --> 00:17:17,030
nu ne scoate la sfârșitul q.

329
00:17:17,030 --> 00:17:19,130
Vrem să-și scoată capul, nu?

330
00:17:19,130 --> 00:17:24,260
Deci, ca urmare, cap se va schimba,
și de aceea, atunci când Puneți în coadă,

331
00:17:24,260 --> 00:17:26,800
le-ați luat pentru a urmări
în cazul în care capul și dimensiunea

332
00:17:26,800 --> 00:17:29,450
trebuie să fie capabilă să insereze
în poziția corectă.

333
00:17:29,450 --> 00:17:32,740
>> Și așa, atunci când dequeue,
Am, de asemenea, o pseudocod afară.

334
00:17:32,740 --> 00:17:35,480
Simțiți-vă liber să, dacă doriți
să încerce codificare asta.

335
00:17:35,480 --> 00:17:36,980
Doriți să mutați capul, nu?

336
00:17:36,980 --> 00:17:39,320
Dacă aș vrea să dequeue, am
s-ar muta capul peste.

337
00:17:39,320 --> 00:17:40,800
Acest lucru ar fi capul.

338
00:17:40,800 --> 00:17:45,617
>> Și dimensiunea noastră actuală ar
scade pentru că noi nu mai

339
00:17:45,617 --> 00:17:46,950
au patru elemente din matrice.

340
00:17:46,950 --> 00:17:51,370
Avem doar trei, iar apoi ne-o dorim
pentru a reveni orice a fost depozitat în interiorul

341
00:17:51,370 --> 00:17:56,260
a capului pentru că vrem să profit de această
Valoarea așa de foarte similar cu stiva.

342
00:17:56,260 --> 00:17:58,010
Doar tu iei
dintr-un loc diferit,

343
00:17:58,010 --> 00:18:01,770
și va trebui să realocați indicatorul
la alt loc ca un rezultat.

344
00:18:01,770 --> 00:18:03,890
În mod logic, toată lumea să urmeze?

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

346
00:18:05,690 --> 00:18:10,156
>> OK, deci vom vorbi un pic
mai în profunzime despre listele legate

347
00:18:10,156 --> 00:18:13,280
pentru că ei vor fi foarte, foarte valoros
pentru tine în cursul acestei saptamani

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

349
00:18:14,964 --> 00:18:17,130
Liste legate, ca voi
pot aminti, toate acestea sunt

350
00:18:17,130 --> 00:18:22,570
sunt noduri care sunt nodurile de anumite
Valorile atât o valoare și un pointer

351
00:18:22,570 --> 00:18:26,290
care sunt legate împreună
de aceste indicii.

352
00:18:26,290 --> 00:18:29,880
Și astfel struct cu privire la modul
vom crea un nod aici e că

353
00:18:29,880 --> 00:18:33,569
au int n, care este indiferent
valoarea într-un magazin sau un șir n

354
00:18:33,569 --> 00:18:35,610
sau ce vrei să
numesc, n stele char.

355
00:18:35,610 --> 00:18:41,482
Struct stele nod, care este indicatorul
pe care doriți să aveți în fiecare nod,

356
00:18:41,482 --> 00:18:43,690
ai de gând să aibă ca
Punct de pointer spre viitor.

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

358
00:18:48,207 --> 00:18:50,040
Vei avea capul
de o listă care este legat

359
00:18:50,040 --> 00:18:53,140
a merge la punctul de restul
valorile așa mai departe și așa mai departe

360
00:18:53,140 --> 00:18:55,290
până când ajungeți în cele din urmă la sfârșitul.

361
00:18:55,290 --> 00:18:58,040
Și acest ultim nod este doar
va să nu aibă un pointer.

362
00:18:58,040 --> 00:18:59,952
Se va indica
nul, și atunci

363
00:18:59,952 --> 00:19:01,910
știi că ai lovit
sfârșitul listei de legat

364
00:19:01,910 --> 00:19:04,076
este atunci când ultima dvs. pointer
nu indică nimic.

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

366
00:19:06,670 --> 00:19:10,990
>> Deci vom merge un pic mai mult în
profunzime cu privire la modul în care s-ar putea, eventual,

367
00:19:10,990 --> 00:19:12,400
Căutare o listă legată.

368
00:19:12,400 --> 00:19:15,460
Amintiți-vă ce sunt unele dintre
dezavantaje ale listelor legate

369
00:19:15,460 --> 00:19:19,340
versetele o serie cu privire la căutări.

370
00:19:19,340 --> 00:19:22,565
O serie puteți căuta binar, dar
de ce nu se poate face asta într-o listă legată?

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

372
00:19:26,834 --> 00:19:30,320
>> Audiența: Pentru că sunt toate conectate,
dar nu știu de unde destul de

373
00:19:30,320 --> 00:19:31,330
[Neauzit].

374
00:19:31,330 --> 00:19:34,600
>> ANDI Peng: Da, exact așa amintesc
că strălucirea de o serie

375
00:19:34,600 --> 00:19:37,190
a fost faptul că am avut
memorie cu acces aleator în cazul în care

376
00:19:37,190 --> 00:19:41,580
dacă am vrut valoarea din indexul
șase, am putea spune doar index șase,

377
00:19:41,580 --> 00:19:42,407
da-mi ca valoarea.

378
00:19:42,407 --> 00:19:45,240
Și asta pentru că matrice sunt sortate
într-un spațiu contiguu de memorie

379
00:19:45,240 --> 00:19:48,020
într-un singur loc, în timp ce
fel de liste legate

380
00:19:48,020 --> 00:19:52,820
sunt intercalate aleator în jurul,
și singura modalitate de puteți găsi unul

381
00:19:52,820 --> 00:19:56,890
este printr-un pointer care vă spune
adresa de unde care nod următor este.

382
00:19:56,890 --> 00:20:00,290
>> Și astfel, ca urmare, singura cale
pentru a căuta într-o listă legată

383
00:20:00,290 --> 00:20:01,560
este căutarea liniară.

384
00:20:01,560 --> 00:20:05,890
Pentru că nu știu exact unde
valoarea 12 în lista legat este,

385
00:20:05,890 --> 00:20:08,780
Trebuie să traverseze în întregime
de care lista pe o legătură

386
00:20:08,780 --> 00:20:12,450
câte unul de la cap la primul nod,
la al doilea nod, la a treia nodul,

387
00:20:12,450 --> 00:20:17,690
tot drumul în jos, până când în cele din urmă mă
unde acel nod caut este.

388
00:20:17,690 --> 00:20:22,110
Și astfel, în acest sens, căutare
pe o listă legată este întotdeauna n.

389
00:20:22,110 --> 00:20:23,040
Este întotdeauna n.

390
00:20:23,040 --> 00:20:25,690
E mereu la timp liniar.

391
00:20:25,690 --> 00:20:28,470
>> Și astfel codul în care
punem în aplicare acest lucru, iar acest lucru

392
00:20:28,470 --> 00:20:32,620
este un pic nou pentru voi de când ați
baieti nu au într-adevăr vorbit despre sau vreodată

393
00:20:32,620 --> 00:20:35,000
indicii văzut în modul de
căutare prin indicii,

394
00:20:35,000 --> 00:20:37,670
asa ca vom trece prin
acest lucru foarte, foarte încet.

395
00:20:37,670 --> 00:20:40,200
Deci căutare bool, dreapta,
să ne imaginăm vrem

396
00:20:40,200 --> 00:20:42,820
pentru a crea o funcție numită
căutare care returnează true

397
00:20:42,820 --> 00:20:46,820
dacă ați găsit o valoare în interiorul strâns legat
listă și returnează false altfel.

398
00:20:46,820 --> 00:20:50,030
Lista de stele nod este
în prezent doar indicatorul

399
00:20:50,030 --> 00:20:52,960
la primul element din lista de legat.

400
00:20:52,960 --> 00:20:56,700
int n este valoarea pe care ești
căutarea în această listă.

401
00:20:56,700 --> 00:20:58,770
>> Deci, pointer stele nod este egal listă.

402
00:20:58,770 --> 00:21:00,970
Asta înseamnă că suntem de stabilire
și crearea unui pointer

403
00:21:00,970 --> 00:21:03,592
în acest primul nod din interiorul listei.

404
00:21:03,592 --> 00:21:04,300
Toată lumea cu mine?

405
00:21:04,300 --> 00:21:06,530
Deci, dacă ar fi să mergem
aici, mi-ar fi

406
00:21:06,530 --> 00:21:13,850
initializat un pointer care indică spre
indiferent capului că lista este.

407
00:21:13,850 --> 00:21:18,600
>> Și apoi odată ce te aici,
în timp ce indicatorul nu egal nul,

408
00:21:18,600 --> 00:21:22,160
astfel încât este bucla în care suntem
O să fie ulterior traversează

409
00:21:22,160 --> 00:21:25,940
restul lista noastră pentru că ceea ce
se întâmplă atunci când indicatorul este egal nul?

410
00:21:25,940 --> 00:21:27,550
Noi știm că have--

411
00:21:27,550 --> 00:21:28,450
>> Audiența: [inaudibil]

412
00:21:28,450 --> 00:21:31,491
>> ANDI Peng: Exact, așa știm că
am ajuns la sfârșitul listei, nu?

413
00:21:31,491 --> 00:21:34,470
Dacă te duci înapoi aici, fiecare nod
Trebuie arătând spre un alt nod

414
00:21:34,470 --> 00:21:36,550
și așa mai departe și așa mai departe
până în cele din urmă te-a lovit

415
00:21:36,550 --> 00:21:41,589
coada de lista legate,
care are un pointer care tocmai

416
00:21:41,589 --> 00:21:43,130
nu indică nicăieri, altele decât nr.

417
00:21:43,130 --> 00:21:47,510
Și ca să știți că, practic
lista este încă acolo sus

418
00:21:47,510 --> 00:21:50,900
până pointer nu este egal
nul deoarece odată ce este egal nul,

419
00:21:50,900 --> 00:21:53,310
știi că nu există mai multe lucruri.

420
00:21:53,310 --> 00:21:56,930
>> Deci, care este bucla în care suntem
Va trebui de căutare actuale.

421
00:21:56,930 --> 00:22:01,690
Și dacă pointer-- vedeți
acest tip de funcții săgeată acolo?

422
00:22:01,690 --> 00:22:06,930
Deci, dacă indicatorul de n, în cazul în care
indicatorul la n egal egal n,

423
00:22:06,930 --> 00:22:09,180
astfel că înseamnă că, dacă
indicatorul ca esti

424
00:22:09,180 --> 00:22:13,420
căutarea pe la sfârșitul fiecărui
nod este de fapt egală cu valoarea

425
00:22:13,420 --> 00:22:15,990
sunteți în căutarea pentru, apoi
doriți să reveniți adevărat.

426
00:22:15,990 --> 00:22:19,280
Deci, practic, dacă ești la un nod care
are valoarea pe care o căutați,

427
00:22:19,280 --> 00:22:23,550
știi că ai fost
posibilitatea de a căuta cu succes.

428
00:22:23,550 --> 00:22:27,150
>> În caz contrar, pe care doriți să setați
pointer la nodul următor.

429
00:22:27,150 --> 00:22:28,850
Asta este ceea ce linia de aici este de a face.

430
00:22:28,850 --> 00:22:31,750
Pointer este egal cu indicatorul următor.

431
00:22:31,750 --> 00:22:33,360
Toată lumea vedea cum că lucrează?

432
00:22:33,360 --> 00:22:36,580
>> Și, în esență, ai de gând să doar
traversa totalitatea listei,

433
00:22:36,580 --> 00:22:41,920
resetarea indicatorul de fiecare dată, până când
vă în cele din urmă a lovit la sfârșitul listei.

434
00:22:41,920 --> 00:22:45,030
Și știi că nu există
mai multe noduri pentru a căuta prin,

435
00:22:45,030 --> 00:22:47,999
și apoi vă puteți întoarce false
pentru că știți că, oh, bine,

436
00:22:47,999 --> 00:22:50,540
dacă am fost în stare pentru a căuta
prin totalitatea listei.

437
00:22:50,540 --> 00:22:54,530
Dacă în acest exemplu, dacă am vrut
să caute pentru valoarea de 10,

438
00:22:54,530 --> 00:22:57,250
și am început la cap, și
Caut tot drumul în jos,

439
00:22:57,250 --> 00:23:00,550
și, eventual, am ajuns la acest lucru, care
un pointer care indică spre nul,

440
00:23:00,550 --> 00:23:04,415
Știu asta, rahat, cred 10 nu este în
această listă pentru că nu am putut găsi.

441
00:23:04,415 --> 00:23:06,520
Și eu sunt la sfârșitul listei.

442
00:23:06,520 --> 00:23:11,040
Și în cazul în care știți
Am de gând să se întoarcă false.

443
00:23:11,040 --> 00:23:12,900
>> Lăsa să se scufunda într-un pic.

444
00:23:12,900 --> 00:23:17,350
Acest lucru va fi destul de
important pentru PSET ta.

445
00:23:17,350 --> 00:23:21,140
Logica este foarte simplu, poate
sintactic doar de punere în aplicare.

446
00:23:21,140 --> 00:23:23,365
Vreți să facă
vă că ați înțeles.

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

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

449
00:23:27,650 --> 00:23:32,560
>> OK, deci cum ne-ar fi
inserarea de noduri, drept,

450
00:23:32,560 --> 00:23:35,380
într-o listă amintesc că
Care sunt ceea ce a beneficiilor

451
00:23:35,380 --> 00:23:39,230
de a avea o listă legată față de
o serie în termeni de stocare?

452
00:23:39,230 --> 00:23:41,110
>> Audiența: E dinamic,
așa că este mai ușor sa--

453
00:23:41,110 --> 00:23:43,180
>> ANDI Peng: Exact,
așa că este dinamic, care

454
00:23:43,180 --> 00:23:46,880
înseamnă că se poate extinde și micșora
în funcție de nevoile utilizatorului.

455
00:23:46,880 --> 00:23:56,570
Și astfel, în acest sens, nu avem nevoie de
a deșeurilor de memorie inutile pentru că am

456
00:23:56,570 --> 00:24:00,850
dacă nu știu cât de multe valori Vreau
la magazin, aceasta nu are sens pentru mine

457
00:24:00,850 --> 00:24:04,310
pentru a crea un tablou pentru că
dacă vreau să stocați 10 valori

458
00:24:04,310 --> 00:24:08,380
și pot crea o serie de 1.000, care este
o mulțime de memorie pierdut, alocat.

459
00:24:08,380 --> 00:24:11,180
De aceea, dorim să utilizați o legătură
Lista pentru a putea dinamic

460
00:24:11,180 --> 00:24:13,860
schimba sau micșora dimensiunea noastră.

461
00:24:13,860 --> 00:24:17,040
>> Și pentru ca face inserție
un pic mai complicat.

462
00:24:17,040 --> 00:24:20,810
Din moment ce nu pot accesa la întâmplare elemente
modul în care ne-ar de o matrice.

463
00:24:20,810 --> 00:24:24,270
Dacă vreau să insera un element
în a șaptea index,

464
00:24:24,270 --> 00:24:26,930
Eu doar pot insera
în a șaptea index.

465
00:24:26,930 --> 00:24:30,020
Pe o listă legată, aceasta nu
destul de lucru la fel de ușor,

466
00:24:30,020 --> 00:24:34,947
și așa, dacă ne-am dorit pentru a introduce
cel aici, în lista legate,

467
00:24:34,947 --> 00:24:36,280
vizual, este foarte ușor pentru a vedea.

468
00:24:36,280 --> 00:24:39,363
Vrem doar să-l introduceți acolo,
chiar de la începutul listei,

469
00:24:39,363 --> 00:24:40,840
imediat după cap.

470
00:24:40,840 --> 00:24:44,579
>> Dar modul în care trebuie să realocați
indicii este un pic complicate

471
00:24:44,579 --> 00:24:47,620
sau, în mod logic, este logic, dar
doriți să vă asigurați că-l ai

472
00:24:47,620 --> 00:24:50,250
complet în jos pentru că
ultimul lucru pe care doriți

473
00:24:50,250 --> 00:24:52,990
este de a realoca un pointer
astfel încât facem aici.

474
00:24:52,990 --> 00:24:58,170
Dacă ați dereference
pointer la cap la 1,

475
00:24:58,170 --> 00:25:01,086
apoi dintr-o brusc
restul lista legate

476
00:25:01,086 --> 00:25:04,680
este pierdut pentru că nu au de fapt
creat un nimic temporară.

477
00:25:04,680 --> 00:25:06,220
Care a subliniat la 2.

478
00:25:06,220 --> 00:25:10,080
Dacă realocați indicatorul, apoi
restul de lista este total pierdut.

479
00:25:10,080 --> 00:25:13,310
Deci vrei să fie
foarte, foarte atent aici

480
00:25:13,310 --> 00:25:17,010
a atribui mai întâi
pointer la tot ce

481
00:25:17,010 --> 00:25:20,150
doriți să introduceți în oriunde
vrei, și apoi

482
00:25:20,150 --> 00:25:22,710
poate dereference restul listei.

483
00:25:22,710 --> 00:25:25,250
>> Deci, acest lucru este valabil pentru orice destinație
sunteți încercarea de a introduce în.

484
00:25:25,250 --> 00:25:27,520
Dacă doriți să introduceți la
cap, dacă doriți să răspundeți aici,

485
00:25:27,520 --> 00:25:29,455
dacă doriți să introduceți la
cele din urmă, ei bine, final am

486
00:25:29,455 --> 00:25:30,910
că v-ar doar
nu au nici o pointer, dar

487
00:25:30,910 --> 00:25:33,830
doriți să vă asigurați că nu
pierde restul listei.

488
00:25:33,830 --> 00:25:36,640
Mereu doriți să vă asigurați
noul nod este îndreptat

489
00:25:36,640 --> 00:25:39,330
spre tot ce
doresc să introduceți în,

490
00:25:39,330 --> 00:25:42,170
și apoi puteți adăuga înlănțuirii pe.

491
00:25:42,170 --> 00:25:43,330
Toată lumea clar?

492
00:25:43,330 --> 00:25:45,427
>> Acest lucru va fi
una dintre problemele reale.

493
00:25:45,427 --> 00:25:48,010
Una dintre cele mai importante aspecte
ai de gând să aibă pe PSET dvs.

494
00:25:48,010 --> 00:25:51,340
este că ai de gând să încercați să creați
o listă legată și lucruri Insert

495
00:25:51,340 --> 00:25:53,340
dar apoi doar pierde
restul lista legate.

496
00:25:53,340 --> 00:25:54,900
Și tu vei fi ca, am
nu știu de ce acest lucru se întâmplă?

497
00:25:54,900 --> 00:25:58,040
Și este o durere de a trece prin
și de căutare toate indicii tale.

498
00:25:58,040 --> 00:26:02,100
>> Și vă garantez pe acest PSET,
scris și de desen aceste noduri din

499
00:26:02,100 --> 00:26:03,344
va fi foarte, foarte util.

500
00:26:03,344 --> 00:26:06,010
Astfel încât să puteți ține evidența complet
de unde toate indicii tale sunt,

501
00:26:06,010 --> 00:26:08,540
ce se întâmplă greșit,
în cazul în care toate nodurile dumneavoastră sunt,

502
00:26:08,540 --> 00:26:12,660
ceea ce trebuie să faceți pentru a accesa sau
inserați sau ștergeți sau la oricare dintre ele.

503
00:26:12,660 --> 00:26:14,550
Toată lumea bună cu asta?

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

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

506
00:26:19,300 --> 00:26:22,600
>> Deci, dacă am vrut să se uite la codul?

507
00:26:22,600 --> 00:26:24,470
Oh, nu știu dacă am
Puteti vedea the-- OK, deci

508
00:26:24,470 --> 00:26:27,940
în partea de sus tot ce este este o funcție
numit inserție unde vrem

509
00:26:27,940 --> 00:26:31,365
pentru a insera int n în lista legat.

510
00:26:31,365 --> 00:26:32,740
Vom trece prin asta.

511
00:26:32,740 --> 00:26:34,770
Este o mulțime de cod, o mulțime de noi sintaxă.

512
00:26:34,770 --> 00:26:36,220
Vom fi în regulă.

513
00:26:36,220 --> 00:26:39,120
>> Deci până la partea de sus, ori de câte ori
dorim să creăm ceva

514
00:26:39,120 --> 00:26:42,380
ce trebuie să facem, mai ales dacă
doresc să nu fi stocate pe stiva

515
00:26:42,380 --> 00:26:43,920
dar în grămadă?

516
00:26:43,920 --> 00:26:45,460
Mergem la un malloc, nu?

517
00:26:45,460 --> 00:26:48,240
Deci vom crea un pointer.

518
00:26:48,240 --> 00:26:52,074
Nod, pointer, noi egali
malloc de mărimea unui nod

519
00:26:52,074 --> 00:26:53,740
pentru că vrem ca nod să fie create.

520
00:26:53,740 --> 00:26:56,720
Vrem cantitatea de
memorie care un nod preia

521
00:26:56,720 --> 00:26:59,300
care urmează să fie alocate pentru
crearea de noul nod.

522
00:26:59,300 --> 00:27:02,270
>> Și apoi vom verifica la
a vedea dacă noi egali egal nul.

523
00:27:02,270 --> 00:27:03,370
Amintiți-vă ce am spus?

524
00:27:03,370 --> 00:27:06,470
Orice ai malloc,
ceea ce trebuie să faci mereu?

525
00:27:06,470 --> 00:27:09,490
Trebuie să verificați întotdeauna pentru a vedea
sau nu, care este nul.

526
00:27:09,490 --> 00:27:13,620
>> De exemplu, în cazul în care dumneavoastră de operare
Sistemul a fost complet plin,

527
00:27:13,620 --> 00:27:17,060
dacă ați avut nici mai multă memorie la
toate și încercați să malloc,

528
00:27:17,060 --> 00:27:18,410
ar intoarce null pentru tine.

529
00:27:18,410 --> 00:27:21,094
Și așa că, dacă încercați să-l utilizați
când a fost îndreptat la nul,

530
00:27:21,094 --> 00:27:23,260
nu sunteți de gând să poată
pentru a accesa aceste informații.

531
00:27:23,260 --> 00:27:27,010
Și astfel, ca atare, ne-am dorit să
sigur că ori de câte ori sunteți mallocing,

532
00:27:27,010 --> 00:27:30,500
te mereu de verificare pentru a vedea dacă
că memoria dat la tine este nul.

533
00:27:30,500 --> 00:27:33,670
Și dacă nu e, atunci ne putem muta
mai departe cu restul codului nostru.

534
00:27:33,670 --> 00:27:36,140
>> Așa că am de gând să
inițializa noul nod.

535
00:27:36,140 --> 00:27:39,050
Vom face noi n este egal cu n.

536
00:27:39,050 --> 00:27:42,390
Și apoi ne-am de gând să faci
stabilit noi cursorul pe noua

537
00:27:42,390 --> 00:27:46,900
la null pentru că acum nu avem
vreau nimic pentru ca aceasta să indice.

538
00:27:46,900 --> 00:27:48,755
Nu avem nici o idee unde
o să te pun,

539
00:27:48,755 --> 00:27:50,630
și apoi, dacă vrem să
introduceți-l la cap,

540
00:27:50,630 --> 00:27:53,820
atunci putem realoca
indicatorul la cap.

541
00:27:53,820 --> 00:27:58,530
Are toată lumea să urmeze logica
de unde ce se intampla?

542
00:27:58,530 --> 00:28:02,502
>> Tot ce facem este de a crea un nou
nod, setarea indicatorul de nul,

543
00:28:02,502 --> 00:28:04,210
și apoi realocarea
l la cap dacă am

544
00:28:04,210 --> 00:28:06,320
Știu că vrei să-l introduceți la cap.

545
00:28:06,320 --> 00:28:09,420
Și apoi capul se va
punctul spre care nou nod.

546
00:28:09,420 --> 00:28:11,060
Toată lumea OK cu asta?

547
00:28:11,060 --> 00:28:12,380
>> Deci, este un proces în două etape.

548
00:28:12,380 --> 00:28:14,760
Trebuie să atribui primul
indiferent ce creați.

549
00:28:14,760 --> 00:28:18,260
Setați ca pointer la
de referință, și apoi

550
00:28:18,260 --> 00:28:21,400
poate un fel de dereference
prima indicatorul

551
00:28:21,400 --> 00:28:22,972
și punctul spre noul nod.

552
00:28:22,972 --> 00:28:25,680
Oriunde doriți să-l inserați,
că logica este de gând să dețină adevărat.

553
00:28:25,680 --> 00:28:27,530
>> E un fel de atribuire
variabile temporare.

554
00:28:27,530 --> 00:28:28,700
Amintiți-vă, ai
pentru a vă asigura că

555
00:28:28,700 --> 00:28:30,346
Nu pierde urma, dacă sunteți pompare.

556
00:28:30,346 --> 00:28:33,470
Doriți să vă asigurați că aveți o
variabilă temporară acest tip de tine

557
00:28:33,470 --> 00:28:35,620
urmări în cazul în care acel lucru
este depozitat astfel încât să

558
00:28:35,620 --> 00:28:41,190
Nu pierde nici o valoare în cursul
de cum ar fi în jur de joc cu ea.

559
00:28:41,190 --> 00:28:42,710
>> OK, deci codul va fi aici.

560
00:28:42,710 --> 00:28:45,020
Voi arunca o privire după secțiune.

561
00:28:45,020 --> 00:28:48,060
Acesta va fi acolo.

562
00:28:48,060 --> 00:28:50,280
>> Deci cred cum se
acest diferă dacă ne-am dorit

563
00:28:50,280 --> 00:28:52,300
pentru a introduce în mijlocul sau la sfârșitul?

564
00:28:52,300 --> 00:28:57,892
Are cineva are o idee de ceea ce este
pseudocod ca referință logică

565
00:28:57,892 --> 00:29:00,350
care ne-ar lua dacă ne-am dorit
pentru al introduce în mijloc?

566
00:29:00,350 --> 00:29:03,391
Deci, dacă am vrut să-l introduceți la
cap, tot ce faceți este să creați un nou nod.

567
00:29:03,391 --> 00:29:06,311
Am stabilit indicatorul de care
nod nou la orice cap,

568
00:29:06,311 --> 00:29:08,310
și apoi ne-am stabilit capul
la noul nod, nu?

569
00:29:08,310 --> 00:29:11,560
Dacă am vrut să-l introducă în mijlocul
a listei, ceea ce ar trebui să facem?

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

571
00:29:14,108 --> 00:29:16,110
>> Audiența: Ar fi încă
fie un proces similar

572
00:29:16,110 --> 00:29:19,114
ca și cum atribuirea pointer și
apoi atribuirea că pointer,

573
00:29:19,114 --> 00:29:20,530
dar ne-ar trebui pentru a localiza acolo.

574
00:29:20,530 --> 00:29:23,560
>> ANDI Peng: Exact, așa exact
același proces în afară de tine

575
00:29:23,560 --> 00:29:27,820
Trebuie să localizeze unde te
doresc ca noi să se deplaseze indicatorul în,

576
00:29:27,820 --> 00:29:44,790
așa că dacă vreau să insera în
mijlocul legate list-- OK,

577
00:29:44,790 --> 00:29:46,370
să spunem că e lista noastră legată.

578
00:29:46,370 --> 00:29:49,500
Dacă vrem să-l inserați aici,
vom crea un nou nod.

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

580
00:29:50,520 --> 00:29:52,220
Vom crea un nou nod.

581
00:29:52,220 --> 00:29:55,940
Vom fi atribuit
pointer de acest nod aici.

582
00:29:55,940 --> 00:29:58,335
>> Dar problema care diferă
de unde capul este

583
00:29:58,335 --> 00:30:00,490
este că am știut exact
în cazul în care capul este.

584
00:30:00,490 --> 00:30:01,930
Acesta a fost chiar la început, nu?

585
00:30:01,930 --> 00:30:04,870
Dar aici avem de a urmări
de unde ne-l introduceți în.

586
00:30:04,870 --> 00:30:07,930
Dacă suntem introducerea nostru
nod aici, avem

587
00:30:07,930 --> 00:30:12,270
pentru a vă asigura că
un precedent pentru acest nod

588
00:30:12,270 --> 00:30:14,172
este cel care reassigns indicatorul.

589
00:30:14,172 --> 00:30:16,380
Deci atunci va trebui să fel de
urmări două lucruri.

590
00:30:16,380 --> 00:30:19,420
Dacă vă urmări în cazul în care acest lucru
nod în prezent este introducerea în.

591
00:30:19,420 --> 00:30:23,280
Trebuie, de asemenea, pentru a urmări în cazul în care
nodul anterior că sunteți în căutarea la

592
00:30:23,280 --> 00:30:24,340
a fost de asemenea acolo.

593
00:30:24,340 --> 00:30:25,830
Toată lumea bună cu asta?

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

595
00:30:26,500 --> 00:30:28,000
>> Cum despre introducerea în cele din urmă?

596
00:30:28,000 --> 00:30:34,220
Dacă am vrut să-l adăugați here-- dacă aș vrea
pentru a adăuga un nou nod la sfârșitul unei liste,

597
00:30:34,220 --> 00:30:37,009
cum s-ar putea să merg despre a face asta?

598
00:30:37,009 --> 00:30:39,300
Audiența: Deci prezent,
a subliniat ultima la null.

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

600
00:30:40,960 --> 00:30:43,560
Exact, așa aceasta
în prezent este indicat să știe,

601
00:30:43,560 --> 00:30:46,720
și așa cred că, în acest sens, este
foarte ușor de a adăuga la sfârșitul unei liste.

602
00:30:46,720 --> 00:30:51,810
Tot ce trebuie să faceți este să-l setat
egală cu null si apoi boom-ul.

603
00:30:51,810 --> 00:30:53,070
Chiar acolo, foarte usor.

604
00:30:53,070 --> 00:30:53,960
Foarte simplu.

605
00:30:53,960 --> 00:30:56,430
>> Foarte similar cu
cap, dar în mod logic te

606
00:30:56,430 --> 00:30:59,690
doriți să vă asigurați că pașii
luați spre a face orice de acest lucru,

607
00:30:59,690 --> 00:31:01,500
te în urma de-a lungul.

608
00:31:01,500 --> 00:31:04,420
Este foarte ușor să, în mijloc
de codul, prins pe,

609
00:31:04,420 --> 00:31:05,671
oh, am atât de multe indicii.

610
00:31:05,671 --> 00:31:07,461
Nu știu unde
ceva se indică spre.

611
00:31:07,461 --> 00:31:09,170
Nu știu nici ce nod sunt pe.

612
00:31:09,170 --> 00:31:11,490
Ce se intampla?

613
00:31:11,490 --> 00:31:13,620
>> Relaxați-vă, calma, să ia o respiratie adanca.

614
00:31:13,620 --> 00:31:15,530
Scoate lista dvs. legate.

615
00:31:15,530 --> 00:31:18,800
Dacă spui, știu unde
Am nevoie de a introduce acest lucru în

616
00:31:18,800 --> 00:31:22,970
și știu exact cum să realocați meu
indicii, mult, mult mai ușor să-și imagineze

617
00:31:22,970 --> 00:31:27,200
out-- mult, mult mai ușor să nu
se pierd in bug-uri de codul.

618
00:31:27,200 --> 00:31:29,410
Toată lumea OK cu asta?

619
00:31:29,410 --> 00:31:31,380
BINE.

620
00:31:31,380 --> 00:31:35,120
>> Deci cred un concept pe care nu am
într-adevăr a vorbit despre înainte de acum,

621
00:31:35,120 --> 00:31:38,131
și te-am ghicit, probabil,
nu se va întâlni mult yet--

622
00:31:38,131 --> 00:31:40,880
e un fel de concept-- avansat
este că avem de fapt o date

623
00:31:40,880 --> 00:31:43,900
structura numita o listă de două ori legată.

624
00:31:43,900 --> 00:31:46,390
Deci, ca voi poate vedea,
tot ce facem este crearea

625
00:31:46,390 --> 00:31:50,400
o valoare reală, un plus de
indicatorul pe fiecare din noduri noastre

626
00:31:50,400 --> 00:31:52,660
care, de asemenea, puncte de la nodul anterior.

627
00:31:52,660 --> 00:31:58,170
Deci, nu numai că ne-am nostru
noduri punct la următoarea.

628
00:31:58,170 --> 00:32:01,430
Ei, de asemenea punctul de la cel anterior.

629
00:32:01,430 --> 00:32:04,310
Am de gând să ignore aceste două chiar acum.

630
00:32:04,310 --> 00:32:06,740
>> Deci atunci aveți un lanț
care poate muta în ambele sensuri,

631
00:32:06,740 --> 00:32:09,630
și atunci este un pic mai ușor
să urmeze în mod logic de-a lungul.

632
00:32:09,630 --> 00:32:11,896
Ca aici, în loc de
urmărirea de, oh, am

633
00:32:11,896 --> 00:32:14,520
trebuie să știi că acest nod este
cel care trebuie să realocați,

634
00:32:14,520 --> 00:32:17,532
Eu pot merge doar aici și
doar trage anterior.

635
00:32:17,532 --> 00:32:19,490
Atunci știu exact unde
care este, și apoi

636
00:32:19,490 --> 00:32:21,130
nu trebuie să traverseze
elementele listei de legătura.

637
00:32:21,130 --> 00:32:22,180
Este un pic mai ușor.

638
00:32:22,180 --> 00:32:24,960
>> Dar, ca atare, trebuie de două ori
cantitatea de indicii,

639
00:32:24,960 --> 00:32:26,960
asta e dublu față de cantitatea de memorie.

640
00:32:26,960 --> 00:32:28,950
Este o mulțime de indicii pentru a urmări.

641
00:32:28,950 --> 00:32:32,140
Este un pic mai complex, dar este
un pic mai mult de utilizat în funcție

642
00:32:32,140 --> 00:32:34,080
pe ceea ce încearcă să realizeze.

643
00:32:34,080 --> 00:32:36,910
>> Deci, acest tip de date
structură există total,

644
00:32:36,910 --> 00:32:40,280
și structura este foarte, foarte
simplu cu excepția tot ce avea este,

645
00:32:40,280 --> 00:32:43,850
în loc de doar un pointer la următorul,
aveți, de asemenea un pointer la anterioară.

646
00:32:43,850 --> 00:32:45,940
Asta e tot diferența a fost.

647
00:32:45,940 --> 00:32:47,740
Toată lumea bună cu asta?

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

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

650
00:32:50,940 --> 00:32:53,280
>> Bine, asa ca acum eu sunt
să-și petreacă într-adevăr, probabil,

651
00:32:53,280 --> 00:32:56,870
ca 15 la 20 minute sau cea mai mare parte
a restul timpului în secțiunea

652
00:32:56,870 --> 00:32:58,360
vorbesc despre tabele de dispersie.

653
00:32:58,360 --> 00:33:02,590
Câți dintre voi
au citit spec pset5?

654
00:33:02,590 --> 00:33:03,620
Bine, bine.

655
00:33:03,620 --> 00:33:06,160
Asta e mai mare decât 50% din normal.

656
00:33:06,160 --> 00:33:07,560
E bine.

657
00:33:07,560 --> 00:33:10,345
>> Deci, ca voi vedea,
esti provocare în pset5

658
00:33:10,345 --> 00:33:16,790
va fi de a pune în aplicare un dicționar
în cazul în care încărcați peste 140.000 de cuvinte

659
00:33:16,790 --> 00:33:20,610
că vă oferim și verificare a ortografiei
se împotriva tot textul.

660
00:33:20,610 --> 00:33:22,580
Vă vom da aleatoare
piese de literatură.

661
00:33:22,580 --> 00:33:23,520
Vă vom oferi Odiseea.

662
00:33:23,520 --> 00:33:24,561
Vă vom oferi Iliada.

663
00:33:24,561 --> 00:33:26,350
Vă vom oferi Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> Și provocarea
va fi de a scrie cec

665
00:33:28,220 --> 00:33:31,760
fiecare cuvânt în toate
dintre aceste dicționare

666
00:33:31,760 --> 00:33:34,960
în esență, cu checker nostru vraja.

667
00:33:34,960 --> 00:33:38,620
Și așa sunt câteva piese
de a crea acest PSET,

668
00:33:38,620 --> 00:33:41,970
în primul rând pe care doriți să fie
capabil de a încărca de fapt

669
00:33:41,970 --> 00:33:43,970
toate cuvintele dvs. în
dicționar, și apoi

670
00:33:43,970 --> 00:33:45,530
doresc să fie în măsură să
vraja verifica toate.

671
00:33:45,530 --> 00:33:48,780
Și astfel, ca atare, ai de gând să solicite
o structură de date care pot face acest lucru rapid

672
00:33:48,780 --> 00:33:50,790
și eficient și dinamic.

673
00:33:50,790 --> 00:33:52,900
>> Deci, cred că cel mai ușor
mod de a face acest lucru,

674
00:33:52,900 --> 00:33:55,010
ar crea, probabil, o serie, nu?

675
00:33:55,010 --> 00:33:58,910
Cel mai simplu mod de depozitare este de tine
poate crea o serie de 140.000 de cuvinte

676
00:33:58,910 --> 00:34:03,400
și doar le pe toate acolo și puneți
apoi traversează le de căutare binară

677
00:34:03,400 --> 00:34:06,780
sau prin selecții sau not--
pare rău că e de sortare.

678
00:34:06,780 --> 00:34:10,729
Le puteți sorta și apoi le traversa
de căutare binară sau Căutare doar liniar

679
00:34:10,729 --> 00:34:13,730
și doar finale cuvintele, dar că
ia o mare cantitate de memorie,

680
00:34:13,730 --> 00:34:15,190
și nu este foarte eficient.

681
00:34:15,190 --> 00:34:18,350
>> Și așa vom începe
vorbesc despre moduri de a face

682
00:34:18,350 --> 00:34:20,110
timpul nostru de funcționare mai eficientă.

683
00:34:20,110 --> 00:34:23,190
Și scopul nostru este de a obtine
constanta de timp în cazul în care

684
00:34:23,190 --> 00:34:25,810
e aproape ca în cazul în care, tablouri
aveți acces instantaneu.

685
00:34:25,810 --> 00:34:28,560
Dacă aș fi vrut pentru a căuta ceva,
Vreau să fie în măsură să doar,

686
00:34:28,560 --> 00:34:30,810
boom-ul, se pare exact, și trageți-l afară.

687
00:34:30,810 --> 00:34:34,100
Și astfel o structură în care
vom deveni foarte aproape

688
00:34:34,100 --> 00:34:37,569
a putea accesa constantă
timp, această Sfântul Graal

689
00:34:37,569 --> 00:34:41,370
în programarea constant
timp este numit un tabel hash.

690
00:34:41,370 --> 00:34:45,370
Și astfel David menționat anterior
[Inaudibil] un pic în curs,

691
00:34:45,370 --> 00:34:49,100
dar vom într-adevăr
se arunca cu capul în adâncime în această săptămână

692
00:34:49,100 --> 00:34:51,780
pe o piesă care în ceea ce privește
cum funcționează un tabel hash.

693
00:34:51,780 --> 00:34:53,949
>> Deci modul în care un hash
lucrări de masă, de exemplu,

694
00:34:53,949 --> 00:35:00,230
dacă am vrut pentru a stoca o mulțime de cuvinte, un
grămadă de cuvinte în limba engleză,

695
00:35:00,230 --> 00:35:02,940
Am putea pune, teoretic,
banane, mere, kiwi, mango, pereche,

696
00:35:02,940 --> 00:35:04,980
și pepene galben toate doar pe o matrice.

697
00:35:04,980 --> 00:35:07,044
Acestea ar putea potrivi toate în și să fie găsiți.

698
00:35:07,044 --> 00:35:09,210
Ar fi un fel de o durere de
căuta prin și de acces,

699
00:35:09,210 --> 00:35:12,920
dar cale mai ușoară de a face acest lucru este
pe care le poate crea de fapt o structură

700
00:35:12,920 --> 00:35:15,680
numit un tabel hash care ne hash.

701
00:35:15,680 --> 00:35:19,880
Vom rula toate cheile prin
o funcție hash, o ecuație,

702
00:35:19,880 --> 00:35:22,600
care-le pe toate se transformă în
un fel de valoare

703
00:35:22,600 --> 00:35:28,740
că atunci putem stoca pe
în esență, o serie de liste legate.

704
00:35:28,740 --> 00:35:32,570
>> Și astfel aici, dacă ne-am dorit
pentru a stoca cuvinte în limba engleză,

705
00:35:32,570 --> 00:35:37,250
am putea eventual doar, eu nu
știu, rândul său, toate primele litere

706
00:35:37,250 --> 00:35:39,630
într-un fel a unui număr.

707
00:35:39,630 --> 00:35:43,140
Și astfel, de exemplu, în cazul în care mi-am dorit
O să fie sinonim cu apple--

708
00:35:43,140 --> 00:35:47,460
sau cu indicele de 0, și
B pentru a fi sinonim cu 1,

709
00:35:47,460 --> 00:35:51,030
putem avea 26 de intrări
care poate stoca doar

710
00:35:51,030 --> 00:35:53,610
toate literele
alfabet că vom începe cu.

711
00:35:53,610 --> 00:35:56,130
Si atunci putem avea
mere la indicele de 0.

712
00:35:56,130 --> 00:35:59,160
Putem avea banane la indicele de
1, pepene galben la indicele de 2,

713
00:35:59,160 --> 00:36:00,540
și așa mai departe și așa mai departe.

714
00:36:00,540 --> 00:36:04,460
Și astfel, dacă am vrut să căutare
hash meu de masă și de acces de mere,

715
00:36:04,460 --> 00:36:07,560
Știu de mere începe cu
o A, și știu exact

716
00:36:07,560 --> 00:36:10,860
că trebuie să fie și hash
masa la index 0, deoarece

717
00:36:10,860 --> 00:36:13,620
de funcția atribuită anterior.

718
00:36:13,620 --> 00:36:16,572
>> Deci, eu nu știu, suntem
un program de utilizator în cazul în care

719
00:36:16,572 --> 00:36:18,780
veți fi taxat cu
nu arbitrarily-- arbitrar,

720
00:36:18,780 --> 00:36:22,530
cu încercarea de a gînditor
cred că de ecuații bune

721
00:36:22,530 --> 00:36:25,460
să fie capabil să se răspândească
din toate valorile

722
00:36:25,460 --> 00:36:29,370
într-un fel, ei pot accesa cu ușurință
mai târziu la o ecuație cu ca

723
00:36:29,370 --> 00:36:31,130
pe care le, le știu.

724
00:36:31,130 --> 00:36:35,210
Deci, în sensul dacă am vrut să merg la
mango, știu, oh, aceasta începe cu m.

725
00:36:35,210 --> 00:36:37,134
Acesta trebuie să fie la indicele de 12.

726
00:36:37,134 --> 00:36:38,800
Nu trebuie să căutați prin nimic.

727
00:36:38,800 --> 00:36:42,080
Știu exactly-- am putea merge doar la
indicele de 12 și trageți asta.

728
00:36:42,080 --> 00:36:45,520
>> Toată lumea clar cu privire la modul de
Funcția de tabelă hash funcționează?

729
00:36:45,520 --> 00:36:48,380
E un fel de doar o gamă mult mai complex.

730
00:36:48,380 --> 00:36:50,010
Asta e tot ce este.

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

732
00:36:51,630 --> 00:36:57,690
>> Deci cred că rula în
această problemă de ceea ce

733
00:36:57,690 --> 00:37:06,390
se întâmplă dacă aveți mai multe lucruri
care vă oferă același index?

734
00:37:06,390 --> 00:37:10,570
Deci, spune funcția noastră, tot ce
a făcut a fost că prima literă ia

735
00:37:10,570 --> 00:37:14,490
și să se întoarcă că într-o
respectiv de la 0 la 25 index.

736
00:37:14,490 --> 00:37:17,137
Asta e cu totul în regulă dacă
ai doar unul din fiecare.

737
00:37:17,137 --> 00:37:18,970
Dar al doilea a începe
având mai mult, ești

738
00:37:18,970 --> 00:37:20,910
Va trebui ceea ce se numește o coliziune.

739
00:37:20,910 --> 00:37:25,580
>> Deci, dacă am încerca să introduceți îngropa într-un hash
tabel care are deja banane pe ea,

740
00:37:25,580 --> 00:37:27,870
ce se va întâmpla atunci când
încercați să introduceți asta?

741
00:37:27,870 --> 00:37:30,930
Lucruri rele pentru că banana
există deja cadrul indicelui

742
00:37:30,930 --> 00:37:33,800
pe care doriți să-l stocați în.

743
00:37:33,800 --> 00:37:35,560
Berry fel de este ca, ah, ce să fac?

744
00:37:35,560 --> 00:37:37,080
Nu știu unde să mă duc.

745
00:37:37,080 --> 00:37:38,410
Cum pot rezolva această?

746
00:37:38,410 --> 00:37:41,150
>> Și așa voi va fel de
vezi facem chestia asta complicat

747
00:37:41,150 --> 00:37:44,810
unde putem fel de efectiv
crea lista legat în matrice noastre.

748
00:37:44,810 --> 00:37:46,840
Și astfel cel mai simplu mod
să se gândească la acest lucru,

749
00:37:46,840 --> 00:37:50,830
toate tabel hash este un
serie de liste legate.

750
00:37:50,830 --> 00:37:55,670
Și astfel, în acest sens, aveți
această matrice frumos de indicii,

751
00:37:55,670 --> 00:37:58,740
și apoi fiecare indicator în
această valoare, în acest index,

752
00:37:58,740 --> 00:38:00,740
poate indica de fapt, la alte lucruri.

753
00:38:00,740 --> 00:38:05,720
Și astfel încât să aveți toate aceste separat
lanțurile care vin de pe o mare matrice.

754
00:38:05,720 --> 00:38:07,960
>> Și astfel aici, dacă am
a vrut să introduceți Berry,

755
00:38:07,960 --> 00:38:11,220
Știu, bine, am de gând pentru a introduce
aceasta prin funcția mea hash.

756
00:38:11,220 --> 00:38:15,070
Am de gând să se încheie cu indicele de
1, și apoi am de gând să fie în măsură să aibă

757
00:38:15,070 --> 00:38:20,410
doar un subset mic de acest
gigant Dicționar 140.000 de cuvinte.

758
00:38:20,410 --> 00:38:24,220
Și apoi mă pot uita doar
prin 1/26 de asta.

759
00:38:24,220 --> 00:38:27,910
>> Și așa atunci eu pot insera doar
Berry fie înainte, fie după banana

760
00:38:27,910 --> 00:38:28,820
în acest caz?

761
00:38:28,820 --> 00:38:29,700
După, nu?

762
00:38:29,700 --> 00:38:33,920
Și așa ai de gând să doriți să
inserați acest nod după banane,

763
00:38:33,920 --> 00:38:36,667
și așa vei introduce
la coada acestei liste legate.

764
00:38:36,667 --> 00:38:38,500
Am de gând să mă întorc
la acest diapozitiv anterior,

765
00:38:38,500 --> 00:38:40,680
astfel încât voi puteți vedea cum
funcție hash funcționează.

766
00:38:40,680 --> 00:38:43,980
>> Deci funcție hash este această ecuație
că rulați un fel de intrare dvs.

767
00:38:43,980 --> 00:38:46,940
prin pentru a obține, indiferent de index
doriți să-l atribuiți spre.

768
00:38:46,940 --> 00:38:51,130
Și astfel, în acest exemplu, toate ne-am dorit
pentru a face a fost să ia prima literă,

769
00:38:51,130 --> 00:38:55,890
rândul său, că într-un index, apoi ne
poate stoca că în funcția noastră hash.

770
00:38:55,890 --> 00:39:00,160
Tot ce facem aici este că suntem
conversia prima literă.

771
00:39:00,160 --> 00:39:04,770
Deci keykey [0] este doar prima literă
indiferent de string avem,

772
00:39:04,770 --> 00:39:05,720
ne trece în.

773
00:39:05,720 --> 00:39:09,740
Suntem de conversie care la partea superioară, și
suntem scăderea de majuscule A,

774
00:39:09,740 --> 00:39:11,740
deci tot ce este de a face
dă-ne un număr

775
00:39:11,740 --> 00:39:13,670
în care putem hash valorile noastre pe.

776
00:39:13,670 --> 00:39:16,550
>> Și apoi vom
reveni hash SIZE modul.

777
00:39:16,550 --> 00:39:19,340
Fiți foarte, foarte atent
pentru că, teoretic, aici

778
00:39:19,340 --> 00:39:21,870
valoarea ta hash ar putea fi infinit.

779
00:39:21,870 --> 00:39:23,660
Ar putea merge doar pe și de pe și de pe.

780
00:39:23,660 --> 00:39:26,080
Ar putea fi ceva cu adevărat,
într-adevăr de mare valoare,

781
00:39:26,080 --> 00:39:29,849
ci pentru că tabelul hash care
ați creat are doar 26 de indici,

782
00:39:29,849 --> 00:39:31,890
doriți să vă asigurați că
modulusing astfel încât să

783
00:39:31,890 --> 00:39:33,848
Nu run-- este la fel
lucru ca queue-- dvs.

784
00:39:33,848 --> 00:39:36,320
astfel încât să nu a alerga pe
partea de jos a funcției hash.

785
00:39:36,320 --> 00:39:39,210
>> Vrei să-l încheie în jurul valorii de spate
în același mod în [Inaudibil] atunci când

786
00:39:39,210 --> 00:39:41,750
ai avut ca un foarte,
scrisoare foarte mare, vă

787
00:39:41,750 --> 00:39:43,740
nu a vrut asta
doar rulați de pe la sfârșitul.

788
00:39:43,740 --> 00:39:46,948
Acelasi lucru aici, pe care doriți să vă asigurați
aceasta nu se execută de pe la sfârșitul de ambalaj

789
00:39:46,948 --> 00:39:48,330
în jurul la partea de sus a tabelului.

790
00:39:48,330 --> 00:39:50,530
Deci, aceasta este doar o foarte
funcție hash simplă.

791
00:39:50,530 --> 00:39:56,570
Tot ce a făcut a fost să ia primul
scrisoare de orice intrare noastre a fost

792
00:39:56,570 --> 00:40:01,660
și să se întoarcă că într-un index care
am putea pune în masa noastră hash.

793
00:40:01,660 --> 00:40:05,450
>> Da, și așa cum am spus mai înainte,
modul în care ne rezolva coliziuni

794
00:40:05,450 --> 00:40:09,330
în hash nostru tabele sunt cu,
ceea ce noi numim, înlănțuirea.

795
00:40:09,330 --> 00:40:13,860
Deci, dacă încercați să introduceți mai multe
cuvinte care incep cu același lucru,

796
00:40:13,860 --> 00:40:16,145
ai de gând să aibă o valoare hash.

797
00:40:16,145 --> 00:40:18,770
Avocado și mere, dacă ați
rulați-l prin funcția noastră hash,

798
00:40:18,770 --> 00:40:21,450
sunt de gând să vă dau
același număr, numărul de 0.

799
00:40:21,450 --> 00:40:24,550
Și astfel modul în care rezolva, care este
că putem de fapt un fel de le lege

800
00:40:24,550 --> 00:40:27,010
împreună prin liste legate.

801
00:40:27,010 --> 00:40:29,600
>> Și astfel, în acest sens,
voi poate vedea un fel

802
00:40:29,600 --> 00:40:32,640
de modul in care structurile de date care
am fost de stabilire anterior

803
00:40:32,640 --> 00:40:35,870
ca o stafidă legat listă fel
de pot veni împreună într-o singură.

804
00:40:35,870 --> 00:40:38,860
Și apoi puteți crea departe
structuri de date mai eficiente

805
00:40:38,860 --> 00:40:43,350
care se pot ocupa sume mai mari de
date, care redimensiona dinamic în funcție

806
00:40:43,350 --> 00:40:44,870
de nevoile dumneavoastra.

807
00:40:44,870 --> 00:40:45,620
Toată lumea clar?

808
00:40:45,620 --> 00:40:47,580
Toată lumea fel de clare
pe ceea ce se întâmplă aici?

809
00:40:47,580 --> 00:40:52,110
>> Dacă aș fi vrut să insert-- ceea ce este un
fructe, care începe cu, nu știu,

810
00:40:52,110 --> 00:40:54,726
B, altele decât Berry, banana.

811
00:40:54,726 --> 00:40:55,710
>> Audiența: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI Peng: Blackberry, mure.

813
00:40:57,910 --> 00:41:00,530
În cazul în care nu merge blackberry aici?

814
00:41:00,530 --> 00:41:04,251
Ei bine, am de fapt, nu am sortat
acest lucru încă, dar teoretic

815
00:41:04,251 --> 00:41:06,250
dacă ne-am dorit să avem această
în ordine alfabetică,

816
00:41:06,250 --> 00:41:07,944
în cazul în care ar trebui să meargă BLACKBERRY?

817
00:41:07,944 --> 00:41:09,210
>> Audiența: [inaudibil]

818
00:41:09,210 --> 00:41:11,100
>> ANDI Peng: Exact, după aici, nu?

819
00:41:11,100 --> 00:41:14,950
Dar din moment ce este foarte dificil de a
reorder-- Cred că depinde de voi.

820
00:41:14,950 --> 00:41:17,920
Voi poate total
punerea în aplicare a ceea ce vrei.

821
00:41:17,920 --> 00:41:20,730
Mai mult eficient mod
a face acest lucru, probabil,

822
00:41:20,730 --> 00:41:24,570
ar fi pentru a sorta legate dumneavoastră
lista în ordine alfabetică,

823
00:41:24,570 --> 00:41:26,520
și așa mai departe atunci când sunteți
inserarea lucruri, pe care doriți

824
00:41:26,520 --> 00:41:28,632
pentru a fi sigur de a le insera
în ordine alfabetică

825
00:41:28,632 --> 00:41:30,590
astfel încât atunci când ești
încercarea de a le căuta,

826
00:41:30,590 --> 00:41:32,410
nu trebuie să traverseze tot.

827
00:41:32,410 --> 00:41:35,290
Știi exact unde
este, și este mai ușor.

828
00:41:35,290 --> 00:41:39,100
>> Dar, dacă aveți un fel de
lucruri intercalate aleator,

829
00:41:39,100 --> 00:41:41,420
sunteți încă de gând să aibă
să-l traverseze oricum.

830
00:41:41,420 --> 00:41:44,990
Și așa, dacă am vrut să doar
introduceți blackberry aici

831
00:41:44,990 --> 00:41:47,470
și am vrut pentru a căuta
ea, știu, oh, mure

832
00:41:47,470 --> 00:41:52,012
trebuie să înceapă cu indicele de 1, asa ca am
știu instantaneu doar de căutare la 1.

833
00:41:52,012 --> 00:41:53,970
Și apoi pot fel de
traversa lista legată

834
00:41:53,970 --> 00:41:56,120
până ajung la Blackberry,
și then-- da?

835
00:41:56,120 --> 00:41:59,550
>> Audiența: Dacă sunteți încercarea de a create--
Cred că acest lucru este o ca hash foarte simplu

836
00:41:59,550 --> 00:42:00,050
funcţie.

837
00:42:00,050 --> 00:42:02,835
Și dacă ne-am vrut să fac
mai multe straturi de care cum ar fi,

838
00:42:02,835 --> 00:42:05,870
OK, vrem să se separe în
la fel ca toate literele alfabetice

839
00:42:05,870 --> 00:42:09,040
și apoi din nou să-i placă un alt set
de scrisori alfabetic în care,

840
00:42:09,040 --> 00:42:11,715
ne pune ca un hash
tabel într-un tabel hash,

841
00:42:11,715 --> 00:42:13,256
sau ca o funcție într-o funcție?

842
00:42:13,256 --> 00:42:14,880
Sau este that--

843
00:42:14,880 --> 00:42:17,510
>> ANDI Peng: Deci hash-ul
function-- masa ta hash

844
00:42:17,510 --> 00:42:19,360
poate fi la fel de mare ca și doriți să-l.

845
00:42:19,360 --> 00:42:21,930
Deci, în acest sens, m-am gândit
a fost foarte usor, foarte

846
00:42:21,930 --> 00:42:25,320
simplu pentru mine pentru a bazat doar un fel
pe scrisori de primul cuvânt.

847
00:42:25,320 --> 00:42:28,690
Și deci nu e doar 26 de opțiuni.

848
00:42:28,690 --> 00:42:32,650
Nu pot sa ma doar 26 de opțiuni din
0 până la 25, deoarece acestea pot doar

849
00:42:32,650 --> 00:42:36,510
începe de la A la Z. Dar dacă ai vrut
pentru a adăuga, probabil, o mai mare complexitate

850
00:42:36,510 --> 00:42:39,260
sau mai rapid a alerga timp pentru dvs.
tabel hash, absolut

851
00:42:39,260 --> 00:42:40,760
pot face tot felul de lucruri.

852
00:42:40,760 --> 00:42:43,330
Puteți face propriul
ecuație care vă oferă

853
00:42:43,330 --> 00:42:48,000
mai mult de distribuție în ta
cuvinte, atunci când căutați,

854
00:42:48,000 --> 00:42:49,300
o să fie mai rapid.

855
00:42:49,300 --> 00:42:52,100
>> Este complet până la voi
modul în care doriți să pună în aplicare acest lucru.

856
00:42:52,100 --> 00:42:55,140
Ganditi-va ca doar galeti.

857
00:42:55,140 --> 00:42:57,376
Dacă am vrut să am
26 găleți, am de gând

858
00:42:57,376 --> 00:42:59,420
pentru a sorta lucrurile în aceste galeti.

859
00:42:59,420 --> 00:43:02,980
Dar am de gând să aibă o grămadă
de lucruri în fiecare compartiment,

860
00:43:02,980 --> 00:43:05,890
deci, dacă doriți să-l facă
mai rapid și mai eficient,

861
00:43:05,890 --> 00:43:07,190
lasă-mă să o sută de găleți.

862
00:43:07,190 --> 00:43:09,290
>> Dar atunci va trebui să găsească o
modalitate de a sorta lucrurile, astfel încât acestea sunt

863
00:43:09,290 --> 00:43:11,040
în găleată corespunzătoare ar trebui să fie în.

864
00:43:11,040 --> 00:43:13,331
Dar atunci când de fapt
vrei să te uiți la asta găleată,

865
00:43:13,331 --> 00:43:16,410
e mult mai repede, deoarece nu există
lucruri mai puțin în fiecare compartiment.

866
00:43:16,410 --> 00:43:20,250
Și astfel, da, asta e de fapt
truc pentru voi în pset5

867
00:43:20,250 --> 00:43:22,360
este că vei
contestat de a crea doar

868
00:43:22,360 --> 00:43:26,170
ceea ce este cel mai eficient
Funcția vă puteți gândi de a fi

869
00:43:26,170 --> 00:43:28,520
capabil să stocheze și să verifice aceste valori.

870
00:43:28,520 --> 00:43:30,840
>> În totalitate până la voi
Cu toate acestea vrei sa o faci,

871
00:43:30,840 --> 00:43:32,229
dar asta e un punct foarte bun.

872
00:43:32,229 --> 00:43:34,520
Că tipul de logica tine
doresc să înceapă să se gândească despre

873
00:43:34,520 --> 00:43:37,236
este, ei bine, de ce nu am face mai multe galeti.

874
00:43:37,236 --> 00:43:39,527
Și atunci am să caute
mai puțin lucruri, și atunci poate am

875
00:43:39,527 --> 00:43:41,640
au o funcție hash diferit.

876
00:43:41,640 --> 00:43:45,500
>> Da, există o mulțime de moduri de a face acest lucru
PSET, unele sunt mai repede decât altele.

877
00:43:45,500 --> 00:43:50,630
Sunt total de gând pentru a vedea cât de
rapid a fost cel mai rapid voi va

878
00:43:50,630 --> 00:43:55,170
să poată obține funcțiile la locul de muncă.

879
00:43:55,170 --> 00:43:58,176
OK, toată lumea de pe bun
tabele înlănțuirea și hash?

880
00:43:58,176 --> 00:44:00,800
Este de fapt foarte simplu ca un
Conceptul dacă te gândești la asta.

881
00:44:00,800 --> 00:44:05,160
Tot ce este este separarea indiferent
intrări tale sunt în găleți,

882
00:44:05,160 --> 00:44:10,670
sortarea lor, iar apoi căutarea
listele care nu este asociat cu.

883
00:44:10,670 --> 00:44:11,852
>> Misto.

884
00:44:11,852 --> 00:44:18,160
Bine, acum avem un alt fel
de structură de date care se numește un copac.

885
00:44:18,160 --> 00:44:20,850
Să mergem mai departe și vorbim despre încercări
care sunt distinct diferite,

886
00:44:20,850 --> 00:44:22,330
dar în aceeași categorie.

887
00:44:22,330 --> 00:44:29,010
În esență, toate un copac este în schimb
de organizare a datelor în mod liniar

888
00:44:29,010 --> 00:44:32,560
că un tabel hash te does--
Știi, e luat un top și un fund

889
00:44:32,560 --> 00:44:37,900
și apoi un fel de legături de pe o it--
copac are un top care te sun rădăcină,

890
00:44:37,900 --> 00:44:40,220
și apoi are frunze tot în jurul ei.

891
00:44:40,220 --> 00:44:42,390
>> Și astfel tot ce trebuie aici
este doar nodul de sus

892
00:44:42,390 --> 00:44:45,980
care indică spre alte noduri, că punctele
la mai multe noduri, și așa mai departe și așa mai departe.

893
00:44:45,980 --> 00:44:48,130
Și așa trebuie doar ramuri de divizare.

894
00:44:48,130 --> 00:44:53,255
Este doar un mod diferit de organizare
date, și pentru că am un copac apel,

895
00:44:53,255 --> 00:44:56,270
voi doar-- e doar
modelat la arate ca un copac.

896
00:44:56,270 --> 00:44:57,670
De aceea o numim copaci.

897
00:44:57,670 --> 00:44:59,370
>> Tabelul Hash arata ca un tabel.

898
00:44:59,370 --> 00:45:01,310
Un copac doar arata ca un copac.

899
00:45:01,310 --> 00:45:03,300
Tot ce este este un separată
mod de organizare noduri

900
00:45:03,300 --> 00:45:06,020
în funcție de ceea ce sunt nevoile dumneavoastra.

901
00:45:06,020 --> 00:45:11,810
>> Astfel încât să aibă o rădăcină și
atunci aveți frunze.

902
00:45:11,810 --> 00:45:15,380
Modul în care putem special
cred despre acesta este un arbore binar,

903
00:45:15,380 --> 00:45:18,150
un arbore binar este doar o
tip specific de un copac

904
00:45:18,150 --> 00:45:22,450
în cazul în care fiecare nod doar puncte
la, la max, alte două noduri.

905
00:45:22,450 --> 00:45:25,434
Și astfel aici aveți distinct
simetrie în arborele

906
00:45:25,434 --> 00:45:28,600
care face mai ușor să se uite un fel de
la ce valori ești pentru că atunci

907
00:45:28,600 --> 00:45:30,150
au întotdeauna un stânga sau la dreapta.

908
00:45:30,150 --> 00:45:33,150
Nu e niciodată ca o treime din stânga
stânga sau sfert din stânga.

909
00:45:33,150 --> 00:45:36,358
E doar ai un stânga și un drept
și puteți căuta oricare dintre cei doi.

910
00:45:36,358 --> 00:45:38,980
Și așa de ce este acest util?

911
00:45:38,980 --> 00:45:40,980
Modul în care acest lucru este
util este dacă sunteți în căutarea

912
00:45:40,980 --> 00:45:42,890
pentru a căuta prin valori, nu?

913
00:45:42,890 --> 00:45:45,640
Mai degrabă decât de punere în aplicare binare
căutare într-o matrice de eroare,

914
00:45:45,640 --> 00:45:49,260
dacă ai vrut să fie în măsură de a introduce noduri
și ia noduri după bunul plac și, de asemenea

915
00:45:49,260 --> 00:45:52,185
păstra căutarea
capacități de căutare binară.

916
00:45:52,185 --> 00:45:54,560
Deci, în acest fel, suntem un fel de
tricking-- amintesc când am

917
00:45:54,560 --> 00:45:56,530
a declarat liste legate nu poate căuta binare?

918
00:45:56,530 --> 00:46:01,700
Suntem un fel de a crea o structură de date
că trucuri care în lucru.

919
00:46:01,700 --> 00:46:05,034
>> Și liste așa că legate sunt liniare,
ele se leagă numai una după alta.

920
00:46:05,034 --> 00:46:06,950
Putem avea un fel de
diferită de indicii fel

921
00:46:06,950 --> 00:46:09,408
acel punct la diferite noduri
care ne poate ajuta cu căutare.

922
00:46:09,408 --> 00:46:12,590
Și astfel aici, dacă am vrut să
au un arbore binar de căutare,

923
00:46:12,590 --> 00:46:14,090
Știu că de mijloc mea, dacă 55.

924
00:46:14,090 --> 00:46:18,280
Mă duc pentru a crea acea
ca mijloc mea, ca root meu,

925
00:46:18,280 --> 00:46:20,770
și apoi am de gând să aibă
Valorile spin off de ea.

926
00:46:20,770 --> 00:46:25,610
>> Deci, aici, dacă am de gând pentru a căuta
valoarea de 66, eu pot începe la 55.

927
00:46:25,610 --> 00:46:27,310
E 66 mai mare decât 55?

928
00:46:27,310 --> 00:46:30,970
Da, este, așa că știu că mus căutare
I n indicatorul din dreapta a acestui copac.

929
00:46:30,970 --> 00:46:32,440
Mă duc la 77.

930
00:46:32,440 --> 00:46:35,367
OK, este mai mică de 66 sau mai mare de 77?

931
00:46:35,367 --> 00:46:37,950
E mai puțin de, ca să știi, oh,
care trebuie să fie nodul din stânga.

932
00:46:37,950 --> 00:46:41,410
>> Și astfel aici suntem un fel de conservare
toate lucrurile mari despre tablouri,

933
00:46:41,410 --> 00:46:44,420
așa cum ar fi redimensionarea dinamică
de obiecte, fiind

934
00:46:44,420 --> 00:46:49,530
posibilitatea de a insera și șterge în voie,
fără a fi nevoie să vă faceți griji cu privire la tip fix

935
00:46:49,530 --> 00:46:50,370
cantitate de spațiu.

936
00:46:50,370 --> 00:46:52,820
Noi încă păstra toate
aceste lucruri minunate

937
00:46:52,820 --> 00:46:57,140
în același timp, de asemenea, posibilitatea de a păstra
jurnal și ora de căutare binare de căutare

938
00:46:57,140 --> 00:47:00,450
că am fost doar anterior
posibilitatea de a obține o frază.

939
00:47:00,450 --> 00:47:06,310
>> Structură de date rece, un fel de
de implementat, nodul.

940
00:47:06,310 --> 00:47:08,311
După cum puteți vedea, tot ce
este struct nodului

941
00:47:08,311 --> 00:47:10,143
este că aveți o stânga
și un pointer drept.

942
00:47:10,143 --> 00:47:11,044
Asta e tot ce este.

943
00:47:11,044 --> 00:47:12,960
Deci, mai degrabă decât doar
având o x sau un precedent.

944
00:47:12,960 --> 00:47:15,920
Aveți un stânga sau dreapta, apoi
puteți fel de link-ul împreună

945
00:47:15,920 --> 00:47:16,836
Aveți însă asa ca alege.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, vom merge de fapt
să ia doar câteva minute.

948
00:47:24,270 --> 00:47:25,790
Deci vom întoarce aici.

949
00:47:25,790 --> 00:47:28,270
Așa cum am spus mai înainte,
Am facut un fel de explicat

950
00:47:28,270 --> 00:47:31,520
logica din spatele modul în care
ar căuta prin asta.

951
00:47:31,520 --> 00:47:33,860
Vom încerca
pseudocoding acest lucru pentru a vedea

952
00:47:33,860 --> 00:47:38,000
dacă putem fel de aplicați
aceeași logică de căutare binară

953
00:47:38,000 --> 00:47:40,055
la un alt tip de structură de date.

954
00:47:40,055 --> 00:47:45,049
Dacă vreți să luați ca un cuplu
minute să se gândească doar despre asta.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
BINE.

957
00:48:46,925 --> 00:48:51,407
Bine, am de gând să
de fapt, da doar the-- nu,

958
00:48:51,407 --> 00:48:52,990
vom vorbi despre Pseudocodul primul.

959
00:48:52,990 --> 00:48:56,580
Deci, nimeni nu vrea
pentru a da o lovitură de cuțit la ceea ce

960
00:48:56,580 --> 00:49:02,100
primul lucru pe care doriți să facă atunci când
te început căutarea este?

961
00:49:02,100 --> 00:49:04,460
Dacă căutăm
valoarea 66, ceea ce este

962
00:49:04,460 --> 00:49:07,940
primul lucru pe care vrem sa facem dacă
vrem în binar a căuta acest copac?

963
00:49:07,940 --> 00:49:10,760
>> Audiența: vrei să te uiți drept
si uita-te la stânga și se vedea [neauzit]

964
00:49:10,760 --> 00:49:11,230
mai mare număr.

965
00:49:11,230 --> 00:49:12,271
>> ANDI Peng: Da, exact.

966
00:49:12,271 --> 00:49:15,350
Deci ai de gând să se uite la rădăcină ta.

967
00:49:15,350 --> 00:49:18,180
Există o mulțime de modalități în care puteți apela
aceasta, poporul tău nod părinte spune.

968
00:49:18,180 --> 00:49:21,317
Îmi place să spun că rădăcină
asta e ca rădăcina copacului.

969
00:49:21,317 --> 00:49:23,400
Vei să se uite la
nodul rădăcină, și tu ești

970
00:49:23,400 --> 00:49:26,940
va pentru a vedea este de 66 mai mare
sau în minus față 55.

971
00:49:26,940 --> 00:49:30,360
Și dacă e mai mare decât, bine, aceasta este
mai mare decât, în cazul în care vrem să se uite?

972
00:49:30,360 --> 00:49:32,000
În cazul în care vrem să căutați acum, nu?

973
00:49:32,000 --> 00:49:34,340
Vrem pentru a căuta în
jumătate din dreapta a acestui copac.

974
00:49:34,340 --> 00:49:38,390
>> Deci avem, convenabil, o
pointer care indică spre dreapta.

975
00:49:38,390 --> 00:49:44,325
Și astfel, atunci putem stabili
noul nostru rădăcină să fie 77.

976
00:49:44,325 --> 00:49:46,450
Putem merge doar la oriunde
indicatorul este îndreptat.

977
00:49:46,450 --> 00:49:49,100
Ei bine, oh, aici suntem de pornire
la 77, si putem doar

978
00:49:49,100 --> 00:49:51,172
face acest lucru recursiv nou și din nou.

979
00:49:51,172 --> 00:49:52,880
În acest fel, vă fel
de au o funcție.

980
00:49:52,880 --> 00:49:57,430
Ai un mod de a căuta pe care le
poate repeta doar peste si peste si peste,

981
00:49:57,430 --> 00:50:02,720
în funcție de cazul în care doriți să căutați
până când veți obține în cele din urmă la valoarea

982
00:50:02,720 --> 00:50:04,730
pe care le căutați pentru.

983
00:50:04,730 --> 00:50:05,230
Are sens?

984
00:50:05,230 --> 00:50:07,800
>> Sunt pe cale să-ți arăt real
cod, și este o mulțime de cod.

985
00:50:07,800 --> 00:50:08,674
Nu este nevoie să sperii.

986
00:50:08,674 --> 00:50:09,910
Vom vorbi prin ea.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> De fapt nu.

989
00:50:14,020 --> 00:50:15,061
Asta a fost doar pseudocod.

990
00:50:15,061 --> 00:50:17,860
OK, că a fost doar Pseudocodul,
care este un complex pic,

991
00:50:17,860 --> 00:50:19,751
dar este absolut în regulă.

992
00:50:19,751 --> 00:50:21,000
Toată lumea în urma de-a lungul aici?

993
00:50:21,000 --> 00:50:24,260
Dacă rădăcina este nul, întoarcerea
fals, pentru că mijloacele

994
00:50:24,260 --> 00:50:26,850
tu nici măcar nu au nimic acolo.

995
00:50:26,850 --> 00:50:31,376
>> Dacă rădăcină n este valoarea, deci, dacă aceasta
se întâmplă să fie cel ce te uiți,

996
00:50:31,376 --> 00:50:34,000
atunci ai de gând să se întoarcă adevărat
pentru că știi că găsit-o.

997
00:50:34,000 --> 00:50:36,250
Dar dacă valoarea este mai mică
decât rădăcină de n, ești

998
00:50:36,250 --> 00:50:38,332
merge pentru a căuta stânga
copil sau frunza din stânga,

999
00:50:38,332 --> 00:50:39,540
ce vrei să-i spunem.

1000
00:50:39,540 --> 00:50:41,750
Iar dacă valoarea este mai mare decât rădăcină,
ai de gând să căutați copac corect,

1001
00:50:41,750 --> 00:50:44,610
apoi executați doar funcția
prin căutare din nou.

1002
00:50:44,610 --> 00:50:48,037
>> Și dacă rădăcina este nul, că această
înseamnă că ai ajuns la sfârșitul?

1003
00:50:48,037 --> 00:50:50,120
Asta înseamnă că nu aveți nici o
mai multe frunze pentru a căuta,

1004
00:50:50,120 --> 00:50:52,230
atunci știi, oh, am
Cred că nu e aici

1005
00:50:52,230 --> 00:50:55,063
pentru că după ce am uitat prin
totul și nu este aici,

1006
00:50:55,063 --> 00:50:56,930
pur și simplu nu ar putea fi aici.

1007
00:50:56,930 --> 00:50:58,350
>> Asta face sens pentru toată lumea?

1008
00:50:58,350 --> 00:51:03,230
Deci e ca si cum de căutare binară conservarea
capacitățile de liste legate.

1009
00:51:03,230 --> 00:51:09,200
Se răcește, și așa mai departe al doilea tip
de voi structura de date baieti

1010
00:51:09,200 --> 00:51:13,180
Puteți încerca de punere în aplicare pe PSET dumneavoastră,
trebuie doar să aleagă o metodă.

1011
00:51:13,180 --> 00:51:19,430
Dar poate o metodă alternativă de a
tabelul hash este ceea ce noi numim un trie.

1012
00:51:19,430 --> 00:51:24,080
>> Toate un trie este un
anumit tip de copac care

1013
00:51:24,080 --> 00:51:28,600
are valori care merg la alte valori.

1014
00:51:28,600 --> 00:51:31,450
Deci, în loc de a avea un binar
copac în sensul că un singur

1015
00:51:31,450 --> 00:51:35,940
lucru poate indica două, puteți avea
punct un singur lucru la multe, multe lucruri.

1016
00:51:35,940 --> 00:51:39,450
Aveți în esență, tablouri
interiorul care să stocați

1017
00:51:39,450 --> 00:51:41,790
indicii care indică alte matrice.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Deci nodul de modul în care
ar defini un trie

1020
00:51:49,460 --> 00:51:52,590
este vrem să avem o
Boolean, C cuvânt, nu?

1021
00:51:52,590 --> 00:51:54,920
Deci nodul este Boolean
cum ar fi adevărat sau fals,

1022
00:51:54,920 --> 00:51:58,490
în primul rând în fruntea
că matrice, este aceasta un cuvânt?

1023
00:51:58,490 --> 00:52:03,620
În al doilea rând, doriți să aveți indicii
la orice restul dintre ele sunt.

1024
00:52:03,620 --> 00:52:07,470
Un complex pic, un pic abstract, dar
Voi explica ce că toate mijloacele.

1025
00:52:07,470 --> 00:52:13,800
>> Deci, aici, în partea de sus, dacă
au o serie declarat deja,

1026
00:52:13,800 --> 00:52:17,040
un nod în cazul în care aveți un Boolean
valoarea stocată în față

1027
00:52:17,040 --> 00:52:19,490
care vă spune este acest cuvânt?

1028
00:52:19,490 --> 00:52:20,520
Nu este acesta un cuvânt?

1029
00:52:20,520 --> 00:52:23,240
Și atunci aveți
restul de matrice dvs., care

1030
00:52:23,240 --> 00:52:26,040
de fapt, stochează toate
posibilități de ceea ce ar putea fi.

1031
00:52:26,040 --> 00:52:28,660
Astfel, de exemplu, cum ar fi
în partea de sus ai

1032
00:52:28,660 --> 00:52:32,140
primul lucru pe care spune adevărate sau
false, da sau nu, acesta este un cuvânt.

1033
00:52:32,140 --> 00:52:38,130
>> Și apoi trebuie de la 0 la 26 de
literele pe care le puteți stoca.

1034
00:52:38,130 --> 00:52:42,790
Dacă aș fi vrut să caute aici
pentru BAT, mă duc la partea de sus

1035
00:52:42,790 --> 00:52:49,200
și mă uit pentru B. găsesc B în mea
matrice, și așa știu, OK, este un cuvânt B?

1036
00:52:49,200 --> 00:52:53,010
B nu este un cuvânt, așa că astfel
Trebuie să continuați căutarea.

1037
00:52:53,010 --> 00:52:56,410
Mă duc la B, și mă uit la
indicatorul care arată spre B

1038
00:52:56,410 --> 00:53:00,900
și văd un alt gamă largă de informații,
aceeași structură pe care am avut-o înainte.

1039
00:53:00,900 --> 00:53:05,240
>> Și here-- oh, următoarea
scrisoare în [neauzit] este A.

1040
00:53:05,240 --> 00:53:07,210
Deci, ne uităm în matrice.

1041
00:53:07,210 --> 00:53:10,860
Găsim a opta valoarea,
și apoi ne să vedem, oh,

1042
00:53:10,860 --> 00:53:12,840
Hei, este că un cuvânt, este B-A-un cuvânt?

1043
00:53:12,840 --> 00:53:13,807
Acesta nu este un cuvânt.

1044
00:53:13,807 --> 00:53:14,890
Trebuie să continui să cauți.

1045
00:53:14,890 --> 00:53:17,850
>> Și așa, atunci ne uităm la cazul în care
indicatorul de A puncte,

1046
00:53:17,850 --> 00:53:21,130
și puncte de la un alt mod în
pe care o avem mai multă valoare stocată.

1047
00:53:21,130 --> 00:53:24,150
Și, eventual,, ajungem la
B-A-T, care este un cuvânt.

1048
00:53:24,150 --> 00:53:25,970
Și astfel încât data viitoare
te uiți, te duci

1049
00:53:25,970 --> 00:53:30,850
să aibă ca verificare, da,
Această funcție booleană este adevărat.

1050
00:53:30,850 --> 00:53:35,450
Și astfel, în sensul că suntem un fel
de a avea un copac cu matrice.

1051
00:53:35,450 --> 00:53:39,890
>> Deci atunci puteți tip de căutare în jos.

1052
00:53:39,890 --> 00:53:43,650
Mai degrabă decât o funcție și hashing
atribuirea de valori de listă legate,

1053
00:53:43,650 --> 00:53:49,190
puteți pune în aplicare doar o
trie care caută downwords.

1054
00:53:49,190 --> 00:53:50,850
Într-adevăr, într-adevăr lucruri complicate.

1055
00:53:50,850 --> 00:53:54,060
Nu este ușor să se gândească la, deoarece eu sunt ca
scuipa atât de multe structuri de date din

1056
00:53:54,060 --> 00:53:58,710
la tine, dar nu toată lumea un fel de
să înțeleagă cum funcționează logica asta?

1057
00:53:58,710 --> 00:54:01,920
>> Bine, in regula.

1058
00:54:01,920 --> 00:54:05,600
Așa B-A-T, și apoi
ai de gând pentru a căuta.

1059
00:54:05,600 --> 00:54:07,940
Data viitoare când te duci
pentru a vedea, oh, hei, e adevărat,

1060
00:54:07,940 --> 00:54:09,273
astfel Știu că trebuie să fie un cuvânt.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Același lucru pentru Zoo.

1063
00:54:13,770 --> 00:54:17,960
Deci, aici e un lucru chiar acum, dacă am
a vrut pentru a căuta zoo, chiar acum,

1064
00:54:17,960 --> 00:54:20,780
în prezent, este o grădină zoologică nu
cuvânt în dicționarul nostru

1065
00:54:20,780 --> 00:54:25,300
pentru că, așa cum voi puteți vedea,
primul loc ca avem o Boolean

1066
00:54:25,300 --> 00:54:28,590
return true este la sfârșitul zoom.

1067
00:54:28,590 --> 00:54:30,430
Avem Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> Și astfel aici, nu avem de fapt
cuvântul, gradina zoologica, în dicționarul nostru

1069
00:54:33,900 --> 00:54:36,070
pentru că această casetă de selectare nu este bifată.

1070
00:54:36,070 --> 00:54:39,540
Deci calculatorul nu
stiu ca zoo este un cuvânt

1071
00:54:39,540 --> 00:54:42,430
pentru că modul în care ne-am
stocate ea, doar un zoom aici

1072
00:54:42,430 --> 00:54:44,920
de fapt, are o valoare Boolean
care a fost transformat adevărat.

1073
00:54:44,920 --> 00:54:49,380
Deci, dacă vrem să introduceți CD-ul
cuvânt, grădină zoologică, în dicționarul nostru,

1074
00:54:49,380 --> 00:54:51,770
cum ne-am merge despre a face asta?

1075
00:54:51,770 --> 00:54:55,960
Ce trebuie să facem pentru a vă asigura nostru
calculator știe că Z-O-O este un cuvânt

1076
00:54:55,960 --> 00:54:58,130
și nu primul cuvânt este Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> Audiența: [inaudibil]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI Peng: Exact, am
doriți să vă asigurați că această

1079
00:55:01,450 --> 00:55:07,890
aici, că valoarea Boolean este
verificat la e adevărat.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, atunci vom verifica dacă,
așa că știm exact, hei, gradina zoologica este un cuvânt.

1081
00:55:13,297 --> 00:55:15,380
Am de gând să-i spuneți
computer care este un cuvânt atât de

1082
00:55:15,380 --> 00:55:18,000
că, atunci când controalele de calculator,
se știe că grădină zoologică este un cuvânt.

1083
00:55:18,000 --> 00:55:21,269
>> Deoarece ne amintim toate aceste date
structuri, este foarte ușor pentru noi

1084
00:55:21,269 --> 00:55:22,310
să spun, oh, liliac e un cuvânt.

1085
00:55:22,310 --> 00:55:22,851
Zoo este un cuvânt.

1086
00:55:22,851 --> 00:55:23,611
Zoom e un cuvânt.

1087
00:55:23,611 --> 00:55:25,860
Dar atunci cand esti o clădire,
computerul are nici o idee.

1088
00:55:25,860 --> 00:55:28,619
>> Deci, va trebui să-l spun exact
la ce punct este aceasta un cuvânt?

1089
00:55:28,619 --> 00:55:29,910
La ce punct nu este un cuvânt?

1090
00:55:29,910 --> 00:55:31,784
Și la ce punct îmi
trebuie să caute lucruri,

1091
00:55:31,784 --> 00:55:34,000
și la ce punct am nevoie pentru a merge mai departe?

1092
00:55:34,000 --> 00:55:37,010
Toată lumea clar de asta?

1093
00:55:37,010 --> 00:55:39,540
Misto.

1094
00:55:39,540 --> 00:55:42,530
>> Și astfel apoi vine
problemă de cum ne-ar

1095
00:55:42,530 --> 00:55:45,560
du-te despre inserarea ceva
asta nu e de fapt acolo?

1096
00:55:45,560 --> 00:55:49,090
Deci, hai să spunem că doriți să introduceți
cuvântul, baie, în trie nostru.

1097
00:55:49,090 --> 00:55:53,589
După cum voi putea vedea ca in prezent
tot ce avem acum este B-A-T,

1098
00:55:53,589 --> 00:55:55,630
și această nouă structură de date
acolo a avut o halbă care

1099
00:55:55,630 --> 00:55:59,740
a subliniat null pentru că presupunem
că, oh, nu e fără cuvinte după B-A-T,

1100
00:55:59,740 --> 00:56:02,530
de ce avem nevoie pentru a păstra
având lucruri după care T.

1101
00:56:02,530 --> 00:56:06,581
>> Dar problema apare dacă facem te
doresc să aibă un cuvânt care vine după

1102
00:56:06,581 --> 00:56:07,080
lui T.

1103
00:56:07,080 --> 00:56:09,500
Dacă aveți de baie, ești
de gând să doriți un drept H.

1104
00:56:09,500 --> 00:56:13,290
Și astfel modul în care vom face acest lucru este
vom crea un nod pentru a separat.

1105
00:56:13,290 --> 00:56:16,840
Nu ne aloca orice sumă
de memorie pentru această nouă serie,

1106
00:56:16,840 --> 00:56:20,720
si vom realoca indicii.

1107
00:56:20,720 --> 00:56:22,947
>> Vom fi atribuit
H, întâi de toate, acest null,

1108
00:56:22,947 --> 00:56:24,030
vom scăpa de.

1109
00:56:24,030 --> 00:56:26,590
Vom avea
cele descendentă litera h.

1110
00:56:26,590 --> 00:56:30,600
Dacă vom vedea o H, l-am dori
pentru a merge în altă parte.

1111
00:56:30,600 --> 00:56:33,910
>> În aici, putem verifica apoi pe Da.

1112
00:56:33,910 --> 00:56:38,170
Dacă ne-am lovit un H după T, oh,
atunci știm că acest lucru este un cuvânt.

1113
00:56:38,170 --> 00:56:41,110
Boolean va reveni adevărat.

1114
00:56:41,110 --> 00:56:42,950
Toată lumea clar cu privire la modul sa întâmplat?

1115
00:56:42,950 --> 00:56:45,110
BINE.

1116
00:56:45,110 --> 00:56:47,214
>> Deci, în esență, toate
aceste structuri de date

1117
00:56:47,214 --> 00:56:50,130
că am trecut peste ziua de azi, am
trecut peste ele foarte, foarte repede

1118
00:56:50,130 --> 00:56:52,192
și nu în prea mult
detaliu, și asta e în regulă.

1119
00:56:52,192 --> 00:56:53,900
Odată ce ați începe încurcați
cu el, vei

1120
00:56:53,900 --> 00:56:55,733
urmărirea în cazul în care
toate indicii sunt,

1121
00:56:55,733 --> 00:56:58,060
ce se întâmplă în dumneavoastră
structuri de date, etc..

1122
00:56:58,060 --> 00:56:59,810
Vor fi foarte util,
și este de până la tine

1123
00:56:59,810 --> 00:57:03,890
voi să dau totul cum
pe care doriți să pună în aplicare lucrurile.

1124
00:57:03,890 --> 00:57:07,650
>> Și astfel pset4, de 5-- oh, că este greșit.

1125
00:57:07,650 --> 00:57:10,140
Pset5 este greșeli de ortografie.

1126
00:57:10,140 --> 00:57:13,710
Așa cum am spus mai înainte, ai de gând să, o dată
din nou, descărca codul sursă de la noi.

1127
00:57:13,710 --> 00:57:16,210
Nu va fi de trei principale
lucruri veți fi descărcarea.

1128
00:57:16,210 --> 00:57:18,470
Veți descărca dictionare,
KERS, și texte.

1129
00:57:18,470 --> 00:57:21,660
>> Toate aceste lucruri sunt sunt
fie dicționare de cuvinte

1130
00:57:21,660 --> 00:57:25,190
pe care ne-o dorim să verificați
sau test de informații

1131
00:57:25,190 --> 00:57:26,930
pe care ne-o dorim sa verificarea ortografică.

1132
00:57:26,930 --> 00:57:29,670
Și astfel dicționarele
dăm aveți de gând

1133
00:57:29,670 --> 00:57:34,870
pentru a vă oferi cuvinte reale pe care ne-o dorim
să stocați într-un fel într-un mod care este

1134
00:57:34,870 --> 00:57:36,530
mai eficient decât un tablou.

1135
00:57:36,530 --> 00:57:38,470
Și apoi textele sunt
Va fi ceea ce suntem

1136
00:57:38,470 --> 00:57:43,900
care vă solicită să prezinte asigurați-vă că
toate cuvintele sunt cuvinte reale.

1137
00:57:43,900 --> 00:57:47,970
>> Și astfel cele trei blocuri de
programe pe care le vom oferi

1138
00:57:47,970 --> 00:57:51,130
sunt numite dictionary.c,
dictionary.h, și speller.c.

1139
00:57:51,130 --> 00:57:56,500
Și atunci tot dictionary.c nu este
ceea ce a cerut să pună în aplicare.

1140
00:57:56,500 --> 00:57:57,880
Se încarcă cuvinte.

1141
00:57:57,880 --> 00:58:02,000
Se scrie cecuri lor, și-l face sigur
este introdusă corect ca totul.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h este doar un fișier bibliotecă
că declară toate aceste funcții.

1143
00:58:05,180 --> 00:58:07,650
Si speller.c, vom să vă dau.

1144
00:58:07,650 --> 00:58:09,290
Nu aveți nevoie de a modifica nimic.

1145
00:58:09,290 --> 00:58:14,290
Toate speller.c nu este să ia că,
loturile aceasta, verifică viteza de ea,

1146
00:58:14,290 --> 00:58:19,190
testează referință de ca și cum
repede sunteți în stare să facă lucruri.

1147
00:58:19,190 --> 00:58:20,410
>> Este un Speller.

1148
00:58:20,410 --> 00:58:23,920
Doar nu te pui cu el, dar face
vă că ați înțeles ce face.

1149
00:58:23,920 --> 00:58:28,090
Noi folosim o functie numita getrusage care
testează performanța vraja ta

1150
00:58:28,090 --> 00:58:28,590
checker.

1151
00:58:28,590 --> 00:58:32,200
Tot ce face este, în principiu testa
timp de totul în dicționarul,

1152
00:58:32,200 --> 00:58:33,680
astfel încât asigurați-vă că înțelege.

1153
00:58:33,680 --> 00:58:36,660
Fii atent pentru a nu te pui cu ea sau
celelalte lucruri nu se va executa în mod corespunzător.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> Și cea mai mare parte a acestei provocări este pentru
voi de a modifica într-adevăr dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Vom să vă dau
140.000 de cuvinte în dicționar. O

1157
00:58:48,526 --> 00:58:50,900
Vom să vă dau un text
fișier care are aceste cuvinte,

1158
00:58:50,900 --> 00:58:54,840
și vrem să fie în măsură să organizeze
le într-un tabel hash sau o trie

1159
00:58:54,840 --> 00:58:58,140
pentru că atunci când cerem să scrie
check-- imagina daca esti vraja

1160
00:58:58,140 --> 00:59:00,690
verificarea ca Odiseea lui Homer.

1161
00:59:00,690 --> 00:59:03,010
E ca și cum acest test enorm, imens.

1162
00:59:03,010 --> 00:59:05,190
>> Imaginați-vă dacă fiecare
cuvânt pe care a trebuit să se uite

1163
00:59:05,190 --> 00:59:08,100
printr-o serie de 140.000 de valori.

1164
00:59:08,100 --> 00:59:10,350
Asta ar lua pentru totdeauna
pentru masina dvs. pentru a rula.

1165
00:59:10,350 --> 00:59:14,490
De aceea dorim să organizăm nostru
date în structuri de date mai eficiente

1166
00:59:14,490 --> 00:59:17,270
cum ar fi un tabel hash sau o trie.

1167
00:59:17,270 --> 00:59:20,700
Și apoi voi putea fel
de atunci când căutați acces

1168
00:59:20,700 --> 00:59:22,570
lucrurile mai ușor și mai rapid.

1169
00:59:22,570 --> 00:59:24,934
>> Și astfel încât să fie atent pentru a rezolva coliziuni.

1170
00:59:24,934 --> 00:59:27,350
Vei obține o grămadă
de cuvinte de care încep cu A.

1171
00:59:27,350 --> 00:59:29,957
Vei obține o grămadă de cuvinte
care începe cu B. Până la tine

1172
00:59:29,957 --> 00:59:31,290
baieti modul în care doriți să-l rezolve.

1173
00:59:31,290 --> 00:59:34,144
Poate e mai mult
funcție hash eficientă

1174
00:59:34,144 --> 00:59:36,810
decât doar prima literă a
ceva, și pentru ca depinde de tine

1175
00:59:36,810 --> 00:59:38,190
voi să fel de a face ce vrei.

1176
00:59:38,190 --> 00:59:40,148
>> Poate doriți să adăugați
toate scrisorile împreună.

1177
00:59:40,148 --> 00:59:43,410
Poate vrei să faci lucruri ciudate plac
pentru a ține cont de numărul de litere,

1178
00:59:43,410 --> 00:59:43,970
tot ceea ce.

1179
00:59:43,970 --> 00:59:45,386
Până la voi cum vă doriți să faceți.

1180
00:59:45,386 --> 00:59:49,262
Dacă vrei să faci un tabel hash, dacă
doriți să încercați un trie, în totalitate până la tine.

1181
00:59:49,262 --> 00:59:52,470
Am să vă arăt înainte de momentul în care
trie este de obicei un pic mai dificil

1182
00:59:52,470 --> 00:59:54,520
doar pentru că există o mulțime
mai multe indicii pentru a urmări.

1183
00:59:54,520 --> 00:59:55,645
Dar în totalitate până la voi.

1184
00:59:55,645 --> 00:59:58,742
Este mult mai eficient
în cele mai multe cazuri.

1185
00:59:58,742 --> 01:00:01,450
Vrei să fii cu adevărat capabil să țină
evidența tuturor indicii tale.

1186
01:00:01,450 --> 01:00:03,850
Ca face acelasi lucru
ca am fost aici.

1187
01:00:03,850 --> 01:00:06,871
Când sunteți încercarea de a introduce
valorile într-un tabel hash sau șterge,

1188
01:00:06,871 --> 01:00:08,620
asigurați-vă că sunteți
păstrarea într-adevăr piesa

1189
01:00:08,620 --> 01:00:11,860
de unde totul se datorează faptului că
este foarte ușor pentru că dacă eu sunt

1190
01:00:11,860 --> 01:00:14,727
încercarea de a introduce ca cuvântul, Andy.

1191
01:00:14,727 --> 01:00:16,810
Să spunem doar că este o
cuvânt reală, cuvântul, Andy,

1192
01:00:16,810 --> 01:00:19,640
într-o listă gigant de o cuvinte.

1193
01:00:19,640 --> 01:00:22,450
>> Dacă doar se întâmplă să realocați
un pointer greșit, Oops,

1194
01:00:22,450 --> 01:00:24,940
acolo se duce în întregime de
restul de lista mea legată.

1195
01:00:24,940 --> 01:00:26,897
Acum, singurul cuvânt am
au este andy, iar acum

1196
01:00:26,897 --> 01:00:29,230
toate celelalte cuvinte în
Dicționar s-au pierdut.

1197
01:00:29,230 --> 01:00:31,370
Și așa doriți să vă asigurați că
ține evidența tuturor indicii dvs.

1198
01:00:31,370 --> 01:00:33,661
sau altceva ai de gând să obțineți
Probleme uriașe în codul dumneavoastră.

1199
01:00:33,661 --> 01:00:35,840
Trage lucrurile cu atenție pas cu pas.

1200
01:00:35,840 --> 01:00:37,870
Se face mult mai ușor să se gândească la.

1201
01:00:37,870 --> 01:00:40,910
>> Și, în fine, pe care doriți să fie în măsură să
testa performanța de programul

1202
01:00:40,910 --> 01:00:41,618
pe placa de mare.

1203
01:00:41,618 --> 01:00:43,710
Dacă voi lua o
uita-te la CS50 chiar acum,

1204
01:00:43,710 --> 01:00:45,210
avem ceea ce se numește consiliul mare.

1205
01:00:45,210 --> 01:00:50,200
Este foaia de arbitraj dintre cele mai rapide
vraja ori verificarea pe toate CS50

1206
01:00:50,200 --> 01:00:55,720
chiar acum, cred că în partea de sus ca 10
ori cred că opt dintre ele sunt personal.

1207
01:00:55,720 --> 01:00:57,960
Vrem cu adevărat să voi să ne bată.

1208
01:00:57,960 --> 01:01:00,870
>> Toate dintre noi au încercat să pună în aplicare
cel mai rapid codul posibil.

1209
01:01:00,870 --> 01:01:04,880
Vrem ca voi să încerce să conteste
ne și punerea în aplicare mai repede decât noi toți

1210
01:01:04,880 --> 01:01:05,550
poate sa.

1211
01:01:05,550 --> 01:01:07,970
Și așa este într-adevăr acest lucru
prima dată când suntem

1212
01:01:07,970 --> 01:01:12,680
cere voi să faceți un PSET care
poți să faci cu adevărat în orice metodă

1213
01:01:12,680 --> 01:01:13,760
tu vrei.

1214
01:01:13,760 --> 01:01:17,730
>> Eu spun mereu, acest lucru este mai asemănător
la o soluție din viața reală, nu?

1215
01:01:17,730 --> 01:01:19,550
Eu spun, hei, am nevoie de tine pentru a face acest lucru.

1216
01:01:19,550 --> 01:01:21,380
Construi un program care face acest lucru pentru mine.

1217
01:01:21,380 --> 01:01:22,630
Fă-o cum vrei.

1218
01:01:22,630 --> 01:01:24,271
Știu doar că vreau să postească.

1219
01:01:24,271 --> 01:01:25,770
Asta e provocarea pentru această săptămână.

1220
01:01:25,770 --> 01:01:27,531
Băieți, vom
pentru a vă oferi o sarcină.

1221
01:01:27,531 --> 01:01:29,030
Vom pentru a vă oferi o provocare.

1222
01:01:29,030 --> 01:01:31,559
Și apoi este de până la voi
pentru complet doar dau seama

1223
01:01:31,559 --> 01:01:34,100
ceea ce este cel mai rapid și cel mai mult
modalitate eficientă de a pune în aplicare acest lucru.

1224
01:01:34,100 --> 01:01:34,600
Da?

1225
01:01:34,600 --> 01:01:37,476
>> Audiența: Avem voie sa dacă
A vrut să cercetare moduri mai rapide

1226
01:01:37,476 --> 01:01:40,821
de a face tabele de dispersie on-line, putem face
că și citează cod altcuiva?

1227
01:01:40,821 --> 01:01:42,070
ANDI Peng: Da, în regulă.

1228
01:01:42,070 --> 01:01:44,320
Deci, dacă voi citi
spec, există o linie

1229
01:01:44,320 --> 01:01:48,310
în spec care spune voi
sunt complet lipsite de cercetare hash

1230
01:01:48,310 --> 01:01:51,070
funcțiile in care sunt unele
funcțiilor hash mai repede

1231
01:01:51,070 --> 01:01:54,720
pentru a rula lucruri prin ca
timp cât vă cita acest cod.

1232
01:01:54,720 --> 01:01:57,220
Deci, unii oameni au deja
a dat seama moduri rapide

1233
01:01:57,220 --> 01:02:00,250
de a face dame vraja, de rapid
modalități de stocare a informației.

1234
01:02:00,250 --> 01:02:02,750
În totalitate până la voi, dacă
doresc să ia doar asta, nu?

1235
01:02:02,750 --> 01:02:04,045
Asigurați-vă că a cita.

1236
01:02:04,045 --> 01:02:06,170
Provocarea aici într-adevăr
că încercăm să testeze

1237
01:02:06,170 --> 01:02:09,750
este de a face sigur că știți
ți de drum în jurul valorii de pointer.

1238
01:02:09,750 --> 01:02:12,700
În măsura în care punerea în aplicare a
funcția propriu-zisă hash

1239
01:02:12,700 --> 01:02:15,070
și vine cu ca
matematica a face acest lucru,

1240
01:02:15,070 --> 01:02:17,570
voi poate de cercetare, indiferent de
Metodele on-line vreți.

1241
01:02:17,570 --> 01:02:17,996
Da?

1242
01:02:17,996 --> 01:02:19,700
>> Audiența: Putem cita doar
folosind [neauzit]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI Peng: Da.

1244
01:02:20,120 --> 01:02:22,328
Puteți doar, în comentariu,
puteți cita ca, oh,

1245
01:02:22,328 --> 01:02:26,127
luate de la bla, bla,
bla, funcție hash.

1246
01:02:26,127 --> 01:02:27,210
Oricine are orice întrebări?

1247
01:02:27,210 --> 01:02:29,694
Noi de fapt breezed
prin secțiunea de astăzi.

1248
01:02:29,694 --> 01:02:31,610
Eu voi fi aici la
răspundă la întrebări, de asemenea.

1249
01:02:31,610 --> 01:02:36,570
>> De asemenea, așa cum am spus, de birou
ore în seara asta și mâine.

1250
01:02:36,570 --> 01:02:40,307
Spec în această săptămână este de fapt
super usor si super scurt pentru a citi.

1251
01:02:40,307 --> 01:02:43,140
Aș sugera lua o privire, doar
citit prin totalitatea ei.

1252
01:02:43,140 --> 01:02:45,730
>> Și de fapt, vă plimba Zamyla
prin fiecare dintre funcțiile

1253
01:02:45,730 --> 01:02:49,796
aveți nevoie pentru a pune în aplicare, și așa e
foarte, foarte clar cum se face totul.

1254
01:02:49,796 --> 01:02:51,920
Doar să vă asigurați că sunteți
urmarirea indicii.

1255
01:02:51,920 --> 01:02:53,650
Acesta este un PSET foarte provocator.

1256
01:02:53,650 --> 01:02:56,744
>> Nu e din cauza ca o provocare,
oh, conceptele sunt atât de mult mai mult

1257
01:02:56,744 --> 01:02:59,160
dificil, sau va trebui să învețe
atât de mult sintaxă nou drum

1258
01:02:59,160 --> 01:03:00,650
că ai făcut pentru ultima PSET.

1259
01:03:00,650 --> 01:03:03,320
Aceasta este dificil, deoarece PSET
există atât de multe indicii,

1260
01:03:03,320 --> 01:03:06,980
și atunci este foarte, foarte usor de dată
aveți un bug în cod nu putea

1261
01:03:06,980 --> 01:03:08,315
pentru a găsi în cazul în care bug-ul este.

1262
01:03:08,315 --> 01:03:13,200
>> Și atât de completă și credința totală în tine
voi să fie în măsură să bată nostru [Inaudibil]

1263
01:03:13,200 --> 01:03:13,700
ortografii.

1264
01:03:13,700 --> 01:03:16,640
Nu am de fapt, nu orice mină scris
încă, dar eu sunt pe cale de a scrie a mea.

1265
01:03:16,640 --> 01:03:19,070
Deci, în timp ce scrieți
a ta, voi fi scris mea.

1266
01:03:19,070 --> 01:03:21,070
Am de gând să încerce să facă
al meu mai repede decât a ta.

1267
01:03:21,070 --> 01:03:23,940
Vom vedea cine are cel mai rapid cea.

1268
01:03:23,940 --> 01:03:27,340
>> Și da, voi vedea tot
voi aici marți.

1269
01:03:27,340 --> 01:03:29,510
Eu va rula un fel ca un atelier PSET.

1270
01:03:29,510 --> 01:03:32,640
Toate secțiunile acestui
săptămână sunt ateliere de lucru PSET,

1271
01:03:32,640 --> 01:03:36,690
așa voi avea o mulțime de oportunități
Pentru ajutor, orelor de program ca întotdeauna,

1272
01:03:36,690 --> 01:03:41,330
și chiar cu nerăbdare să
citirea toate cod băieții tăi.

1273
01:03:41,330 --> 01:03:44,160
Am teste aici dacă
Vreți să vină să cele.

1274
01:03:44,160 --> 01:03:45,880
Asta e tot.

1275
01:03:45,880 --> 01:03:48,180