1
00:00:00,000 --> 00:00:08,250

2
00:00:08,250 --> 00:00:12,680
>> JASON Hirschhorn: Bine ati venit toată lumea
la secțiunea Seven.

3
00:00:12,680 --> 00:00:15,040
Suntem în săptămâna de șapte a cursului.

4
00:00:15,040 --> 00:00:18,440
Și această viitoare joi
este Halloween așa că eu sunt

5
00:00:18,440 --> 00:00:21,420
îmbrăcat ca un dovleac.

6
00:00:21,420 --> 00:00:23,460
Nu am putut indoi peste și a pus pe
pantofii mei, de aceea sunt

7
00:00:23,460 --> 00:00:25,660
purtând doar șosete.

8
00:00:25,660 --> 00:00:29,220
De asemenea, nu port nimic sub
acest lucru, așa că am putea să nu-l scoate, dacă este

9
00:00:29,220 --> 00:00:29,950
distrage pentru tine.

10
00:00:29,950 --> 00:00:31,860
Îmi cer scuze în avans pentru asta.

11
00:00:31,860 --> 00:00:33,170
Nu aveți nevoie să ne imaginăm
ceea ce se întâmplă.

12
00:00:33,170 --> 00:00:34,240
Sunt poartă boxeri.

13
00:00:34,240 --> 00:00:36,170
Deci, totul e bine.

14
00:00:36,170 --> 00:00:41,120
>> Eu am o poveste mai lungă despre ce sunt
îmbrăcat ca un dovleac, dar am de gând să

15
00:00:41,120 --> 00:00:45,110
cu excepția că pentru mai târziu în această secțiune
pentru că eu nu vreau să începeți.

16
00:00:45,110 --> 00:00:47,720
Avem o mulțime de lucruri interesante
pentru a trece peste această săptămână.

17
00:00:47,720 --> 00:00:51,810
Cele mai multe dintre ele se referă direct la acest
set problemă saptamana, greșeli de ortografie.

18
00:00:51,810 --> 00:00:54,680
Vom merge peste legată
liste și tabele de dispersie

19
00:00:54,680 --> 00:00:57,160
pentru întreaga secțiune.

20
00:00:57,160 --> 00:01:02,490
Am pus această listă în fiecare săptămână, o listă a
resurse pentru tine pentru a te ajuta cu

21
00:01:02,490 --> 00:01:04,120
material de pe acest curs.

22
00:01:04,120 --> 00:01:07,600
În cazul în care la o pierdere sau în cazul în care căutarea unor
mai multe informații, a verifica afară unul din

23
00:01:07,600 --> 00:01:09,930
aceste resurse.

24
00:01:09,930 --> 00:01:14,530
>> Din nou, pset6 este greseli de scriere,
PSET această săptămână.

25
00:01:14,530 --> 00:01:17,690
Și, de asemenea, te încurajează, și eu
vă încurajez, să utilizeze alte

26
00:01:17,690 --> 00:01:20,320
resurse în mod special pentru acest PSET.

27
00:01:20,320 --> 00:01:23,390
În special, cele trei am
listate pe ecran -

28
00:01:23,390 --> 00:01:27,160
gdb, pe care am fost familiarizați cu
și a fost folosind pentru un timp acum, este

29
00:01:27,160 --> 00:01:29,270
va fi de foarte mare ajutor în această săptămână.

30
00:01:29,270 --> 00:01:30,190
Așa că am pus asta aici.

31
00:01:30,190 --> 00:01:32,910
Dar ori de câte ori lucrați cu C,
ar trebui să fie întotdeauna folosind gdb la

32
00:01:32,910 --> 00:01:34,430
depana programele pe care.

33
00:01:34,430 --> 00:01:36,660
În această săptămână, de asemenea, Valgrind.

34
00:01:36,660 --> 00:01:38,535
Stie cineva ce Valgrind face?

35
00:01:38,535 --> 00:01:42,184

36
00:01:42,184 --> 00:01:43,890
>> Audiența: Se verifică pentru pierderi de memorie?

37
00:01:43,890 --> 00:01:45,950
>> JASON Hirschhorn: Valgrind
verificări pentru pierderi de memorie.

38
00:01:45,950 --> 00:01:49,970
Deci, dacă ai ceva malloc în ta
Programul, ceri pentru memorie.

39
00:01:49,970 --> 00:01:52,920
La sfârșitul programului dumneavoastră, aveți
pentru a scrie liber pe tot ceea ce ai

40
00:01:52,920 --> 00:01:54,800
malloced pentru a da memoria înapoi.

41
00:01:54,800 --> 00:01:58,420
Dacă nu scriu liber, la sfârșitul și
programul dvs. ajunge la o concluzie,

42
00:01:58,420 --> 00:02:00,000
totul va fi în mod automat
să fie eliberat.

43
00:02:00,000 --> 00:02:02,340
Și pentru programe mici, este
Nu mare lucru.

44
00:02:02,340 --> 00:02:05,250
Dar dacă sunteți scris o funcționare mai
program care nu renunta,

45
00:02:05,250 --> 00:02:09,180
în mod necesar, în câteva minute sau o
câteva secunde, apoi de memorie scurgeri

46
00:02:09,180 --> 00:02:10,710
poate deveni o afacere mare.

47
00:02:10,710 --> 00:02:14,940
>> Deci, pentru pset6, speranța este că
va avea pierderi de memorie la zero cu

48
00:02:14,940 --> 00:02:15,910
programul.

49
00:02:15,910 --> 00:02:18,690
Pentru a verifica pentru pierderi de memorie, a alerga Valgrind
și-l voi da ceva frumos

50
00:02:18,690 --> 00:02:21,190
ieșire permițându-vă să știu dacă
sau nu totul a fost gratuit.

51
00:02:21,190 --> 00:02:23,940
Vom exersa cu el mai târziu
astăzi, sperăm.

52
00:02:23,940 --> 00:02:25,790
>> În final, comanda dif.

53
00:02:25,790 --> 00:02:28,900
Ai folosit ceva similar cu o
în pset5 cu instrumentul ochiul.

54
00:02:28,900 --> 00:02:30,780
Permis să se uite înăuntru.

55
00:02:30,780 --> 00:02:33,400
Puteți, de asemenea folosit diff, de asemenea, pe
Problema set spec..

56
00:02:33,400 --> 00:02:35,950
Dar în Ai voie să
compara două fișiere.

57
00:02:35,950 --> 00:02:39,180
Ai putea compara fișierul bitmap și
anteturile informații dintr-o soluție de personal și

58
00:02:39,180 --> 00:02:42,200
soluția în cazul în care pset5
ați ales să-l folosească.

59
00:02:42,200 --> 00:02:44,030
Diff vă va permite să
face acest lucru, la fel de bine.

60
00:02:44,030 --> 00:02:48,620
Puteți compara răspunsul corect pentru
problema din această săptămână stabilit pentru răspunsul dumneavoastră

61
00:02:48,620 --> 00:02:52,210
și a vedea dacă se aliniază sau vedea
în cazul în care erorile sunt.

62
00:02:52,210 --> 00:02:55,870
>> Deci, acestea sunt cele trei instrumente bune pe care
ar trebui să utilizați pentru această săptămână, și

63
00:02:55,870 --> 00:02:58,130
verificați cu siguranta programul dvs.
cu aceste trei instrumente

64
00:02:58,130 --> 00:03:00,520
înainte de a porni-l inch

65
00:03:00,520 --> 00:03:04,650
Din nou, așa cum am menționat în fiecare săptămână,
dacă aveți orice feedback-ul pentru mine - atât

66
00:03:04,650 --> 00:03:06,470
pozitivă și constructivă -

67
00:03:06,470 --> 00:03:09,930
nu ezitați să mergeți la site-ul web
în partea de jos a acestei diapozitiv

68
00:03:09,930 --> 00:03:11,270
și de intrare-l acolo.

69
00:03:11,270 --> 00:03:13,440
Apreciez orice
și toate feedback-ul.

70
00:03:13,440 --> 00:03:17,360
Și dacă-mi dai lucruri specifice pe care
Ce pot face pentru a îmbunătăți sau care sunt

71
00:03:17,360 --> 00:03:21,350
face bine că v-ar place de mine să
continua, eu iau asta la inimă și

72
00:03:21,350 --> 00:03:24,040
încearcă într-adevăr greu pentru a asculta
pentru feedback-ul dumneavoastră.

73
00:03:24,040 --> 00:03:27,720
Nu pot să promit că voi face
totul, deși, cum ar fi purtarea un

74
00:03:27,720 --> 00:03:30,700
dovleac costum în fiecare săptămână.

75
00:03:30,700 --> 00:03:34,020
>> Așa că am de gând să-și petreacă cea mai mare parte a
secțiune, așa cum am menționat, vorbesc despre

76
00:03:34,020 --> 00:03:37,240
liste legate și tabele de dispersie, care
va fi direct aplicabile

77
00:03:37,240 --> 00:03:38,780
problema stabilit această săptămână.

78
00:03:38,780 --> 00:03:42,580
Liste legate vom merge peste relativ
repede pentru că ne-am petrecut un pic echitabil

79
00:03:42,580 --> 00:03:44,930
de timp a merge peste ea în secțiunea.

80
00:03:44,930 --> 00:03:48,680
Și astfel vom ajunge direct în
codificare pentru probleme legate de liste.

81
00:03:48,680 --> 00:03:52,740
Și apoi, la sfârșitul vom vorbi despre
hash mese și modul în care se aplică această

82
00:03:52,740 --> 00:03:55,280
problema săptămână stabilit.

83
00:03:55,280 --> 00:03:57,560
>> Ați văzut acest cod înainte.

84
00:03:57,560 --> 00:04:02,730
Acesta este un struct, și este definirea
ceva nou numit un nod.

85
00:04:02,730 --> 00:04:10,660
Și în interiorul unui nod este un număr întreg
chiar aici și acolo este un pointer la

86
00:04:10,660 --> 00:04:11,830
un alt nod.

87
00:04:11,830 --> 00:04:12,790
Am mai văzut asta înainte.

88
00:04:12,790 --> 00:04:14,830
Acest lucru a fost vine pentru
câteva săptămâni acum.

89
00:04:14,830 --> 00:04:18,680
Acesta combină indicii, pe care le-am fost
de lucru cu, și structs, care permit

90
00:04:18,680 --> 00:04:22,079
ne să combine două tipuri diferite
lucrurile într-un singur tip de date.

91
00:04:22,079 --> 00:04:24,830

92
00:04:24,830 --> 00:04:26,490
>> Există o mulțime întâmplă pe ecran.

93
00:04:26,490 --> 00:04:30,220
Dar toate ar trebui să fie relativ
familiarizat cu tine.

94
00:04:30,220 --> 00:04:33,810
Pe prima linie, am
declara un nou nod.

95
00:04:33,810 --> 00:04:41,650
Și apoi în interiorul că noul nod, am stabilit
întreg în care nodul la unul.

96
00:04:41,650 --> 00:04:44,950
Ne vedem pe linia următoare fac o
printf comanda, dar am gri

97
00:04:44,950 --> 00:04:48,080
comanda printf pentru că într-adevăr
parte importantă este această linie aici -

98
00:04:48,080 --> 00:04:50,020
new_node.n.

99
00:04:50,020 --> 00:04:51,270
Ce înseamnă punctul spui?

100
00:04:51,270 --> 00:04:53,810

101
00:04:53,810 --> 00:04:57,240
>> Audiența: Du-te la nodul și
evalua valoarea n pentru ea.

102
00:04:57,240 --> 00:04:58,370
>> JASON Hirschhorn: Asta-i
exact dreapta.

103
00:04:58,370 --> 00:05:03,300
Dot înseamnă acces la n partea
din acest nou nod.

104
00:05:03,300 --> 00:05:05,690
Această linie viitoare ce face?

105
00:05:05,690 --> 00:05:16,140

106
00:05:16,140 --> 00:05:17,050
Michael.

107
00:05:17,050 --> 00:05:21,910
>> Audiența: Se creează un alt nod
care va indica la noul nod.

108
00:05:21,910 --> 00:05:24,870
>> JASON Hirschhorn: Deci, nu
a crea un nou nod.

109
00:05:24,870 --> 00:05:26,120
Se creează o ce?

110
00:05:26,120 --> 00:05:28,300

111
00:05:28,300 --> 00:05:29,300
>> Audiența: Un pointer.

112
00:05:29,300 --> 00:05:33,460
>> JASON Hirschhorn: Un pointer la un nod,
așa cum este indicat prin acest nod * aici.

113
00:05:33,460 --> 00:05:34,800
Deci, se creează un pointer la un nod.

114
00:05:34,800 --> 00:05:37,490
Și care nod este o îndreptat
la, Michael?

115
00:05:37,490 --> 00:05:38,440
>> Audiența: nod nou?

116
00:05:38,440 --> 00:05:39,240
>> JASON Hirschhorn: nod nou.

117
00:05:39,240 --> 00:05:43,020
Și este îndreptat acolo pentru că ne-am
având în vedere că adresa de nod nou.

118
00:05:43,020 --> 00:05:45,820
Și acum, în această linie vom vedea
două moduri diferite de

119
00:05:45,820 --> 00:05:46,910
exprimă același lucru.

120
00:05:46,910 --> 00:05:49,650
Și am vrut să subliniez modul în care acestea
două lucruri sunt la fel.

121
00:05:49,650 --> 00:05:54,740
În primul rând, am dereferire
indicatorul.

122
00:05:54,740 --> 00:05:55,830
Deci, mergem la nodul.

123
00:05:55,830 --> 00:05:56,830
Asta e ceea ce înseamnă acest lucru stea.

124
00:05:56,830 --> 00:05:57,930
Am văzut că, înainte cu indicii.

125
00:05:57,930 --> 00:05:59,280
Du-te la acel nod.

126
00:05:59,280 --> 00:06:00,370
Care este în paranteze.

127
00:06:00,370 --> 00:06:04,610
Și apoi a accesa prin intermediul operatorului dot
elementul de n acel nod.

128
00:06:04,610 --> 00:06:08,430
>> Astfel că, luând sintaxa
am văzut aici și acum

129
00:06:08,430 --> 00:06:09,670
folosindu-l cu un pointer.

130
00:06:09,670 --> 00:06:13,730
Desigur, acesta devine un fel de ocupat în cazul în care
sunteți scris aceste paranteze -

131
00:06:13,730 --> 00:06:14,940
că stele și acel punct.

132
00:06:14,940 --> 00:06:16,220
Ea devine un pic ocupat.

133
00:06:16,220 --> 00:06:18,500
Deci avem niște zahăr sintactic.

134
00:06:18,500 --> 00:06:19,920
Și aceasta linie de aici -

135
00:06:19,920 --> 00:06:21,170
ptr_node-> n.

136
00:06:21,170 --> 00:06:25,400

137
00:06:25,400 --> 00:06:28,000
Care face exact același lucru.

138
00:06:28,000 --> 00:06:30,840
Deci, cele două linii de cod sunt
echivalente și va face

139
00:06:30,840 --> 00:06:31,650
exact același lucru.

140
00:06:31,650 --> 00:06:34,210
>> Dar am vrut să subliniez acele înainte de
a merge mai departe, astfel încât să înțelegeți

141
00:06:34,210 --> 00:06:39,000
că într-adevăr acest lucru chiar aici este
doar zahăr sintactic pentru dereferencing

142
00:06:39,000 --> 00:06:44,200
indicatorul și apoi merge la
n partea de care struct.

143
00:06:44,200 --> 00:06:45,525
Orice întrebări cu privire la acest diapozitiv?

144
00:06:45,525 --> 00:06:53,020

145
00:06:53,020 --> 00:06:54,390
OK.

146
00:06:54,390 --> 00:06:58,510
>> Așa că am de gând să treacă printr-un cuplu
operațiunilor pe care le puteți face pe

147
00:06:58,510 --> 00:06:59,730
liste legate.

148
00:06:59,730 --> 00:07:05,770
O listă legată, amintesc, este o serie de
noduri care trimit unul altuia.

149
00:07:05,770 --> 00:07:12,470
Și, în general, vom începe cu un pointer
numit cap, în general, care indică

150
00:07:12,470 --> 00:07:14,040
primul lucru pe listă.

151
00:07:14,040 --> 00:07:18,900
Deci, pe prima linie de aici, ne-am
au L noastră originală primul.

152
00:07:18,900 --> 00:07:21,370
Astfel încât lucru vă puteți gândi de - acest
text, chiar aici, vă puteți gândi ca

153
00:07:21,370 --> 00:07:23,560
doar indicatorul care le-am stocat
că undeva puncte

154
00:07:23,560 --> 00:07:24,670
la primul element.

155
00:07:24,670 --> 00:07:27,500
Și în această listă legată
avem patru noduri.

156
00:07:27,500 --> 00:07:29,530
Fiecare nod este o cutie mare.

157
00:07:29,530 --> 00:07:33,430
Caseta de mare din interiorul Big
casetă este partea întreagă.

158
00:07:33,430 --> 00:07:37,400
Și atunci avem o parte pointer.

159
00:07:37,400 --> 00:07:39,630
>> Aceste cutii nu sunt atrași de
scară din cauza cât de mare este

160
00:07:39,630 --> 00:07:42,320
un întreg în bytes?

161
00:07:42,320 --> 00:07:43,290
Cât de mare acum?

162
00:07:43,290 --> 00:07:43,710
Patru.

163
00:07:43,710 --> 00:07:45,470
Și cât de mare este un pointer?

164
00:07:45,470 --> 00:07:45,940
Patru.

165
00:07:45,940 --> 00:07:48,180
Deci, într-adevăr, dacă ar fi să atragă
acest lucru la scară ambele cutii

166
00:07:48,180 --> 00:07:49,690
ar fi de aceeași dimensiune.

167
00:07:49,690 --> 00:07:52,870
În acest caz, dorim să introduceți
ceva în lista de legătura.

168
00:07:52,870 --> 00:07:57,190
Astfel încât să puteți vedea aici vom introduce
cinci Am traversa prin

169
00:07:57,190 --> 00:08:01,310
lista legate, găsiți în cazul în care cinci
merge, și apoi introduceți-l.

170
00:08:01,310 --> 00:08:03,560
>> Să rupe-l jos și du-te
un pic mai lent.

171
00:08:03,560 --> 00:08:05,510
Am de gând să subliniez la bord.

172
00:08:05,510 --> 00:08:09,930
Deci avem nod noastre cinci care
am creat în mallocs.

173
00:08:09,930 --> 00:08:11,190
De ce este toată lumea de râs?

174
00:08:11,190 --> 00:08:12,130
Glumeam.

175
00:08:12,130 --> 00:08:13,310
OK.

176
00:08:13,310 --> 00:08:14,820
Deci, ne-am malloced cinci.

177
00:08:14,820 --> 00:08:16,310
Am creat acest nod
în altă parte.

178
00:08:16,310 --> 00:08:17,740
Avem gata să meargă.

179
00:08:17,740 --> 00:08:20,130
Noi încep de la partea din față a
lista cu doi.

180
00:08:20,130 --> 00:08:22,380
Și ne-o dorim pentru a insera
într-un mod sortat.

181
00:08:22,380 --> 00:08:27,550
>> Deci, dacă vom vedea două și ne-o dorim pentru a pune
în cinci, ce facem când vedem

182
00:08:27,550 --> 00:08:28,800
ceva mai puțin decât noi?

183
00:08:28,800 --> 00:08:31,850

184
00:08:31,850 --> 00:08:33,520
Ce?

185
00:08:33,520 --> 00:08:36,750
Vrem să inserați cinci în acest
lista legate, menținându-l sortate.

186
00:08:36,750 --> 00:08:37,520
Vom vedea numărul doi.

187
00:08:37,520 --> 00:08:38,769
Deci, ce facem?

188
00:08:38,769 --> 00:08:39,179
Marcus?

189
00:08:39,179 --> 00:08:40,679
>> Audiența: Sunați la indicatorul
următorului nod.

190
00:08:40,679 --> 00:08:42,530
>> JASON Hirschhorn: Și de ce
mergem la următorul?

191
00:08:42,530 --> 00:08:45,970
>> Audiența: Pentru că este
următorul nod în listă.

192
00:08:45,970 --> 00:08:48,310
Și știm doar că o altă locație.

193
00:08:48,310 --> 00:08:50,410
>> JASON Hirschhorn: Cinci este mai mare
mult de două, în special.

194
00:08:50,410 --> 00:08:51,600
Pentru că vrem să-l păstrați sortat.

195
00:08:51,600 --> 00:08:52,730
Deci, cinci este mai mare de doi.

196
00:08:52,730 --> 00:08:54,460
Așa că am trece la următoarea.

197
00:08:54,460 --> 00:08:55,240
Și acum ajungem la patru.

198
00:08:55,240 --> 00:08:56,490
Și ce se întâmplă atunci când vom ajunge la patru?

199
00:08:56,490 --> 00:08:58,920

200
00:08:58,920 --> 00:09:00,310
>> Cinci este mai mare de patru.

201
00:09:00,310 --> 00:09:01,460
Așa că am continua.

202
00:09:01,460 --> 00:09:03,110
Iar acum suntem la șase.

203
00:09:03,110 --> 00:09:04,360
Și ce vedem la șase?

204
00:09:04,360 --> 00:09:08,672

205
00:09:08,672 --> 00:09:09,608
Da, Carlos?

206
00:09:09,608 --> 00:09:10,544
>> Audiența: Șase este mai mare de cinci.

207
00:09:10,544 --> 00:09:11,480
>> JASON Hirschhorn: Six este
mai mare de cinci.

208
00:09:11,480 --> 00:09:13,660
Deci, asta e în cazul în care ne-o dorim
pentru a introduce cinci.

209
00:09:13,660 --> 00:09:17,320
Cu toate acestea, rețineți că, dacă ne-am
au doar un singur indicator de aici -

210
00:09:17,320 --> 00:09:19,840
aceasta este pointer nostru suplimentar care este
traversează prin lista.

211
00:09:19,840 --> 00:09:21,860
Și ne indică la șase.

212
00:09:21,860 --> 00:09:25,010
Ne-am pierdut urma a ceea ce
vine înainte de șase.

213
00:09:25,010 --> 00:09:29,130
Deci, dacă vrem să introduceți ceva în
această listă menținându-l sortate, ne-am

214
00:09:29,130 --> 00:09:31,630
, probabil, nevoie de cât mai multe indicii?

215
00:09:31,630 --> 00:09:32,280
>> Audiența: Two.

216
00:09:32,280 --> 00:09:32,920
>> JASON Hirschorn: Two.

217
00:09:32,920 --> 00:09:35,720
O pentru a urmări de curent
unul și unul pentru a ține evidența

218
00:09:35,720 --> 00:09:37,050
cel anterior.

219
00:09:37,050 --> 00:09:38,450
Aceasta este doar o listă individual legat.

220
00:09:38,450 --> 00:09:39,670
Se merge doar o singură direcție.

221
00:09:39,670 --> 00:09:43,220
Dacă am avea o listă de două ori legat, în cazul în care
totul a fost îndreptat la lucru

222
00:09:43,220 --> 00:09:46,240
după ce și lucrul înainte de a, atunci
nu ne-ar trebui să faci asta.

223
00:09:46,240 --> 00:09:49,350
Dar în acest caz nu vrem să-și piardă
evidența a ceea ce a venit în fața noastră, în cazul în care

224
00:09:49,350 --> 00:09:53,350
avem nevoie de a introduce cinci undeva
în mijloc.

225
00:09:53,350 --> 00:09:55,610
Spune-ne inserarea nouă.

226
00:09:55,610 --> 00:09:57,260
Ce s-ar întâmpla, atunci când
am ajuns la opt?

227
00:09:57,260 --> 00:10:01,860

228
00:10:01,860 --> 00:10:04,880
>> Audiența: Ar trebui să
obține acel punct nul.

229
00:10:04,880 --> 00:10:07,820
În loc de a avea punctul de nul vei avea
pentru a adăuga un element și apoi au

230
00:10:07,820 --> 00:10:09,216
l punct de nouă.

231
00:10:09,216 --> 00:10:09,700
>> JASON Hirschorn: Exact.

232
00:10:09,700 --> 00:10:10,600
Deci, avem opt.

233
00:10:10,600 --> 00:10:13,140
Vom ajunge la sfârșitul listei, deoarece
acest lucru se indică la null.

234
00:10:13,140 --> 00:10:16,330
Și acum, în loc de a se indica
nul trebuie să indice către noul nostru nod.

235
00:10:16,330 --> 00:10:19,870
Și ne-am stabilit indicatorul în
noul nostru nod la null.

236
00:10:19,870 --> 00:10:21,445
Are cineva intrebari
despre introducerea?

237
00:10:21,445 --> 00:10:25,620

238
00:10:25,620 --> 00:10:28,100
Ce se întâmplă dacă nu-mi pasă de
actualiza lista sortată?

239
00:10:28,100 --> 00:10:31,701

240
00:10:31,701 --> 00:10:34,350
>> Audiența: Stick-l la
începutul sau la sfârșitul.

241
00:10:34,350 --> 00:10:35,510
>> JASON Hirschorn: Stick-l la
la începutul sau la sfârșitul.

242
00:10:35,510 --> 00:10:37,276
Care ar trebui să facem?

243
00:10:37,276 --> 00:10:38,770
Bobby?

244
00:10:38,770 --> 00:10:41,020
De ce cele din urmă?

245
00:10:41,020 --> 00:10:43,250
>> Audiența: Pentru că la început
este deja plin.

246
00:10:43,250 --> 00:10:43,575
>> JASON Hirschorn: OK.

247
00:10:43,575 --> 00:10:44,360
Inceputul este deja plin.

248
00:10:44,360 --> 00:10:46,090
Cine vrea să argumenta împotriva lui Bobby.

249
00:10:46,090 --> 00:10:47,290
Marcus.

250
00:10:47,290 --> 00:10:48,910
>> Audiența: Ei bine, probabil că doriți să
stick-l la început pentru că

251
00:10:48,910 --> 00:10:50,140
în caz contrar, dacă l-ai pus la
final va trebui să-

252
00:10:50,140 --> 00:10:51,835
traversa întreaga listă.

253
00:10:51,835 --> 00:10:52,990
>> JASON Hirschorn: Exact.

254
00:10:52,990 --> 00:10:57,970
Deci, dacă ne gândim la rulare,
execuție a introduce la sfârșitul

255
00:10:57,970 --> 00:11:00,110
ar fi n, dimensiunea acestei.

256
00:11:00,110 --> 00:11:03,080
Care este O rulare mare de a introduce
la început?

257
00:11:03,080 --> 00:11:04,170
Constantă de timp.

258
00:11:04,170 --> 00:11:07,075
Deci, dacă nu-mi pasă despre păstrarea
ceva sortate, mult mai bine la doar

259
00:11:07,075 --> 00:11:08,420
introduce la începutul acestei liste.

260
00:11:08,420 --> 00:11:10,320
Și ce se poate face în timp constant.

261
00:11:10,320 --> 00:11:13,900

262
00:11:13,900 --> 00:11:14,690
>> OK.

263
00:11:14,690 --> 00:11:18,870
Operație următor este să găsească, pe care alte -
am formulat acest lucru ca pe căutare.

264
00:11:18,870 --> 00:11:22,470
Dar ne vom uita prin
Lista de legat pentru un obiect.

265
00:11:22,470 --> 00:11:26,000
Ați văzut cod pentru
căutare înainte în curs.

266
00:11:26,000 --> 00:11:29,490
Dar am un fel de pur și simplu a făcut-o cu
introduce, sau cel puțin de a introduce

267
00:11:29,490 --> 00:11:30,580
ceva sortate.

268
00:11:30,580 --> 00:11:36,350
Te uiți prin, va nod de nod,
până când găsiți numărul pe care ești

269
00:11:36,350 --> 00:11:37,780
caută.

270
00:11:37,780 --> 00:11:39,670
Ce se întâmplă dacă ajunge
sfârșitul listei?

271
00:11:39,670 --> 00:11:43,020
Spune caut nouă și eu
ajunge la sfârșitul listei.

272
00:11:43,020 --> 00:11:44,270
Ce facem?

273
00:11:44,270 --> 00:11:47,147

274
00:11:47,147 --> 00:11:48,110
>> Audiența: Înapoi fals?

275
00:11:48,110 --> 00:11:48,690
>> JASON Hirschorn: Înapoi false.

276
00:11:48,690 --> 00:11:49,960
Noi nu l-am găsit.

277
00:11:49,960 --> 00:11:52,010
Dacă ajungi la sfârșitul listei și
nu ați găsit numărul pe care ești

278
00:11:52,010 --> 00:11:54,170
caută, nu e acolo.

279
00:11:54,170 --> 00:11:55,420
Orice întrebări cu privire la găsit?

280
00:11:55,420 --> 00:11:59,530

281
00:11:59,530 --> 00:12:04,615
În cazul în care acest lucru a fost o listă sortată, ceea ce ar fi
fi diferit pentru căutarea noastră?

282
00:12:04,615 --> 00:12:07,370

283
00:12:07,370 --> 00:12:08,103
Da.

284
00:12:08,103 --> 00:12:10,600
>> Audiența: ar găsi prima valoare
care este mai mare decât cea

285
00:12:10,600 --> 00:12:12,390
sunteți în căutarea pentru și
apoi să se întoarcă false.

286
00:12:12,390 --> 00:12:13,190
>> JASON Hirschorn: Exact.

287
00:12:13,190 --> 00:12:17,310
Deci, în cazul în care este o listă sortată, dacă ajungem la
ceva care este mai mare decât ceea ce

288
00:12:17,310 --> 00:12:20,180
căutăm, nu avem nevoie să
mergi la sfârșitul listei.

289
00:12:20,180 --> 00:12:24,060
La acel moment, ne putem întoarce false
pentru că noi nu o să-l găsească.

290
00:12:24,060 --> 00:12:27,340
Întrebarea este acum, am vorbit despre
păstrarea listelor legate sortate,

291
00:12:27,340 --> 00:12:28,180
menținându-le nesortat.

292
00:12:28,180 --> 00:12:30,050
Asta va fi ceva de care ești
probabil, va trebui să se gândească la

293
00:12:30,050 --> 00:12:34,240
atunci când codificare problema stabilit cinci, dacă
alege un tabel hash cu separat

294
00:12:34,240 --> 00:12:36,360
abordare înlănțuirea, care
vom vorbi despre mai târziu.

295
00:12:36,360 --> 00:12:41,400
>> Dar este merită să păstreze lista
sortate și apoi să fie capabil de a avea, poate,

296
00:12:41,400 --> 00:12:42,310
Cautari mai repede?

297
00:12:42,310 --> 00:12:47,220
Sau este mai bine pentru a introduce rapid
ceva în timpul rulării constant, dar apoi

298
00:12:47,220 --> 00:12:48,430
au mai caută?

299
00:12:48,430 --> 00:12:52,250
Acesta este un compromis chiar acolo pe care le
ajunge pentru a decide ce este mai adecvat

300
00:12:52,250 --> 00:12:53,590
pentru problema dvs. specifice.

301
00:12:53,590 --> 00:12:56,680
Și nu e neapărat un
răspuns absolut corect.

302
00:12:56,680 --> 00:12:59,520
Dar este cu siguranță o decizie te
de a face, și, probabil, bun pentru a apăra

303
00:12:59,520 --> 00:13:05,270
că în, să zicem, un comentariu sau două de ce
ai ales unul peste celălalt.

304
00:13:05,270 --> 00:13:06,490
>> În cele din urmă, ștergerea.

305
00:13:06,490 --> 00:13:08,100
Am văzut ștergerea.

306
00:13:08,100 --> 00:13:09,180
Este similar cu căutarea.

307
00:13:09,180 --> 00:13:11,020
Ne uităm pentru elementul.

308
00:13:11,020 --> 00:13:12,390
Spune-ne încercarea de a șterge șase.

309
00:13:12,390 --> 00:13:14,450
Așa că am găsit șase aici.

310
00:13:14,450 --> 00:13:18,860
Lucru pe care trebuie să ne asigurăm că
face este că orice este îndreptat la

311
00:13:18,860 --> 00:13:21,220
șase - așa cum vom vedea în pasul
doi aici -

312
00:13:21,220 --> 00:13:26,500
orice este îndreptat la șase trebuie să
săriți peste șase acum și să fie modificat pentru a

313
00:13:26,500 --> 00:13:28,160
indiferent de șase indică spre.

314
00:13:28,160 --> 00:13:31,410
Noi nu vrem să orfani tot restul
Lista noastră de a uita de a stabili că

315
00:13:31,410 --> 00:13:32,960
pointer anterior.

316
00:13:32,960 --> 00:13:35,960
Și apoi, uneori, în funcție de
privind programul, ei vor doar

317
00:13:35,960 --> 00:13:37,380
șterge acest nod în întregime.

318
00:13:37,380 --> 00:13:40,135
Uneori, veți dori să se întoarcă
valoarea care este în acest nod.

319
00:13:40,135 --> 00:13:42,490
Deci, asta e cum ștergerea lucrărilor.

320
00:13:42,490 --> 00:13:44,610
Orice întrebări cu privire la ștergeți?

321
00:13:44,610 --> 00:13:51,280

322
00:13:51,280 --> 00:13:53,850
>> Audiența: Deci, dacă ai de gând să-l ștergeți
ea, ai doar folosi gratuit, deoarece

323
00:13:53,850 --> 00:13:55,655
probabil a fost malloced?

324
00:13:55,655 --> 00:13:57,976
>> JASON Hirschorn: Dacă doriți să eliberați
ceva care este exact corect și tu

325
00:13:57,976 --> 00:13:58,540
malloced ea.

326
00:13:58,540 --> 00:14:00,410
Spune-am vrut să se întoarcă această valoare.

327
00:14:00,410 --> 00:14:04,010
S-ar putea întoarce șase și apoi gratuit
acest nod și fără apel pe ea.

328
00:14:04,010 --> 00:14:06,180
Sau probabil ne-ar suna gratuit întâi
și apoi să se întoarcă șase.

329
00:14:06,180 --> 00:14:11,210

330
00:14:11,210 --> 00:14:11,580
>> OK.

331
00:14:11,580 --> 00:14:14,010
Deci, haideți să trecem la practica de codificare.

332
00:14:14,010 --> 00:14:16,090
Vom cod trei funcții.

333
00:14:16,090 --> 00:14:18,260
Primul se numește insert_node.

334
00:14:18,260 --> 00:14:22,170
Deci, aveți cod pe care le-am prin e-mail, și
dacă te uiți la asta mai târziu

335
00:14:22,170 --> 00:14:28,020
puteți accesa codul în linked.c
pe site-ul CS50.

336
00:14:28,020 --> 00:14:30,880
Dar în linked.c, există unele
cod schelet care este deja

337
00:14:30,880 --> 00:14:32,280
a fost scris pentru tine.

338
00:14:32,280 --> 00:14:34,560
Și apoi există câteva funcții
aveți nevoie pentru a scrie.

339
00:14:34,560 --> 00:14:36,380
>> În primul rând vom
scrie insert_node.

340
00:14:36,380 --> 00:14:39,800
Și ce face insert_node
IS introduce un număr întreg.

341
00:14:39,800 --> 00:14:42,440
Și dai întreg
într-o listă de legat.

342
00:14:42,440 --> 00:14:45,470
Și, în special, ai nevoie de
pentru a menține lista sortată

343
00:14:45,470 --> 00:14:47,650
de la cel mai mic la cel mai mare.

344
00:14:47,650 --> 00:14:51,360
De asemenea, nu doriți să
introduce orice duplicate.

345
00:14:51,360 --> 00:14:54,600
În cele din urmă, după cum puteți vedea insert_node
returnează un bool.

346
00:14:54,600 --> 00:14:57,140
Deci, tu ar trebui pentru a permite utilizatorului știu
dacă inserția a fost sau nu

347
00:14:57,140 --> 00:15:00,800
de succes de a reveni adevărat sau fals.

348
00:15:00,800 --> 00:15:02,580
La finalul acestui program -

349
00:15:02,580 --> 00:15:05,750
și pentru acest stadiu nu aveți nevoie de
să vă faceți griji cu privire la eliberarea nimic.

350
00:15:05,750 --> 00:15:11,790
Deci, tot ce faci este de a lua un întreg
și se introduce într-o listă.

351
00:15:11,790 --> 00:15:13,890
>> Asta este ceea ce îți cer să faci acum.

352
00:15:13,890 --> 00:15:17,620
Din nou, în linked.c, care vă
toate au, este codul de schelet.

353
00:15:17,620 --> 00:15:20,980
Și ar trebui să vedeți spre partea de jos
declarația funcției de probă.

354
00:15:20,980 --> 00:15:27,390
Cu toate acestea, înainte de a merge într-o codificare
în C, am foarte vă încurajez să mergeți

355
00:15:27,390 --> 00:15:29,330
prin măsurile pe care le-am fost
practicarea în fiecare săptămână.

356
00:15:29,330 --> 00:15:31,100
Am trecut deja prin
o imagine de aceasta.

357
00:15:31,100 --> 00:15:33,380
Deci, ar trebui să aveți o înțelegere
de modul în care funcționează.

358
00:15:33,380 --> 00:15:36,590
Dar v-aș încuraja să scrie
unele pseudocod înainte de scufundare inch

359
00:15:36,590 --> 00:15:38,640
Și vom trece peste
pseudocod ca un grup.

360
00:15:38,640 --> 00:15:41,470
Și apoi, o dată ce ați scris dvs.
pseudocod, și odată ce ne-am scris noastre

361
00:15:41,470 --> 00:15:45,850
pseudocod ca un grup, aveți posibilitatea să
du-te în ea codificare în C.

362
00:15:45,850 --> 00:15:49,980
>> Ca un heads-up, funcția insert_node
este, probabil, mai delicată de

363
00:15:49,980 --> 00:15:53,550
trei ne-am de gând să scrie pentru că am
a adăugat unele constrângeri suplimentare pentru a

364
00:15:53,550 --> 00:15:57,190
programarea, în special, că
nu sunteți de gând să introduceți orice

365
00:15:57,190 --> 00:15:59,880
duplicate și că lista
ar trebui să rămână sortat.

366
00:15:59,880 --> 00:16:02,660
Deci, acesta este un program non-trivial
de care aveți nevoie să cod.

367
00:16:02,660 --> 00:16:06,470
Și de ce nu te duci cinci la șapte
minute doar pentru a obține de lucru privind

368
00:16:06,470 --> 00:16:07,640
pseudocod și codul.

369
00:16:07,640 --> 00:16:09,460
Și apoi vom începe
merge ca un grup.

370
00:16:09,460 --> 00:16:11,680
Din nou, dacă aveți întrebări doar
ridica mâna și voi veni în jur.

371
00:16:11,680 --> 00:16:15,258

372
00:16:15,258 --> 00:16:16,508
.

373
00:16:16,508 --> 00:18:28,370

374
00:18:28,370 --> 00:18:30,120
>> Noi, de asemenea, în general, face aceste -

375
00:18:30,120 --> 00:18:32,070
sau eu nu voi spune în mod explicit
poate lucra cu oamenii.

376
00:18:32,070 --> 00:18:36,500
Dar, evident, am foarte vă încurajez,
dacă aveți întrebări, să solicite

377
00:18:36,500 --> 00:18:39,840
vecinul care sta langa tine
sau chiar de lucru cu cineva

378
00:18:39,840 --> 00:18:40,510
altfel, dacă doriți să.

379
00:18:40,510 --> 00:18:42,600
Acest lucru nu trebuie să fie un individ
activitate tăcut.

380
00:18:42,600 --> 00:20:11,770

381
00:20:11,770 --> 00:20:16,330
>> Să începem cu scrierea unele
pseudocod pe bord.

382
00:20:16,330 --> 00:20:19,395
Cine poate da-mi prima linie de
pseudocod pentru acest program?

383
00:20:19,395 --> 00:20:22,240

384
00:20:22,240 --> 00:20:23,640
Pentru această funcție, mai degrabă -
insert_node.

385
00:20:23,640 --> 00:20:29,960

386
00:20:29,960 --> 00:20:31,830
Alden?

387
00:20:31,830 --> 00:20:36,560
>> Audiența: Deci, primul lucru pe care am făcut a fost
a crea un nou pointer la nodul și I

388
00:20:36,560 --> 00:20:41,320
inițializat se indică spre aceeași
lucru care listă este îndreptat la.

389
00:20:41,320 --> 00:20:41,550
>> JASON Hirschorn: OK.

390
00:20:41,550 --> 00:20:45,190
Deci, creați un nou indicator
la lista, nu la nodul.

391
00:20:45,190 --> 00:20:45,420
>> Audiența: Corect.

392
00:20:45,420 --> 00:20:46,150
Da.

393
00:20:46,150 --> 00:20:46,540
>> JASON Hirschorn: OK.

394
00:20:46,540 --> 00:20:48,221
Și apoi ce vrem sa facem?

395
00:20:48,221 --> 00:20:49,163
Ce după asta?

396
00:20:49,163 --> 00:20:50,105
Ce despre nodul?

397
00:20:50,105 --> 00:20:51,050
Nu avem un nod.

398
00:20:51,050 --> 00:20:52,300
Avem doar o valoare.

399
00:20:52,300 --> 00:20:55,918

400
00:20:55,918 --> 00:20:58,890
Dacă vrem să insera un nod, ce facem noi
trebuie să faceți înainte de a ne putea chiar

401
00:20:58,890 --> 00:20:59,980
cred despre introducerea ea?

402
00:20:59,980 --> 00:21:00,820
>> Audiența: Oh, îmi pare rău.

403
00:21:00,820 --> 00:21:02,160
avem nevoie pentru a malloc spațiu pentru un nod.

404
00:21:02,160 --> 00:21:02,455
>> JASON Hirschorn: Excelent.

405
00:21:02,455 --> 00:21:03,210
Să facem -

406
00:21:03,210 --> 00:21:04,628
OK.

407
00:21:04,628 --> 00:21:06,065
Nu se poate ajunge la această mare.

408
00:21:06,065 --> 00:21:08,939

409
00:21:08,939 --> 00:21:09,897
OK.

410
00:21:09,897 --> 00:21:13,236
Vom merge în jos, și apoi
suntem cu ajutorul a două coloane.

411
00:21:13,236 --> 00:21:13,732
Nu pot să merg că -

412
00:21:13,732 --> 00:21:14,982
OK.

413
00:21:14,982 --> 00:21:23,660

414
00:21:23,660 --> 00:21:25,130
A crea un nou nod.

415
00:21:25,130 --> 00:21:29,380
Puteți crea un alt pointer la lista
sau puteți folosi doar listă ca ea exista.

416
00:21:29,380 --> 00:21:30,720
Nu aveți cu adevărat nevoie să faci asta.

417
00:21:30,720 --> 00:21:31,750
>> Așa că am crea un nou nod.

418
00:21:31,750 --> 00:21:32,010
Mare.

419
00:21:32,010 --> 00:21:32,840
Asta e ceea ce facem noi mai întâi.

420
00:21:32,840 --> 00:21:34,870
Ce urmează?

421
00:21:34,870 --> 00:21:35,080
>> Audiența: Așteaptă.

422
00:21:35,080 --> 00:21:38,330
În cazul în care vom crea un nou nod acum sau
ar trebui să ne așteptăm să ne asigurăm că

423
00:21:38,330 --> 00:21:42,260
nu exista nici duplicate ale nodului
pe lista inainte de a le crea?

424
00:21:42,260 --> 00:21:43,100
>> JASON Hirschorn: Bună întrebare.

425
00:21:43,100 --> 00:21:47,770
Să susțin că pentru mai târziu, deoarece
majoritate a timpului, vom crea

426
00:21:47,770 --> 00:21:48,220
un nou nod.

427
00:21:48,220 --> 00:21:49,110
Deci, vom păstra asta aici.

428
00:21:49,110 --> 00:21:51,006
Dar asta este o întrebare bună.

429
00:21:51,006 --> 00:21:53,250
Dacă vom crea și noi găsim
un duplicat, ceea ce ar trebui să

430
00:21:53,250 --> 00:21:54,490
facem înainte de a reveni?

431
00:21:54,490 --> 00:21:55,190
>> Audiența: Eliberați-l.

432
00:21:55,190 --> 00:21:55,470
>> JASON Hirschorn: Da.

433
00:21:55,470 --> 00:21:56,500
Probabil că-l gratuit.

434
00:21:56,500 --> 00:21:56,760
OK.

435
00:21:56,760 --> 00:21:59,850
Ce facem după ce ne-am
a crea un nou nod?

436
00:21:59,850 --> 00:22:02,260
Annie?

437
00:22:02,260 --> 00:22:04,780
>> Audiența: Am pus
număr în nodul?

438
00:22:04,780 --> 00:22:05,140
>> JASON Hirschorn: Exact.

439
00:22:05,140 --> 00:22:07,190
Am pus numărul - am malloc spațiu.

440
00:22:07,190 --> 00:22:08,160
Am de gând să părăsească
toate ca o singură linie.

441
00:22:08,160 --> 00:22:08,720
Dar ai dreptate.

442
00:22:08,720 --> 00:22:10,305
Noi malloc spațiu, și apoi
am pus numărul inch

443
00:22:10,305 --> 00:22:12,585
Putem chiar să setați indicatorul
o parte din ea la null.

444
00:22:12,585 --> 00:22:13,720
Asta-i exact corect.

445
00:22:13,720 --> 00:22:17,400
Și atunci ce despre după aceea?

446
00:22:17,400 --> 00:22:18,490
Am desenat această imagine de pe bord.

447
00:22:18,490 --> 00:22:21,190
Deci, ce facem?

448
00:22:21,190 --> 00:22:22,680
>> Audiența: Trecem prin lista.

449
00:22:22,680 --> 00:22:23,930
>> JASON Hirschorn: Du-te prin lista.

450
00:22:23,930 --> 00:22:30,620

451
00:22:30,620 --> 00:22:31,100
OK.

452
00:22:31,100 --> 00:22:34,280
Și ce vom verifica de la fiecare nod.

453
00:22:34,280 --> 00:22:35,955
Kurt, ce vom verifica
pentru la fiecare nod?

454
00:22:35,955 --> 00:22:41,640
>> Audiența: A se vedea dacă valoarea n a
acel nod este mai mare decât valoarea n

455
00:22:41,640 --> 00:22:43,070
de nod noastre.

456
00:22:43,070 --> 00:22:43,340
>> JASON Hirschorn: OK.

457
00:22:43,340 --> 00:22:44,280
Am de gând să fac -

458
00:22:44,280 --> 00:22:45,855
Da, OK.

459
00:22:45,855 --> 00:22:48,160
Deci e n -

460
00:22:48,160 --> 00:22:59,040
Am de gând să spun, dacă valoarea este mai mare
decât acest nod, atunci ce facem?

461
00:22:59,040 --> 00:23:07,290
>> Audiența: Ei bine, atunci vom introduce
ceea ce trebuie, înainte de asta.

462
00:23:07,290 --> 00:23:07,970
>> JASON Hirschorn: OK.

463
00:23:07,970 --> 00:23:09,410
Deci, dacă este mai mare decât aceasta,
apoi ne-o dorim pentru a insera.

464
00:23:09,410 --> 00:23:14,010
Dar vrem să-l inserați chiar înainte de
pentru că avem, de asemenea, ar trebui să fie

465
00:23:14,010 --> 00:23:16,070
urmarirea, apoi,
din ceea ce a fost înainte.

466
00:23:16,070 --> 00:23:22,690
Deci, înainte de a insera.

467
00:23:22,690 --> 00:23:25,120
Așa că am ratat, probabil, ceva
mai devreme.

468
00:23:25,120 --> 00:23:27,770
Probabil, avem nevoie să fie păstrarea
urmări ce se întâmplă.

469
00:23:27,770 --> 00:23:28,460
Dar vom ajunge acolo.

470
00:23:28,460 --> 00:23:30,160
Deci, ce valoare este mai mică?

471
00:23:30,160 --> 00:23:38,030

472
00:23:38,030 --> 00:23:39,710
Kurt, ce facem dacă
valoare este mai mică?

473
00:23:39,710 --> 00:23:43,000
>> Audiența: Apoi, doar continui
dacă nu e ultima.

474
00:23:43,000 --> 00:23:43,550
>> JASON Hirschorn: Imi place asta.

475
00:23:43,550 --> 00:23:44,800
Deci, du-te la urmatorul nod.

476
00:23:44,800 --> 00:23:47,410

477
00:23:47,410 --> 00:23:48,930
Doar dacă nu e ultima -

478
00:23:48,930 --> 00:23:51,100
suntem, probabil, de verificare pentru care
în termenii unei condiții.

479
00:23:51,100 --> 00:23:54,870
Dar da, nod următor.

480
00:23:54,870 --> 00:23:58,680
Și care este prea mic,
așa că ne vom muta aici.

481
00:23:58,680 --> 00:24:02,030
Dar, în cazul în care -

482
00:24:02,030 --> 00:24:03,280
se poate vedea toată lumea acest lucru?

483
00:24:03,280 --> 00:24:07,230

484
00:24:07,230 --> 00:24:11,610
Dacă suntem egali, ce facem?

485
00:24:11,610 --> 00:24:15,740
În cazul în care valoarea încercăm să introducă
este egală cu valoarea acestui nod lui?

486
00:24:15,740 --> 00:24:16,320
Da?

487
00:24:16,320 --> 00:24:18,400
>> Audiența: [inaudibil].

488
00:24:18,400 --> 00:24:18,850
>> JASON Hirschorn: Da.

489
00:24:18,850 --> 00:24:19,290
Având în vedere acest lucru -

490
00:24:19,290 --> 00:24:20,090
Marcus are dreptate.

491
00:24:20,090 --> 00:24:21,330
Am fi putut face, poate,
ceva diferit.

492
00:24:21,330 --> 00:24:25,360
Dar având în vedere că ne-am creat-o, aici
ar trebui să ne elibereze și apoi să se întoarcă.

493
00:24:25,360 --> 00:24:26,774
Oh boy.

494
00:24:26,774 --> 00:24:30,080
E mai bine?

495
00:24:30,080 --> 00:24:31,850
Cum e asta?

496
00:24:31,850 --> 00:24:33,100
OK.

497
00:24:33,100 --> 00:24:35,360

498
00:24:35,360 --> 00:24:37,640
Liber și apoi ce facem noi
reveni, [imperceptibil]?

499
00:24:37,640 --> 00:24:41,330

500
00:24:41,330 --> 00:24:44,110
OK.

501
00:24:44,110 --> 00:24:45,360
Ne lipsește ceva?

502
00:24:45,360 --> 00:24:53,500

503
00:24:53,500 --> 00:24:59,650
Deci, unde ne-am ține evidența
din nodul anterior?

504
00:24:59,650 --> 00:25:02,370
>> Audiența: Cred că ar merge
după ce a crea un nou nod.

505
00:25:02,370 --> 00:25:02,600
>> JASON Hirschorn: OK.

506
00:25:02,600 --> 00:25:03,940
Deci, la început vom probabil -

507
00:25:03,940 --> 00:25:07,175
Da, putem crea un pointer la un nou
nod, ca un pointer nod anterior și

508
00:25:07,175 --> 00:25:09,600
un pointer curent nod.

509
00:25:09,600 --> 00:25:12,640
Deci, haideți să introduceți asta aici.

510
00:25:12,640 --> 00:25:15,610

511
00:25:15,610 --> 00:25:26,900
Crea curente și anterioare
indicii de noduri.

512
00:25:26,900 --> 00:25:28,955
Dar atunci când ne adapta aceste indicii?

513
00:25:28,955 --> 00:25:30,205
În cazul în care vom face ca în codul?

514
00:25:30,205 --> 00:25:33,830

515
00:25:33,830 --> 00:25:34,160
Jeff?

516
00:25:34,160 --> 00:25:35,170
>> Audiența: - condițiile de valoare?

517
00:25:35,170 --> 00:25:36,420
>> JASON Hirschorn: Care
unul în special?

518
00:25:36,420 --> 00:25:39,862

519
00:25:39,862 --> 00:25:40,720
>> Audiența: Sunt doar confuz.

520
00:25:40,720 --> 00:25:44,200
Dacă valoarea este mai mare decât acest nod,
nu asta înseamnă că vrei să mergi

521
00:25:44,200 --> 00:25:45,320
la nodul următor?

522
00:25:45,320 --> 00:25:49,515
>> JASON Hirschhorn: Deci, în cazul în care valoarea noastră este
mai mare decât valoarea acestui nod.

523
00:25:49,515 --> 00:25:52,130
>> Publicul: Da, atunci ai vrea să
merge mai departe în jos linia, corect?

524
00:25:52,130 --> 00:25:52,590
>> JASON Hirschhorn: Corect.

525
00:25:52,590 --> 00:25:53,840
Așa că nu-l introduceți aici.

526
00:25:53,840 --> 00:25:58,430

527
00:25:58,430 --> 00:26:03,240
Dacă valoarea este mai mică decât acest nod, apoi
mergem la nodul următor - sau atunci

528
00:26:03,240 --> 00:26:03,835
introduce înainte.

529
00:26:03,835 --> 00:26:05,966
>> Audiența: Stai, care este aceasta
nod și care este valoarea?

530
00:26:05,966 --> 00:26:08,510

531
00:26:08,510 --> 00:26:09,280
>> JASON Hirschhorn: Bună întrebare.

532
00:26:09,280 --> 00:26:13,260
Valoarea pe această definiție funcție
este ceea ce suntem dat.

533
00:26:13,260 --> 00:26:16,910
Deci, valoarea este numărul suntem dat.

534
00:26:16,910 --> 00:26:21,120
Deci, dacă valoarea este mai mică decât aceasta
nod, avem nevoie de timp pentru a insera.

535
00:26:21,120 --> 00:26:24,575
Dacă valoarea este mai mare decât acest nod,
mergem la nodul următor.

536
00:26:24,575 --> 00:26:26,790
Și înapoi la întrebarea inițială,
totuși, în cazul în care -

537
00:26:26,790 --> 00:26:29,060
>> Audiența: Dacă valoarea este mai mare
decât acest nod.

538
00:26:29,060 --> 00:26:30,310
>> JASON Hirschhorn: Și așa
ce facem aici?

539
00:26:30,310 --> 00:26:36,790

540
00:26:36,790 --> 00:26:38,160
Dulce.

541
00:26:38,160 --> 00:26:38,860
Că este corect.

542
00:26:38,860 --> 00:26:41,370
Sunt doar de gând să scrie
actualizare indicii.

543
00:26:41,370 --> 00:26:44,010
Dar, da, cu cel actual
v-ar actualiza la

544
00:26:44,010 --> 00:26:46,080
punct la următoarea.

545
00:26:46,080 --> 00:26:47,330
Orice altceva ne lipsește?

546
00:26:47,330 --> 00:26:52,710

547
00:26:52,710 --> 00:26:54,940
Așa că am de gând să tastați acest
cod în gedit.

548
00:26:54,940 --> 00:26:58,375
Și în timp ce eu fac acest lucru, puteți avea un
cuplu mai multe minute pentru a lucra la codificare

549
00:26:58,375 --> 00:28:19,240
acest lucru în C.

550
00:28:19,240 --> 00:28:20,940
>> Așa că am de intrare pseudocod.

551
00:28:20,940 --> 00:28:22,940
O notă rapidă înainte de a începe.

552
00:28:22,940 --> 00:28:25,560
Noi nu poate fi în măsură să complet
termina acest lucru în toate

553
00:28:25,560 --> 00:28:27,300
trei dintre aceste funcții.

554
00:28:27,300 --> 00:28:30,630
Există soluții corecte pentru a le
că voi e-mail de la voi

555
00:28:30,630 --> 00:28:33,730
după secțiune, și se va
fi postate pe CS50.net.

556
00:28:33,730 --> 00:28:35,640
Așa că nu vă încurajez să
du-te uita-te la secțiunile.

557
00:28:35,640 --> 00:28:40,550
Am să vă încurajez să încercați aceste pe dvs.
proprii, iar apoi utilizați practica

558
00:28:40,550 --> 00:28:41,760
Probleme pentru a verifica răspunsurile dumneavoastră.

559
00:28:41,760 --> 00:28:47,070
Acestea toate au fost concepute pentru a strâns
se referă la și să adere la ceea

560
00:28:47,070 --> 00:28:48,400
ce trebuie sa faci pe platourile de filmare problemă.

561
00:28:48,400 --> 00:28:53,820
Deci, eu vă încurajez să practice acest
pe cont propriu și apoi utilizați codul de

562
00:28:53,820 --> 00:28:54,660
verifica răspunsurile dumneavoastră.

563
00:28:54,660 --> 00:28:57,060
Pentru că eu nu vreau să se mute la hash
tabele la un moment dat în secțiunea.

564
00:28:57,060 --> 00:28:58,150
Așa că s-ar putea să nu trece prin toate.

565
00:28:58,150 --> 00:28:59,960
Dar noi vom face la fel de mult putem acum.

566
00:28:59,960 --> 00:29:00,370
>> OK.

567
00:29:00,370 --> 00:29:01,960
Să începem.

568
00:29:01,960 --> 00:29:04,770
Asam, cum putem crea un nou nod?

569
00:29:04,770 --> 00:29:06,810
>> Audiența: Tu struct *.

570
00:29:06,810 --> 00:29:09,640
>> JASON Hirschhorn: Deci, ne-am
au ca aici.

571
00:29:09,640 --> 00:29:10,040
Oh, îmi pare rău.

572
00:29:10,040 --> 00:29:13,530
Ce spuneai struct *.

573
00:29:13,530 --> 00:29:17,260
>> Audiența: Și apoi [? fel?]
nod sau c nod.

574
00:29:17,260 --> 00:29:17,780
>> JASON Hirschhorn: OK.

575
00:29:17,780 --> 00:29:19,740
Am de gând să-l numesc new_node
astfel încât să putem sta consistent.

576
00:29:19,740 --> 00:29:22,646

577
00:29:22,646 --> 00:29:33,180
>> Audiența: Și doriți să setați ca
la cap, primul nod.

578
00:29:33,180 --> 00:29:33,580
>> JASON Hirschhorn: OK.

579
00:29:33,580 --> 00:29:37,290
Deci, acum acest lucru indică spre - astfel încât acest
nu a creat un nou nod încă.

580
00:29:37,290 --> 00:29:41,380
Acest lucru este pur și simplu indică spre
primul nod în listă.

581
00:29:41,380 --> 00:29:42,630
Cum pot crea un nou nod?

582
00:29:42,630 --> 00:29:45,490

583
00:29:45,490 --> 00:29:48,070
Dacă am nevoie de spațiu pentru a crea un nou nod.

584
00:29:48,070 --> 00:29:49,230
Malloc.

585
00:29:49,230 --> 00:29:51,710
Și cât de mare?

586
00:29:51,710 --> 00:30:00,390
>> Audiența: Dimensiunea struct.

587
00:30:00,390 --> 00:30:01,150
>> JASON Hirschhorn:
mărimea struct.

588
00:30:01,150 --> 00:30:02,400
Și ceea ce se numește struct?

589
00:30:02,400 --> 00:30:09,670

590
00:30:09,670 --> 00:30:09,840
>> Audiența: Nod?

591
00:30:09,840 --> 00:30:11,640
>> JASON Hirschhorn: Nod.

592
00:30:11,640 --> 00:30:17,640
Deci, malloc (sizeof (nod));
ne dă spațiu.

593
00:30:17,640 --> 00:30:19,740
Și este această linie -

594
00:30:19,740 --> 00:30:21,740
un lucru este incorect pe această linie.

595
00:30:21,740 --> 00:30:24,430
New_node este un pointer la o struct?

596
00:30:24,430 --> 00:30:25,650
Acesta este un nume generic.

597
00:30:25,650 --> 00:30:26,520
Ce este aceasta -

598
00:30:26,520 --> 00:30:27,450
nod, exact.

599
00:30:27,450 --> 00:30:29,340
Este un nod *.

600
00:30:29,340 --> 00:30:33,010
Și ce facem imediat după
noi malloc ceva, Asan?

601
00:30:33,010 --> 00:30:34,476
Care e primul lucru pe care îl facem?

602
00:30:34,476 --> 00:30:38,850

603
00:30:38,850 --> 00:30:40,320
Ce se întâmplă dacă nu funcționează?

604
00:30:40,320 --> 00:30:42,430
>> Audiența: Oh, verificați dacă
indică nodul?

605
00:30:42,430 --> 00:30:43,310
>> JASON Hirschhorn: Exact.

606
00:30:43,310 --> 00:30:46,750
Deci, dacă new_node egal la egal la egal
null, ce facem?

607
00:30:46,750 --> 00:30:51,650

608
00:30:51,650 --> 00:30:54,820
Aceasta returnează un bool, această funcție.

609
00:30:54,820 --> 00:30:57,760
Exact.

610
00:30:57,760 --> 00:30:58,450
Arata bine.

611
00:30:58,450 --> 00:30:59,680
Ceva pentru a adăuga acolo?

612
00:30:59,680 --> 00:31:00,670
Vom adăuga lucruri la sfârșitul anului.

613
00:31:00,670 --> 00:31:03,160
Dar că până în prezent arată bine.

614
00:31:03,160 --> 00:31:06,170
Crea indicii curente și anterioare.

615
00:31:06,170 --> 00:31:08,650
Michael, cum fac asta?

616
00:31:08,650 --> 00:31:12,810
>> Audiența: Tu ar trebui
pentru a face un nod *.

617
00:31:12,810 --> 00:31:21,800

618
00:31:21,800 --> 00:31:25,502
Ar trebui să nu o facă
pentru new_node dar pentru

619
00:31:25,502 --> 00:31:26,905
noduri avem deja.

620
00:31:26,905 --> 00:31:27,230
>> JASON Hirschhorn: OK.

621
00:31:27,230 --> 00:31:29,255
Deci, nodul curent suntem.

622
00:31:29,255 --> 00:31:30,505
Voi suna ca pac.

623
00:31:30,505 --> 00:31:39,650

624
00:31:39,650 --> 00:31:39,770
Bine.

625
00:31:39,770 --> 00:31:41,620
Ne-am decis că doriți să păstrați
două pentru că avem nevoie să știm

626
00:31:41,620 --> 00:31:42,870
ceea ce este în fața sa.

627
00:31:42,870 --> 00:31:45,770

628
00:31:45,770 --> 00:31:47,020
Ce primesc inițializat la?

629
00:31:47,020 --> 00:31:49,874

630
00:31:49,874 --> 00:31:54,180
>> Audiența: Valoarea lor în lista noastră.

631
00:31:54,180 --> 00:31:58,090
>> JASON Hirschhorn: Deci, ce este
primul lucru pe lista noastră?

632
00:31:58,090 --> 00:32:04,050
Sau cum știm unde
începând din lista noastră este?

633
00:32:04,050 --> 00:32:08,015
>> Audiența: nu este ea a trecut
în funcție?

634
00:32:08,015 --> 00:32:08,466
>> JASON Hirschhorn: Corect.

635
00:32:08,466 --> 00:32:09,716
Acesta a fost adoptată în chiar aici.

636
00:32:09,716 --> 00:32:15,910

637
00:32:15,910 --> 00:32:18,980
Deci, dacă este trecut în funcție,
începe a listei, ceea ce ar trebui să ne

638
00:32:18,980 --> 00:32:21,270
setat curent egal cu?

639
00:32:21,270 --> 00:32:22,110
>> Audiența: List.

640
00:32:22,110 --> 00:32:22,900
>> JASON Hirschhorn: List.

641
00:32:22,900 --> 00:32:24,090
Asta-i exact corect.

642
00:32:24,090 --> 00:32:26,290
Acum are adresa
începutul listei noastre.

643
00:32:26,290 --> 00:32:28,450
Și ce despre anterior?

644
00:32:28,450 --> 00:32:31,920
>> Audiența: Lista minus unul?

645
00:32:31,920 --> 00:32:32,690
>> JASON Hirschhorn: Nu
nimic înainte de a fi.

646
00:32:32,690 --> 00:32:34,580
Deci, ce putem face pentru a semnifica nimic?

647
00:32:34,580 --> 00:32:35,050
>> Audiența: Null.

648
00:32:35,050 --> 00:32:35,450
>> JASON Hirschhorn: Da.

649
00:32:35,450 --> 00:32:37,950
Pare a fi o idee bună.

650
00:32:37,950 --> 00:32:38,360
Perfect.

651
00:32:38,360 --> 00:32:39,630
Mulțumesc.

652
00:32:39,630 --> 00:32:42,850
Du-te prin lista.

653
00:32:42,850 --> 00:32:45,490
Constantin, cât timp vom
pentru a merge prin lista?

654
00:32:45,490 --> 00:32:49,010
>> Audiența: Până când vom ajunge la zero.

655
00:32:49,010 --> 00:32:49,390
>> JASON Hirschhorn: OK.

656
00:32:49,390 --> 00:32:50,430
Deci, dacă, în timp ce, pentru bucla.

657
00:32:50,430 --> 00:32:52,200
Ce facem?

658
00:32:52,200 --> 00:32:53,320
>> Audiența: Poate o pentru buclă?

659
00:32:53,320 --> 00:32:53,910
>> JASON Hirschhorn: Să facem o pentru buclă.

660
00:32:53,910 --> 00:32:55,870
OK.

661
00:32:55,870 --> 00:33:02,465
>> Audiența: Și noi spunem pentru -

662
00:33:02,465 --> 00:33:09,764

663
00:33:09,764 --> 00:33:13,390
până când indicatorul de curent
nu este egal cu zero.

664
00:33:13,390 --> 00:33:19,160
>> JASON Hirschhorn: Deci, dacă știm
condiție, cum putem scrie o buclă

665
00:33:19,160 --> 00:33:21,740
bazat pe această condiție.

666
00:33:21,740 --> 00:33:24,380
Ce fel de buclă ar trebui să le folosim?

667
00:33:24,380 --> 00:33:25,260
>> Audiența: în timp ce.

668
00:33:25,260 --> 00:33:25,590
>> JASON Hirschhorn: Da.

669
00:33:25,590 --> 00:33:27,130
Care face mai mult sens pe baza
off de ceea ce ai spus.

670
00:33:27,130 --> 00:33:29,430
Dacă vrem doar să merg în noi că ar fi
doar știu că ceva, ar face

671
00:33:29,430 --> 00:33:31,680
sens pentru a face o buclă în timp.

672
00:33:31,680 --> 00:33:39,880
În timp ce actuala nu este egal cu zero,
dacă valoarea este mai mică decât acest nod.

673
00:33:39,880 --> 00:33:41,650
Akshar, dă-mi această linie.

674
00:33:41,650 --> 00:33:48,810

675
00:33:48,810 --> 00:33:56,955
>> Audiența: Dacă curent-> n
n mai putin de valoare.

676
00:33:56,955 --> 00:34:00,170

677
00:34:00,170 --> 00:34:03,260
Sau invers asta.

678
00:34:03,260 --> 00:34:06,140
Comutator care suport.

679
00:34:06,140 --> 00:34:06,620
>> JASON Hirschhorn: Îmi pare rău.

680
00:34:06,620 --> 00:34:08,760
>> Audiența: Schimbați suportul.

681
00:34:08,760 --> 00:34:10,914
>> JASON Hirschhorn: Deci, dacă este
mai mare decât valoarea.

682
00:34:10,914 --> 00:34:18,719

683
00:34:18,719 --> 00:34:22,120
Pentru că e confuz cu
comentariul de mai sus, am de gând să fac asta.

684
00:34:22,120 --> 00:34:22,480
Dar da.

685
00:34:22,480 --> 00:34:25,125
În cazul în care valoarea noastră este mai mică decât aceasta
nod, ce facem?

686
00:34:25,125 --> 00:34:25,540
Oh.

687
00:34:25,540 --> 00:34:26,710
Îl am chiar aici.

688
00:34:26,710 --> 00:34:27,960
Introduce înainte.

689
00:34:27,960 --> 00:34:32,080

690
00:34:32,080 --> 00:34:32,370
OK.

691
00:34:32,370 --> 00:34:33,933
Cum facem asta?

692
00:34:33,933 --> 00:34:34,900
>> Audiența: Este încă mă?

693
00:34:34,900 --> 00:34:36,150
>> JASON Hirschhorn: Da.

694
00:34:36,150 --> 00:34:38,520

695
00:34:38,520 --> 00:34:39,770
>> Audiența: Ai -

696
00:34:39,770 --> 00:34:42,909

697
00:34:42,909 --> 00:34:44,159
new_node-> următor.

698
00:34:44,159 --> 00:34:46,770

699
00:34:46,770 --> 00:34:50,163
>> JASON Hirschhorn: Deci, ce e
care merge la egal?

700
00:34:50,163 --> 00:34:52,070
>> Audiența: Va curent egal.

701
00:34:52,070 --> 00:34:53,889
>> JASON Hirschhorn: Exact.

702
00:34:53,889 --> 00:34:55,730
Și astfel de altă parte -

703
00:34:55,730 --> 00:34:56,730
ce altceva mai avem nevoie pentru a actualiza?

704
00:34:56,730 --> 00:34:59,982
>> Audiența: Verificați dacă trecutul este egal cu zero.

705
00:34:59,982 --> 00:35:01,870
>> JASON Hirschhorn: Dacă prev -

706
00:35:01,870 --> 00:35:03,730
așa că, dacă prev este egal cu zero.

707
00:35:03,730 --> 00:35:05,990
>> Audienta: Asta înseamnă că va
pentru a deveni cap.

708
00:35:05,990 --> 00:35:06,780
>> JASON Hirschhorn: Asta înseamnă că
acesta a devenit cap.

709
00:35:06,780 --> 00:35:07,620
Deci, atunci ce facem?

710
00:35:07,620 --> 00:35:12,510
>> Audiența: Noi facem cap egal new_node.

711
00:35:12,510 --> 00:35:16,690
>> JASON Hirschhorn: Cap
este egal cu new_node.

712
00:35:16,690 --> 00:35:20,540
Și de ce cap aici, nu lista?

713
00:35:20,540 --> 00:35:24,940
>> Audiența: Deoarece cap este un nivel global
variabilă, care este locul de pornire.

714
00:35:24,940 --> 00:35:26,190
>> JASON Hirschhorn: dulce.

715
00:35:26,190 --> 00:35:33,750

716
00:35:33,750 --> 00:35:34,170
OK.

717
00:35:34,170 --> 00:35:36,150
Și -

718
00:35:36,150 --> 00:35:53,796
>> Audiența: Atunci nu mai prev->
este egal cu următoarea new_node.

719
00:35:53,796 --> 00:35:55,080
Și apoi vă întoarceți adevărat.

720
00:35:55,080 --> 00:35:59,560

721
00:35:59,560 --> 00:36:02,700
>> JASON Hirschhorn: Unde
ne-am stabilit la sfârșitul new_node?

722
00:36:02,700 --> 00:36:04,850
>> Audiența: Aș -

723
00:36:04,850 --> 00:36:06,180
Am stabilit că la început.

724
00:36:06,180 --> 00:36:07,430
>> JASON Hirschhorn: Deci, ce linie?

725
00:36:07,430 --> 00:36:10,000

726
00:36:10,000 --> 00:36:12,598
>> Audiența: După if
a verifica dacă acesta este cunoscut.

727
00:36:12,598 --> 00:36:13,057
>> JASON Hirschhorn: Chiar aici?

728
00:36:13,057 --> 00:36:18,335
>> Audiența: Aș face new_node-> n
este egal cu valoarea.

729
00:36:18,335 --> 00:36:19,585
>> JASON Hirschhorn: Sună bine.

730
00:36:19,585 --> 00:36:21,740

731
00:36:21,740 --> 00:36:25,090
Probabil are sens - nu avem
Trebuie să știu ce lista suntem pe

732
00:36:25,090 --> 00:36:26,280
pentru că avem de-a face doar
cu o singură listă.

733
00:36:26,280 --> 00:36:29,560
Deci, o declarație funcție mai bun pentru
acest lucru este doar pentru a scăpa de această

734
00:36:29,560 --> 00:36:34,360
în întregime și doar introduceți
o valoare în cap.

735
00:36:34,360 --> 00:36:35,930
Nici măcar nu trebuie să știe
ceea ce Lista suntem inch

736
00:36:35,930 --> 00:36:39,140
Dar voi păstra pentru acum și
apoi schimba la actualizarea

737
00:36:39,140 --> 00:36:42,590
slide-uri și cod.

738
00:36:42,590 --> 00:36:44,980
Astfel că arată bine pentru acum.

739
00:36:44,980 --> 00:36:46,560
Dacă valoare - care pot face această linie?

740
00:36:46,560 --> 00:36:47,810
În cazul în care -

741
00:36:47,810 --> 00:36:52,240

742
00:36:52,240 --> 00:36:53,840
ce facem aici, Noah.

743
00:36:53,840 --> 00:36:57,890

744
00:36:57,890 --> 00:37:07,100
>> Audiența: Dacă valoarea este mai mare
decât pac-> n -

745
00:37:07,100 --> 00:37:16,830

746
00:37:16,830 --> 00:37:18,240
>> JASON Hirschhorn: Cum
mergem la nodul următor?

747
00:37:18,240 --> 00:37:27,760

748
00:37:27,760 --> 00:37:30,530
>> Audiența: Curr-> n este
egal la new_node.

749
00:37:30,530 --> 00:37:37,630

750
00:37:37,630 --> 00:37:39,195
>> JASON Hirschhorn: Deci, n este
ce face parte din struct?

751
00:37:39,195 --> 00:37:43,065

752
00:37:43,065 --> 00:37:46,020
Întreg.

753
00:37:46,020 --> 00:37:50,420
Și new_node este un pointer la un nod.

754
00:37:50,420 --> 00:37:51,880
Deci, ce parte a curr ar trebui să actualizeze?

755
00:37:51,880 --> 00:38:03,900

756
00:38:03,900 --> 00:38:05,400
Dacă nu n, atunci ceea ce este pe de altă parte?

757
00:38:05,400 --> 00:38:21,680

758
00:38:21,680 --> 00:38:22,810
Noah, ceea ce este pe de altă parte.

759
00:38:22,810 --> 00:38:23,570
>> Audiența: Oh, următorul.

760
00:38:23,570 --> 00:38:25,645
>> JASON Hirschhorn: Apoi, exact.

761
00:38:25,645 --> 00:38:26,410
Exact.

762
00:38:26,410 --> 00:38:28,770
Următorul este cel potrivit.

763
00:38:28,770 --> 00:38:31,540
Și ce altceva mai avem nevoie
pentru a actualiza, Noah?

764
00:38:31,540 --> 00:38:32,840
>> Audiența: The indicii.

765
00:38:32,840 --> 00:38:34,840
>> JASON Hirschhorn: Deci,
am actualizat curent.

766
00:38:34,840 --> 00:38:36,090
>> Audiența: Anterior-> următor.

767
00:38:36,090 --> 00:38:48,160

768
00:38:48,160 --> 00:38:49,410
>> JASON Hirschhorn: Da.

769
00:38:49,410 --> 00:38:57,465

770
00:38:57,465 --> 00:38:58,370
OK, ne vom opri.

771
00:38:58,370 --> 00:39:02,200
Cine ne poate ajuta aici?

772
00:39:02,200 --> 00:39:03,385
Manu, ceea ce ar trebui să facem?

773
00:39:03,385 --> 00:39:05,615
>> Audiența: Trebuie să setați
l egal cu-pac> următor.

774
00:39:05,615 --> 00:39:09,110

775
00:39:09,110 --> 00:39:11,630
Dar face acest lucru înainte de linia anterioară.

776
00:39:11,630 --> 00:39:12,880
>> JASON Hirschhorn: OK.

777
00:39:12,880 --> 00:39:16,590

778
00:39:16,590 --> 00:39:18,260
Altceva?

779
00:39:18,260 --> 00:39:19,170
Akshar.

780
00:39:19,170 --> 00:39:22,680
>> Audiența: Eu nu cred că ești
menirea de a schimba-pac> următor.

781
00:39:22,680 --> 00:39:29,270
Cred că ai vrut să faci egal Curr
pac-> de lângă pentru a merge la nodul următor.

782
00:39:29,270 --> 00:39:30,500
>> JASON Hirschhorn: Îmi pare rău, în cazul în care?

783
00:39:30,500 --> 00:39:32,680
Pe ce linie?

784
00:39:32,680 --> 00:39:33,420
Această linie?

785
00:39:33,420 --> 00:39:33,750
>> Audienta: Da.

786
00:39:33,750 --> 00:39:35,745
Face pac egal pac-> următor.

787
00:39:35,745 --> 00:39:39,690

788
00:39:39,690 --> 00:39:43,360
>> JASON Hirschhorn: Deci asta e corect
deoarece este un curent

789
00:39:43,360 --> 00:39:45,220
pointer la un nod.

790
00:39:45,220 --> 00:39:48,550
Și vrem să punct la altul
nod de ceea ce se obține în prezent

791
00:39:48,550 --> 00:39:49,930
a subliniat.

792
00:39:49,930 --> 00:39:54,410
Curr sine are un viitor.

793
00:39:54,410 --> 00:39:58,620
Dar dacă ar fi să actualizeze curr.next, ne-am
ar fi actualizarea nota real

794
00:39:58,620 --> 00:40:01,430
în sine, nu unde această
pointer a fost îndreptat.

795
00:40:01,430 --> 00:40:02,680
Ce zici de această linie, totuși.

796
00:40:02,680 --> 00:40:05,160

797
00:40:05,160 --> 00:40:07,330
Avi?

798
00:40:07,330 --> 00:40:09,590
>> Audiența: Anterior-> egal următor pac.

799
00:40:09,590 --> 00:40:12,500

800
00:40:12,500 --> 00:40:19,440
>> JASON Hirschhorn: Deci, din nou, în cazul în care prev este un
pointer la un nod, prev-> următor este

801
00:40:19,440 --> 00:40:23,020
pointer real în nodul.

802
00:40:23,020 --> 00:40:27,190
Deci, acest lucru ar fi actualizarea o
pointer la un nod la pac.

803
00:40:27,190 --> 00:40:28,570
Noi nu vrem să actualizați
un pointer la un nod.

804
00:40:28,570 --> 00:40:30,570
Vrem să actualizeze anterior.

805
00:40:30,570 --> 00:40:31,850
Deci, cum facem asta?

806
00:40:31,850 --> 00:40:34,250
>> Audiența: Ar fi doar prev.

807
00:40:34,250 --> 00:40:34,565
>> JASON Hirschhorn: Corect.

808
00:40:34,565 --> 00:40:35,560
Anterior este un pointer la un nod.

809
00:40:35,560 --> 00:40:38,750
Acum suntem o schimbare la un
nou pointer la un nod.

810
00:40:38,750 --> 00:40:40,830
OK Să ne muta în jos.

811
00:40:40,830 --> 00:40:41,940
În fine, această ultimă condiție.

812
00:40:41,940 --> 00:40:44,896
Jeff, ce facem aici?

813
00:40:44,896 --> 00:40:47,515
>> Audiența: Dacă valoare este
egal cu pac-> n.

814
00:40:47,515 --> 00:40:51,030

815
00:40:51,030 --> 00:40:51,300
>> JASON Hirschhorn: Îmi pare rău.

816
00:40:51,300 --> 00:40:52,372
Dumnezeule.

817
00:40:52,372 --> 00:40:54,330
Ce?

818
00:40:54,330 --> 00:40:55,580
Valoarea == pac-> n.

819
00:40:55,580 --> 00:41:01,050

820
00:41:01,050 --> 00:41:02,300
Ce facem?

821
00:41:02,300 --> 00:41:04,760

822
00:41:04,760 --> 00:41:10,950
>> Audiența: Ai liber new_node nostru,
și apoi te-ai întoarce false.

823
00:41:10,950 --> 00:41:21,410

824
00:41:21,410 --> 00:41:23,460
>> JASON Hirschhorn: Aceasta este ceea ce
am scris până acum.

825
00:41:23,460 --> 00:41:25,710
Are cineva ceva
pentru a adăuga înainte de a face?

826
00:41:25,710 --> 00:41:35,460

827
00:41:35,460 --> 00:41:35,710
OK.

828
00:41:35,710 --> 00:41:36,960
Să încercăm.

829
00:41:36,960 --> 00:41:44,180

830
00:41:44,180 --> 00:41:46,110
De control poate ajunge la sfârșitul
de o funcție non-gol.

831
00:41:46,110 --> 00:41:48,310
Avi, ce se întâmplă?

832
00:41:48,310 --> 00:41:51,380
>> Audiența:-ar trebui să pună retur
adevărat în afara buclei în timp ce?

833
00:41:51,380 --> 00:41:53,900

834
00:41:53,900 --> 00:41:54,400
>> JASON Hirschhorn: Nu știu.

835
00:41:54,400 --> 00:41:54,780
Nu vrei să?

836
00:41:54,780 --> 00:41:55,520
>> Audiența: Nu contează.

837
00:41:55,520 --> 00:41:56,350
Nu.

838
00:41:56,350 --> 00:41:57,180
>> JASON Hirschhorn: Akshar?

839
00:41:57,180 --> 00:41:59,460
>> Audiența: Cred că ai vrut să
pune false întoarcere la sfârșitul

840
00:41:59,460 --> 00:42:02,230
din bucla în timp ce.

841
00:42:02,230 --> 00:42:03,270
>> JASON Hirschhorn: Deci, în cazul în care
vrei să mergi?

842
00:42:03,270 --> 00:42:05,270
>> Audiența: La fel ca în afara buclei în timp.

843
00:42:05,270 --> 00:42:08,800
Deci, dacă ieși din bucla în timp ce aceea că mijloacele de
că ați ajuns la sfârșitul și

844
00:42:08,800 --> 00:42:09,980
nimic nu sa întâmplat.

845
00:42:09,980 --> 00:42:10,410
>> JASON Hirschhorn: OK.

846
00:42:10,410 --> 00:42:12,340
Deci, ce facem aici?

847
00:42:12,340 --> 00:42:13,702
>> Audiența: Veți reveni false
acolo, de asemenea.

848
00:42:13,702 --> 00:42:15,040
>> JASON Hirschhorn: Oh, ne-am
o fac în ambele locuri?

849
00:42:15,040 --> 00:42:15,650
>> Audienta: Da.

850
00:42:15,650 --> 00:42:16,900
>> JASON Hirschhorn: OK.

851
00:42:16,900 --> 00:42:24,840

852
00:42:24,840 --> 00:42:26,160
Ar trebui să mergem?

853
00:42:26,160 --> 00:42:26,980
Dumnezeule.

854
00:42:26,980 --> 00:42:27,290
Îmi pare rău.

855
00:42:27,290 --> 00:42:28,480
Îmi cer scuze pentru ecran.

856
00:42:28,480 --> 00:42:30,530
Este un fel de speriat de noi.

857
00:42:30,530 --> 00:42:31,520
Asa ca alege o opțiune.

858
00:42:31,520 --> 00:42:35,260
Zero, pe codul, închide programul.

859
00:42:35,260 --> 00:42:36,700
Unul introduce ceva.

860
00:42:36,700 --> 00:42:37,990
Să introduce trei.

861
00:42:37,990 --> 00:42:42,900

862
00:42:42,900 --> 00:42:45,380
Inserția nu a avut succes.

863
00:42:45,380 --> 00:42:46,500
Am de gând să imprima.

864
00:42:46,500 --> 00:42:48,050
Nu am nimic.

865
00:42:48,050 --> 00:42:48,450
OK.

866
00:42:48,450 --> 00:42:50,250
Poate că a fost doar o întâmplare.

867
00:42:50,250 --> 00:42:52,810
Introduceți unul.

868
00:42:52,810 --> 00:42:55,770
Nu a avut succes.

869
00:42:55,770 --> 00:42:57,470
OK.

870
00:42:57,470 --> 00:43:02,400
Să fugi prin GDB foarte repede
pentru a verifica ce se întâmplă.

871
00:43:02,400 --> 00:43:06,055
>> Amintiți-vă gdb. / Numele dvs.
Programul ne ajunge în GDB.

872
00:43:06,055 --> 00:43:07,610
Este că o mulțime să se ocupe?

873
00:43:07,610 --> 00:43:08,560
Intermitent?

874
00:43:08,560 --> 00:43:10,400
Probabil.

875
00:43:10,400 --> 00:43:12,760
Închide ochii și să ia ceva profund
respiră dacă te plictisești

876
00:43:12,760 --> 00:43:13,580
de a privi la ea.

877
00:43:13,580 --> 00:43:14,200
Sunt în GDB.

878
00:43:14,200 --> 00:43:15,830
Care este primul lucru pe care îl fac în GDB?

879
00:43:15,830 --> 00:43:17,050
Trebuie să ne dăm seama
ceea ce se întâmplă aici.

880
00:43:17,050 --> 00:43:17,310
Să vedem.

881
00:43:17,310 --> 00:43:21,650
Avem șase minute pentru a cifră
ce se întâmplă.

882
00:43:21,650 --> 00:43:22,900
Break principal.

883
00:43:22,900 --> 00:43:25,950

884
00:43:25,950 --> 00:43:28,130
Și apoi ce fac?

885
00:43:28,130 --> 00:43:29,180
Carlos?

886
00:43:29,180 --> 00:43:31,060
Rula.

887
00:43:31,060 --> 00:43:32,250
OK.

888
00:43:32,250 --> 00:43:34,160
Să alegeți o opțiune.

889
00:43:34,160 --> 00:43:36,330
Și ce N face?

890
00:43:36,330 --> 00:43:38,480
Următor.

891
00:43:38,480 --> 00:43:38,950
Da.

892
00:43:38,950 --> 00:43:39,740
>> Audiența: Nu ai spus -

893
00:43:39,740 --> 00:43:45,230
nu ai spus că șeful, era
inițializat la zero la început.

894
00:43:45,230 --> 00:43:47,140
Dar am crezut că ai spus că a fost OK.

895
00:43:47,140 --> 00:43:50,040

896
00:43:50,040 --> 00:43:52,640
>> JASON Hirschhorn: Să mergem - să ne uităm
în GDB, și apoi ne vom întoarce.

897
00:43:52,640 --> 00:43:54,910
Dar se pare că aveți deja
câteva idei despre ceea ce se întâmplă.

898
00:43:54,910 --> 00:43:58,340
Așa că ne-o dorim pentru a introduce ceva.

899
00:43:58,340 --> 00:43:59,390
OK.

900
00:43:59,390 --> 00:44:00,150
Am introduce.

901
00:44:00,150 --> 00:44:00,770
Vă rugăm să introduceți un int.

902
00:44:00,770 --> 00:44:01,990
Vom introduce trei.

903
00:44:01,990 --> 00:44:03,000
Și atunci eu sunt pe această linie.

904
00:44:03,000 --> 00:44:07,030
Cum pot să merg încep de depanare
inserția funcție cunoscută?

905
00:44:07,030 --> 00:44:08,280
Dumnezeule.

906
00:44:08,280 --> 00:44:10,990

907
00:44:10,990 --> 00:44:12,240
Asta e mult.

908
00:44:12,240 --> 00:44:14,372

909
00:44:14,372 --> 00:44:16,445
Este că speriat o mulțime?

910
00:44:16,445 --> 00:44:19,696

911
00:44:19,696 --> 00:44:21,680
>> Audiența: Oh, ea a murit.

912
00:44:21,680 --> 00:44:22,930
>> JASON Hirschhorn: Eu doar
a scos-o afară.

913
00:44:22,930 --> 00:44:27,364

914
00:44:27,364 --> 00:44:28,310
OK.

915
00:44:28,310 --> 00:44:29,560
>> Audiența: Poate e
celălalt capăt al firului.

916
00:44:29,560 --> 00:44:37,000

917
00:44:37,000 --> 00:44:39,470
>> JASON Hirschhorn: Wow.

918
00:44:39,470 --> 00:44:42,330
Deci, linia de jos -

919
00:44:42,330 --> 00:44:43,470
Ce-ai spus?

920
00:44:43,470 --> 00:44:46,040
>> Audiența: I-am spus ironia de tehnic
dificultăți în această clasă.

921
00:44:46,040 --> 00:44:46,410
>> JASON Hirschhorn: Știu.

922
00:44:46,410 --> 00:44:48,660
Dacă doar am avut control asupra acea parte.

923
00:44:48,660 --> 00:44:49,910
[Inaudibil]

924
00:44:49,910 --> 00:44:54,430

925
00:44:54,430 --> 00:44:55,400
Asta sună grozav.

926
00:44:55,400 --> 00:44:58,680
De ce nu voi începe să gândesc despre
ceea ce am fi putut face rău,

927
00:44:58,680 --> 00:45:01,140
și vom fi din nou în 90 de secunde.

928
00:45:01,140 --> 00:46:18,160

929
00:46:18,160 --> 00:46:23,010
>> Avica, am de gând să vă întreb cum de a merge
insert_node interior pentru a depana.

930
00:46:23,010 --> 00:46:28,940

931
00:46:28,940 --> 00:46:31,460
Deci, acest lucru este în cazul în care am plecat de pe ultima.

932
00:46:31,460 --> 00:46:35,110
Cum pot să merg în interiorul insert_node, Avica,
pentru a examina ceea ce se întâmplă?

933
00:46:35,110 --> 00:46:36,360
Ce comanda GDB?

934
00:46:36,360 --> 00:46:41,050

935
00:46:41,050 --> 00:46:42,390
Break nu m-ar lua în interiorul.

936
00:46:42,390 --> 00:46:46,200

937
00:46:46,200 --> 00:46:47,130
Nu știu Marquise?

938
00:46:47,130 --> 00:46:48,240
>> Audiența: Ce?

939
00:46:48,240 --> 00:46:51,780
>> JASON Hirschhorn: Ce comanda GDB
Eu folosesc pentru a merge în această funcție?

940
00:46:51,780 --> 00:46:52,070
>> Audiența: Step?

941
00:46:52,070 --> 00:46:55,140
>> JASON Hirschhorn: Pasul prin
S. Asta mă duce în interior.

942
00:46:55,140 --> 00:46:55,476
OK.

943
00:46:55,476 --> 00:46:58,040
New_node mallocing spațiu.

944
00:46:58,040 --> 00:46:59,120
Că toate arata ca sa mergi.

945
00:46:59,120 --> 00:47:00,370
Să examinăm new_node.

946
00:47:00,370 --> 00:47:03,270

947
00:47:03,270 --> 00:47:05,410
, Am o anumită adresă de memorie.

948
00:47:05,410 --> 00:47:07,440
Să verificăm -

949
00:47:07,440 --> 00:47:08,500
care este tot corect.

950
00:47:08,500 --> 00:47:12,220
Deci, totul aici pare să
fi de lucru corect.

951
00:47:12,220 --> 00:47:14,530
>> Audienta: Care este diferența
între P și de afișare?

952
00:47:14,530 --> 00:47:16,160
>> JASON Hirschhorn: P standuri pentru imprimare.

953
00:47:16,160 --> 00:47:19,310
Și astfel încât să ceri ceea ce este
diferență între asta și asta?

954
00:47:19,310 --> 00:47:22,330
În acest caz, nimic.

955
00:47:22,330 --> 00:47:26,960
Dar, în general, există
unele diferențe.

956
00:47:26,960 --> 00:47:28,220
Și ar trebui să arate în manualul GDB.

957
00:47:28,220 --> 00:47:29,560
Dar, în acest caz, nimic.

958
00:47:29,560 --> 00:47:31,460
Avem tendința de a folosi de imprimare, deși, pentru că
noi nu trebuie să facem mult mai mult decât

959
00:47:31,460 --> 00:47:33,960
imprima o singură valoare.

960
00:47:33,960 --> 00:47:34,640
>> OK.

961
00:47:34,640 --> 00:47:40,300
Deci, suntem pe linia 80 din codul nostru,
stabilirea nod * pac egal la lista.

962
00:47:40,300 --> 00:47:42,500
Să ne imprima pac.

963
00:47:42,500 --> 00:47:45,260

964
00:47:45,260 --> 00:47:46,840
Acesta este egal cu lista.

965
00:47:46,840 --> 00:47:48,850
Dulce.

966
00:47:48,850 --> 00:47:49,340
Așteaptă.

967
00:47:49,340 --> 00:47:50,590
Acesta este egal cu ceva.

968
00:47:50,590 --> 00:47:53,680

969
00:47:53,680 --> 00:47:56,190
Asta nu mi se pare corect.

970
00:47:56,190 --> 00:47:56,840
Acolo mergem.

971
00:47:56,840 --> 00:47:59,470
E pentru că în GDB, drept, în cazul în care
este linia esti pe ea

972
00:47:59,470 --> 00:48:00,330
nu a executat încă.

973
00:48:00,330 --> 00:48:03,100
Deci, ai nevoie să tastați de fapt,
lângă executa linia

974
00:48:03,100 --> 00:48:05,230
înainte de a vedea rezultatele sale.

975
00:48:05,230 --> 00:48:06,680
Deci, aici suntem.

976
00:48:06,680 --> 00:48:09,490
Tocmai am executat această linie,
precedent este egal cu zero.

977
00:48:09,490 --> 00:48:13,590
Deci, din nou, dacă vom imprima anterior
nu vom vedea nimic ciudat.

978
00:48:13,590 --> 00:48:18,680
Dar dacă am executa de fapt că
linie, atunci vom vedea

979
00:48:18,680 --> 00:48:20,380
că acea linie a lucrat.

980
00:48:20,380 --> 00:48:21,060
>> Deci avem pac.

981
00:48:21,060 --> 00:48:23,180
Cei care sunt atât de bună.

982
00:48:23,180 --> 00:48:24,010
Corect?

983
00:48:24,010 --> 00:48:28,130
Acum suntem pe această linie aici.

984
00:48:28,130 --> 00:48:29,310
În timp ce pac nu este egal cu zero.

985
00:48:29,310 --> 00:48:31,110
Ei bine, ceea ce face pac egal?

986
00:48:31,110 --> 00:48:32,450
Tocmai am văzut-o a fost de nul.

987
00:48:32,450 --> 00:48:33,210
Am imprimat.

988
00:48:33,210 --> 00:48:35,110
O să-l imprimați din nou.

989
00:48:35,110 --> 00:48:36,720
Deci, este că, în timp ce buclă
va executa?

990
00:48:36,720 --> 00:48:37,270
>> Audiența: Nu.

991
00:48:37,270 --> 00:48:39,790
>> JASON Hirschhorn: Deci, când am scris că
linie, veți vedea am sărit tot drumul

992
00:48:39,790 --> 00:48:41,390
jos la partea de jos, intoarce false.

993
00:48:41,390 --> 00:48:44,520
Și apoi vom reveni false
și du-te înapoi la programul nostru și

994
00:48:44,520 --> 00:48:48,020
în cele din urmă a imprima, cum am văzut,
inserția nu a avut succes.

995
00:48:48,020 --> 00:48:51,010
Deci, cineva vreo idee cu privire la ceea ce
trebuie să facem pentru a remedia acest lucru?

996
00:48:51,010 --> 00:48:54,200

997
00:48:54,200 --> 00:48:57,570
Am de gând să aștept până când voi vedea
o pereche de mâini du-te în sus.

998
00:48:57,570 --> 00:48:58,830
Noi nu am executat acest lucru.

999
00:48:58,830 --> 00:49:01,660
Păstrați în minte, acesta a fost primul
lucru pe care îl făceam.

1000
00:49:01,660 --> 00:49:02,430
Eu nu am de gând să fac un cuplu.

1001
00:49:02,430 --> 00:49:03,670
Am de gând să fac câteva.

1002
00:49:03,670 --> 00:49:04,830
Pentru ca un cuplu inseamna doi.

1003
00:49:04,830 --> 00:49:07,620
Voi aștepta mai mult de două.

1004
00:49:07,620 --> 00:49:10,690
>> La prima introducere, pac,
în mod implicit este egal cu zero.

1005
00:49:10,690 --> 00:49:14,050
Și această buclă execută numai
dacă pac nu este nul.

1006
00:49:14,050 --> 00:49:18,740
Deci, cum pot rezolva aceasta?

1007
00:49:18,740 --> 00:49:19,990
Văd trei mâini.

1008
00:49:19,990 --> 00:49:28,490

1009
00:49:28,490 --> 00:49:29,780
Voi aștepta mai mult de trei.

1010
00:49:29,780 --> 00:49:33,460

1011
00:49:33,460 --> 00:49:35,940
Marcus, ce crezi?

1012
00:49:35,940 --> 00:49:37,730
>> Audiența: Ei bine, dacă aveți nevoie de ea pentru a
executa mai mult de o dată, tu doar

1013
00:49:37,730 --> 00:49:39,948
schimba-l la o buclă do-timp.

1014
00:49:39,948 --> 00:49:41,250
>> JASON Hirschhorn: OK.

1015
00:49:41,250 --> 00:49:44,240
Va ca rezolva problema noastră, deși?

1016
00:49:44,240 --> 00:49:47,750
>> Audiența: În acest caz, nu din cauza
faptul că lista este goală.

1017
00:49:47,750 --> 00:49:52,150
Deci, atunci, probabil, ai nevoie doar pentru a adăuga
o declarație că, dacă ieșirile bucla

1018
00:49:52,150 --> 00:49:55,312
atunci va trebui să fie la sfârșitul anului
lista, la care punct

1019
00:49:55,312 --> 00:49:56,562
doar se poate introduce.

1020
00:49:56,562 --> 00:49:58,920

1021
00:49:58,920 --> 00:49:59,680
>> JASON Hirschhorn: Imi place asta.

1022
00:49:59,680 --> 00:50:00,500
Asta are sens.

1023
00:50:00,500 --> 00:50:03,390
Dacă bucla iese -

1024
00:50:03,390 --> 00:50:04,800
deoarece acesta va returna false aici.

1025
00:50:04,800 --> 00:50:08,220
Deci, dacă ieșirile bucla, atunci suntem la
la sfârșitul listei, sau poate

1026
00:50:08,220 --> 00:50:10,690
începe o listă în cazul în care nu există nimic în
aceasta, care este la fel ca la sfârșitul.

1027
00:50:10,690 --> 00:50:12,770
Deci, acum ne-o dorim pentru a insera
ceva aici.

1028
00:50:12,770 --> 00:50:17,380
Deci, cum poate acest cod arata, Marcus?

1029
00:50:17,380 --> 00:50:21,600
>> Audiența: Dacă ai deja nodul
malloced, ai putea spune doar

1030
00:50:21,600 --> 00:50:25,400
new_node-> următor este egal cu zero, deoarece
trebuie să fie la sfârșit.

1031
00:50:25,400 --> 00:50:27,510
Sau-new_node> următor este egal cu zero.

1032
00:50:27,510 --> 00:50:27,765
>> JASON Hirschhorn: OK.

1033
00:50:27,765 --> 00:50:28,190
Scuze.

1034
00:50:28,190 --> 00:50:35,760
New_node-> următor este egal cu zero
pentru că suntem la sfârșitul anului.

1035
00:50:35,760 --> 00:50:36,460
Asta nu-l pune inch

1036
00:50:36,460 --> 00:50:37,710
Cum ne-am pus-o în listă?

1037
00:50:37,710 --> 00:50:46,130

1038
00:50:46,130 --> 00:50:46,460
Corect.

1039
00:50:46,460 --> 00:50:47,750
Asta e doar o setare egal.

1040
00:50:47,750 --> 00:50:50,940
Nu cum suntem de fapt
pune-l in lista?

1041
00:50:50,940 --> 00:50:54,170
Ceea ce indică spre
la sfârșitul listei?

1042
00:50:54,170 --> 00:50:56,090
>> Audiența: Cap.

1043
00:50:56,090 --> 00:50:57,566
>> JASON Hirschhorn: Îmi pare rău?

1044
00:50:57,566 --> 00:50:59,440
>> Audiența: Head este îndreptat
la sfârșitul listei.

1045
00:50:59,440 --> 00:51:01,480
>> JASON Hirschhorn: Dacă nu e nimic în
lista, capul este îndreptat la

1046
00:51:01,480 --> 00:51:04,170
la sfârșitul listei.

1047
00:51:04,170 --> 00:51:06,920
Astfel că va lucra pentru
în primul rând de inserare.

1048
00:51:06,920 --> 00:51:09,810
Ce zici dacă există un cuplu
lucruri din lista?

1049
00:51:09,810 --> 00:51:12,470
Mult nu vrem să setați
cap egal cu new_node.

1050
00:51:12,470 --> 00:51:13,790
Ce vrem să facem acolo?

1051
00:51:13,790 --> 00:51:15,610
Da?

1052
00:51:15,610 --> 00:51:16,860
Probabil precedent.

1053
00:51:16,860 --> 00:51:23,560

1054
00:51:23,560 --> 00:51:24,810
Va merge?

1055
00:51:24,810 --> 00:51:28,950

1056
00:51:28,950 --> 00:51:33,050
Amintiti-va ca anterior este doar
un pointer la un nod.

1057
00:51:33,050 --> 00:51:34,770
Și anterior este o variabilă locală.

1058
00:51:34,770 --> 00:51:38,080
Deci, această linie va stabili o variabilă locală,
precedent, egal sau

1059
00:51:38,080 --> 00:51:39,380
arătând spre un nou nod.

1060
00:51:39,380 --> 00:51:41,500
Că nu se va pune de fapt
în lista noastră, deși.

1061
00:51:41,500 --> 00:51:44,330
Cum ne-am pus-o în lista noastră?

1062
00:51:44,330 --> 00:51:45,620
Akchar?

1063
00:51:45,620 --> 00:51:46,870
>> Audiența: Te crezi
face curent-> următor.

1064
00:51:46,870 --> 00:51:50,186

1065
00:51:50,186 --> 00:51:52,550
>> JASON Hirschhorn: OK.

1066
00:51:52,550 --> 00:51:54,010
pac-> următor.

1067
00:51:54,010 --> 00:51:58,768
Deci, din nou, singurul motiv pentru care suntem în jos
aici este, ce face curent egal?

1068
00:51:58,768 --> 00:51:59,760
>> Audiența: Egal nul.

1069
00:51:59,760 --> 00:52:01,790
>> JASON Hirschhorn: Și ce
se întâmplă dacă facem null-> următor?

1070
00:52:01,790 --> 00:52:02,810
Ce avem de gând pentru a obține?

1071
00:52:02,810 --> 00:52:04,060
Vom lua o eroare de segmentare.

1072
00:52:04,060 --> 00:52:06,600

1073
00:52:06,600 --> 00:52:08,880
>> Audiența: Do curr este egal cu zero.

1074
00:52:08,880 --> 00:52:10,760
>> JASON Hirschhorn: E același lucru
ca prev, deși, pentru că există

1075
00:52:10,760 --> 00:52:12,820
o variabilă locală suntem setarea
egal cu acest nou nod.

1076
00:52:12,820 --> 00:52:16,680

1077
00:52:16,680 --> 00:52:20,920
Să ne întoarcem la imaginea noastră
de a insera ceva.

1078
00:52:20,920 --> 00:52:25,500
Spune-ne de a introduce la sfârșitul anului
a listei, astfel încât chiar aici.

1079
00:52:25,500 --> 00:52:30,010
Avem un pointer curent care este
arătând spre null și un punct anterior

1080
00:52:30,010 --> 00:52:32,800
care este îndreptat la 8.

1081
00:52:32,800 --> 00:52:35,330
Deci, ceea ce avem nevoie pentru a actualiza, Avi?

1082
00:52:35,330 --> 00:52:36,680
>> Audiența: Anterior-> următoare?

1083
00:52:36,680 --> 00:52:41,980
>> JASON Hirschhorn: Inapoi-> următoare este ceea ce
ne-o dorim pentru a actualiza pentru că

1084
00:52:41,980 --> 00:52:44,960
se va introduce de fapt la
sfârșitul listei.

1085
00:52:44,960 --> 00:52:47,220
Încă mai avem un bug, totuși,
că vom rula în.

1086
00:52:47,220 --> 00:52:50,090
Ce-i asta bug?

1087
00:52:50,090 --> 00:52:50,790
Da?

1088
00:52:50,790 --> 00:52:53,860
>> Audiența: O să se întoarcă
false în acest caz?

1089
00:52:53,860 --> 00:52:56,380
>> JASON Hirschhorn: Oh, este este
O să se întoarcă false.

1090
00:52:56,380 --> 00:52:57,430
Dar există un alt bug.

1091
00:52:57,430 --> 00:52:58,930
Deci, vom avea nevoie pentru a pune în schimb adevărat.

1092
00:52:58,930 --> 00:53:01,370
>> Audiența: Are anterior încă egal
nul în partea de sus a listei?

1093
00:53:01,370 --> 00:53:03,645
>> JASON Hirschhorn: încă Deci anterior
este egal cu zero la început.

1094
00:53:03,645 --> 00:53:07,480

1095
00:53:07,480 --> 00:53:10,440
Deci, cum putem trece peste asta?

1096
00:53:10,440 --> 00:53:10,950
Da?

1097
00:53:10,950 --> 00:53:15,280
>> Audiența: Cred că pot face o verificare
înainte bucla în timp ce pentru a vedea dacă este

1098
00:53:15,280 --> 00:53:16,610
o listă goală.

1099
00:53:16,610 --> 00:53:17,000
>> JASON Hirschhorn: OK.

1100
00:53:17,000 --> 00:53:17,710
Deci, haideți să mergem aici.

1101
00:53:17,710 --> 00:53:18,530
Face o verificare.

1102
00:53:18,530 --> 00:53:19,380
În cazul în care -

1103
00:53:19,380 --> 00:53:20,770
>> Audiența: Deci, dacă cap
este egal este egal cu zero.

1104
00:53:20,770 --> 00:53:24,300

1105
00:53:24,300 --> 00:53:26,320
>> JASON Hirschhorn: cazul în care capul
este egal cu egal nul -

1106
00:53:26,320 --> 00:53:27,790
care ne va spune dacă este o listă goală.

1107
00:53:27,790 --> 00:53:31,090
>> Audiența: Și apoi
face cap este egal cu noi.

1108
00:53:31,090 --> 00:53:34,740
>> JASON Hirschhorn: Cap
este egal cu new_node?

1109
00:53:34,740 --> 00:53:35,730
Și ce altceva mai trebuie să facem?

1110
00:53:35,730 --> 00:53:37,020
>> Audiența: Și atunci vă întoarceți adevărat.

1111
00:53:37,020 --> 00:53:37,535
>> JASON Hirschhorn: Nu chiar.

1112
00:53:37,535 --> 00:53:38,785
Ne lipsește un singur pas.

1113
00:53:38,785 --> 00:53:41,590

1114
00:53:41,590 --> 00:53:43,710
>> Audiența: New_node următor
trebuie să indice null.

1115
00:53:43,710 --> 00:53:44,570
>> JASON Hirschhorn: Exact, Alden.

1116
00:53:44,570 --> 00:53:46,600
Și atunci ne putem întoarce adevărat.

1117
00:53:46,600 --> 00:53:47,560
OK.

1118
00:53:47,560 --> 00:53:51,630
Dar este încă o idee bună de a face lucrurile
la sfârșitul listei, corect?

1119
00:53:51,630 --> 00:53:51,950
Bine.

1120
00:53:51,950 --> 00:53:54,450
Noi încă s-ar putea obține de fapt,
la sfârșitul listei.

1121
00:53:54,450 --> 00:53:57,870
Deci, este acest cod în regulă dacă suntem la
sfârșitul listei și există unele

1122
00:53:57,870 --> 00:53:59,120
lucruri din lista?

1123
00:53:59,120 --> 00:54:01,830

1124
00:54:01,830 --> 00:54:02,040
Corect?

1125
00:54:02,040 --> 00:54:03,540
Pentru că încă mai avem idee a lui Marcus.

1126
00:54:03,540 --> 00:54:06,870
Am putea ieși din această buclă, deoarece
suntem la sfârșitul listei.

1127
00:54:06,870 --> 00:54:09,308
Deci, nu ne mai dorim acest lucru
codul de aici?

1128
00:54:09,308 --> 00:54:10,520
>> Publicul: Da.

1129
00:54:10,520 --> 00:54:11,000
>> JASON Hirschhorn: Da.

1130
00:54:11,000 --> 00:54:14,190
Și de ce avem nevoie pentru a schimba acest lucru?

1131
00:54:14,190 --> 00:54:15,440
Adevărat.

1132
00:54:15,440 --> 00:54:19,580

1133
00:54:19,580 --> 00:54:21,640
Sună bine
pentru toată lumea până acum?

1134
00:54:21,640 --> 00:54:22,420
Oricine are orice -

1135
00:54:22,420 --> 00:54:23,480
Avi, ai ceva de adăugat?

1136
00:54:23,480 --> 00:54:23,920
>> Audiența: Nu.

1137
00:54:23,920 --> 00:54:25,276
>> JASON Hirschhorn: OK.

1138
00:54:25,276 --> 00:54:27,010
Așa că am făcut o serie de schimbări.

1139
00:54:27,010 --> 00:54:29,540
Am făcut această verificare înainte de a ne
intrat pentru o listă goală.

1140
00:54:29,540 --> 00:54:31,790
Deci, ne-am ocupat de o listă goală.

1141
00:54:31,790 --> 00:54:35,500
Și aici am avut grija de a introduce
ceva la sfârșitul listei.

1142
00:54:35,500 --> 00:54:38,930
Deci, se pare ca aceasta luare în timp ce buclă
grijă de lucruri în între,

1143
00:54:38,930 --> 00:54:41,920
undeva în listă, dacă există
sunt lucruri pe lista.

1144
00:54:41,920 --> 00:54:42,280
>> OK.

1145
00:54:42,280 --> 00:54:44,310
Să alergăm din nou acest program.

1146
00:54:44,310 --> 00:54:50,170

1147
00:54:50,170 --> 00:54:50,755
Nu a avut succes.

1148
00:54:50,755 --> 00:54:52,190
>> Audiența: Tu nu-l face.

1149
00:54:52,190 --> 00:54:53,940
>> JASON Hirschhorn: Oh,
Nu l-am face.

1150
00:54:53,940 --> 00:54:56,250
Bun punct, Michael.

1151
00:54:56,250 --> 00:54:57,500
Să adăugăm o face legat.

1152
00:54:57,500 --> 00:55:01,590

1153
00:55:01,590 --> 00:55:04,830
Linia 87 nu este o eroare.

1154
00:55:04,830 --> 00:55:05,420
Linia 87.

1155
00:55:05,420 --> 00:55:06,600
Alden, aceasta a fost linia pe care mi-ai dat.

1156
00:55:06,600 --> 00:55:08,962
Ce sa întâmplat?

1157
00:55:08,962 --> 00:55:10,710
>> Audiența: Trebuie să fie la null.

1158
00:55:10,710 --> 00:55:11,000
>> JASON Hirschhorn: Excelent.

1159
00:55:11,000 --> 00:55:11,630
Exact dreapta.

1160
00:55:11,630 --> 00:55:13,290
Aceasta ar trebui null.

1161
00:55:13,290 --> 00:55:15,210
Să facem din nou.

1162
00:55:15,210 --> 00:55:17,220
Compila.

1163
00:55:17,220 --> 00:55:17,890
OK.

1164
00:55:17,890 --> 00:55:19,400
Să introduce trei.

1165
00:55:19,400 --> 00:55:20,570
Inserția a fost de succes.

1166
00:55:20,570 --> 00:55:21,660
Hai să-l imprimați.

1167
00:55:21,660 --> 00:55:23,590
Oh, dacă am putea verifica.

1168
00:55:23,590 --> 00:55:25,500
Dar nu am făcut
Funcția de imprimare încă.

1169
00:55:25,500 --> 00:55:27,840
Hai să intrăm altceva.

1170
00:55:27,840 --> 00:55:29,090
Ce ar trebui să intrăm?

1171
00:55:29,090 --> 00:55:31,120

1172
00:55:31,120 --> 00:55:31,940
>> Audiența: Seven.

1173
00:55:31,940 --> 00:55:33,340
>> JASON Hirschhorn: Seven?

1174
00:55:33,340 --> 00:55:34,590
>> Publicul: Da.

1175
00:55:34,590 --> 00:55:38,680

1176
00:55:38,680 --> 00:55:39,780
>> JASON Hirschhorn: Avem un defect segment.

1177
00:55:39,780 --> 00:55:43,760
Așa că am luat unul, dar am în mod clar
nu se poate obține două.

1178
00:55:43,760 --> 00:55:45,690
Este 05:07.

1179
00:55:45,690 --> 00:55:48,370
Deci, am putea depana această
timp de trei minute.

1180
00:55:48,370 --> 00:55:51,240
Dar am de gând să ne lase aici
și trece la hash mese.

1181
00:55:51,240 --> 00:55:54,290
Dar, din nou, răspunsurile pentru acest cod
Voi e-mail pentru a vă într-un pic.

1182
00:55:54,290 --> 00:55:55,440
Suntem foarte aproape de ea.

1183
00:55:55,440 --> 00:55:58,300
Am foarte vă încurajez să dau seama
ceea ce se întâmplă aici și fixați-l.

1184
00:55:58,300 --> 00:56:02,400
Așa că vom trimite acest cod ca
bine plus soluția -

1185
00:56:02,400 --> 00:56:03,670
Probabil soluția mai târziu.

1186
00:56:03,670 --> 00:56:05,110
În primul rând acest cod.

1187
00:56:05,110 --> 00:56:08,290
>> Celălalt lucru pe care vreau să fac înainte de a ne
finisaj este de nu ne-am eliberat nimic.

1188
00:56:08,290 --> 00:56:10,370
Deci, vreau să-ți arăt ce
Valgrind arata ca.

1189
00:56:10,370 --> 00:56:14,310
Dacă vom rula limite Valgrind
în programul nostru,. / legate.

1190
00:56:14,310 --> 00:56:22,540
Din nou, în conformitate cu acest diapozitiv, ne
ar trebui să ruleze Valgrind cu un anumit tip de

1191
00:56:22,540 --> 00:56:26,410
opțiune, în acest caz,
- Scurgeri de check-= complet.

1192
00:56:26,410 --> 00:56:27,660
Deci, haideți să scrie Valgrind
- Scurgeri de check-= complet.

1193
00:56:27,660 --> 00:56:31,910

1194
00:56:31,910 --> 00:56:35,080
Deci, aceasta va rula Valgrind
în programul nostru.

1195
00:56:35,080 --> 00:56:37,000
Iar acum programul rulează de fapt.

1196
00:56:37,000 --> 00:56:40,190
Așa că am de gând să-l rulați la fel ca
înainte, a pus ceva inch

1197
00:56:40,190 --> 00:56:40,830
Am de gând să pună în trei.

1198
00:56:40,830 --> 00:56:41,790
Care funcționează.

1199
00:56:41,790 --> 00:56:43,202
Eu nu am de gând să încerce să pună în ceva
altfel pentru că am de gând să

1200
00:56:43,202 --> 00:56:44,710
a obține o falsă segment în acest caz.

1201
00:56:44,710 --> 00:56:46,700
Așa că eu sunt doar de gând să renunțe.

1202
00:56:46,700 --> 00:56:50,160
>> Și acum tu vezi aici
scurgeri și rezumat grămadă.

1203
00:56:50,160 --> 00:56:52,310
Acestea sunt lucrurile bune pe care
pe care doriți să verificați.

1204
00:56:52,310 --> 00:56:56,780
Deci, rezumatul heap - se spune, în uz
la ieșire - opt bytes într-un singur bloc.

1205
00:56:56,780 --> 00:56:58,370
Că un bloc este
nod am malloced.

1206
00:56:58,370 --> 00:57:02,230
Michael, ai spus mai devreme un nod este de opt
muscaturi deoarece are un număr întreg

1207
00:57:02,230 --> 00:57:02,680
și indicatorul.

1208
00:57:02,680 --> 00:57:04,550
Deci, asta e nod nostru.

1209
00:57:04,550 --> 00:57:08,170
Și apoi se spune am folosit malloc
de șapte ori și ne-am eliberat

1210
00:57:08,170 --> 00:57:08,940
ceva de șase ori.

1211
00:57:08,940 --> 00:57:13,680
Dar niciodată nu am numit liber, așa că nu am nici o
idee ce acest lucru este vorba.

1212
00:57:13,680 --> 00:57:18,490
>> Dar este suficient să spunem că, atunci când vă
ruleaza programe, malloc se numește

1213
00:57:18,490 --> 00:57:20,330
în alte locuri pe care le
nu trebuie să vă faceți griji.

1214
00:57:20,330 --> 00:57:22,460
Deci, malloc a fost, probabil, numit
în unele locuri.

1215
00:57:22,460 --> 00:57:24,480
Nu avem nevoie să vă faceți griji în cazul în care.

1216
00:57:24,480 --> 00:57:26,240
Dar acest lucru este într-adevăr ne.

1217
00:57:26,240 --> 00:57:27,380
Această primă linie este noi.

1218
00:57:27,380 --> 00:57:28,320
Am plecat din acel bloc.

1219
00:57:28,320 --> 00:57:30,330
Și puteți vedea că aici
în rezumatul scurgere.

1220
00:57:30,330 --> 00:57:31,950
Mai accesibil -

1221
00:57:31,950 --> 00:57:32,930
opt bytes într-un singur bloc.

1222
00:57:32,930 --> 00:57:34,100
Asta înseamnă că de memorie -

1223
00:57:34,100 --> 00:57:35,730
ne-au scurs ca memorie.

1224
00:57:35,730 --> 00:57:37,570
Cu siguranta pierdut -

1225
00:57:37,570 --> 00:57:38,770
ceva este pierdut pentru totdeauna.

1226
00:57:38,770 --> 00:57:40,590
În general, nu se va
vezi ceva acolo.

1227
00:57:40,590 --> 00:57:44,780
Totuși, în general, în cazul în care este accesibil
veți vedea lucrurile, în cazul în care veți dori

1228
00:57:44,780 --> 00:57:48,900
să se uite pentru a vedea ce cod ar trebui să
s-au eliberat, dar ai uitat să elibereze.

1229
00:57:48,900 --> 00:57:53,170
>> Și apoi, dacă acest lucru nu a fost cazul,
dacă am făcut totul gratuit,

1230
00:57:53,170 --> 00:57:54,360
putem verifica asta.

1231
00:57:54,360 --> 00:57:57,330
Să rula programul
nu pune în nimic.

1232
00:57:57,330 --> 00:57:59,800
Veți vedea aici în uz, la ieșire -

1233
00:57:59,800 --> 00:58:01,310
de zero la zero bytes în blocuri.

1234
00:58:01,310 --> 00:58:06,310
Asta înseamnă că am avut mai rămas nimic
atunci când acest program ieșit.

1235
00:58:06,310 --> 00:58:12,090
Deci, înainte de a porni în pset6, rula Valgrind
și asigurați-vă că nu aveți

1236
00:58:12,090 --> 00:58:15,310
orice scurgeri de memorie în programul dumneavoastră.

1237
00:58:15,310 --> 00:58:17,910
Dacă aveți orice întrebări cu Valgrind,
nu ezitați să ajungă.

1238
00:58:17,910 --> 00:58:18,700
Dar acest lucru este modul în care îl utilizați.

1239
00:58:18,700 --> 00:58:20,890
Foarte simplu - a se vedea dacă
au în uz la ieșire -

1240
00:58:20,890 --> 00:58:22,270
orice bytes în orice blocuri.

1241
00:58:22,270 --> 00:58:27,890

1242
00:58:27,890 --> 00:58:29,580
>> Așa că am fost de lucru pe insert nod.

1243
00:58:29,580 --> 00:58:33,840
Am avut alte două funcții aici -
imprima noduri și nodurile libere.

1244
00:58:33,840 --> 00:58:37,780
Din nou, acestea sunt functii care sunt
va fi bine pentru tine de a practica

1245
00:58:37,780 --> 00:58:40,990
, deoarece acestea vă vor ajuta nu numai cu
aceste exerciții eșantion, dar, de asemenea,

1246
00:58:40,990 --> 00:58:42,180
pe problema setat.

1247
00:58:42,180 --> 00:58:44,230
Ei harta pe destul de strâns de lucruri
ai de gând să aibă de a face în

1248
00:58:44,230 --> 00:58:45,010
problemă set.

1249
00:58:45,010 --> 00:58:47,640
Dar vreau să vă asigurați
ne atinge pe toate.

1250
00:58:47,640 --> 00:58:50,400
Și tabele de dispersie sunt, de asemenea, cruciale pentru
ceea ce facem în această secțiune

1251
00:58:50,400 --> 00:58:51,980
săptămână - sau în setul problemă.

1252
00:58:51,980 --> 00:58:55,200
>> Așa că am de gând să termin secțiunea
vorbesc despre tabele de dispersie.

1253
00:58:55,200 --> 00:58:58,140
Dacă observați am făcut o
tabel hash mic.

1254
00:58:58,140 --> 00:59:00,020
Asta nu este ceea ce vorbim
despre, cu toate acestea.

1255
00:59:00,020 --> 00:59:03,540
Vorbim despre un alt
tip de tabele de dispersie.

1256
00:59:03,540 --> 00:59:07,300
Și la bază, un tabel de hash
nu este nimic mai mult decât o

1257
00:59:07,300 --> 00:59:08,860
matrice plus o funcție hash.

1258
00:59:08,860 --> 00:59:11,150
Vom vorbi de un pic doar pentru a
asigurați-vă că toată lumea înțelege ceea ce o

1259
00:59:11,150 --> 00:59:12,110
Funcția hash este.

1260
00:59:12,110 --> 00:59:15,420
Și vă spun acum că este
nimic mai mult decât de două lucruri -

1261
00:59:15,420 --> 00:59:18,590
o matrice și o funcție hash.

1262
00:59:18,590 --> 00:59:20,716
Și aici sunt pașii prin
care aceasta funcționează.

1263
00:59:20,716 --> 00:59:31,560

1264
00:59:31,560 --> 00:59:32,810
>> Există gama noastră.

1265
00:59:32,810 --> 00:59:38,460

1266
00:59:38,460 --> 00:59:39,460
Nu este funcția noastră.

1267
00:59:39,460 --> 00:59:43,180
În special, funcțiile hash trebuie să
face o serie de lucruri cu aceasta.

1268
00:59:43,180 --> 00:59:45,040
Am de gând să vorbesc în mod special
despre această problemă set.

1269
00:59:45,040 --> 00:59:46,450
Este, probabil, va
ia într-un șir.

1270
00:59:46,450 --> 00:59:50,570

1271
00:59:50,570 --> 00:59:51,770
Și ce-o să se întoarcă?

1272
00:59:51,770 --> 00:59:52,640
Ce tip de date?

1273
00:59:52,640 --> 00:59:54,260
Alden?

1274
00:59:54,260 --> 00:59:55,760
Funcția hash-ul se întoarcă?

1275
00:59:55,760 --> 00:59:58,760
Un întreg.

1276
00:59:58,760 --> 01:00:01,700
Deci, aceasta este ceea ce hash
tabel este format din -

1277
01:00:01,700 --> 01:00:05,430
o masă sub formă de matrice
și o funcție hash.

1278
01:00:05,430 --> 01:00:06,010
Cum funcționează?

1279
01:00:06,010 --> 01:00:07,300
Acesta funcționează în trei etape.

1280
01:00:07,300 --> 01:00:08,740
Ne da o cheie.

1281
01:00:08,740 --> 01:00:11,470
În acest caz, vom da un șir.

1282
01:00:11,470 --> 01:00:18,140
Noi numim funcția de distribuire pe un singur pas
la cheie și vom obține o valoare.

1283
01:00:18,140 --> 01:00:20,310
>> În mod specific, vom spune
vom obține un număr întreg.

1284
01:00:20,310 --> 01:00:25,630
Că întreg, nu sunt foarte specifice
limite la ceea ce poate fi că întreg.

1285
01:00:25,630 --> 01:00:28,880
În acest exemplu, gama noastră
este de dimensiune trei.

1286
01:00:28,880 --> 01:00:32,330
Deci, ce numere pot fi faptul că întreg.

1287
01:00:32,330 --> 01:00:35,970
Care este intervalul de valori valide pentru
ca întreg, tipul de returnare a acestei

1288
01:00:35,970 --> 01:00:37,220
Funcția hash?

1289
01:00:37,220 --> 01:00:40,440

1290
01:00:40,440 --> 01:00:42,110
Zero, unu și doi.

1291
01:00:42,110 --> 01:00:46,060
Punctul de funcția de distribuire este de a
dau seama de locul în matrice

1292
01:00:46,060 --> 01:00:47,790
în cazul în care cheia noastră se întâmplă.

1293
01:00:47,790 --> 01:00:51,290
Există doar trei posibile
locuri de aici -

1294
01:00:51,290 --> 01:00:52,130
zero, unu, sau doi.

1295
01:00:52,130 --> 01:00:55,360
Deci, această funcție mai bine de retur
zero, unu, sau doi.

1296
01:00:55,360 --> 01:00:58,740
Unele indice valabil în această matrice.

1297
01:00:58,740 --> 01:01:02,770
>> Și apoi, în funcție de cazul în care se întoarce,
puteți vedea acolo matrice deschis

1298
01:01:02,770 --> 01:01:03,730
încadreze valoarea.

1299
01:01:03,730 --> 01:01:05,800
Acolo am pus cheia.

1300
01:01:05,800 --> 01:01:11,280
Deci, ne-am arunca în dovleac,
ieșim la zero.

1301
01:01:11,280 --> 01:01:15,540
La suport matrice 0, am pus dovleac.

1302
01:01:15,540 --> 01:01:21,070
Ne arunca la pisici, avem unul.

1303
01:01:21,070 --> 01:01:24,110
Am pus pisica la unul.

1304
01:01:24,110 --> 01:01:25,480
Am pus în păianjen.

1305
01:01:25,480 --> 01:01:26,710
Ieșim doi.

1306
01:01:26,710 --> 01:01:30,200
Am pus păianjen la matrice suport doi.

1307
01:01:30,200 --> 01:01:32,300
Ar fi atât de frumos în cazul în care
a lucrat ca asta.

1308
01:01:32,300 --> 01:01:35,570
Dar, din păcate, așa cum vom vedea,
E un pic mai complicat.

1309
01:01:35,570 --> 01:01:37,570
>> Înainte de a ajunge acolo, întrebări
despre acest lucru de bază

1310
01:01:37,570 --> 01:01:38,820
set-up a unui tabel hash?

1311
01:01:38,820 --> 01:01:49,050

1312
01:01:49,050 --> 01:01:51,940
Aceasta este o imagine de exact
ceea ce ne-am desenat pe tablă.

1313
01:01:51,940 --> 01:01:55,420
Dar din moment ce l-am desenat pe tablă, am
Nu am de gând să meargă în ea mai departe.

1314
01:01:55,420 --> 01:02:00,430
În esență, chei, magie cutia neagră -
sau, în acest caz, cutie teal - de o

1315
01:02:00,430 --> 01:02:02,410
Funcția hash le pune în găleți.

1316
01:02:02,410 --> 01:02:04,690
Și în acest exemplu suntem
nu pune numele.

1317
01:02:04,690 --> 01:02:07,880
Punem la telefon asociat
numărul de nume în găleată.

1318
01:02:07,880 --> 01:02:10,430
Dar ai putea foarte bine doar
a pus numele în găleată.

1319
01:02:10,430 --> 01:02:12,950
>> Aceasta este doar o imagine a ceea ce
ne-am desenat pe tablă.

1320
01:02:12,950 --> 01:02:14,460
Avem potențiale capcane, totuși.

1321
01:02:14,460 --> 01:02:17,470
Și acolo sunt două, în special
slide-uri pe care vreau să merg peste.

1322
01:02:17,470 --> 01:02:20,230
Primul este de aproximativ
o funcție hash.

1323
01:02:20,230 --> 01:02:22,620
Așa că am pus întrebarea, ce
face o funcție hash bun?

1324
01:02:22,620 --> 01:02:24,220
Eu dau două răspunsuri.

1325
01:02:24,220 --> 01:02:26,630
Primul este că este determinist.

1326
01:02:26,630 --> 01:02:29,660
In contextul funcții hash,
Ce înseamnă acest lucru?

1327
01:02:29,660 --> 01:02:37,840

1328
01:02:37,840 --> 01:02:39,282
Da?

1329
01:02:39,282 --> 01:02:42,850
>> Audiența: Se poate găsi
index în timp constant?

1330
01:02:42,850 --> 01:02:43,810
>> JASON Hirschhorn: A
nu este ceea ce înseamnă.

1331
01:02:43,810 --> 01:02:44,725
Dar asta este o presupunere bun.

1332
01:02:44,725 --> 01:02:46,100
Mai are cineva o presupunere
la ce înseamnă acest lucru?

1333
01:02:46,100 --> 01:02:47,780
Ca o funcție hash bună
este determinist?

1334
01:02:47,780 --> 01:02:48,280
Annie?

1335
01:02:48,280 --> 01:02:51,680
>> Audienta: Asta o cheie poate fi mapate numai
la un loc în tabelul hash.

1336
01:02:51,680 --> 01:02:53,070
>> JASON Hirschhorn: Asta-i
exact dreapta.

1337
01:02:53,070 --> 01:02:57,430
De fiecare dată când pune în dovleac,
returnează întotdeauna zero.

1338
01:02:57,430 --> 01:03:01,660
Dacă ați pus în dovleac și hash-ul
Funcția returnează zero, dar are un

1339
01:03:01,660 --> 01:03:06,060
probabilitate de a se întoarce ceva
altceva mai mare decât zero -

1340
01:03:06,060 --> 01:03:09,280
asa ca poate se poate returna unul, uneori,
sau alte două ori -

1341
01:03:09,280 --> 01:03:11,100
care nu este o funcție hash bună.

1342
01:03:11,100 --> 01:03:11,800
Ai dreptate.

1343
01:03:11,800 --> 01:03:15,680
Funcția hash-ul ar trebui să returneze
același întreg exact, în acest caz, pentru

1344
01:03:15,680 --> 01:03:17,780
același șir exact.

1345
01:03:17,780 --> 01:03:22,210
>> Poate se întoarce în același întreg exact
pentru același șir exact

1346
01:03:22,210 --> 01:03:24,430
indiferent de capitalizare.

1347
01:03:24,430 --> 01:03:27,980
Dar în acest caz este încă
deterministic pentru că multe lucruri

1348
01:03:27,980 --> 01:03:29,350
sunt mapate pe aceeași valoare.

1349
01:03:29,350 --> 01:03:30,170
Asta e bine.

1350
01:03:30,170 --> 01:03:32,615
Atâta timp cât există o singură
ieșire pentru o anumită intrare.

1351
01:03:32,615 --> 01:03:35,630

1352
01:03:35,630 --> 01:03:36,350
>> OK.

1353
01:03:36,350 --> 01:03:38,340
Al doilea lucru este că
întoarce indicii valide.

1354
01:03:38,340 --> 01:03:40,220
Ne-am adus mai devreme.

1355
01:03:40,220 --> 01:03:41,860
Această funcție hash -

1356
01:03:41,860 --> 01:03:43,710
oh boy -

1357
01:03:43,710 --> 01:03:46,840
o funcție hash ar trebui
reveni indicii valide.

1358
01:03:46,840 --> 01:03:47,740
Deci, spune -

1359
01:03:47,740 --> 01:03:48,990
să ne întoarcem la acest exemplu.

1360
01:03:48,990 --> 01:03:52,580

1361
01:03:52,580 --> 01:03:57,540
Funcția hash mea contează în sus
literele din cuvântul.

1362
01:03:57,540 --> 01:03:58,380
Asta e funcția de distribuire.

1363
01:03:58,380 --> 01:03:59,740
Și se întoarce ca întreg.

1364
01:03:59,740 --> 01:04:04,280
Deci, dacă am cuvinte A, este
O să se întoarcă unul.

1365
01:04:04,280 --> 01:04:06,900
Și se va pune un drept aici.

1366
01:04:06,900 --> 01:04:09,430
Ce se întâmplă dacă am pus în liliacul cuvânt?

1367
01:04:09,430 --> 01:04:11,310
O să se întoarcă trei.

1368
01:04:11,310 --> 01:04:12,560
În cazul în care se merge bat?

1369
01:04:12,560 --> 01:04:18,730

1370
01:04:18,730 --> 01:04:19,750
>> Nu se potrivește.

1371
01:04:19,750 --> 01:04:21,000
Dar ea trebuie să meargă undeva.

1372
01:04:21,000 --> 01:04:23,340
Aceasta este masa mea hash la urma urmei, și
tot ceea ce trebuie să meargă undeva.

1373
01:04:23,340 --> 01:04:24,590
Deci, în cazul în care ar trebui să bat meargă?

1374
01:04:24,590 --> 01:04:28,020

1375
01:04:28,020 --> 01:04:28,710
Orice gândurile?

1376
01:04:28,710 --> 01:04:29,450
Ghicește?

1377
01:04:29,450 --> 01:04:30,280
Presupuneri bune?

1378
01:04:30,280 --> 01:04:31,220
>> Audiența: Zero.

1379
01:04:31,220 --> 01:04:32,120
>> JASON Hirschhorn: De ce la zero?

1380
01:04:32,120 --> 01:04:35,990
>> Audiența: Pentru trei
modulo trei este zero?

1381
01:04:35,990 --> 01:04:38,620
>> JASON Hirschhorn: Trei
modulo trei este zero.

1382
01:04:38,620 --> 01:04:40,810
Aceasta este o mare presupunere,
și asta e corect.

1383
01:04:40,810 --> 01:04:43,870
Deci, în acest caz, ar trebui
probabil, du-te la zero.

1384
01:04:43,870 --> 01:04:51,080
Deci, o modalitate buna de a se asigura că acest hash
Funcția returnează numai indicii valide este

1385
01:04:51,080 --> 01:04:54,580
să-l modulo de mărimea mesei.

1386
01:04:54,580 --> 01:04:57,360
Dacă aveți orice modulo acest întoarce de
trei, esti mereu de gând pentru a obține

1387
01:04:57,360 --> 01:05:00,930
ceva între zero, unu, doi.

1388
01:05:00,930 --> 01:05:05,160
Și dacă acest lucru se întoarce mereu șapte, și
întotdeauna modulo de trei, tu ești

1389
01:05:05,160 --> 01:05:06,030
întotdeauna merge pentru a obține același lucru.

1390
01:05:06,030 --> 01:05:09,270
>> Deci e încă deterministe
dacă modulo.

1391
01:05:09,270 --> 01:05:11,420
Dar asta se va asigura că
nu obține ceva -

1392
01:05:11,420 --> 01:05:12,940
o industrie invalid.

1393
01:05:12,940 --> 01:05:16,840
În general, că modulo trebui să se întâmple
în funcția hash.

1394
01:05:16,840 --> 01:05:18,240
Deci, nu aveți nevoie să vă faceți griji despre acest lucru.

1395
01:05:18,240 --> 01:05:20,555
Trebuie doar poate asigura că
aceasta este o indice valid.

1396
01:05:20,555 --> 01:05:23,700

1397
01:05:23,700 --> 01:05:26,700
Orice întrebări cu privire la acest
potențial capcană?

1398
01:05:26,700 --> 01:05:36,590

1399
01:05:36,590 --> 01:05:39,060
>> OK.

1400
01:05:39,060 --> 01:05:40,290
Și acolo mergem.

1401
01:05:40,290 --> 01:05:42,890
Următor potențial capcană, și
acesta este unul mare.

1402
01:05:42,890 --> 01:05:46,880
Ce se întâmplă dacă două chei hartă
la aceeași valoare?

1403
01:05:46,880 --> 01:05:49,350
Deci, există două moduri de a rezolva aceasta.

1404
01:05:49,350 --> 01:05:53,140

1405
01:05:53,140 --> 01:05:56,020
Primul se numește liniar
sondare, care sunt

1406
01:05:56,020 --> 01:05:57,300
nu va trece peste.

1407
01:05:57,300 --> 01:06:01,120
Dar ar trebui să fie familiarizați cu modul în care
care funcționează și ceea ce este.

1408
01:06:01,120 --> 01:06:05,610
>> Cea de a doua am de gând să merg peste
pentru că este cel care mulți

1409
01:06:05,610 --> 01:06:08,290
oameni, probabil, se va termina decide
pentru a utiliza în setul lor probleme.

1410
01:06:08,290 --> 01:06:09,820
Desigur, tu nu trebuie sa.

1411
01:06:09,820 --> 01:06:15,280
Dar pentru setul de probleme, multe persoane
au tendința de a alege pentru a crea un tabel hash

1412
01:06:15,280 --> 01:06:17,950
cu înlănțuirea separată a pune în aplicare
dicționar lor.

1413
01:06:17,950 --> 01:06:21,390
Așa că am de gând să merg peste ceea ce înseamnă
pentru a crea un tabel hash cu

1414
01:06:21,390 --> 01:06:23,890
înlănțuirea separată.

1415
01:06:23,890 --> 01:06:26,260
>> Așa că am pus în dovleac.

1416
01:06:26,260 --> 01:06:29,560
Returnează zero.

1417
01:06:29,560 --> 01:06:31,410
Și am pus dovleac aici.

1418
01:06:31,410 --> 01:06:35,880

1419
01:06:35,880 --> 01:06:37,930
Apoi m-am pus in -

1420
01:06:37,930 --> 01:06:39,922
ceea ce este un alt lucru Halloween-tematice?

1421
01:06:39,922 --> 01:06:42,200
>> Audiența: Candy.

1422
01:06:42,200 --> 01:06:42,770
>> JASON Hirschhorn: Candy!

1423
01:06:42,770 --> 01:06:43,910
Acesta este un mare unul.

1424
01:06:43,910 --> 01:06:47,760
Am pus în bomboane, și bomboane
De asemenea, îmi dă zero.

1425
01:06:47,760 --> 01:06:49,350
Ce să fac?

1426
01:06:49,350 --> 01:06:51,940
Orice idei?

1427
01:06:51,940 --> 01:06:53,940
Pentru că tot felul de know-
ceea ce înlănțuirea separată este.

1428
01:06:53,940 --> 01:06:55,190
Deci, orice idei ce să fac?

1429
01:06:55,190 --> 01:06:58,170

1430
01:06:58,170 --> 01:06:59,110
Da.

1431
01:06:59,110 --> 01:07:03,810
>> Audiența: Punerea șirul
de fapt, în tabelul de hașiș.

1432
01:07:03,810 --> 01:07:08,910
>> JASON Hirschhorn: Deci vom
atrage ideea de bine aici.

1433
01:07:08,910 --> 01:07:09,340
OK.

1434
01:07:09,340 --> 01:07:12,290
>> Audiența: Au Hashtable
[Inaudibil]

1435
01:07:12,290 --> 01:07:16,640
indicatorul care indică
începutul unei liste.

1436
01:07:16,640 --> 01:07:20,930
Și apoi au dovleac fi prima valoare
în această listă legat și bomboane fie

1437
01:07:20,930 --> 01:07:22,800
a doua valoare în această listă legat.

1438
01:07:22,800 --> 01:07:23,420
>> JASON Hirschhorn: OK.

1439
01:07:23,420 --> 01:07:24,670
Marcus, care a fost remarcabil.

1440
01:07:24,670 --> 01:07:26,160
Am de gând să rupă acea jos.

1441
01:07:26,160 --> 01:07:28,890
Marcus este de a spune nu
suprascrie dovleac.

1442
01:07:28,890 --> 01:07:30,660
Asta ar fi rău.

1443
01:07:30,660 --> 01:07:33,640
Nu pune bomboane în altă parte.

1444
01:07:33,640 --> 01:07:35,390
Vom le-a pus atât la zero.

1445
01:07:35,390 --> 01:07:37,770
Dar am de gând să se ocupe de
sa le puna la zero, prin

1446
01:07:37,770 --> 01:07:39,395
crearea unei liste de la zero.

1447
01:07:39,395 --> 01:07:42,430
Și vom crea o listă de
tot ceea ce mapate la zero.

1448
01:07:42,430 --> 01:07:47,960
Și cel mai bun mod am învățat pentru a crea
o listă care poate crește și micșora

1449
01:07:47,960 --> 01:07:49,840
dinamic nu este în
un alt tablou.

1450
01:07:49,840 --> 01:07:51,510
Deci, nu o matrice multi-dimensionale.

1451
01:07:51,510 --> 01:07:54,080
Dar pentru a crea o listă de legat.

1452
01:07:54,080 --> 01:07:55,330
>> Deci, ceea ce a propus -

1453
01:07:55,330 --> 01:07:57,950

1454
01:07:57,950 --> 01:07:59,200
Mă duc pentru a obține un nou -

1455
01:07:59,200 --> 01:08:15,380

1456
01:08:15,380 --> 01:08:19,689
este de a crea un tablou cu indicatori,
o serie de indicii.

1457
01:08:19,689 --> 01:08:20,580
OK.

1458
01:08:20,580 --> 01:08:24,180
Orice idee sau sugestie ce tipul
din acest indicii ar trebui să fie?

1459
01:08:24,180 --> 01:08:26,290
Marcus?

1460
01:08:26,290 --> 01:08:27,250
>> Audiența: indicii pentru a -

1461
01:08:27,250 --> 01:08:28,609
>> JASON Hirschhorn: Pentru că
a declarat o listă legată, așa -

1462
01:08:28,609 --> 01:08:29,520
>> Audiența: indicii nod?

1463
01:08:29,520 --> 01:08:30,670
>> JASON Hirschhorn: indicii nod.

1464
01:08:30,670 --> 01:08:32,830
Dacă lucrurile din legate noastră
listă sunt noduri, atunci ele

1465
01:08:32,830 --> 01:08:34,370
ar trebui să fie indicii de noduri.

1466
01:08:34,370 --> 01:08:35,939
Și ce fac ei egala inițial?

1467
01:08:35,939 --> 01:08:36,990
>> Audiența: Null.

1468
01:08:36,990 --> 01:08:38,240
>> JASON Hirschhorn: Null.

1469
01:08:38,240 --> 01:08:44,540

1470
01:08:44,540 --> 01:08:46,080
Deci, nu e treaba noastră gol.

1471
01:08:46,080 --> 01:08:47,170
Se întoarce de dovleac la zero.

1472
01:08:47,170 --> 01:08:48,569
Ce facem?

1473
01:08:48,569 --> 01:08:49,609
Plimbare mine prin ea?

1474
01:08:49,609 --> 01:08:50,810
De fapt, Marcus mi-a dat deja.

1475
01:08:50,810 --> 01:08:52,439
Altcineva mi-plimbare prin ea.

1476
01:08:52,439 --> 01:08:54,760
Ce facem atunci când ne -

1477
01:08:54,760 --> 01:08:56,609
acest lucru arata foarte similar cu
ceea ce ne-am face doar.

1478
01:08:56,609 --> 01:08:57,396
Avi.

1479
01:08:57,396 --> 01:08:59,090
>> Audiența: am de gând să ia o presupunere.

1480
01:08:59,090 --> 01:09:01,250
Deci, atunci când vei ajunge bomboane.

1481
01:09:01,250 --> 01:09:01,640
>> JASON Hirschhorn: Da.

1482
01:09:01,640 --> 01:09:03,120
Ei bine, avem dovleac.

1483
01:09:03,120 --> 01:09:03,870
Să trecem primul unul.

1484
01:09:03,870 --> 01:09:04,324
Avem dovleac.

1485
01:09:04,324 --> 01:09:04,779
>> Audiența: OK.

1486
01:09:04,779 --> 01:09:05,880
Se întoarce de dovleac la zero.

1487
01:09:05,880 --> 01:09:08,770
Deci, l-ai pus în asta.

1488
01:09:08,770 --> 01:09:10,810
Sau de fapt, l-ai pus
în lista de legătura.

1489
01:09:10,810 --> 01:09:13,550
>> JASON Hirschhorn: Cum ne
pune-l în lista de legat?

1490
01:09:13,550 --> 01:09:15,479
>> Audiența: Oh, sintaxa real?

1491
01:09:15,479 --> 01:09:16,240
>> JASON Hirschhorn: Doar de mers pe jos -

1492
01:09:16,240 --> 01:09:16,740
spun mai mult.

1493
01:09:16,740 --> 01:09:19,310
Ce facem?

1494
01:09:19,310 --> 01:09:22,100
>> Audiența: Tocmai ai introduce
ca primul nod.

1495
01:09:22,100 --> 01:09:22,675
>> JASON Hirschhorn: OK.

1496
01:09:22,675 --> 01:09:29,069
Deci avem nodul nostru, dovleac.

1497
01:09:29,069 --> 01:09:31,560
Și acum cum l-am introduce?

1498
01:09:31,560 --> 01:09:34,590

1499
01:09:34,590 --> 01:09:37,090
>> Audiența: Ai atribui
se la indicatorul.

1500
01:09:37,090 --> 01:09:37,970
>> JASON Hirschhorn: Care pointer?

1501
01:09:37,970 --> 01:09:39,620
>> Audiența: indicatorul la zero.

1502
01:09:39,620 --> 01:09:41,420
>> JASON Hirschhorn: Deci, în cazul în care
face acest punct?

1503
01:09:41,420 --> 01:09:42,810
>> Audiența: Pentru null chiar acum.

1504
01:09:42,810 --> 01:09:43,529
>> JASON Hirschhorn: Ei bine,
se indică la null.

1505
01:09:43,529 --> 01:09:44,499
Dar eu pun în dovleac.

1506
01:09:44,499 --> 01:09:46,053
Deci, în cazul în care ar trebui să arate?

1507
01:09:46,053 --> 01:09:46,880
>> Audiența: Pentru a dovleac.

1508
01:09:46,880 --> 01:09:47,399
>> JASON Hirschhorn: Pentru a dovleac.

1509
01:09:47,399 --> 01:09:48,760
Exact.

1510
01:09:48,760 --> 01:09:50,010
Deci, acest lucru indică dovleac.

1511
01:09:50,010 --> 01:09:52,500

1512
01:09:52,500 --> 01:09:54,250
Și în cazul în care face acest lucru pointer
la punctul de dovleac?

1513
01:09:54,250 --> 01:09:57,986

1514
01:09:57,986 --> 01:09:58,340
La

1515
01:09:58,340 --> 01:09:58,590
>> Audiența: Null.

1516
01:09:58,590 --> 01:09:59,210
>> JASON Hirschhorn: la NULL.

1517
01:09:59,210 --> 01:10:00,460
Exact.

1518
01:10:00,460 --> 01:10:03,570

1519
01:10:03,570 --> 01:10:05,140
Deci, ne-am introdus ceva
în lista de legătura.

1520
01:10:05,140 --> 01:10:07,210
Tocmai am scris acest cod pentru a face acest lucru.

1521
01:10:07,210 --> 01:10:09,520
Aproape aproape am ajuns
complet spart.

1522
01:10:09,520 --> 01:10:10,790
Acum vom introduce bomboane.

1523
01:10:10,790 --> 01:10:13,480
Bomboane nostru, de asemenea, duce la zero.

1524
01:10:13,480 --> 01:10:16,100
Deci, ce facem cu bomboane?

1525
01:10:16,100 --> 01:10:18,790
>> Audiența: Depinde dacă sau
nu încercăm să-l rezolve.

1526
01:10:18,790 --> 01:10:19,640
>> JASON Hirschhorn: Asta-i
exact dreapta.

1527
01:10:19,640 --> 01:10:21,070
Depinde dacă sau nu
noi încercăm să-l rezolve.

1528
01:10:21,070 --> 01:10:22,660
Să presupunem că nu suntem
de gând să-l rezolve.

1529
01:10:22,660 --> 01:10:24,880
>> Audiența: Ei bine, atunci, așa cum am discutat
înainte, este mai simplă doar să-l puneți

1530
01:10:24,880 --> 01:10:28,590
chiar de la început, astfel încât indicatorul
de la zero puncte la bomboane.

1531
01:10:28,590 --> 01:10:29,020
>> JASON Hirschhorn: OK.

1532
01:10:29,020 --> 01:10:29,380
Stai.

1533
01:10:29,380 --> 01:10:30,630
Permiteți-mi crea bomboane chiar aici.

1534
01:10:30,630 --> 01:10:34,030

1535
01:10:34,030 --> 01:10:35,150
Deci, acest indicator -

1536
01:10:35,150 --> 01:10:37,590
>> Publicul: Da, ar trebui acum
să fie îndreptată la bomboane.

1537
01:10:37,590 --> 01:10:40,580
Apoi, au indicatorul de
Punct de bomboane de dovleac.

1538
01:10:40,580 --> 01:10:43,140

1539
01:10:43,140 --> 01:10:44,560
>> JASON Hirschhorn: Cum ar fi asta?

1540
01:10:44,560 --> 01:10:47,380
Și spun că un alt
lucru pentru a mapa la zero?

1541
01:10:47,380 --> 01:10:48,660
>> Audiența: Ei bine, tu doar
face acelasi lucru?

1542
01:10:48,660 --> 01:10:50,290
>> JASON Hirschhorn: Faceți același lucru.

1543
01:10:50,290 --> 01:10:53,700
Deci, în acest caz, dacă nu o facem
Vreau să-l păstrați-l sortate

1544
01:10:53,700 --> 01:10:55,270
Pare destul de simplu.

1545
01:10:55,270 --> 01:10:59,920
Ne ia indicatorul în indicelui care
dat de funcția noastră hash.

1546
01:10:59,920 --> 01:11:03,830
Avem ca punct de noul nostru nod.

1547
01:11:03,830 --> 01:11:07,830
Și apoi tot ce a fost îndreptat
a anterior -

1548
01:11:07,830 --> 01:11:10,620
în acest caz nul, în
caz al doilea dovleac -

1549
01:11:10,620 --> 01:11:15,310
că, oricare ar fi acesta este îndreptat la
în prealabil, se adaugă în următoarea a

1550
01:11:15,310 --> 01:11:17,810
noul nostru nod.

1551
01:11:17,810 --> 01:11:19,650
Suntem introducerea ceva
la început.

1552
01:11:19,650 --> 01:11:22,900
De fapt, aceasta este mult mai simplu decât
încearcă să mențină lista sortată.

1553
01:11:22,900 --> 01:11:25,340
Dar, din nou, căutarea va fi
mai complicat pe aici.

1554
01:11:25,340 --> 01:11:28,300
Vom avea mereu pentru a merge până la capăt.

1555
01:11:28,300 --> 01:11:29,650
>> OK.

1556
01:11:29,650 --> 01:11:32,750
Orice întrebări cu privire la înlănțuirea separată?

1557
01:11:32,750 --> 01:11:34,690
Cum funcționează?

1558
01:11:34,690 --> 01:11:35,820
Vă rugăm să cereți-le acum.

1559
01:11:35,820 --> 01:11:39,260
Eu chiar vreau să vă asigurați că toate
înțelege acest lucru înainte de capul afară.

1560
01:11:39,260 --> 01:11:48,410

1561
01:11:48,410 --> 01:11:52,060
>> Audiența: De ce ai pus de dovleac
și bomboane în același

1562
01:11:52,060 --> 01:11:54,108
o parte din tabelul hash?

1563
01:11:54,108 --> 01:11:55,860
>> JASON Hirschhorn: Bună întrebare.

1564
01:11:55,860 --> 01:11:59,140
De ce nu le-am pus în aceeași
o parte din tabelul hash?

1565
01:11:59,140 --> 01:12:03,200
Ei bine, în acest caz, funcția noastră hash
revine la zero pentru ambele dintre ele.

1566
01:12:03,200 --> 01:12:05,310
Așa că au nevoie pentru a merge la indice zero,
pentru că în cazul în care vom

1567
01:12:05,310 --> 01:12:07,420
uita-te pentru ei, dacă ne-am vreodată
doriți să le căutați.

1568
01:12:07,420 --> 01:12:11,750
Din nou, cu o abordare liniar de sondare
nu le-ar pune atât la zero.

1569
01:12:11,750 --> 01:12:13,900
Dar în abordarea separată lanț,
am de gând să le pună, atât la zero

1570
01:12:13,900 --> 01:12:16,620
și apoi a crea o listă de pe zero.

1571
01:12:16,620 --> 01:12:20,140
>> Și nu vrem să suprascrie dovleac
pur și simplu pentru că pentru că atunci vom

1572
01:12:20,140 --> 01:12:21,860
presupune că a fost dovleac
niciodată introdus.

1573
01:12:21,860 --> 01:12:25,230
Dacă vom păstra doar un singur lucru în
locație care ar fi rău.

1574
01:12:25,230 --> 01:12:28,590
Atunci nu ar fi nici o
Șanse de noi vreodată -

1575
01:12:28,590 --> 01:12:31,660
dacă am avut vreodată un duplicat, apoi ne-am
ar șterge doar valoarea noastră inițială.

1576
01:12:31,660 --> 01:12:34,090
Deci, de ce facem această abordare.

1577
01:12:34,090 --> 01:12:36,580
Sau de aceea am ales - dar, din nou, ne-am
a ales abordarea separată înlănțuirea,

1578
01:12:36,580 --> 01:12:39,670
care există multe alte abordări
s-ar putea alege.

1579
01:12:39,670 --> 01:12:41,185
Asta răspunde la întrebarea dvs.?

1580
01:12:41,185 --> 01:12:41,660
>> OK.

1581
01:12:41,660 --> 01:12:42,910
Carlos.

1582
01:12:42,910 --> 01:12:46,130

1583
01:12:46,130 --> 01:12:47,720
Linear de sondare ar implica -

1584
01:12:47,720 --> 01:12:51,913
în cazul în care am găsit-o coliziune la zero, ne-am
ar arăta în locul următor pentru a vedea dacă

1585
01:12:51,913 --> 01:12:54,310
a fost deschis și a pus-o acolo.

1586
01:12:54,310 --> 01:12:57,320
Și apoi ne-am uita la sport următor și
a se vedea dacă a fost deschisă și a pus-o acolo.

1587
01:12:57,320 --> 01:12:59,780
Așa că am găsi următorul disponibile
loc deschis și a pus-o acolo.

1588
01:12:59,780 --> 01:13:02,580

1589
01:13:02,580 --> 01:13:03,890
Orice alte întrebări?

1590
01:13:03,890 --> 01:13:05,370
Da, Avi.

1591
01:13:05,370 --> 01:13:07,490
>> Audiența: Ca o continuare la faptul că,
ce vrei sa spui de la fața locului viitor?

1592
01:13:07,490 --> 01:13:10,250
În tabelul hash sau într-o listă înlănțuită.

1593
01:13:10,250 --> 01:13:12,100
>> JASON Hirschhorn: Pentru liniar
programare, liste legate.

1594
01:13:12,100 --> 01:13:13,400
Următorul loc pe tabelul hash.

1595
01:13:13,400 --> 01:13:13,820
>> Audiența: OK.

1596
01:13:13,820 --> 01:13:17,570
Deci, tabelul hash ar fi
inițializat la dimensiunea -

1597
01:13:17,570 --> 01:13:19,560
cum ar fi numărul de șiruri
că ai fost introducerea?

1598
01:13:19,560 --> 01:13:22,170
>> JASON Hirschhorn: Ai vrea
vrei sa fie foarte mare.

1599
01:13:22,170 --> 01:13:23,910
Da.

1600
01:13:23,910 --> 01:13:27,900
Aici este o imagine a ceea ce ne-am
doar a atras de pe bord.

1601
01:13:27,900 --> 01:13:29,470
Din nou, avem o coliziune aici.

1602
01:13:29,470 --> 01:13:30,710
la 152.

1603
01:13:30,710 --> 01:13:33,570
Și veți vedea am creat
o listă legat de pe ea.

1604
01:13:33,570 --> 01:13:38,200

1605
01:13:38,200 --> 01:13:41,850
Din nou, tabelul hash înlănțuirea separată
abordarea nu este cea pe care o

1606
01:13:41,850 --> 01:13:45,590
trebuie să ia pentru problemele de set
șase dar este una care o mulțime de

1607
01:13:45,590 --> 01:13:47,100
elevii au tendința de a lua.

1608
01:13:47,100 --> 01:13:51,140
Deci, pe această notă, să ne vorbim pe scurt
înainte de a ne capul afară de problema șase,

1609
01:13:51,140 --> 01:13:52,160
și apoi voi împărtăși o poveste cu tine.

1610
01:13:52,160 --> 01:13:55,120
Avem trei minute.

1611
01:13:55,120 --> 01:13:55,750
>> Problema stabilit șase.

1612
01:13:55,750 --> 01:13:57,790
Ai patru funcții -

1613
01:13:57,790 --> 01:14:02,430
încărcare, verificați, dimensiune, și descărcare.

1614
01:14:02,430 --> 01:14:03,380
Încărcare -

1615
01:14:03,380 --> 01:14:07,120
bine, am fost de gând
peste sarcină tocmai acum.

1616
01:14:07,120 --> 01:14:09,330
Am atras sarcina pe bord.

1617
01:14:09,330 --> 01:14:13,230
Și chiar am început de codificare o mulțime de
introducerea într-o listă legat.

1618
01:14:13,230 --> 01:14:18,020
Deci, sarcina nu este cu mult mai mult decât
ceea ce ne-am face doar.

1619
01:14:18,020 --> 01:14:21,070
>> Verificare este dată ai
ceva încărcat.

1620
01:14:21,070 --> 01:14:22,580
Este același proces ca aceasta.

1621
01:14:22,580 --> 01:14:26,845
Aceleași primele două părți în cazul în care arunca
ceva în funcția de distribuire

1622
01:14:26,845 --> 01:14:29,190
și să obțină valoarea sa.

1623
01:14:29,190 --> 01:14:30,700
Dar acum nu-l introduce.

1624
01:14:30,700 --> 01:14:33,350
Acum suntem în căutarea pentru el.

1625
01:14:33,350 --> 01:14:37,130
Am mostre de cod scris pentru găsirea
ceva într-o listă legat.

1626
01:14:37,130 --> 01:14:38,250
Am să vă încurajez pentru a practica acest lucru.

1627
01:14:38,250 --> 01:14:43,000
Dar găsirea intuitiv ceva este
destul de similar cu introducerea ceva.

1628
01:14:43,000 --> 01:14:46,540
Într-adevăr, am desenat o imagine a găsi
ceva într-o listă legată, în mișcare

1629
01:14:46,540 --> 01:14:48,910
prin intermediul până când a ajuns la sfârșitul anului.

1630
01:14:48,910 --> 01:14:52,430
Și dacă ai până la capăt și nu a putut
se pare, atunci ea nu e acolo.

1631
01:14:52,430 --> 01:14:55,400
Deci, asta e cec, în esență.

1632
01:14:55,400 --> 01:14:57,030
>> Următorul este dimensiunea.

1633
01:14:57,030 --> 01:14:57,910
Să trecem peste dimensiune.

1634
01:14:57,910 --> 01:15:00,040
În cele din urmă ați descărca.

1635
01:15:00,040 --> 01:15:02,890
Descarcare este unul care nu au atras
pe bord sau codificate încă.

1636
01:15:02,890 --> 01:15:05,990
Dar am să vă încurajez să încercați să-l codificare
în eșantionul nostru legat Lista exemplu.

1637
01:15:05,990 --> 01:15:11,440
Dar descărca intuitiv
este similar cu gratuit -

1638
01:15:11,440 --> 01:15:14,010
sau vreau să spun este similară pentru a verifica.

1639
01:15:14,010 --> 01:15:17,350
Cu excepția acum de fiecare dată când te duci
prin, tu nu esti pur si simplu de verificare a

1640
01:15:17,350 --> 01:15:19,090
a se vedea dacă aveți o valoare acolo.

1641
01:15:19,090 --> 01:15:22,490
Dar sunteți luați ca nod și
eliberându-se, în esență.

1642
01:15:22,490 --> 01:15:23,610
Asta e ceea ce descărcare îți cere să faci.

1643
01:15:23,610 --> 01:15:24,670
Tot gratuit ai malloced.

1644
01:15:24,670 --> 01:15:27,480
Deci, te duci prin toata lista
din nou, merge prin toată hash

1645
01:15:27,480 --> 01:15:27,760
masă din nou.

1646
01:15:27,760 --> 01:15:29,240
De data aceasta nu se verifica
pentru a vedea ce este acolo.

1647
01:15:29,240 --> 01:15:31,080
Doar elibera ceea ce-i acolo.

1648
01:15:31,080 --> 01:15:33,260
>> Și, în sfârșit dimensiune.

1649
01:15:33,260 --> 01:15:34,350
Dimensiune ar trebui să fie puse în aplicare.

1650
01:15:34,350 --> 01:15:35,590
Dacă nu pune în aplicare dimensiune -

1651
01:15:35,590 --> 01:15:36,250
Eu voi spune ca aceasta.

1652
01:15:36,250 --> 01:15:39,740
Dacă nu pune în aplicare dimensiune în exact
o linie de cod, inclusiv

1653
01:15:39,740 --> 01:15:43,760
reveni declarație, sunteți
face dimensiunea incorect.

1654
01:15:43,760 --> 01:15:47,170
Deci, asigurați-vă că dimensiunea, de proiectare complet
puncte, o faci în exact o

1655
01:15:47,170 --> 01:15:49,970
linie de cod, inclusiv
declarația de returnare.

1656
01:15:49,970 --> 01:15:52,450
>> Și nu bagajele încă, Akchar.

1657
01:15:52,450 --> 01:15:53,700
Castor Eager.

1658
01:15:53,700 --> 01:15:55,820

1659
01:15:55,820 --> 01:16:01,300
Am vrut să-ți mulțumesc baieti
pentru a veni la secțiune.

1660
01:16:01,300 --> 01:16:02,550
Au un Halloween fericit.

1661
01:16:02,550 --> 01:16:05,300

1662
01:16:05,300 --> 01:16:05,960
Acesta este costumul meu.

1663
01:16:05,960 --> 01:16:08,850
Voi purta acest joi
dacă te văd la ore de birou.

1664
01:16:08,850 --> 01:16:14,640
Și dacă ești curios despre ceva mai mult
fundal ca la acest costum, se simt

1665
01:16:14,640 --> 01:16:19,135
liber pentru a verifica 2011 Secțiunea
pentru o poveste despre de ce sunt

1666
01:16:19,135 --> 01:16:20,900
purtând costumul dovleac.

1667
01:16:20,900 --> 01:16:23,680
Și aceasta este o poveste tristă.

1668
01:16:23,680 --> 01:16:27,050
Deci, asigurați-vă că aveți
unele tesuturile din jur.

1669
01:16:27,050 --> 01:16:28,680
Dar pe care, dacă aveți orice
întrebări voi lipi în jurul

1670
01:16:28,680 --> 01:16:29,960
în afara după secțiune.

1671
01:16:29,960 --> 01:16:31,510
Mult noroc pe probleme stabilit șase.

1672
01:16:31,510 --> 01:16:33,540
Și, ca întotdeauna, în cazul în care aveți orice
întrebări, să-mi spuneți.

1673
01:16:33,540 --> 01:16:35,584