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

2
00:00:08,250 --> 00:00:12,680
>> JASON HIRSCHHORN: Velkommen alle
til § Seven.

3
00:00:12,680 --> 00:00:15,040
Vi er i uge syv af kurset.

4
00:00:15,040 --> 00:00:18,440
Og denne kommende torsdag
er Halloween, så jeg

5
00:00:18,440 --> 00:00:21,420
klædt ud som et græskar.

6
00:00:21,420 --> 00:00:23,460
Jeg kunne ikke bøje og sættes på
mine sko, så det er derfor jeg er

7
00:00:23,460 --> 00:00:25,660
blot iført sokker.

8
00:00:25,660 --> 00:00:29,220
Jeg er også ikke at bære noget under
dette, så kan jeg ikke tage det fra, hvis det er

9
00:00:29,220 --> 00:00:29,950
distraherende for dig.

10
00:00:29,950 --> 00:00:31,860
Jeg undskylder på forhånd for det.

11
00:00:31,860 --> 00:00:33,170
Du behøver ikke at forestille
hvad der foregår.

12
00:00:33,170 --> 00:00:34,240
Jeg bærer boksere.

13
00:00:34,240 --> 00:00:36,170
Så det er alle gode.

14
00:00:36,170 --> 00:00:41,120
>> Jeg har en længere historie om, hvorfor jeg er
klædt som et græskar, men jeg har tænkt mig at

15
00:00:41,120 --> 00:00:45,110
gemme det til senere i dette afsnit
fordi jeg ønsker at komme i gang.

16
00:00:45,110 --> 00:00:47,720
Vi har en masse spændende ting
at gå over denne uge.

17
00:00:47,720 --> 00:00:51,810
De fleste af dem relaterer sig direkte til dette
uges problem sæt, stavefejl.

18
00:00:51,810 --> 00:00:54,680
Vi kommer til at være at gå over forbundet
lister og hash-tabeller

19
00:00:54,680 --> 00:00:57,160
for hele afsnittet.

20
00:00:57,160 --> 00:01:02,490
Jeg sætter denne liste op hver uge en liste over
ressourcer for dig at hjælpe dig med

21
00:01:02,490 --> 00:01:04,120
materialet på dette kursus.

22
00:01:04,120 --> 00:01:07,600
Hvis der på et tab, eller hvis udkig efter nogle
mere information, så tjek en af

23
00:01:07,600 --> 00:01:09,930
disse ressourcer.

24
00:01:09,930 --> 00:01:14,530
>> Igen, pset6 er stavefejl,
denne uges PSET.

25
00:01:14,530 --> 00:01:17,690
Og det også opfordrer dig, og jeg
opmuntre dig, at bruge nogle andre

26
00:01:17,690 --> 00:01:20,320
ressourcer specifikt til denne PSET.

27
00:01:20,320 --> 00:01:23,390
Især de tre jeg har
noteret op på skærmen -

28
00:01:23,390 --> 00:01:27,160
gdb, som vi har været bekendt med
og er blevet brugt et stykke tid nu, er

29
00:01:27,160 --> 00:01:29,270
kommer til at være meget nyttige i denne uge.

30
00:01:29,270 --> 00:01:30,190
Så jeg sætte det op her.

31
00:01:30,190 --> 00:01:32,910
Men når du arbejder med C,
bør du altid bruge gdb til

32
00:01:32,910 --> 00:01:34,430
debug dine programmer.

33
00:01:34,430 --> 00:01:36,660
I denne uge også Valgrind.

34
00:01:36,660 --> 00:01:38,535
Er der nogen vide, hvad valgrind gør?

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

36
00:01:42,184 --> 00:01:43,890
>> PUBLIKUM: Den kontrollerer for memory leaks?

37
00:01:43,890 --> 00:01:45,950
>> JASON HIRSCHHORN: Valgrind
checks for memory leaks.

38
00:01:45,950 --> 00:01:49,970
Så hvis du allokere noget i dit
program, du beder for hukommelse.

39
00:01:49,970 --> 00:01:52,920
Ved slutningen af ​​dit program, du har
at skrive frit om alt, hvad du har

40
00:01:52,920 --> 00:01:54,800
malloced at give hukommelsen tilbage.

41
00:01:54,800 --> 00:01:58,420
Hvis du ikke skriver fri ved slutningen og
dit program kommer til en konklusion,

42
00:01:58,420 --> 00:02:00,000
Alt vil automatisk
blive befriet.

43
00:02:00,000 --> 00:02:02,340
Og for små programmer, er det
ikke så stor en aftale.

44
00:02:02,340 --> 00:02:05,250
Men hvis du skriver en længere indkøringsfase
program, der ikke holde op,

45
00:02:05,250 --> 00:02:09,180
nødvendigvis, i et par minutter eller et
par sekunder, så memory leaks

46
00:02:09,180 --> 00:02:10,710
kan blive en stor aftale.

47
00:02:10,710 --> 00:02:14,940
>> Så for pset6 er det forventningen, at
vil du have nul memory leaks med

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

49
00:02:15,910 --> 00:02:18,690
At kontrollere for memory leaks, køre valgrind
og det vil give dig nogle gode

50
00:02:18,690 --> 00:02:21,190
output lade dig vide, om
eller ikke alt var gratis.

51
00:02:21,190 --> 00:02:23,940
Vi vil øve med den senere
i dag, forhåbentlig.

52
00:02:23,940 --> 00:02:25,790
>> Endelig kommandoen diff.

53
00:02:25,790 --> 00:02:28,900
Du brugte noget der ligner det
i pset5 med peek værktøj.

54
00:02:28,900 --> 00:02:30,780
Tilladt dig at kigge indenfor.

55
00:02:30,780 --> 00:02:33,400
Du brugte også diff, også, per
problemet indstillet spec.

56
00:02:33,400 --> 00:02:35,950
Men i givet mulighed for at
sammenligne to filer.

57
00:02:35,950 --> 00:02:39,180
Du kan sammenligne bitmapfil og
info-headers i en personale-løsning og

58
00:02:39,180 --> 00:02:42,200
din løsning i pset5 hvis
du vælger at bruge det.

59
00:02:42,200 --> 00:02:44,030
Diff vil tillade dig at
gøre det, så godt.

60
00:02:44,030 --> 00:02:48,620
Du kan sammenligne det rigtige svar for
denne uges problem indstillet til dit svar

61
00:02:48,620 --> 00:02:52,210
og se om det linjer op, eller se
hvor fejlene.

62
00:02:52,210 --> 00:02:55,870
>> Så det er tre gode værktøjer, som
du skal bruge til denne uge, og

63
00:02:55,870 --> 00:02:58,130
helt sikkert tjekke dit program
med disse tre værktøjer

64
00:02:58,130 --> 00:03:00,520
før du tænder det i.

65
00:03:00,520 --> 00:03:04,650
Igen, som jeg har nævnt hver uge,
hvis du har feedback til mig - både

66
00:03:04,650 --> 00:03:06,470
positiv og konstruktiv -

67
00:03:06,470 --> 00:03:09,930
velkommen til at hovedet til hjemmesiden
i bunden af ​​dette dias

68
00:03:09,930 --> 00:03:11,270
og input det der.

69
00:03:11,270 --> 00:03:13,440
Jeg virkelig sætter pris på enhver
og alle tilbagemeldinger.

70
00:03:13,440 --> 00:03:17,360
Og hvis du giver mig specifikke ting,
Jeg kan gøre for at forbedre eller at jeg er

71
00:03:17,360 --> 00:03:21,350
klarer sig godt, at du gerne vil have mig til
fortsætter, tager jeg det til hjerte og

72
00:03:21,350 --> 00:03:24,040
virkelig forsøger hårdt at lytte
til din feedback.

73
00:03:24,040 --> 00:03:27,720
Jeg kan ikke love jeg tænkt mig at gøre
alting, selv om, som at bære en

74
00:03:27,720 --> 00:03:30,700
græskar kostume hver uge.

75
00:03:30,700 --> 00:03:34,020
>> Så vi kommer til at tilbringe størstedelen af
sektion, som jeg nævnte, tale om

76
00:03:34,020 --> 00:03:37,240
hægtede lister og hash-tabeller, som
vil være direkte anvendelig for

77
00:03:37,240 --> 00:03:38,780
problem indstille denne uge.

78
00:03:38,780 --> 00:03:42,580
Hægtede lister vi vil gå over relativt
hurtigt, fordi vi har brugt en retfærdig bit

79
00:03:42,580 --> 00:03:44,930
af tid at gå over den i afsnit.

80
00:03:44,930 --> 00:03:48,680
Og så vi får lige ind i
kodning problemer for hægtede lister.

81
00:03:48,680 --> 00:03:52,740
Og så i slutningen, vi vil tale om
hash tabeller og hvordan de gælder for denne

82
00:03:52,740 --> 00:03:55,280
uges problem indstillet.

83
00:03:55,280 --> 00:03:57,560
>> Du har set denne kode før.

84
00:03:57,560 --> 00:04:02,730
Dette er en struct, og det definerer
noget nyt kaldet en knude.

85
00:04:02,730 --> 00:04:10,660
Og inden for en node der er et helt tal
lige her og der er en pointer til

86
00:04:10,660 --> 00:04:11,830
anden node.

87
00:04:11,830 --> 00:04:12,790
Vi har set det før.

88
00:04:12,790 --> 00:04:14,830
Dette har været kommer op til
et par uger nu.

89
00:04:14,830 --> 00:04:18,680
Det kombinerer pegepinde, som vi har været
arbejder med, og structs, som tillader

90
00:04:18,680 --> 00:04:22,079
os til at kombinere to forskellige
ting i én datatype.

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

92
00:04:24,830 --> 00:04:26,490
>> Der er en masse i gang på skærmen.

93
00:04:26,490 --> 00:04:30,220
Men det hele bør være relativt
fortrolig med dig.

94
00:04:30,220 --> 00:04:33,810
På den første linje, vi
erklære en ny node.

95
00:04:33,810 --> 00:04:41,650
Og så inde i den nye node, sæt jeg
heltallet i dette knudepunkt til én.

96
00:04:41,650 --> 00:04:44,950
Vi ser på den næste linje jeg gør en
printf kommandoen, men jeg har nedtonet

97
00:04:44,950 --> 00:04:48,080
printf kommandoen, fordi de virkelig
vigtig del er denne linje her -

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

99
00:04:50,020 --> 00:04:51,270
Hvad betyder prik betyder?

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

101
00:04:53,810 --> 00:04:57,240
>> PUBLIKUM: Gå til noden og
vurdere værdien n for det.

102
00:04:57,240 --> 00:04:58,370
>> JASON HIRSCHHORN: Det er
helt rigtigt.

103
00:04:58,370 --> 00:05:03,300
Dot betyder adgang n del
af denne nye knudepunkt.

104
00:05:03,300 --> 00:05:05,690
Denne næste linie gør hvad?

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
>> PUBLIKUM: Det skaber en anden node
der vil pege på den nye knudepunkt.

108
00:05:21,910 --> 00:05:24,870
>> JASON HIRSCHHORN: så det ikke
oprette en ny node.

109
00:05:24,870 --> 00:05:26,120
Det skaber en hvad?

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

111
00:05:28,300 --> 00:05:29,300
>> PUBLIKUM: En pointer.

112
00:05:29,300 --> 00:05:33,460
>> JASON HIRSCHHORN: En pointer til en knude,
som angivet af denne node * her.

113
00:05:33,460 --> 00:05:34,800
Så det skaber en pointer til et knudepunkt.

114
00:05:34,800 --> 00:05:37,490
Og hvilken node er det peger
til Michael?

115
00:05:37,490 --> 00:05:38,440
>> PUBLIKUM: Ny knude?

116
00:05:38,440 --> 00:05:39,240
>> JASON HIRSCHHORN: Ny knude.

117
00:05:39,240 --> 00:05:43,020
Og det peger der, fordi vi har
givet den adressen på nye node.

118
00:05:43,020 --> 00:05:45,820
Og nu i denne linje, vi ser
to forskellige måder

119
00:05:45,820 --> 00:05:46,910
udtrykker det samme.

120
00:05:46,910 --> 00:05:49,650
Og jeg ønskede at påpege, hvordan disse
to ting er ens.

121
00:05:49,650 --> 00:05:54,740
I første linje, vi dereferering
markøren.

122
00:05:54,740 --> 00:05:55,830
Så vi går til node.

123
00:05:55,830 --> 00:05:56,830
Det er, hvad denne stjerne betyder.

124
00:05:56,830 --> 00:05:57,930
Vi har set det før med pointere.

125
00:05:57,930 --> 00:05:59,280
Gå til dette knudepunkt.

126
00:05:59,280 --> 00:06:00,370
Det er i parentes.

127
00:06:00,370 --> 00:06:04,610
Og derefter få adgang via prik operatør
n element i denne knude.

128
00:06:04,610 --> 00:06:08,430
>> Så det tager syntaksen
så vi lige nu og her

129
00:06:08,430 --> 00:06:09,670
bruge den med en pegepind.

130
00:06:09,670 --> 00:06:13,730
Selvfølgelig, det får lidt travlt, hvis
du skriver disse parenteser -

131
00:06:13,730 --> 00:06:14,940
at stjerne og prik.

132
00:06:14,940 --> 00:06:16,220
Det får lidt travlt.

133
00:06:16,220 --> 00:06:18,500
Så vi har nogle syntaktisk sukker.

134
00:06:18,500 --> 00:06:19,920
Og denne linje lige her -

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
Det gør nøjagtig de samme ting.

138
00:06:28,000 --> 00:06:30,840
Så disse to linjer kode er
ækvivalent og vil gøre

139
00:06:30,840 --> 00:06:31,650
præcis de samme ting.

140
00:06:31,650 --> 00:06:34,210
>> Men jeg ønskede at påpege dem ud før
vi går videre, så du forstår

141
00:06:34,210 --> 00:06:39,000
der virkelig denne ting lige her er
bare syntaktisk sukker til dereferere

142
00:06:39,000 --> 00:06:44,200
markøren, og derefter gå til
n del af denne struct.

143
00:06:44,200 --> 00:06:45,525
Eventuelle spørgsmål vedrørende denne slide?

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
>> Så vi kommer til at gå igennem et par
af operationer, som du kan gøre på

147
00:06:58,510 --> 00:06:59,730
hægtede lister.

148
00:06:59,730 --> 00:07:05,770
En sammenkædet liste, husker, er en serie af
knudepunkter, der peger på hinanden.

149
00:07:05,770 --> 00:07:12,470
Og vi generelt starter med en pegepind
kaldes hoved generelt, der peger på

150
00:07:12,470 --> 00:07:14,040
den første ting på listen.

151
00:07:14,040 --> 00:07:18,900
Så på den første linje her, vi
har vores oprindelige L først.

152
00:07:18,900 --> 00:07:21,370
Så ting du kan tænke på - det
tekst lige her du kan tænke på som

153
00:07:21,370 --> 00:07:23,560
bare markøren vi har gemt
et eller andet sted, der peger

154
00:07:23,560 --> 00:07:24,670
til det første element.

155
00:07:24,670 --> 00:07:27,500
Og i denne linkede liste
vi har fire noder.

156
00:07:27,500 --> 00:07:29,530
Hver node er en stor kasse.

157
00:07:29,530 --> 00:07:33,430
Jo større kasse inde i store
boks er heltalsdelen.

158
00:07:33,430 --> 00:07:37,400
Og så har vi en pegepind del.

159
00:07:37,400 --> 00:07:39,630
>> Disse bokse er ikke tegnet i
skala, fordi hvor stort er

160
00:07:39,630 --> 00:07:42,320
et heltal i bytes?

161
00:07:42,320 --> 00:07:43,290
Hvor stor nu?

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

163
00:07:43,710 --> 00:07:45,470
Og hvor stor er en pointer?

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

165
00:07:45,940 --> 00:07:48,180
Så virkelig, hvis vi skulle tegne
dette for at skalere begge bokse

166
00:07:48,180 --> 00:07:49,690
ville være den samme størrelse.

167
00:07:49,690 --> 00:07:52,870
I dette tilfælde, vi ønsker at indsætte
noget i den linkede liste.

168
00:07:52,870 --> 00:07:57,190
Så du kan se hernede vi indsætter
fem Vi krydse gennem

169
00:07:57,190 --> 00:08:01,310
linkede liste, finde hvor fem
går, og derefter indsætte det.

170
00:08:01,310 --> 00:08:03,560
>> Lad os bryde det ned og gå
en lille smule langsommere.

171
00:08:03,560 --> 00:08:05,510
Jeg har tænkt mig at pege på tavlen.

172
00:08:05,510 --> 00:08:09,930
Så vi har vores knude fem,
vi har skabt i malloc'erers.

173
00:08:09,930 --> 00:08:11,190
Hvorfor er alle griner?

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

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

176
00:08:13,310 --> 00:08:14,820
Så vi har malloced fem.

177
00:08:14,820 --> 00:08:16,310
Vi har oprettet denne node
et andet sted.

178
00:08:16,310 --> 00:08:17,740
Vi har det klar til at gå.

179
00:08:17,740 --> 00:08:20,130
Vi starter på forsiden af
vores liste med to.

180
00:08:20,130 --> 00:08:22,380
Og vi ønsker at indsætte
i en sorteret måde.

181
00:08:22,380 --> 00:08:27,550
>> Så hvis vi ser to, og vi ønsker at sætte
i fem, hvad gør vi, når vi ser

182
00:08:27,550 --> 00:08:28,800
noget mindre end os?

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

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

185
00:08:33,520 --> 00:08:36,750
Vi ønsker at indsætte fem ind i denne
linkede liste, holde det sorteret.

186
00:08:36,750 --> 00:08:37,520
Vi ser nummer to.

187
00:08:37,520 --> 00:08:38,769
Så hvad gør vi?

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

189
00:08:39,179 --> 00:08:40,679
>> PUBLIKUM: Ring markøren
til det næste knudepunkt.

190
00:08:40,679 --> 00:08:42,530
>> JASON HIRSCHHORN: Og hvorfor gør
vi gå til den næste?

191
00:08:42,530 --> 00:08:45,970
>> PUBLIKUM: Fordi det er den
næste node i listen.

192
00:08:45,970 --> 00:08:48,310
Og vi ved kun, at anden placering.

193
00:08:48,310 --> 00:08:50,410
>> JASON HIRSCHHORN Og fem er større
end to, i særdeleshed.

194
00:08:50,410 --> 00:08:51,600
Fordi vi ønsker at holde det sorteres.

195
00:08:51,600 --> 00:08:52,730
Så fem er større end to.

196
00:08:52,730 --> 00:08:54,460
Så vi gå videre til den næste.

197
00:08:54,460 --> 00:08:55,240
Og nu kommer vi til fire.

198
00:08:55,240 --> 00:08:56,490
Og hvad sker der, når vi når fire?

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

200
00:08:58,920 --> 00:09:00,310
>> Fem er større end fire.

201
00:09:00,310 --> 00:09:01,460
Så vi holde ud.

202
00:09:01,460 --> 00:09:03,110
Og nu vi er ved seks.

203
00:09:03,110 --> 00:09:04,360
Og hvad ser vi på seks?

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

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

206
00:09:09,608 --> 00:09:10,544
>> PUBLIKUM: Seks er større end fem.

207
00:09:10,544 --> 00:09:11,480
>> JASON HIRSCHHORN: Six er
større end fem.

208
00:09:11,480 --> 00:09:13,660
Så det er, hvor vi ønsker
at indsætte fem.

209
00:09:13,660 --> 00:09:17,320
Men husk på, at hvis vi
kun har én pointer her -

210
00:09:17,320 --> 00:09:19,840
dette er vores ekstra pointer, der er
gennemkører gennem listen.

211
00:09:19,840 --> 00:09:21,860
Og vi peger på seks.

212
00:09:21,860 --> 00:09:25,010
Vi har mistet overblikket over, hvad
kommer før seks.

213
00:09:25,010 --> 00:09:29,130
Så hvis vi ønsker at indsætte noget i
denne liste holde det sorteret, vi

214
00:09:29,130 --> 00:09:31,630
sikkert brug for, hvor mange pointers?

215
00:09:31,630 --> 00:09:32,280
>> PUBLIKUM: Two.

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

217
00:09:32,920 --> 00:09:35,720
En til at holde styr på den aktuelle
en og en til at holde styr på

218
00:09:35,720 --> 00:09:37,050
den foregående.

219
00:09:37,050 --> 00:09:38,450
Dette er kun en enkelt bundet listen.

220
00:09:38,450 --> 00:09:39,670
Det går kun én retning.

221
00:09:39,670 --> 00:09:43,220
Hvis vi havde en dobbelt linket liste, hvor
alt var at pege på ting

222
00:09:43,220 --> 00:09:46,240
efter det, og ting, før det, så
vi ikke behøver at gøre det.

223
00:09:46,240 --> 00:09:49,350
Men i dette tilfælde ønsker vi ikke at tabe
styr på, hvad der kom før os i tilfælde

224
00:09:49,350 --> 00:09:53,350
vi nødt til at indsætte fem sted
i midten.

225
00:09:53,350 --> 00:09:55,610
Sig vi indsætte ni.

226
00:09:55,610 --> 00:09:57,260
Hvad ville der ske, når
vi kom til otte?

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

228
00:10:01,860 --> 00:10:04,880
>> PUBLIKUM: Du er nødt til at
få at nulpunktet.

229
00:10:04,880 --> 00:10:07,820
I stedet for at have null punkt, du ville have
at tilføje et element og derefter har

230
00:10:07,820 --> 00:10:09,216
det peger på ni.

231
00:10:09,216 --> 00:10:09,700
>> JASON Hirschorn: Præcis.

232
00:10:09,700 --> 00:10:10,600
Så vi får otte.

233
00:10:10,600 --> 00:10:13,140
Vi når til slutningen af ​​listen, fordi
dette peger til null.

234
00:10:13,140 --> 00:10:16,330
Og nu, i stedet for at have det peger på
null vi har det pege på vores nye node.

235
00:10:16,330 --> 00:10:19,870
Og vi sætter markøren i
vores nye node til null.

236
00:10:19,870 --> 00:10:21,445
Er der nogen har nogen spørgsmål
om indsættelse?

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

238
00:10:25,620 --> 00:10:28,100
Hvad hvis jeg er ligeglad
at listen sorteres?

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

240
00:10:31,701 --> 00:10:34,350
>> PUBLIKUM: Stick det på
starten eller slutningen.

241
00:10:34,350 --> 00:10:35,510
>> JASON Hirschorn: Hold det på
begyndelsen eller slutningen.

242
00:10:35,510 --> 00:10:37,276
Hvilken en skal vi gøre?

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

244
00:10:38,770 --> 00:10:41,020
Hvorfor ende?

245
00:10:41,020 --> 00:10:43,250
>> PUBLIKUM: Da starten
er allerede fyldt.

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

247
00:10:43,575 --> 00:10:44,360
Begyndelsen er allerede fyldt.

248
00:10:44,360 --> 00:10:46,090
Hvem ønsker at argumentere imod Bobby.

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

250
00:10:47,290 --> 00:10:48,910
>> PUBLIKUM: Nå du sandsynligvis ønsker at
holde det i starten, fordi

251
00:10:48,910 --> 00:10:50,140
ellers hvis du sætter det på
enden du er nødt til

252
00:10:50,140 --> 00:10:51,835
krydse hele listen.

253
00:10:51,835 --> 00:10:52,990
>> JASON Hirschorn: Præcis.

254
00:10:52,990 --> 00:10:57,970
Så hvis vi tænker på runtime, den
runtime indsætte slutningen

255
00:10:57,970 --> 00:11:00,110
ville være n, størrelsen af ​​dette.

256
00:11:00,110 --> 00:11:03,080
Hvad er big O runtime indsætte
i starten?

257
00:11:03,080 --> 00:11:04,170
Konstant tid.

258
00:11:04,170 --> 00:11:07,075
Så hvis du er ligeglad om at holde
noget ordnet, meget bedre til bare

259
00:11:07,075 --> 00:11:08,420
indsætte i begyndelsen af ​​denne liste.

260
00:11:08,420 --> 00:11:10,320
Og der kan gøres i konstant tid.

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
Næste operation er at finde, som andre -
Vi har formuleret dette som søgning.

264
00:11:18,870 --> 00:11:22,470
Men vi kommer til at se gennem
forbundet liste til en genstand.

265
00:11:22,470 --> 00:11:26,000
I gutter har set kode for
søg før i foredraget.

266
00:11:26,000 --> 00:11:29,490
Men vi slags gjorde det bare med
indsætte, eller i det mindste at indsætte

267
00:11:29,490 --> 00:11:30,580
noget sorteres.

268
00:11:30,580 --> 00:11:36,350
Du ser igennem, går node efter node,
indtil du finder det nummer, du

269
00:11:36,350 --> 00:11:37,780
udkig efter.

270
00:11:37,780 --> 00:11:39,670
Hvad sker der, hvis du kommer
slutningen af ​​listen?

271
00:11:39,670 --> 00:11:43,020
Sig Jeg leder efter ni, og jeg
nå enden af ​​listen.

272
00:11:43,020 --> 00:11:44,270
Hvad gør vi?

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

274
00:11:47,147 --> 00:11:48,110
>> PUBLIKUM: Tilbage falsk?

275
00:11:48,110 --> 00:11:48,690
>> JASON Hirschorn: Tilbage falsk.

276
00:11:48,690 --> 00:11:49,960
Vi kunne ikke finde det.

277
00:11:49,960 --> 00:11:52,010
Hvis du når til slutningen af ​​listen og
du kunne ikke finde det nummer, du er

278
00:11:52,010 --> 00:11:54,170
leder efter, det er der ikke.

279
00:11:54,170 --> 00:11:55,420
Eventuelle spørgsmål om at finde?

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

281
00:11:59,530 --> 00:12:04,615
Hvis dette var en sorteret liste, hvad ville
være forskellige for vores søgning?

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

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

284
00:12:08,103 --> 00:12:10,600
>> PUBLIKUM: Det vil finde den første værdi
der er større end den

285
00:12:10,600 --> 00:12:12,390
du leder efter, og
derefter vende tilbage falsk.

286
00:12:12,390 --> 00:12:13,190
>> JASON Hirschorn: Præcis.

287
00:12:13,190 --> 00:12:17,310
Så hvis det er en sorteret liste, hvis vi kommer til
noget, der er større end hvad

288
00:12:17,310 --> 00:12:20,180
vi leder efter, har vi ikke brug for
holde ud til slutningen af ​​listen.

289
00:12:20,180 --> 00:12:24,060
Vi kan på det tidspunkt return false
fordi vi ikke kommer til at finde den.

290
00:12:24,060 --> 00:12:27,340
Spørgsmålet er nu, har vi talt om
holde hægtede lister sorteres,

291
00:12:27,340 --> 00:12:28,180
holde dem usorteret.

292
00:12:28,180 --> 00:12:30,050
Det kommer til at være noget, du er
sandsynligvis nødt til at tænke over

293
00:12:30,050 --> 00:12:34,240
når kodning problem sæt fem, hvis du
vælge en hash tabel med separat

294
00:12:34,240 --> 00:12:36,360
kæde tilgang, der
vi vil tale om senere.

295
00:12:36,360 --> 00:12:41,400
>> Men er det værd at holde listen
sorteret og derefter kunne måske have

296
00:12:41,400 --> 00:12:42,310
hurtigere søgninger?

297
00:12:42,310 --> 00:12:47,220
Eller er det bedre til hurtigt at indsætte
noget i konstant runtime, men derefter

298
00:12:47,220 --> 00:12:48,430
har længere søger?

299
00:12:48,430 --> 00:12:52,250
Det er en afvejning, lige der, at du
komme til at beslutte, hvad der er mere passende

300
00:12:52,250 --> 00:12:53,590
til dit specifikke problem.

301
00:12:53,590 --> 00:12:56,680
Og der er ikke nødvendigvis en
helt rigtige svar.

302
00:12:56,680 --> 00:12:59,520
Men det er helt sikkert en beslutning, du får
at gøre, og sandsynligvis god til at forsvare

303
00:12:59,520 --> 00:13:05,270
der i, siger, en kommentar eller to, hvorfor
du vælger den ene frem for den anden.

304
00:13:05,270 --> 00:13:06,490
>> Endelig sletning.

305
00:13:06,490 --> 00:13:08,100
Vi har set at slette.

306
00:13:08,100 --> 00:13:09,180
Det svarer til søgningen.

307
00:13:09,180 --> 00:13:11,020
Vi ser for elementet.

308
00:13:11,020 --> 00:13:12,390
Sig vi forsøger at slette seks.

309
00:13:12,390 --> 00:13:14,450
Så finder vi seks lige her.

310
00:13:14,450 --> 00:13:18,860
De ting, vi er nødt til at sikre, at vi
gøre, er at uanset hvad der peger på

311
00:13:18,860 --> 00:13:21,220
seks - som vi ser i trin
to hernede -

312
00:13:21,220 --> 00:13:26,500
uanset peger til seks behov til
spring seks nu og ændres til

313
00:13:26,500 --> 00:13:28,160
uanset seks peger på.

314
00:13:28,160 --> 00:13:31,410
Vi ønsker ikke at nogensinde forældreløs resten af
vores liste ved at glemme at indstille det

315
00:13:31,410 --> 00:13:32,960
foregående pointer.

316
00:13:32,960 --> 00:13:35,960
Og så nogle gange, afhængigt
på programmet, de vil bare

317
00:13:35,960 --> 00:13:37,380
slette denne node helt.

318
00:13:37,380 --> 00:13:40,135
Nogle gange vil du ønsker at vende tilbage
den værdi, der er i denne knude.

319
00:13:40,135 --> 00:13:42,490
Så det er, hvordan du sletter værker.

320
00:13:42,490 --> 00:13:44,610
Eventuelle spørgsmål vedrørende slette?

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

322
00:13:51,280 --> 00:13:53,850
>> PUBLIKUM: Så hvis du kommer til at slette
det, ville du bare bruge gratis, fordi

323
00:13:53,850 --> 00:13:55,655
formentlig blev malloced?

324
00:13:55,655 --> 00:13:57,976
>> JASON Hirschorn: Hvis du ønsker at frigøre
noget, der er helt rigtigt, og du

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

326
00:13:58,540 --> 00:14:00,410
Sig vi ønskede at vende tilbage denne værdi.

327
00:14:00,410 --> 00:14:04,010
Vi vender måske tilbage seks og derefter frit
denne node og opkald gratis på den.

328
00:14:04,010 --> 00:14:06,180
Eller vi ville nok kalde fri først
og derefter vende tilbage seks.

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
Så lad os gå videre til at øve kodning.

332
00:14:14,010 --> 00:14:16,090
Vi kommer til at kode tre funktioner.

333
00:14:16,090 --> 00:14:18,260
Den første hedder insert_node.

334
00:14:18,260 --> 00:14:22,170
Så du har kode, som jeg mailede dig, og
hvis du ser dette senere

335
00:14:22,170 --> 00:14:28,020
du kan få adgang til koden i linked.c
på CS50 hjemmeside.

336
00:14:28,020 --> 00:14:30,880
Men i linked.c, er der nogle
skelet kode, der allerede er

337
00:14:30,880 --> 00:14:32,280
skrevet til dig.

338
00:14:32,280 --> 00:14:34,560
Og så er der et par funktioner
du nødt til at skrive.

339
00:14:34,560 --> 00:14:36,380
>> Først vil vi
skrive insert_node.

340
00:14:36,380 --> 00:14:39,800
Og hvad insert_node gør
Er indsætter et heltal.

341
00:14:39,800 --> 00:14:42,440
Og du giver heltal
i en sammenkædet liste.

342
00:14:42,440 --> 00:14:45,470
Og i særdeleshed, du har brug for
at holde listen sorteres

343
00:14:45,470 --> 00:14:47,650
fra den mindste til den største.

344
00:14:47,650 --> 00:14:51,360
Også, behøver du ikke ønsker at
indsætte dubletter.

345
00:14:51,360 --> 00:14:54,600
Endelig, som du kan se insert_node
returnerer en bool.

346
00:14:54,600 --> 00:14:57,140
Så du er formodes for at lade brugeren vide
om indsatsen var eller ikke

347
00:14:57,140 --> 00:15:00,800
succes ved at returnere sandt eller falsk.

348
00:15:00,800 --> 00:15:02,580
Ved afslutningen af ​​dette program -

349
00:15:02,580 --> 00:15:05,750
og til dette tidspunkt behøver du ikke
at bekymre sig om at frigøre noget.

350
00:15:05,750 --> 00:15:11,790
Så alt du gør, er at tage et heltal
og indsætte det i en liste.

351
00:15:11,790 --> 00:15:13,890
>> Det er, hvad jeg beder dig om at gøre nu.

352
00:15:13,890 --> 00:15:17,620
Igen i linked.c, som du
alle er skelettet kode.

353
00:15:17,620 --> 00:15:20,980
Og du bør se mod bunden
prøven funktionen erklæring.

354
00:15:20,980 --> 00:15:27,390
Men inden jeg går ind i kodning det
i C, jeg stærkt opfordre dig til at gå

355
00:15:27,390 --> 00:15:29,330
gennem de trin, vi har været
øve hver uge.

356
00:15:29,330 --> 00:15:31,100
Vi har allerede været igennem
et billede af dette.

357
00:15:31,100 --> 00:15:33,380
Så du skal have en vis forståelse
af hvordan det virker.

358
00:15:33,380 --> 00:15:36,590
Men jeg vil opfordre dig til at skrive
nogle pseudokode før dykning i.

359
00:15:36,590 --> 00:15:38,640
Og vi kommer til at gå over
pseudokode som en gruppe.

360
00:15:38,640 --> 00:15:41,470
Og så når du har skrevet din
pseudokode, og når vi har skrevet vores

361
00:15:41,470 --> 00:15:45,850
pseudokode som en gruppe, kan du
gå ind kodning det i C.

362
00:15:45,850 --> 00:15:49,980
>> Som en heads up, den insert_node funktion
er nok den vanskeligste af

363
00:15:49,980 --> 00:15:53,550
de tre vi kommer til at skrive, fordi jeg
tilføjet nogle yderligere begrænsninger for

364
00:15:53,550 --> 00:15:57,190
din programmering, navnlig
du kommer ikke til at indsætte nogen

365
00:15:57,190 --> 00:15:59,880
dubletter og at listen
bør forblive sorteres.

366
00:15:59,880 --> 00:16:02,660
Så dette er en ikke-triviel program
at du skal til at kode.

367
00:16:02,660 --> 00:16:06,470
Og hvorfor tager du ikke 06:55
minutter bare at få arbejde på

368
00:16:06,470 --> 00:16:07,640
pseudokode og koden.

369
00:16:07,640 --> 00:16:09,460
Og så vil vi begynde
går som en gruppe.

370
00:16:09,460 --> 00:16:11,680
Igen, hvis du har spørgsmål bare
hæve din hånd, og jeg vil komme rundt.

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
>> Vi har også generelt gøre disse -

375
00:18:30,120 --> 00:18:32,070
eller jeg ikke udtrykkeligt sige, at du
kan arbejde med mennesker.

376
00:18:32,070 --> 00:18:36,500
Men selvfølgelig, jeg stærkt opfordre dig til,
hvis du har spørgsmål, at spørge

377
00:18:36,500 --> 00:18:39,840
nabo sidder ved siden af ​​dig
eller endda arbejde med nogen

378
00:18:39,840 --> 00:18:40,510
andet, hvis du vil.

379
00:18:40,510 --> 00:18:42,600
Dette behøver ikke at være et individ
tavse aktivitet.

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

381
00:20:11,770 --> 00:20:16,330
>> Lad os starte med at skrive nogle
pseudokode på tavlen.

382
00:20:16,330 --> 00:20:19,395
Hvem kan give mig den første linje i
pseudokode til dette program?

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

384
00:20:22,240 --> 00:20:23,640
Til denne funktion, snarere -
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
>> PUBLIKUM: Så det første jeg gjorde var
oprette en ny pointer til knuden, og jeg

388
00:20:36,560 --> 00:20:41,320
initialiseret det fører til den samme
ting at liste peger på.

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

390
00:20:41,550 --> 00:20:45,190
Så du opretter en ny pointer
til listen, ikke til noden.

391
00:20:45,190 --> 00:20:45,420
>> PUBLIKUM: Right.

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

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

394
00:20:46,540 --> 00:20:48,221
Og hvad vil vi gøre?

395
00:20:48,221 --> 00:20:49,163
Hvad er efter det?

396
00:20:49,163 --> 00:20:50,105
Hvad node?

397
00:20:50,105 --> 00:20:51,050
Vi har ikke et knudepunkt.

398
00:20:51,050 --> 00:20:52,300
Vi skal bare have en værdi.

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

400
00:20:55,918 --> 00:20:58,890
Hvis vi ønsker at indsætte en node, hvad gør vi
nødt til at gøre først, før vi kan endda

401
00:20:58,890 --> 00:20:59,980
tænke indsætter det?

402
00:20:59,980 --> 00:21:00,820
>> PUBLIKUM: Åh, undskyld.

403
00:21:00,820 --> 00:21:02,160
vi nødt til at allokere plads til en knude.

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

405
00:21:02,455 --> 00:21:03,210
Lad os gøre -

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

407
00:21:04,628 --> 00:21:06,065
Kan ikke nå så højt.

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
Vi kommer til at gå ned, og derefter
vi bruger to kolonner.

411
00:21:13,236 --> 00:21:13,732
Jeg kan ikke gå så -

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
Opret en ny node.

415
00:21:25,130 --> 00:21:29,380
Du kan oprette en anden pointer til listen
eller du kan bare bruge listen som den eksisterer.

416
00:21:29,380 --> 00:21:30,720
Du behøver ikke virkelig nødt til at gøre det.

417
00:21:30,720 --> 00:21:31,750
>> Så vi skaber en ny node.

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

419
00:21:32,010 --> 00:21:32,840
Det er, hvad vi gør først.

420
00:21:32,840 --> 00:21:34,870
Hvad er det næste?

421
00:21:34,870 --> 00:21:35,080
>> PUBLIKUM: Vent.

422
00:21:35,080 --> 00:21:38,330
Skal vi lave en ny node nu eller
skal vi vente med at sørge for, at

423
00:21:38,330 --> 00:21:42,260
der er ingen dubletter af node
på listen, før vi skaber det?

424
00:21:42,260 --> 00:21:43,100
>> JASON Hirschorn: Godt spørgsmål.

425
00:21:43,100 --> 00:21:47,770
Lad os holde det til senere, fordi
størstedelen af ​​den tid, vi vil skabe

426
00:21:47,770 --> 00:21:48,220
et nyt knudepunkt.

427
00:21:48,220 --> 00:21:49,110
Så vi vil holde det her.

428
00:21:49,110 --> 00:21:51,006
Men det er et godt spørgsmål.

429
00:21:51,006 --> 00:21:53,250
Hvis vi skaber det, og vi finder
en kopi, hvad skal

430
00:21:53,250 --> 00:21:54,490
vi gør før han vendte tilbage?

431
00:21:54,490 --> 00:21:55,190
>> PUBLIKUM: Befri den.

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

433
00:21:55,470 --> 00:21:56,500
Sandsynligvis frigøre det.

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

435
00:21:56,760 --> 00:21:59,850
Hvad gør vi, når vi
oprette en ny knude?

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

437
00:22:02,260 --> 00:22:04,780
>> PUBLIKUM: Vi sætter
nummer i knudepunktet?

438
00:22:04,780 --> 00:22:05,140
>> JASON Hirschorn: Præcis.

439
00:22:05,140 --> 00:22:07,190
Vi sætter antallet - vi allokere plads.

440
00:22:07,190 --> 00:22:08,160
Jeg har tænkt mig at forlade denne
alle som én linje.

441
00:22:08,160 --> 00:22:08,720
Men du har ret.

442
00:22:08,720 --> 00:22:10,305
Vi allokere plads, og derefter
vi sætter antallet i.

443
00:22:10,305 --> 00:22:12,585
Vi kan endda indstille markøren
en del af den til null.

444
00:22:12,585 --> 00:22:13,720
Det er helt rigtigt.

445
00:22:13,720 --> 00:22:17,400
Og hvad så efter det?

446
00:22:17,400 --> 00:22:18,490
Vi tegnede dette billede på tavlen.

447
00:22:18,490 --> 00:22:21,190
Så hvad gør vi?

448
00:22:21,190 --> 00:22:22,680
>> PUBLIKUM: Vi går gennem listen.

449
00:22:22,680 --> 00:22:23,930
>> JASON Hirschorn: Gå gennem listen.

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
Og hvad gør vi tjekke for ved hvert knudepunkt.

453
00:22:34,280 --> 00:22:35,955
Kurt, hvad skal vi kontrollerer
for ved hvert knudepunkt?

454
00:22:35,955 --> 00:22:41,640
>> PUBLIKUM: Se, om n-værdien af
dette knudepunkt er større end værdien n

455
00:22:41,640 --> 00:22:43,070
vores knudepunkt.

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

457
00:22:43,340 --> 00:22:44,280
Jeg har tænkt mig at gøre -

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

459
00:22:45,855 --> 00:22:48,160
Så det er n -

460
00:22:48,160 --> 00:22:59,040
Jeg har tænkt mig at sige, hvis værdi er større
end denne node, så hvad gør vi?

461
00:22:59,040 --> 00:23:07,290
>> PUBLIKUM: Nå, så vi indsætter
den ting lige før det.

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

463
00:23:07,970 --> 00:23:09,410
Så hvis det er større end denne,
så vi ønsker at indsætte.

464
00:23:09,410 --> 00:23:14,010
Men vi ønsker at indsætte det lige før
fordi vi også skulle være

465
00:23:14,010 --> 00:23:16,070
holde styr, så
af, hvad der var før.

466
00:23:16,070 --> 00:23:22,690
Så indsætte før.

467
00:23:22,690 --> 00:23:25,120
Så vi sandsynligvis glip af noget
tidligere.

468
00:23:25,120 --> 00:23:27,770
Vi sandsynligvis skal holde
styr på, hvad der foregår.

469
00:23:27,770 --> 00:23:28,460
Men vi vil komme tilbage dertil.

470
00:23:28,460 --> 00:23:30,160
Så hvad værdi er mindre end?

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

472
00:23:38,030 --> 00:23:39,710
Kurt, hvad gør vi, hvis
værdi er mindre end?

473
00:23:39,710 --> 00:23:43,000
>> PUBLIKUM: Så du bare holde i gang
medmindre det er den sidste.

474
00:23:43,000 --> 00:23:43,550
>> JASON Hirschorn: Jeg kan lide det.

475
00:23:43,550 --> 00:23:44,800
Så gå til næste node.

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

477
00:23:47,410 --> 00:23:48,930
Medmindre det er den sidste -

478
00:23:48,930 --> 00:23:51,100
vi sandsynligvis kontrollere for at
i form af en betingelse.

479
00:23:51,100 --> 00:23:54,870
Men ja, næste node.

480
00:23:54,870 --> 00:23:58,680
Og det er ved at blive for lav,
så vi vil flytte over her.

481
00:23:58,680 --> 00:24:02,030
Men hvis -

482
00:24:02,030 --> 00:24:03,280
kan alle se det?

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

484
00:24:07,230 --> 00:24:11,610
Hvis vi er lige, hvad gør vi?

485
00:24:11,610 --> 00:24:15,740
Hvis værdien vi forsøger at indsætte
er lig med denne node værdi?

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

487
00:24:16,320 --> 00:24:18,400
>> PUBLIKUM: [uhørligt].

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

489
00:24:18,850 --> 00:24:19,290
I betragtning af dette -

490
00:24:19,290 --> 00:24:20,090
Marcus er rigtigt.

491
00:24:20,090 --> 00:24:21,330
Vi kunne have måske gjort
noget andet.

492
00:24:21,330 --> 00:24:25,360
Men i betragtning af, at vi har lavet det, her
vi skal frigøre og derefter vende tilbage.

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

494
00:24:26,774 --> 00:24:30,080
Er det bedre?

495
00:24:30,080 --> 00:24:31,850
Hvordan er det?

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
Fri og så hvad gør vi
tilbage, [uhørligt]?

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
Mangler vi noget?

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

503
00:24:53,500 --> 00:24:59,650
Så hvor skal vi holde styr
af den forudgående knude?

504
00:24:59,650 --> 00:25:02,370
>> PUBLIKUM: Jeg tror, ​​det ville gå
efter at oprette en ny node.

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

506
00:25:02,600 --> 00:25:03,940
Så i begyndelsen vi sandsynligvis -

507
00:25:03,940 --> 00:25:07,175
yeah, kan vi skabe en pointer til en ny
node, ligesom en tidligere knude pointer og

508
00:25:07,175 --> 00:25:09,600
en aktuel node pointer.

509
00:25:09,600 --> 00:25:12,640
Så lad os indsætte det her.

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

511
00:25:15,610 --> 00:25:26,900
Opret nuværende og tidligere
pointere til noderne.

512
00:25:26,900 --> 00:25:28,955
Men når vi tilpasse disse henvisninger?

513
00:25:28,955 --> 00:25:30,205
Hvor gør vi det i koden?

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
>> PUBLIKUM: - value forhold?

517
00:25:35,170 --> 00:25:36,420
>> JASON Hirschorn: Hvilket
én i særdeleshed?

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

519
00:25:39,862 --> 00:25:40,720
>> PUBLIKUM: Jeg er bare forvirret.

520
00:25:40,720 --> 00:25:44,200
Hvis værdien er større end denne node,
Betyder det ikke, at du ønsker at gå

521
00:25:44,200 --> 00:25:45,320
til den næste knude?

522
00:25:45,320 --> 00:25:49,515
>> JASON HIRSCHHORN: Så hvis vores værdi er
større end værdien af ​​dette emne.

523
00:25:49,515 --> 00:25:52,130
>> PUBLIKUM: Ja, så du gerne vil
gå længere ned linjen, right?

524
00:25:52,130 --> 00:25:52,590
>> JASON HIRSCHHORN: Right.

525
00:25:52,590 --> 00:25:53,840
Så vi behøver ikke indsætte det her.

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

527
00:25:58,430 --> 00:26:03,240
Hvis værdien er mindre end denne knude, så
vi gå til den næste knude - eller så vi

528
00:26:03,240 --> 00:26:03,835
Indsæt før.

529
00:26:03,835 --> 00:26:05,966
>> PUBLIKUM: Vent, der er det
knudepunkt, og som er værdi?

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

531
00:26:08,510 --> 00:26:09,280
>> JASON HIRSCHHORN: Godt spørgsmål.

532
00:26:09,280 --> 00:26:13,260
Værdi per denne funktion definition
er, hvad vi får.

533
00:26:13,260 --> 00:26:16,910
Så værdien er det antal vi er givet.

534
00:26:16,910 --> 00:26:21,120
Så hvis værdien er mindre end denne
node, vi har brug for tid til at indsætte.

535
00:26:21,120 --> 00:26:24,575
Hvis værdien er større end denne node,
vi gå til næste node.

536
00:26:24,575 --> 00:26:26,790
Og tilbage til det oprindelige spørgsmål,
selv, hvor -

537
00:26:26,790 --> 00:26:29,060
>> PUBLIKUM: Hvis værdien er større
end denne node.

538
00:26:29,060 --> 00:26:30,310
>> JASON HIRSCHHORN: Og så
hvad gør vi her?

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

540
00:26:36,790 --> 00:26:38,160
Sød.

541
00:26:38,160 --> 00:26:38,860
Det er korrekt.

542
00:26:38,860 --> 00:26:41,370
Jeg skal bare skrive
opdatere pointers.

543
00:26:41,370 --> 00:26:44,010
Men ja, med den nuværende
du vil opdatere det til

544
00:26:44,010 --> 00:26:46,080
peger på den næste.

545
00:26:46,080 --> 00:26:47,330
Noget andet vi mangler?

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

547
00:26:52,710 --> 00:26:54,940
Så jeg har tænkt mig at skrive dette
kode i gedit.

548
00:26:54,940 --> 00:26:58,375
Og mens jeg gør dette, kan du have en
par minutter mere til at arbejde på kodning

549
00:26:58,375 --> 00:28:19,240
dette i C.

550
00:28:19,240 --> 00:28:20,940
>> Så jeg har input pseudokoden.

551
00:28:20,940 --> 00:28:22,940
En hurtig bemærkning, inden vi går i gang.

552
00:28:22,940 --> 00:28:25,560
Vi kan ikke være i stand til helt
afslutte dette i alle

553
00:28:25,560 --> 00:28:27,300
tre af disse funktioner.

554
00:28:27,300 --> 00:28:30,630
Der er rigtige løsninger på dem
at jeg vil e-mail ud til jer

555
00:28:30,630 --> 00:28:33,730
efter sektion, og det vil
blive lagt på CS50.net.

556
00:28:33,730 --> 00:28:35,640
Så jeg ikke opfordre dig til at
gå se på sektionerne.

557
00:28:35,640 --> 00:28:40,550
Jeg vil opfordre dig til at prøve disse på din
ejer, og derefter bruge den praksis

558
00:28:40,550 --> 00:28:41,760
problemer med at tjekke dine svar.

559
00:28:41,760 --> 00:28:47,070
De er alle blevet designet til nøje
forholde sig til og overholde hvad

560
00:28:47,070 --> 00:28:48,400
du er nødt til at gøre på problemet sæt.

561
00:28:48,400 --> 00:28:53,820
Så jeg opfordre dig til at praktisere denne
på egen hånd og derefter bruge koden til

562
00:28:53,820 --> 00:28:54,660
tjekke dine svar.

563
00:28:54,660 --> 00:28:57,060
Fordi jeg ønsker at gå videre til hash
tabeller på et tidspunkt i afsnittet.

564
00:28:57,060 --> 00:28:58,150
Så vi kan ikke komme igennem det hele.

565
00:28:58,150 --> 00:28:59,960
Men vi vil gøre så meget vi kan nu.

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

567
00:29:00,370 --> 00:29:01,960
Lad os begynde.

568
00:29:01,960 --> 00:29:04,770
Asam, hvordan skaber vi en ny knude?

569
00:29:04,770 --> 00:29:06,810
>> PUBLIKUM: Du behøver struct *.

570
00:29:06,810 --> 00:29:09,640
>> JASON HIRSCHHORN: Så vi
har det heroppe.

571
00:29:09,640 --> 00:29:10,040
Åh, undskyld.

572
00:29:10,040 --> 00:29:13,530
Du sagde struct *.

573
00:29:13,530 --> 00:29:17,260
>> PUBLIKUM: Og så [? art?]
knude eller c node.

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

575
00:29:17,780 --> 00:29:19,740
Jeg har tænkt mig at kalde det new_node
så vi kan forblive konsekvente.

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

577
00:29:22,646 --> 00:29:33,180
>> PUBLIKUM: Og du ønsker at indstille, at
til hovedet, den første knude.

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

579
00:29:33,580 --> 00:29:37,290
Så nu dette peger på - så det
har ikke skabt en ny knude endnu.

580
00:29:37,290 --> 00:29:41,380
Dette er blot peger på
første knudepunkt på listen.

581
00:29:41,380 --> 00:29:42,630
Hvordan opretter jeg en ny knude?

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

583
00:29:45,490 --> 00:29:48,070
Hvis jeg har brug for plads til at oprette en ny node.

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

585
00:29:49,230 --> 00:29:51,710
Og hvor stor?

586
00:29:51,710 --> 00:30:00,390
>> PUBLIKUM: Størrelsen af ​​struct.

587
00:30:00,390 --> 00:30:01,150
>> JASON HIRSCHHORN: Den
størrelsen af ​​struct.

588
00:30:01,150 --> 00:30:02,400
Og hvad struct hedder?

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

590
00:30:09,670 --> 00:30:09,840
>> PUBLIKUM: Node?

591
00:30:09,840 --> 00:30:11,640
>> JASON HIRSCHHORN: Node.

592
00:30:11,640 --> 00:30:17,640
Så malloc (sizeof (node));
giver os plads.

593
00:30:17,640 --> 00:30:19,740
Og er denne linje -

594
00:30:19,740 --> 00:30:21,740
én ting er forkert på denne linje.

595
00:30:21,740 --> 00:30:24,430
Er new_node en pointer til en struct?

596
00:30:24,430 --> 00:30:25,650
Det er et generisk navn.

597
00:30:25,650 --> 00:30:26,520
Hvad er det -

598
00:30:26,520 --> 00:30:27,450
node nøjagtigt.

599
00:30:27,450 --> 00:30:29,340
Det er en node *.

600
00:30:29,340 --> 00:30:33,010
Og hvad gør vi lige efter
vi allokere noget, Asan?

601
00:30:33,010 --> 00:30:34,476
Hvad er det første, vi gør?

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

603
00:30:38,850 --> 00:30:40,320
Hvad hvis det ikke virker?

604
00:30:40,320 --> 00:30:42,430
>> PUBLIKUM: Åh, kontrollere, om det
peger på knudepunktet?

605
00:30:42,430 --> 00:30:43,310
>> JASON HIRSCHHORN: Præcis.

606
00:30:43,310 --> 00:30:46,750
Så hvis du new_node lig ligemænd
null, hvad gør vi?

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

608
00:30:51,650 --> 00:30:54,820
Dette returnerer en bool, denne funktion.

609
00:30:54,820 --> 00:30:57,760
Præcis.

610
00:30:57,760 --> 00:30:58,450
Ser godt ud.

611
00:30:58,450 --> 00:30:59,680
Noget at tilføje der?

612
00:30:59,680 --> 00:31:00,670
Vi vil tilføje ting i slutningen.

613
00:31:00,670 --> 00:31:03,160
Men der hidtil ser godt ud.

614
00:31:03,160 --> 00:31:06,170
Opret nuværende og tidligere pointere.

615
00:31:06,170 --> 00:31:08,650
Michael, hvordan gør jeg det?

616
00:31:08,650 --> 00:31:12,810
>> PUBLIKUM: Du ville have
til at gøre en knude *.

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

618
00:31:21,800 --> 00:31:25,502
Du er nødt til at gøre en ikke
for new_node men for

619
00:31:25,502 --> 00:31:26,905
knuder, vi allerede har.

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

621
00:31:27,230 --> 00:31:29,255
Så den aktuelle node vi er på.

622
00:31:29,255 --> 00:31:30,505
Jeg ringer at curr.

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

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

625
00:31:39,770 --> 00:31:41,620
Vi har besluttet at vi vil beholde
to, fordi vi har brug for at vide

626
00:31:41,620 --> 00:31:42,870
hvad der er før den.

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

628
00:31:45,770 --> 00:31:47,020
Hvad får de initialiseres til?

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

630
00:31:49,874 --> 00:31:54,180
>> PUBLIKUM: Deres værdi på vores liste.

631
00:31:54,180 --> 00:31:58,090
>> JASON HIRSCHHORN: Så hvad er den
første ting på vores liste?

632
00:31:58,090 --> 00:32:04,050
Eller hvordan kan vi vide, hvor
begyndelse på vores liste er?

633
00:32:04,050 --> 00:32:08,015
>> PUBLIKUM: Er det ikke bestået
i funktionen?

634
00:32:08,015 --> 00:32:08,466
>> JASON HIRSCHHORN: Right.

635
00:32:08,466 --> 00:32:09,716
Det blev vedtaget i lige her.

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

637
00:32:15,910 --> 00:32:18,980
Så hvis det er gået i funktion,
starte på listen, hvad skal vi

638
00:32:18,980 --> 00:32:21,270
sat strøm svarende til?

639
00:32:21,270 --> 00:32:22,110
>> PUBLIKUM: List.

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

641
00:32:22,900 --> 00:32:24,090
Det er helt rigtigt.

642
00:32:24,090 --> 00:32:26,290
Nu har adressen
starten på vores liste.

643
00:32:26,290 --> 00:32:28,450
Og hvad med tidligere?

644
00:32:28,450 --> 00:32:31,920
>> PUBLIKUM: List minus en?

645
00:32:31,920 --> 00:32:32,690
>> JASON HIRSCHHORN: Der er
intet før det.

646
00:32:32,690 --> 00:32:34,580
Så hvad kan vi gøre for at betyde noget?

647
00:32:34,580 --> 00:32:35,050
>> PUBLIKUM: Null.

648
00:32:35,050 --> 00:32:35,450
>> JASON HIRSCHHORN: Ja.

649
00:32:35,450 --> 00:32:37,950
Det lyder som en god idé.

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

651
00:32:38,360 --> 00:32:39,630
Tak.

652
00:32:39,630 --> 00:32:42,850
Gå gennem listen.

653
00:32:42,850 --> 00:32:45,490
Konstantin, hvor længe skal vi
at gå gennem listen?

654
00:32:45,490 --> 00:32:49,010
>> PUBLIKUM: indtil vi når nul.

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

656
00:32:49,390 --> 00:32:50,430
Så hvis, mens det for løkke.

657
00:32:50,430 --> 00:32:52,200
Hvad laver vi?

658
00:32:52,200 --> 00:32:53,320
>> PUBLIKUM: Måske en for-løkke?

659
00:32:53,320 --> 00:32:53,910
>> JASON HIRSCHHORN: Lad os gøre en for-løkke.

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

661
00:32:55,870 --> 00:33:02,465
>> PUBLIKUM: Og vi siger til -

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

663
00:33:09,764 --> 00:33:13,390
indtil den aktuelle markørposition
er ikke lig med nul.

664
00:33:13,390 --> 00:33:19,160
>> JASON HIRSCHHORN: Så hvis vi kender
tilstand, hvordan kan vi skrive en løkke

665
00:33:19,160 --> 00:33:21,740
baseret off denne betingelse.

666
00:33:21,740 --> 00:33:24,380
Hvilken slags en løkke skal vi bruge?

667
00:33:24,380 --> 00:33:25,260
>> PUBLIKUM: Mens.

668
00:33:25,260 --> 00:33:25,590
>> JASON HIRSCHHORN: Ja.

669
00:33:25,590 --> 00:33:27,130
Det giver mere mening baseret
off af hvad du sagde.

670
00:33:27,130 --> 00:33:29,430
Hvis vi bare ønsker at gå ind vi det ville
bare vide, at ting, ville det gøre

671
00:33:29,430 --> 00:33:31,680
mening at gøre en while-løkke.

672
00:33:31,680 --> 00:33:39,880
Selv om den nuværende ikke er lig nul,
hvis værdi er mindre end denne node.

673
00:33:39,880 --> 00:33:41,650
Akshar, giv mig denne linje.

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

675
00:33:48,810 --> 00:33:56,955
>> PUBLIKUM: Hvis den aktuelle-> n
n mindre end værdi.

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

677
00:34:00,170 --> 00:34:03,260
Eller omvendt, at.

678
00:34:03,260 --> 00:34:06,140
Skift at beslaget.

679
00:34:06,140 --> 00:34:06,620
>> JASON HIRSCHHORN: Undskyld.

680
00:34:06,620 --> 00:34:08,760
>> PUBLIKUM: Skift beslaget.

681
00:34:08,760 --> 00:34:10,914
>> JASON HIRSCHHORN: Så hvis det er
større end værdi.

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

683
00:34:18,719 --> 00:34:22,120
Fordi det er forvirrende med den
ovenstående kommentar, vil jeg gøre det.

684
00:34:22,120 --> 00:34:22,480
Men ja.

685
00:34:22,480 --> 00:34:25,125
Hvis vores værdi er mindre end dette
node, hvad gør vi?

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

687
00:34:25,540 --> 00:34:26,710
Jeg har det lige her.

688
00:34:26,710 --> 00:34:27,960
Indsæt før.

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
Hvordan gør vi det?

692
00:34:33,933 --> 00:34:34,900
>> PUBLIKUM: Er det stadig mig?

693
00:34:34,900 --> 00:34:36,150
>> JASON HIRSCHHORN: Ja.

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

695
00:34:38,520 --> 00:34:39,770
>> PUBLIKUM: You -

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

697
00:34:42,909 --> 00:34:44,159
new_node-> næste.

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

699
00:34:46,770 --> 00:34:50,163
>> JASON HIRSCHHORN: Så hvad er
der kommer til at svare?

700
00:34:50,163 --> 00:34:52,070
>> PUBLIKUM: Det kommer til at lige strøm.

701
00:34:52,070 --> 00:34:53,889
>> JASON HIRSCHHORN: Præcis.

702
00:34:53,889 --> 00:34:55,730
Og så den anden -

703
00:34:55,730 --> 00:34:56,730
hvad gør vi brug for at opdatere?

704
00:34:56,730 --> 00:34:59,982
>> PUBLIKUM: Kontroller, om fortiden er lig nul.

705
00:34:59,982 --> 00:35:01,870
>> JASON HIRSCHHORN: Hvis Forrige -

706
00:35:01,870 --> 00:35:03,730
så hvis forrige er lig nul.

707
00:35:03,730 --> 00:35:05,990
>> PUBLIKUM: Det betyder, at det vil
at blive hovedet.

708
00:35:05,990 --> 00:35:06,780
>> JASON HIRSCHHORN: Det betyder
det er blevet leder.

709
00:35:06,780 --> 00:35:07,620
Så hvad gør vi?

710
00:35:07,620 --> 00:35:12,510
>> PUBLIKUM: Vi gør hoved lig new_node.

711
00:35:12,510 --> 00:35:16,690
>> JASON HIRSCHHORN: Hoved
lig new_node.

712
00:35:16,690 --> 00:35:20,540
Og hvorfor hovedet her, ikke liste?

713
00:35:20,540 --> 00:35:24,940
>> PUBLIKUM: Da hovedet er en global
variabel, der er udgangsmaterialet sted.

714
00:35:24,940 --> 00:35:26,190
>> JASON HIRSCHHORN: Sød.

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
Og -

718
00:35:36,150 --> 00:35:53,796
>> PUBLIKUM: Så du ellers prev->
næste lig new_node.

719
00:35:53,796 --> 00:35:55,080
Og så skal du returnere sandt.

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

721
00:35:59,560 --> 00:36:02,700
>> JASON HIRSCHHORN: Hvor
vi sat new_node ende?

722
00:36:02,700 --> 00:36:04,850
>> PUBLIKUM: Jeg ville -

723
00:36:04,850 --> 00:36:06,180
Jeg satte det i starten.

724
00:36:06,180 --> 00:36:07,430
>> JASON HIRSCHHORN: Så hvad linje?

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

726
00:36:10,000 --> 00:36:12,598
>> PUBLIKUM: Efter hvis erklæring
kontrol, hvis det er kendt.

727
00:36:12,598 --> 00:36:13,057
>> JASON HIRSCHHORN: Lige her?

728
00:36:13,057 --> 00:36:18,335
>> PUBLIKUM: Jeg ville gøre new_node-> n
lig værdi.

729
00:36:18,335 --> 00:36:19,585
>> JASON HIRSCHHORN: Det lyder godt.

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

731
00:36:21,740 --> 00:36:25,090
Sandsynligvis det er fornuftigt - vi ikke
brug for at vide, hvad listen vi er på

732
00:36:25,090 --> 00:36:26,280
fordi vi kun har at gøre
med én liste.

733
00:36:26,280 --> 00:36:29,560
Så en bedre funktion erklæring for
det er bare for at slippe for denne

734
00:36:29,560 --> 00:36:34,360
helt og bare indsætte
en værdi i hovedet.

735
00:36:34,360 --> 00:36:35,930
Vi behøver ikke engang at vide
hvad liste, vi befinder os i.

736
00:36:35,930 --> 00:36:39,140
Men jeg vil holde det for nu, og
derefter ændre det ved at opdatere

737
00:36:39,140 --> 00:36:42,590
dias og kode.

738
00:36:42,590 --> 00:36:44,980
Så det ser godt ud for nu.

739
00:36:44,980 --> 00:36:46,560
Hvis værdi - der kan gøre denne linje?

740
00:36:46,560 --> 00:36:47,810
Hvis -

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

742
00:36:52,240 --> 00:36:53,840
hvad gør vi her, Noah.

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

744
00:36:57,890 --> 00:37:07,100
>> PUBLIKUM: Hvis værdien er større
end curr-> n -

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

746
00:37:16,830 --> 00:37:18,240
>> JASON HIRSCHHORN: Hvordan
vi gå til næste node?

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

748
00:37:27,760 --> 00:37:30,530
>> PUBLIKUM: Curr-> n er
lig new_node.

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

750
00:37:37,630 --> 00:37:39,195
>> JASON HIRSCHHORN: So n er
hvilken del af struct?

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

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

753
00:37:46,020 --> 00:37:50,420
Og new_node er en pointer til en node.

754
00:37:50,420 --> 00:37:51,880
Så hvad en del af curr skal vi opdatere?

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

756
00:38:03,900 --> 00:38:05,400
Hvis ikke n, hvad er så den anden side?

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

758
00:38:21,680 --> 00:38:22,810
Noa, hvad er den anden side.

759
00:38:22,810 --> 00:38:23,570
>> PUBLIKUM: Åh, næste.

760
00:38:23,570 --> 00:38:25,645
>> JASON HIRSCHHORN: Next, nøjagtigt.

761
00:38:25,645 --> 00:38:26,410
Præcis.

762
00:38:26,410 --> 00:38:28,770
Næste er den rigtige.

763
00:38:28,770 --> 00:38:31,540
Og hvad har vi brug for
at opdatere, Noah?

764
00:38:31,540 --> 00:38:32,840
>> PUBLIKUM: The pointers.

765
00:38:32,840 --> 00:38:34,840
>> JASON HIRSCHHORN: So
vi opdateret løbende.

766
00:38:34,840 --> 00:38:36,090
>> PUBLIKUM: Forrige-> næste.

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

768
00:38:48,160 --> 00:38:49,410
>> JASON HIRSCHHORN: Ja.

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

770
00:38:57,465 --> 00:38:58,370
OK, vi vil holde pause.

771
00:38:58,370 --> 00:39:02,200
Hvem kan hjælpe os ud her?

772
00:39:02,200 --> 00:39:03,385
Manu, hvad skal vi gøre?

773
00:39:03,385 --> 00:39:05,615
>> PUBLIKUM: Du har fået til at indstille
det svarer til curr-> næste.

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

775
00:39:09,110 --> 00:39:11,630
Men gør det inden den tidligere linje.

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
Noget andet?

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

780
00:39:19,170 --> 00:39:22,680
>> PUBLIKUM: Jeg tror ikke, du er
beregnet til at ændre curr-> næste.

781
00:39:22,680 --> 00:39:29,270
Jeg tror, ​​du betød at gøre Curr ligemænd
curr-> Næste for at gå til næste node.

782
00:39:29,270 --> 00:39:30,500
>> JASON HIRSCHHORN: Så ked, hvor?

783
00:39:30,500 --> 00:39:32,680
På hvilke linje?

784
00:39:32,680 --> 00:39:33,420
Denne linje?

785
00:39:33,420 --> 00:39:33,750
>> PUBLIKUM: Ja.

786
00:39:33,750 --> 00:39:35,745
Gør curr lig curr-> næste.

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

788
00:39:39,690 --> 00:39:43,360
>> JASON HIRSCHHORN: Så det er korrekt
fordi de nuværende er en

789
00:39:43,360 --> 00:39:45,220
pointer til en node.

790
00:39:45,220 --> 00:39:48,550
Og vi vil have det til at pege på den næste
node af, hvad der er ved at blive aktuelt

791
00:39:48,550 --> 00:39:49,930
pegede på.

792
00:39:49,930 --> 00:39:54,410
Curr selv har en næste.

793
00:39:54,410 --> 00:39:58,620
Men hvis vi skulle opdatere curr.next, vi
ville være at opdatere den faktiske tone

794
00:39:58,620 --> 00:40:01,430
selv, ikke hvor dette
pointer peger.

795
00:40:01,430 --> 00:40:02,680
Hvad med denne linje, selv om.

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
>> PUBLIKUM: Forrige-> næste lig curr.

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

800
00:40:12,500 --> 00:40:19,440
>> JASON HIRSCHHORN: Så igen, hvis forrige er en
pointer til en knude, prev-> næste er den

801
00:40:19,440 --> 00:40:23,020
faktiske pointer i noden.

802
00:40:23,020 --> 00:40:27,190
Så det ville være en opdatering et
pointer i en node til curr.

803
00:40:27,190 --> 00:40:28,570
Vi ønsker ikke at opdatere
en pointer i en knude.

804
00:40:28,570 --> 00:40:30,570
Vi ønsker at opdatere tidligere.

805
00:40:30,570 --> 00:40:31,850
Så hvordan gør vi det?

806
00:40:31,850 --> 00:40:34,250
>> PUBLIKUM: Det ville bare være prev.

807
00:40:34,250 --> 00:40:34,565
>> JASON HIRSCHHORN: Right.

808
00:40:34,565 --> 00:40:35,560
Forrige er en pointer til en node.

809
00:40:35,560 --> 00:40:38,750
Nu vi er ved at ændre den til en
ny pointer til et knudepunkt.

810
00:40:38,750 --> 00:40:40,830
OK Lad os gå ned.

811
00:40:40,830 --> 00:40:41,940
Endelig er denne sidste betingelse.

812
00:40:41,940 --> 00:40:44,896
Jeff, hvad gør vi her?

813
00:40:44,896 --> 00:40:47,515
>> PUBLIKUM: Hvis værdi er
lig curr-> n.

814
00:40:47,515 --> 00:40:51,030

815
00:40:51,030 --> 00:40:51,300
>> JASON HIRSCHHORN: Undskyld.

816
00:40:51,300 --> 00:40:52,372
Åh min godhed.

817
00:40:52,372 --> 00:40:54,330
Hvad?

818
00:40:54,330 --> 00:40:55,580
Value == curr-> n.

819
00:40:55,580 --> 00:41:01,050

820
00:41:01,050 --> 00:41:02,300
Hvad gør vi?

821
00:41:02,300 --> 00:41:04,760

822
00:41:04,760 --> 00:41:10,950
>> PUBLIKUM: Du ville befri vores new_node,
og så ville du returnere falsk.

823
00:41:10,950 --> 00:41:21,410

824
00:41:21,410 --> 00:41:23,460
>> JASON HIRSCHHORN: Dette er, hvad
vi har skrevet hidtil.

825
00:41:23,460 --> 00:41:25,710
Er der nogen, der har noget
at tilføje, før vi gør?

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
Lad os prøve det.

829
00:41:36,960 --> 00:41:44,180

830
00:41:44,180 --> 00:41:46,110
Kontrol kan nå slutningen
af et ikke-void funktion.

831
00:41:46,110 --> 00:41:48,310
Avi, hvad sker der?

832
00:41:48,310 --> 00:41:51,380
>> PUBLIKUM: Er du formodes at sætte tilbagevenden
sand uden for while-løkken?

833
00:41:51,380 --> 00:41:53,900

834
00:41:53,900 --> 00:41:54,400
>> JASON HIRSCHHORN: Jeg ved det ikke.

835
00:41:54,400 --> 00:41:54,780
Vil du have mig til?

836
00:41:54,780 --> 00:41:55,520
>> PUBLIKUM: Pyt.

837
00:41:55,520 --> 00:41:56,350
Nej.

838
00:41:56,350 --> 00:41:57,180
>> JASON HIRSCHHORN: Akshar?

839
00:41:57,180 --> 00:41:59,460
>> PUBLIKUM: Jeg tror du mente at
sætte return false i slutningen

840
00:41:59,460 --> 00:42:02,230
af while-løkken.

841
00:42:02,230 --> 00:42:03,270
>> JASON HIRSCHHORN: Så hvor
vil du have det til at gå?

842
00:42:03,270 --> 00:42:05,270
>> PUBLIKUM: Ligesom udenfor while-løkken.

843
00:42:05,270 --> 00:42:08,800
Så hvis du afslutter, mens løkken, der betyder
at du har nået slutningen, og

844
00:42:08,800 --> 00:42:09,980
intet er sket.

845
00:42:09,980 --> 00:42:10,410
>> JASON HIRSCHHORN: OK.

846
00:42:10,410 --> 00:42:12,340
Så hvad gør vi her?

847
00:42:12,340 --> 00:42:13,702
>> PUBLIKUM: Du vender tilbage falsk
der.

848
00:42:13,702 --> 00:42:15,040
>> JASON HIRSCHHORN: Åh, vi
gøre det begge steder?

849
00:42:15,040 --> 00:42:15,650
>> PUBLIKUM: Ja.

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
Skal vi gå?

853
00:42:26,160 --> 00:42:26,980
Åh min godhed.

854
00:42:26,980 --> 00:42:27,290
Undskyld.

855
00:42:27,290 --> 00:42:28,480
Jeg undskylder for skærmen.

856
00:42:28,480 --> 00:42:30,530
Det er slags flipper ud på os.

857
00:42:30,530 --> 00:42:31,520
Så vælge en indstilling.

858
00:42:31,520 --> 00:42:35,260
Zero, pr koden, afsluttes programmet.

859
00:42:35,260 --> 00:42:36,700
Man indsætter noget.

860
00:42:36,700 --> 00:42:37,990
Lad os indsætte tre.

861
00:42:37,990 --> 00:42:42,900

862
00:42:42,900 --> 00:42:45,380
Indsatsen var ikke en succes.

863
00:42:45,380 --> 00:42:46,500
Jeg har tænkt mig at printe ud.

864
00:42:46,500 --> 00:42:48,050
Jeg har ikke noget.

865
00:42:48,050 --> 00:42:48,450
OK.

866
00:42:48,450 --> 00:42:50,250
Måske det var bare et lykketræf.

867
00:42:50,250 --> 00:42:52,810
Sæt den ene.

868
00:42:52,810 --> 00:42:55,770
Ikke lykkes.

869
00:42:55,770 --> 00:42:57,470
OK.

870
00:42:57,470 --> 00:43:02,400
Lad os køre gennem GDB virkelig hurtigt
at tjekke ud, hvad der foregår.

871
00:43:02,400 --> 00:43:06,055
>> Husk gdb. / Navnet på din
Programmet får os ind GDB.

872
00:43:06,055 --> 00:43:07,610
Er det en masse at håndtere?

873
00:43:07,610 --> 00:43:08,560
Det blinkende?

874
00:43:08,560 --> 00:43:10,400
Sandsynligvis.

875
00:43:10,400 --> 00:43:12,760
Luk øjnene og tage nogle dybe
vejrtrækninger hvis du bliver træt

876
00:43:12,760 --> 00:43:13,580
af at kigge på det.

877
00:43:13,580 --> 00:43:14,200
Jeg er i GDB.

878
00:43:14,200 --> 00:43:15,830
Hvad er det første, jeg gør i GDB?

879
00:43:15,830 --> 00:43:17,050
Vi har fået at regne ud
hvad der foregår her.

880
00:43:17,050 --> 00:43:17,310
Lad os se.

881
00:43:17,310 --> 00:43:21,650
Vi har seks minutter til figur
ud af, hvad der foregår.

882
00:43:21,650 --> 00:43:22,900
Break main.

883
00:43:22,900 --> 00:43:25,950

884
00:43:25,950 --> 00:43:28,130
Og hvad gør jeg?

885
00:43:28,130 --> 00:43:29,180
Carlos?

886
00:43:29,180 --> 00:43:31,060
Kør.

887
00:43:31,060 --> 00:43:32,250
OK.

888
00:43:32,250 --> 00:43:34,160
Lad os vælge en indstilling.

889
00:43:34,160 --> 00:43:36,330
Og hvad betyder N gøre?

890
00:43:36,330 --> 00:43:38,480
Næste.

891
00:43:38,480 --> 00:43:38,950
Ja.

892
00:43:38,950 --> 00:43:39,740
>> PUBLIKUM: Har du ikke nævne -

893
00:43:39,740 --> 00:43:45,230
har du ikke sige, at hovedet, det var
initialiseres til nul i begyndelsen.

894
00:43:45,230 --> 00:43:47,140
Men jeg troede, du sagde, det var OK.

895
00:43:47,140 --> 00:43:50,040

896
00:43:50,040 --> 00:43:52,640
>> JASON HIRSCHHORN: Lad os gå - lad os se
i GDB, og så vil vi gå tilbage.

897
00:43:52,640 --> 00:43:54,910
Men det lyder som om du allerede har
nogle ideer om, hvad der foregår.

898
00:43:54,910 --> 00:43:58,340
Så vi ønsker at indsætte noget.

899
00:43:58,340 --> 00:43:59,390
OK.

900
00:43:59,390 --> 00:44:00,150
Vi har indsætte.

901
00:44:00,150 --> 00:44:00,770
Indtast venligst en int.

902
00:44:00,770 --> 00:44:01,990
Vi vil indsætte tre.

903
00:44:01,990 --> 00:44:03,000
Og så er jeg på denne linje.

904
00:44:03,000 --> 00:44:07,030
Hvordan går jeg starte debugging
indsatsen kendt funktion?

905
00:44:07,030 --> 00:44:08,280
Åh min godhed.

906
00:44:08,280 --> 00:44:10,990

907
00:44:10,990 --> 00:44:12,240
Det er en masse.

908
00:44:12,240 --> 00:44:14,372

909
00:44:14,372 --> 00:44:16,445
Er det freaking ud en masse?

910
00:44:16,445 --> 00:44:19,696

911
00:44:19,696 --> 00:44:21,680
>> PUBLIKUM: Åh, det døde.

912
00:44:21,680 --> 00:44:22,930
>> JASON HIRSCHHORN: Jeg har lige
trak den ud.

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
>> PUBLIKUM: Måske er det
anden ende af tråden.

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
Så bundlinjen -

919
00:44:42,330 --> 00:44:43,470
hvad sagde du?

920
00:44:43,470 --> 00:44:46,040
>> PUBLIKUM: Jeg sagde ironien i teknisk
vanskeligheder i denne klasse.

921
00:44:46,040 --> 00:44:46,410
>> JASON HIRSCHHORN: jeg kender.

922
00:44:46,410 --> 00:44:48,660
Hvis bare jeg havde kontrol over denne del.

923
00:44:48,660 --> 00:44:49,910
[Uhørligt]

924
00:44:49,910 --> 00:44:54,430

925
00:44:54,430 --> 00:44:55,400
Det lyder godt.

926
00:44:55,400 --> 00:44:58,680
Hvorfor tager du ikke fyre begynde at tænke
hvad vi kunne have gjort forkert,

927
00:44:58,680 --> 00:45:01,140
og vi vil være tilbage i 90 sekunder.

928
00:45:01,140 --> 00:46:18,160

929
00:46:18,160 --> 00:46:23,010
>> Avica, jeg har tænkt mig at spørge dig, hvordan du gå
inde insert_node at debug det.

930
00:46:23,010 --> 00:46:28,940

931
00:46:28,940 --> 00:46:31,460
Så dette er, hvor vi sidst slap.

932
00:46:31,460 --> 00:46:35,110
Hvordan kan jeg gå ind insert_node, Avica,
at undersøge, hvad der foregår?

933
00:46:35,110 --> 00:46:36,360
Hvad GDB kommando?

934
00:46:36,360 --> 00:46:41,050

935
00:46:41,050 --> 00:46:42,390
Break ville ikke tage mig indenfor.

936
00:46:42,390 --> 00:46:46,200

937
00:46:46,200 --> 00:46:47,130
Er Marquise vide?

938
00:46:47,130 --> 00:46:48,240
>> PUBLIKUM: Hvad?

939
00:46:48,240 --> 00:46:51,780
>> JASON HIRSCHHORN: Hvad GDB kommando
Jeg bruger til at gå inde i denne funktion?

940
00:46:51,780 --> 00:46:52,070
>> PUBLIKUM: Step?

941
00:46:52,070 --> 00:46:55,140
>> JASON HIRSCHHORN: Træd via
S. Det tager mig indenfor.

942
00:46:55,140 --> 00:46:55,476
OK.

943
00:46:55,476 --> 00:46:58,040
New_node mallocing noget plads.

944
00:46:58,040 --> 00:46:59,120
At alle ligner dens gang.

945
00:46:59,120 --> 00:47:00,370
Lad os undersøge new_node.

946
00:47:00,370 --> 00:47:03,270

947
00:47:03,270 --> 00:47:05,410
Det fik noget hukommelse adresse.

948
00:47:05,410 --> 00:47:07,440
Lad os se -

949
00:47:07,440 --> 00:47:08,500
der er alle korrekte.

950
00:47:08,500 --> 00:47:12,220
Så alt her synes at
arbejder korrekt.

951
00:47:12,220 --> 00:47:14,530
>> PUBLIKUM: Hvad er forskellen
mellem P og skærm?

952
00:47:14,530 --> 00:47:16,160
>> JASON HIRSCHHORN: P står for print.

953
00:47:16,160 --> 00:47:19,310
Og så spørger du, hvad der er den
Forskellen mellem denne og dette?

954
00:47:19,310 --> 00:47:22,330
I dette tilfælde, intet.

955
00:47:22,330 --> 00:47:26,960
Men generelt er der
nogle forskelle.

956
00:47:26,960 --> 00:47:28,220
Og du bør kigge i GDB manual.

957
00:47:28,220 --> 00:47:29,560
Men i dette tilfælde, intet.

958
00:47:29,560 --> 00:47:31,460
Vi er tilbøjelige til at bruge print, selv om, fordi
vi behøver ikke at gøre meget mere end

959
00:47:31,460 --> 00:47:33,960
udskrive en enkelt værdi.

960
00:47:33,960 --> 00:47:34,640
>> OK.

961
00:47:34,640 --> 00:47:40,300
Så vi er på linje 80 i vores kode,
indstilling node * curr svarende til listen.

962
00:47:40,300 --> 00:47:42,500
Lad os udskrive curr.

963
00:47:42,500 --> 00:47:45,260

964
00:47:45,260 --> 00:47:46,840
Det er lig med listen.

965
00:47:46,840 --> 00:47:48,850
Sød.

966
00:47:48,850 --> 00:47:49,340
Vent.

967
00:47:49,340 --> 00:47:50,590
Det er lig med noget.

968
00:47:50,590 --> 00:47:53,680

969
00:47:53,680 --> 00:47:56,190
Det virker ikke rigtigt.

970
00:47:56,190 --> 00:47:56,840
Der vi går.

971
00:47:56,840 --> 00:47:59,470
Det er fordi i GDB, til højre, hvis
Det er den linje, du er på det

972
00:47:59,470 --> 00:48:00,330
har ikke udført endnu.

973
00:48:00,330 --> 00:48:03,100
Så du er nødt til rent faktisk at skrive
næste til at udføre den linje

974
00:48:03,100 --> 00:48:05,230
før at se resultaterne.

975
00:48:05,230 --> 00:48:06,680
Så her er vi.

976
00:48:06,680 --> 00:48:09,490
Vi har lige gennemført denne linje,
tidligere er lig nul.

977
00:48:09,490 --> 00:48:13,590
Så igen, hvis vi udskriver tidligere
vil vi ikke se noget underligt.

978
00:48:13,590 --> 00:48:18,680
Men hvis vi rent faktisk udfører det
linje, så vil vi se,

979
00:48:18,680 --> 00:48:20,380
at denne linje arbejdet.

980
00:48:20,380 --> 00:48:21,060
>> Så vi har curr.

981
00:48:21,060 --> 00:48:23,180
De er begge god.

982
00:48:23,180 --> 00:48:24,010
Right?

983
00:48:24,010 --> 00:48:28,130
Nu er vi på denne linje lige her.

984
00:48:28,130 --> 00:48:29,310
Mens curr ikke lig nul.

985
00:48:29,310 --> 00:48:31,110
Nå, hvad gør curr lige?

986
00:48:31,110 --> 00:48:32,450
Vi så bare det umådeholdent null.

987
00:48:32,450 --> 00:48:33,210
Vi udskrives det.

988
00:48:33,210 --> 00:48:35,110
Jeg vil printe det ud igen.

989
00:48:35,110 --> 00:48:36,720
Så er, at mens løkken
kommer til at udføre?

990
00:48:36,720 --> 00:48:37,270
>> PUBLIKUM: Nej.

991
00:48:37,270 --> 00:48:39,790
>> JASON HIRSCHHORN: Så når jeg har skrevet, at
linje, kan du se vi hoppede hele vejen

992
00:48:39,790 --> 00:48:41,390
ned til bunden, return false.

993
00:48:41,390 --> 00:48:44,520
Og så vil vi vende tilbage falsk
og gå tilbage til vores program, og

994
00:48:44,520 --> 00:48:48,020
til sidst udskrive, ligesom vi så,
indsatsen ikke var en succes.

995
00:48:48,020 --> 00:48:51,010
Så nogen har nogen ideer om, hvad
vi nødt til at gøre for at løse dette?

996
00:48:51,010 --> 00:48:54,200

997
00:48:54,200 --> 00:48:57,570
Jeg har tænkt mig at vente, indtil jeg ser
et par hænder gå op.

998
00:48:57,570 --> 00:48:58,830
Vi har ikke udføre dette.

999
00:48:58,830 --> 00:49:01,660
Husk på, dette var den første
ting vi lavede.

1000
00:49:01,660 --> 00:49:02,430
Jeg har ikke tænkt mig at gøre et par.

1001
00:49:02,430 --> 00:49:03,670
Jeg har tænkt mig at gøre et par.

1002
00:49:03,670 --> 00:49:04,830
Fordi et par betyder to.

1003
00:49:04,830 --> 00:49:07,620
Jeg venter i mere end to.

1004
00:49:07,620 --> 00:49:10,690
>> Den første indsættelse, curr,
som standard er lig nul.

1005
00:49:10,690 --> 00:49:14,050
Og denne løkke kun udfører
hvis curr er ikke nul.

1006
00:49:14,050 --> 00:49:18,740
Så hvordan kan jeg komme uden om dette?

1007
00:49:18,740 --> 00:49:19,990
Jeg ser tre hænder.

1008
00:49:19,990 --> 00:49:28,490

1009
00:49:28,490 --> 00:49:29,780
Jeg venter på mere end tre.

1010
00:49:29,780 --> 00:49:33,460

1011
00:49:33,460 --> 00:49:35,940
Marcus, hvad tror du?

1012
00:49:35,940 --> 00:49:37,730
>> PUBLIKUM: Tja, hvis du har brug for det
udføre mere end én gang, skal du bare

1013
00:49:37,730 --> 00:49:39,948
ændre det til en gør-while-løkke.

1014
00:49:39,948 --> 00:49:41,250
>> JASON HIRSCHHORN: OK.

1015
00:49:41,250 --> 00:49:44,240
Vil det løse vores problem, selvom?

1016
00:49:44,240 --> 00:49:47,750
>> PUBLIKUM: I dette tilfælde ikke på grund af
den kendsgerning, at listen er tom.

1017
00:49:47,750 --> 00:49:52,150
Så har du sandsynligvis bare nødt til at tilføje
en erklæring om, at hvis loop udgange

1018
00:49:52,150 --> 00:49:55,312
så har du til at være i slutningen af
listen, hvorefter du

1019
00:49:55,312 --> 00:49:56,562
kan bare indsætte det.

1020
00:49:56,562 --> 00:49:58,920

1021
00:49:58,920 --> 00:49:59,680
>> JASON HIRSCHHORN: Jeg kan lide det.

1022
00:49:59,680 --> 00:50:00,500
Det giver mening.

1023
00:50:00,500 --> 00:50:03,390
Hvis sløjfen udgange -

1024
00:50:03,390 --> 00:50:04,800
fordi det vil returnere falsk her.

1025
00:50:04,800 --> 00:50:08,220
Så hvis loop udgange, så vi er på
slutningen af ​​listen, eller måske

1026
00:50:08,220 --> 00:50:10,690
starte på en liste, hvis der ikke er noget i
det, som er det samme som ved udgangen.

1027
00:50:10,690 --> 00:50:12,770
Så nu er vi ønsker at indsætte
noget her.

1028
00:50:12,770 --> 00:50:17,380
Så hvordan gør denne kode ser, Marcus?

1029
00:50:17,380 --> 00:50:21,600
>> PUBLIKUM: Hvis du allerede fået den node
malloced, kan du bare sige

1030
00:50:21,600 --> 00:50:25,400
new_node-> næste lig nul, fordi
det skal være i slutningen.

1031
00:50:25,400 --> 00:50:27,510
Eller new_node-> næste lig nul.

1032
00:50:27,510 --> 00:50:27,765
>> JASON HIRSCHHORN: OK.

1033
00:50:27,765 --> 00:50:28,190
Undskyld.

1034
00:50:28,190 --> 00:50:35,760
New_node-> næste lig nul
fordi vi er i slutningen.

1035
00:50:35,760 --> 00:50:36,460
Det betyder ikke sætte det i.

1036
00:50:36,460 --> 00:50:37,710
Hvordan kan vi sætte det på listen?

1037
00:50:37,710 --> 00:50:46,130

1038
00:50:46,130 --> 00:50:46,460
Right.

1039
00:50:46,460 --> 00:50:47,750
Det er bare at sætte den lig med.

1040
00:50:47,750 --> 00:50:50,940
Nej hvordan gør vi faktisk
sætte den på listen?

1041
00:50:50,940 --> 00:50:54,170
Hvad peger mod
slutningen af ​​listen?

1042
00:50:54,170 --> 00:50:56,090
>> PUBLIKUM: Head.

1043
00:50:56,090 --> 00:50:57,566
>> JASON HIRSCHHORN: Undskyld?

1044
00:50:57,566 --> 00:50:59,440
>> PUBLIKUM: Leder peger
til slutningen af ​​listen.

1045
00:50:59,440 --> 00:51:01,480
>> JASON HIRSCHHORN: Hvis der er noget i
listen, hoved peger på den

1046
00:51:01,480 --> 00:51:04,170
slutningen af ​​listen.

1047
00:51:04,170 --> 00:51:06,920
Så der vil arbejde for
første indsættelse.

1048
00:51:06,920 --> 00:51:09,810
Hvad hvis der er et par
ting på listen?

1049
00:51:09,810 --> 00:51:12,470
End vi ønsker ikke at sætte
hovedet lig new_node.

1050
00:51:12,470 --> 00:51:13,790
Hvad ønsker vi at gøre der?

1051
00:51:13,790 --> 00:51:15,610
Ja?

1052
00:51:15,610 --> 00:51:16,860
Sandsynligvis tidligere.

1053
00:51:16,860 --> 00:51:23,560

1054
00:51:23,560 --> 00:51:24,810
Vil det fungere?

1055
00:51:24,810 --> 00:51:28,950

1056
00:51:28,950 --> 00:51:33,050
Husk på, at tidligere er bare
en pointer til et knudepunkt.

1057
00:51:33,050 --> 00:51:34,770
Og tidligere er en lokal variabel.

1058
00:51:34,770 --> 00:51:38,080
Så denne linje vil sætte en lokal variabel,
tidligere, er lig med eller

1059
00:51:38,080 --> 00:51:39,380
peger på det nye knudepunkt.

1060
00:51:39,380 --> 00:51:41,500
Det vil faktisk ikke sige det
på vores liste, selv om.

1061
00:51:41,500 --> 00:51:44,330
Hvordan kan vi sætte det i vores liste?

1062
00:51:44,330 --> 00:51:45,620
Akchar?

1063
00:51:45,620 --> 00:51:46,870
>> PUBLIKUM: Jeg tror, ​​du
gør strøm-> næste.

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
curr-> næste.

1067
00:51:54,010 --> 00:51:58,768
Så igen, den eneste grund til at vi er nede
Her er, hvad betyder aktuel lige?

1068
00:51:58,768 --> 00:51:59,760
>> PUBLIKUM: Lig null.

1069
00:51:59,760 --> 00:52:01,790
>> JASON HIRSCHHORN: Og hvad så
sker der, hvis vi gør nul-> næste?

1070
00:52:01,790 --> 00:52:02,810
Hvad skal vi komme?

1071
00:52:02,810 --> 00:52:04,060
Vi får en segmentering fejl.

1072
00:52:04,060 --> 00:52:06,600

1073
00:52:06,600 --> 00:52:08,880
>> PUBLIKUM: Do curr lig nul.

1074
00:52:08,880 --> 00:52:10,760
>> JASON HIRSCHHORN: Det er det samme
som forrige, selv om, fordi der er

1075
00:52:10,760 --> 00:52:12,820
en lokal variabel vi sætte
svarende til det nye knudepunkt.

1076
00:52:12,820 --> 00:52:16,680

1077
00:52:16,680 --> 00:52:20,920
Lad os gå tilbage til vores billede
indsætte noget.

1078
00:52:20,920 --> 00:52:25,500
Sig vi indsætter i slutningen
af listen, så lige her.

1079
00:52:25,500 --> 00:52:30,010
Vi har en aktuel pointer, der er
peger på null og et tidligere punkt

1080
00:52:30,010 --> 00:52:32,800
der peger til 8.

1081
00:52:32,800 --> 00:52:35,330
Så hvad har vi brug for at opdatere, Avi?

1082
00:52:35,330 --> 00:52:36,680
>> PUBLIKUM: Forrige-> næste?

1083
00:52:36,680 --> 00:52:41,980
>> JASON HIRSCHHORN: Forrige-> næste er, hvad
vi ønsker at opdatere, fordi det

1084
00:52:41,980 --> 00:52:44,960
rent faktisk vil indsætte det på
enden af ​​listen.

1085
00:52:44,960 --> 00:52:47,220
Vi har stadig en bug, selv om,
at vi kommer til at løbe ind.

1086
00:52:47,220 --> 00:52:50,090
Hvad er det bug?

1087
00:52:50,090 --> 00:52:50,790
Ja?

1088
00:52:50,790 --> 00:52:53,860
>> PUBLIKUM: Det kommer til at vende tilbage
falsk i denne sag?

1089
00:52:53,860 --> 00:52:56,380
>> JASON HIRSCHHORN: Åh, er der
kommer til at vende tilbage falsk.

1090
00:52:56,380 --> 00:52:57,430
Men der er en anden fejl.

1091
00:52:57,430 --> 00:52:58,930
Så vi bliver nødt til at sætte til gengæld sandt.

1092
00:52:58,930 --> 00:53:01,370
>> PUBLIKUM: Er tidligere stadig lige
null øverst på listen?

1093
00:53:01,370 --> 00:53:03,645
>> JASON HIRSCHHORN: So tidligere stadig
lig nul i begyndelsen.

1094
00:53:03,645 --> 00:53:07,480

1095
00:53:07,480 --> 00:53:10,440
Så hvordan kan vi komme over det?

1096
00:53:10,440 --> 00:53:10,950
Ja?

1097
00:53:10,950 --> 00:53:15,280
>> PUBLIKUM: Jeg tror, ​​du kan gøre en check
før while-løkken til at se om det er

1098
00:53:15,280 --> 00:53:16,610
en tom liste.

1099
00:53:16,610 --> 00:53:17,000
>> JASON HIRSCHHORN: OK.

1100
00:53:17,000 --> 00:53:17,710
Så lad os gå her.

1101
00:53:17,710 --> 00:53:18,530
Gør en check.

1102
00:53:18,530 --> 00:53:19,380
Hvis -

1103
00:53:19,380 --> 00:53:20,770
>> PUBLIKUM: Så hvis hoved
lig lig nul.

1104
00:53:20,770 --> 00:53:24,300

1105
00:53:24,300 --> 00:53:26,320
>> JASON HIRSCHHORN: Hvis hoved
lig lig nul -

1106
00:53:26,320 --> 00:53:27,790
der vil fortælle os, om det er en tom liste.

1107
00:53:27,790 --> 00:53:31,090
>> PUBLIKUM: Og så
gøre hoved lig nye.

1108
00:53:31,090 --> 00:53:34,740
>> JASON HIRSCHHORN: Hoved
lig new_node?

1109
00:53:34,740 --> 00:53:35,730
Og hvad skal vi gøre?

1110
00:53:35,730 --> 00:53:37,020
>> PUBLIKUM: Og så returnere sandt.

1111
00:53:37,020 --> 00:53:37,535
>> JASON HIRSCHHORN: Ikke helt.

1112
00:53:37,535 --> 00:53:38,785
Vi mangler et trin.

1113
00:53:38,785 --> 00:53:41,590

1114
00:53:41,590 --> 00:53:43,710
>> PUBLIKUM: New_node næste
skal pege til null.

1115
00:53:43,710 --> 00:53:44,570
>> JASON HIRSCHHORN: Præcis, Alden.

1116
00:53:44,570 --> 00:53:46,600
Og så kan vi vende tilbage sandt.

1117
00:53:46,600 --> 00:53:47,560
OK.

1118
00:53:47,560 --> 00:53:51,630
Men det er stadig en god ide at gøre tingene
i slutningen af ​​listen, right?

1119
00:53:51,630 --> 00:53:51,950
Ok.

1120
00:53:51,950 --> 00:53:54,450
Vi kan stadig faktisk får
til slutningen af ​​listen.

1121
00:53:54,450 --> 00:53:57,870
Så er denne kode fint, hvis vi er på
ende af listen, og der er nogle

1122
00:53:57,870 --> 00:53:59,120
ting på listen?

1123
00:53:59,120 --> 00:54:01,830

1124
00:54:01,830 --> 00:54:02,040
Right?

1125
00:54:02,040 --> 00:54:03,540
Fordi vi stadig har Marcus idé.

1126
00:54:03,540 --> 00:54:06,870
Vi kunne forlade denne løkke, fordi
vi er i slutningen af ​​listen.

1127
00:54:06,870 --> 00:54:09,308
Så har vi stadig ønsker dette
kode hernede?

1128
00:54:09,308 --> 00:54:10,520
>> PUBLIKUM: Ja.

1129
00:54:10,520 --> 00:54:11,000
>> JASON HIRSCHHORN: Ja.

1130
00:54:11,000 --> 00:54:14,190
Og hvad har vi brug for at ændre dette til?

1131
00:54:14,190 --> 00:54:15,440
Sandt.

1132
00:54:15,440 --> 00:54:19,580

1133
00:54:19,580 --> 00:54:21,640
Lyder godt
til alle, indtil videre?

1134
00:54:21,640 --> 00:54:22,420
Nogen, der har nogen -

1135
00:54:22,420 --> 00:54:23,480
Avi, har du noget at tilføje?

1136
00:54:23,480 --> 00:54:23,920
>> PUBLIKUM: Nej.

1137
00:54:23,920 --> 00:54:25,276
>> JASON HIRSCHHORN: OK.

1138
00:54:25,276 --> 00:54:27,010
Så vi har lavet et par ændringer.

1139
00:54:27,010 --> 00:54:29,540
Vi har lavet denne kontrol, inden vi
gik ind for en tom liste.

1140
00:54:29,540 --> 00:54:31,790
Så vi har taget sig af en tom liste.

1141
00:54:31,790 --> 00:54:35,500
Og her tog vi os af at indsætte
noget i slutningen af ​​listen.

1142
00:54:35,500 --> 00:54:38,930
Så det ser ud som dette, mens loop tage
sig af ting i mellem,

1143
00:54:38,930 --> 00:54:41,920
et eller andet sted på listen, hvis der
er ting på listen.

1144
00:54:41,920 --> 00:54:42,280
>> OK.

1145
00:54:42,280 --> 00:54:44,310
Lad os køre dette program igen.

1146
00:54:44,310 --> 00:54:50,170

1147
00:54:50,170 --> 00:54:50,755
Ikke lykkes.

1148
00:54:50,755 --> 00:54:52,190
>> PUBLIKUM: Du klarede det ikke.

1149
00:54:52,190 --> 00:54:53,940
>> JASON HIRSCHHORN: Åh,
Jeg klarede det ikke.

1150
00:54:53,940 --> 00:54:56,250
God pointe, Michael.

1151
00:54:56,250 --> 00:54:57,500
Lad os tilføje en make forbundet.

1152
00:54:57,500 --> 00:55:01,590

1153
00:55:01,590 --> 00:55:04,830
Linje 87 er der en fejl.

1154
00:55:04,830 --> 00:55:05,420
Linie 87.

1155
00:55:05,420 --> 00:55:06,600
Alden, dette var den linje, du gav mig.

1156
00:55:06,600 --> 00:55:08,962
Hvad er der galt?

1157
00:55:08,962 --> 00:55:10,710
>> PUBLIKUM: Det skal være til null.

1158
00:55:10,710 --> 00:55:11,000
>> JASON HIRSCHHORN: Excellent.

1159
00:55:11,000 --> 00:55:11,630
Præcis højre.

1160
00:55:11,630 --> 00:55:13,290
Det bør være nul.

1161
00:55:13,290 --> 00:55:15,210
Lad os gøre igen.

1162
00:55:15,210 --> 00:55:17,220
Kompilere.

1163
00:55:17,220 --> 00:55:17,890
OK.

1164
00:55:17,890 --> 00:55:19,400
Lad os indsætte tre.

1165
00:55:19,400 --> 00:55:20,570
Indsatsen var en succes.

1166
00:55:20,570 --> 00:55:21,660
Lad os printe det ud.

1167
00:55:21,660 --> 00:55:23,590
Åh, hvis bare vi kunne kontrollere.

1168
00:55:23,590 --> 00:55:25,500
Men vi har ikke gjort det
udskrive funktion endnu.

1169
00:55:25,500 --> 00:55:27,840
Lad os komme noget andet.

1170
00:55:27,840 --> 00:55:29,090
Hvad skal vi ind?

1171
00:55:29,090 --> 00:55:31,120

1172
00:55:31,120 --> 00:55:31,940
>> PUBLIKUM: Seven.

1173
00:55:31,940 --> 00:55:33,340
>> JASON HIRSCHHORN: Seven?

1174
00:55:33,340 --> 00:55:34,590
>> PUBLIKUM: Ja.

1175
00:55:34,590 --> 00:55:38,680

1176
00:55:38,680 --> 00:55:39,780
>> JASON HIRSCHHORN: Vi har en seg fejl.

1177
00:55:39,780 --> 00:55:43,760
Så vi fik en, men vi klart
kan ikke få to.

1178
00:55:43,760 --> 00:55:45,690
Det er 05:07.

1179
00:55:45,690 --> 00:55:48,370
Så kunne vi debug dette
tre minutter.

1180
00:55:48,370 --> 00:55:51,240
Men jeg har tænkt mig at forlade os her
og gå videre til hash tabeller.

1181
00:55:51,240 --> 00:55:54,290
Men igen, svarene for denne kode
Jeg vil maile den til dig i en bit.

1182
00:55:54,290 --> 00:55:55,440
Vi er meget tæt på den.

1183
00:55:55,440 --> 00:55:58,300
Jeg stærkt opfordre dig til at finde ud af
hvad der foregår her, og ordne det.

1184
00:55:58,300 --> 00:56:02,400
Så jeg vil emaile dig denne kode som
godt plus løsning -

1185
00:56:02,400 --> 00:56:03,670
sandsynligvis opløsningen senere.

1186
00:56:03,670 --> 00:56:05,110
Først denne kode.

1187
00:56:05,110 --> 00:56:08,290
>> Den anden ting, jeg ønsker at gøre, før vi
finish er vi ikke har frigjort noget.

1188
00:56:08,290 --> 00:56:10,370
Så jeg vil gerne vise dig, hvad
Valgrind ser ud.

1189
00:56:10,370 --> 00:56:14,310
Hvis vi kører Valgrind grænser
på vores program,. / forbundet.

1190
00:56:14,310 --> 00:56:22,540
Igen, ifølge dette dias, vi
skal løbe valgrind med en form for

1191
00:56:22,540 --> 00:56:26,410
valgmulighed, i dette tilfælde
- Lækage-kontrol = fuld.

1192
00:56:26,410 --> 00:56:27,660
Så lad os skrive valgrind
- Lækage-kontrol = fuld.

1193
00:56:27,660 --> 00:56:31,910

1194
00:56:31,910 --> 00:56:35,080
Så dette vil køre valgrind
på vores program.

1195
00:56:35,080 --> 00:56:37,000
Og nu programmet rent faktisk kører.

1196
00:56:37,000 --> 00:56:40,190
Så vi kommer til at køre det ligesom
før, sætte noget i.

1197
00:56:40,190 --> 00:56:40,830
Jeg har tænkt mig at sætte i tre.

1198
00:56:40,830 --> 00:56:41,790
Der virker.

1199
00:56:41,790 --> 00:56:43,202
Jeg har ikke tænkt mig at forsøge at sætte i noget
andet fordi vi kommer til at

1200
00:56:43,202 --> 00:56:44,710
få en seg falsk i denne sag.

1201
00:56:44,710 --> 00:56:46,700
Så jeg bare at holde op.

1202
00:56:46,700 --> 00:56:50,160
>> Og nu kan du se hernede
lække og bunke resumé.

1203
00:56:50,160 --> 00:56:52,310
Det er de gode ting,
du ønsker at tjekke ud.

1204
00:56:52,310 --> 00:56:56,780
Så bunke resumé - det siger i brug
ved afkørsel - otte bytes i en blok.

1205
00:56:56,780 --> 00:56:58,370
Det ene blok er
node vi malloced.

1206
00:56:58,370 --> 00:57:02,230
Michael, du sagde før en node er otte
bites, fordi det har heltal

1207
00:57:02,230 --> 00:57:02,680
og markøren.

1208
00:57:02,680 --> 00:57:04,550
Så det er vores knudepunkt.

1209
00:57:04,550 --> 00:57:08,170
Og så står vi brugte malloc
syv gange, og vi befriet

1210
00:57:08,170 --> 00:57:08,940
noget seks gange.

1211
00:57:08,940 --> 00:57:13,680
Men vi har aldrig kaldt fri, så jeg har ingen
idé om, hvad det taler om.

1212
00:57:13,680 --> 00:57:18,490
>> Men er det tilstrækkeligt at sige, at når din
program kører, malloc bliver kaldt

1213
00:57:18,490 --> 00:57:20,330
i nogle andre steder, som vi
behøver ikke at bekymre sig om.

1214
00:57:20,330 --> 00:57:22,460
Så malloc var sandsynligvis kaldt
nogle steder.

1215
00:57:22,460 --> 00:57:24,480
Vi behøver ikke at bekymre dig hvor.

1216
00:57:24,480 --> 00:57:26,240
Men det er virkelig os.

1217
00:57:26,240 --> 00:57:27,380
Denne første linie er os.

1218
00:57:27,380 --> 00:57:28,320
Vi forlod denne blok.

1219
00:57:28,320 --> 00:57:30,330
Og du kan se, at her
i lækagen resumé.

1220
00:57:30,330 --> 00:57:31,950
Stadig nås -

1221
00:57:31,950 --> 00:57:32,930
otte bytes i en blok.

1222
00:57:32,930 --> 00:57:34,100
Det betyder, at hukommelsen -

1223
00:57:34,100 --> 00:57:35,730
Vi har lækket denne hukommelse.

1224
00:57:35,730 --> 00:57:37,570
Definitely tabt -

1225
00:57:37,570 --> 00:57:38,770
noget er tabt for altid.

1226
00:57:38,770 --> 00:57:40,590
Generelt, vil du ikke
se noget der.

1227
00:57:40,590 --> 00:57:44,780
Stadig nås generelt hvor
vil du se ting, hvor du ønsker

1228
00:57:44,780 --> 00:57:48,900
at se på, hvad kode skal du
har frigjort, men du glemte at befri.

1229
00:57:48,900 --> 00:57:53,170
>> Og hvis dette ikke var tilfældet,
hvis vi gjorde fri alt,

1230
00:57:53,170 --> 00:57:54,360
vi kan kontrollere det.

1231
00:57:54,360 --> 00:57:57,330
Lad os bare køre programmet
ikke at lægge i noget.

1232
00:57:57,330 --> 00:57:59,800
Du vil se hernede i brug ved afkørsel -

1233
00:57:59,800 --> 00:58:01,310
nul bytes i nul blokke.

1234
00:58:01,310 --> 00:58:06,310
Det betyder, at vi ikke havde noget venstre
når programmet forlades.

1235
00:58:06,310 --> 00:58:12,090
Så før du tænder i pset6 køre valgrind
og sørg for at du ikke har

1236
00:58:12,090 --> 00:58:15,310
enhver memory leaks i dit program.

1237
00:58:15,310 --> 00:58:17,910
Hvis du har nogen spørgsmål med valgrind,
velkommen til at nå ud.

1238
00:58:17,910 --> 00:58:18,700
Men det er hvordan du bruger det.

1239
00:58:18,700 --> 00:58:20,890
Meget simpelt - se om du
har i brug ved afkørsel -

1240
00:58:20,890 --> 00:58:22,270
eventuelle bytes i alle blokke.

1241
00:58:22,270 --> 00:58:27,890

1242
00:58:27,890 --> 00:58:29,580
>> Så vi arbejdede på insert node.

1243
00:58:29,580 --> 00:58:33,840
Jeg havde to andre funktioner her -
printe noder og gratis noder.

1244
00:58:33,840 --> 00:58:37,780
Igen er disse funktioner, der er
vil være godt for dig at øve

1245
00:58:37,780 --> 00:58:40,990
fordi de vil hjælpe dig ikke kun med
disse prøve øvelser, men også

1246
00:58:40,990 --> 00:58:42,180
om problemet indstillet.

1247
00:58:42,180 --> 00:58:44,230
De kort på temmelig nøje til tingene
du er nødt til at gøre i

1248
00:58:44,230 --> 00:58:45,010
problem indstillet.

1249
00:58:45,010 --> 00:58:47,640
Men jeg ønsker at sørge
vi komme ind på alt.

1250
00:58:47,640 --> 00:58:50,400
Og hash tabeller er også afgørende for at
hvad vi laver i afsnittet dette

1251
00:58:50,400 --> 00:58:51,980
uge - eller problemet sæt.

1252
00:58:51,980 --> 00:58:55,200
>> Så vi kommer til at afslutte afsnittet
taler om hash-tabeller.

1253
00:58:55,200 --> 00:58:58,140
Hvis du bemærker jeg lavet en
lidt hash tabellen.

1254
00:58:58,140 --> 00:59:00,020
Det er ikke, hvad vi taler
om, dog.

1255
00:59:00,020 --> 00:59:03,540
Vi taler om en anden
type hash tabeller.

1256
00:59:03,540 --> 00:59:07,300
Og på sin kerne, en hash tabel
er intet mere end en

1257
00:59:07,300 --> 00:59:08,860
matrix plus en hash-funktion.

1258
00:59:08,860 --> 00:59:11,150
Vi kommer til at tale lidt bare for at
at sikre alle forstår, hvad en

1259
00:59:11,150 --> 00:59:12,110
hash-funktionen er.

1260
00:59:12,110 --> 00:59:15,420
Og jeg fortæller dig nu, at det er
intet mere end to ting -

1261
00:59:15,420 --> 00:59:18,590
en matrix og en hash-funktion.

1262
00:59:18,590 --> 00:59:20,716
Og her er de skridt gennem
denne driver.

1263
00:59:20,716 --> 00:59:31,560

1264
00:59:31,560 --> 00:59:32,810
>> Der er vores array.

1265
00:59:32,810 --> 00:59:38,460

1266
00:59:38,460 --> 00:59:39,460
Der er vores funktion.

1267
00:59:39,460 --> 00:59:43,180
Navnlig hashfunktioner nødt til at
gøre et par ting med dette.

1268
00:59:43,180 --> 00:59:45,040
Jeg har tænkt mig at tale specifikt
om dette problem indstillet.

1269
00:59:45,040 --> 00:59:46,450
Det er formentlig kommer til at
tage i en streng.

1270
00:59:46,450 --> 00:59:50,570

1271
00:59:50,570 --> 00:59:51,770
Og hvad det kommer til at vende tilbage?

1272
00:59:51,770 --> 00:59:52,640
Hvilke data type?

1273
00:59:52,640 --> 00:59:54,260
Alden?

1274
00:59:54,260 --> 00:59:55,760
Din hash funktion tilbage?

1275
00:59:55,760 --> 00:59:58,760
Et heltal.

1276
00:59:58,760 --> 01:00:01,700
Så dette er hvad hash
tabel består af -

1277
01:00:01,700 --> 01:00:05,430
en tabel i form af matrix
og en hash-funktion.

1278
01:00:05,430 --> 01:00:06,010
Hvordan fungerer det?

1279
01:00:06,010 --> 01:00:07,300
Det virker i tre trin.

1280
01:00:07,300 --> 01:00:08,740
Vi giver det en nøgle.

1281
01:00:08,740 --> 01:00:11,470
I dette tilfælde, vil vi give det en streng.

1282
01:00:11,470 --> 01:00:18,140
Vi kalder hashfunktionen per trin et
på nøglen, og vi får en værdi.

1283
01:00:18,140 --> 01:00:20,310
>> Konkret vil vi sige
vi får et heltal.

1284
01:00:20,310 --> 01:00:25,630
Det heltal, der er meget specifikke
grænser for, hvad der heltal kan være.

1285
01:00:25,630 --> 01:00:28,880
I dette eksempel vores matrix
er størrelse tre.

1286
01:00:28,880 --> 01:00:32,330
Så hvad numre kan det heltal være.

1287
01:00:32,330 --> 01:00:35,970
Hvad er intervallet af gyldige værdier for
at heltal, tilbagesendelse type af denne

1288
01:00:35,970 --> 01:00:37,220
hash funktion?

1289
01:00:37,220 --> 01:00:40,440

1290
01:00:40,440 --> 01:00:42,110
Nul, en og to.

1291
01:00:42,110 --> 01:00:46,060
Pointen i hash funktion er at
regne ud stedet i array

1292
01:00:46,060 --> 01:00:47,790
hvor vores nøgle går.

1293
01:00:47,790 --> 01:00:51,290
Der er kun tre mulige
steder her -

1294
01:00:51,290 --> 01:00:52,130
nul, en eller to.

1295
01:00:52,130 --> 01:00:55,360
Så denne funktion bedre afkast
nul, en eller to.

1296
01:00:55,360 --> 01:00:58,740
Nogle gyldigt indice i dette array.

1297
01:00:58,740 --> 01:01:02,770
>> Og så afhængigt af hvor det vender tilbage,
du kan se der matrix åben

1298
01:01:02,770 --> 01:01:03,730
bracketing værdien.

1299
01:01:03,730 --> 01:01:05,800
Det er, hvor vi sætter nøglen.

1300
01:01:05,800 --> 01:01:11,280
Så vi smider i græskar,
vi kommer ud nul.

1301
01:01:11,280 --> 01:01:15,540
På vifte beslag 0, sætter vi græskar.

1302
01:01:15,540 --> 01:01:21,070
Vi smider i katte, vi får ud en.

1303
01:01:21,070 --> 01:01:24,110
Vi sætter kat på én.

1304
01:01:24,110 --> 01:01:25,480
Vi sætter i edderkop.

1305
01:01:25,480 --> 01:01:26,710
Vi kommer ud to.

1306
01:01:26,710 --> 01:01:30,200
Vi sætter edderkop vifte beslag to.

1307
01:01:30,200 --> 01:01:32,300
Det ville være så rart, hvis
det virkede sådan.

1308
01:01:32,300 --> 01:01:35,570
Men desværre, som vi skal se,
det er lidt mere kompliceret.

1309
01:01:35,570 --> 01:01:37,570
>> Før vi kommer derhen, eventuelle spørgsmål
om denne grundlæggende

1310
01:01:37,570 --> 01:01:38,820
opsætning af en hash tabel?

1311
01:01:38,820 --> 01:01:49,050

1312
01:01:49,050 --> 01:01:51,940
Dette er et billede af præcis
hvad vi trak på tavlen.

1313
01:01:51,940 --> 01:01:55,420
Men da vi trak den på brættet, jeg
vil ikke gå ind i det yderligere.

1314
01:01:55,420 --> 01:02:00,430
Væsentlige nøgler, den magiske sorte boks -
eller i dette tilfælde, krikand box - en

1315
01:02:00,430 --> 01:02:02,410
hash funktion sætter dem i spande.

1316
01:02:02,410 --> 01:02:04,690
Og i dette eksempel er vi
ikke sætte navn.

1317
01:02:04,690 --> 01:02:07,880
Vi sætter den tilhørende telefon
Antallet af navnet i spanden.

1318
01:02:07,880 --> 01:02:10,430
Men du kunne meget vel bare
sætte navn på spanden.

1319
01:02:10,430 --> 01:02:12,950
>> Dette er blot et billede af, hvad
vi trak på tavlen.

1320
01:02:12,950 --> 01:02:14,460
Vi har potentielle faldgruber, selv om.

1321
01:02:14,460 --> 01:02:17,470
Og der er især to
glider, at jeg ønsker at gå over.

1322
01:02:17,470 --> 01:02:20,230
Den første er om
en hash-funktion.

1323
01:02:20,230 --> 01:02:22,620
Så jeg stillede spørgsmålet, hvad
gør en god hashfunktion?

1324
01:02:22,620 --> 01:02:24,220
Jeg giver to svar.

1325
01:02:24,220 --> 01:02:26,630
Den første er, at det er deterministisk.

1326
01:02:26,630 --> 01:02:29,660
I forbindelse med hashfunktioner,
hvad betyder det?

1327
01:02:29,660 --> 01:02:37,840

1328
01:02:37,840 --> 01:02:39,282
Ja?

1329
01:02:39,282 --> 01:02:42,850
>> PUBLIKUM: Det kan finde
indeks i konstant tid?

1330
01:02:42,850 --> 01:02:43,810
>> JASON HIRSCHHORN: At
er ikke, hvad det betyder.

1331
01:02:43,810 --> 01:02:44,725
Men det er et godt gæt.

1332
01:02:44,725 --> 01:02:46,100
Nogen andre har et gæt
hvad dette betyder?

1333
01:02:46,100 --> 01:02:47,780
At en god hash funktion
er deterministisk?

1334
01:02:47,780 --> 01:02:48,280
Annie?

1335
01:02:48,280 --> 01:02:51,680
>> PUBLIKUM: At en nøgle kun kan kortlægges
til ét sted i hash tabellen.

1336
01:02:51,680 --> 01:02:53,070
>> JASON HIRSCHHORN: Det er
helt rigtigt.

1337
01:02:53,070 --> 01:02:57,430
Hver gang du lægger i græskar,
det altid returnerer nul.

1338
01:02:57,430 --> 01:03:01,660
Hvis du lægger i græskar og dit hash
funktion returnerer nul, men har en

1339
01:03:01,660 --> 01:03:06,060
sandsynlighed for at returnere noget
andet større end nul -

1340
01:03:06,060 --> 01:03:09,280
så måske kan det vende tilbage en til tider
eller to andre tidspunkter -

1341
01:03:09,280 --> 01:03:11,100
det er ikke en god hashfunktion.

1342
01:03:11,100 --> 01:03:11,800
Du er helt rigtigt.

1343
01:03:11,800 --> 01:03:15,680
Din hash-funktionen skal returnere
nøjagtig samme tal, i dette tilfælde, for

1344
01:03:15,680 --> 01:03:17,780
nøjagtig de samme streng.

1345
01:03:17,780 --> 01:03:22,210
>> Måske er det returnerer den samme nøjagtige tal
for den samme nøjagtige streng

1346
01:03:22,210 --> 01:03:24,430
uanset kapitalisering.

1347
01:03:24,430 --> 01:03:27,980
Men i så fald er det stadig
deterministisk fordi flere ting

1348
01:03:27,980 --> 01:03:29,350
afbildes på den samme værdi.

1349
01:03:29,350 --> 01:03:30,170
Det er fint.

1350
01:03:30,170 --> 01:03:32,615
Så længe der kun er én
output for et givet input.

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
Den anden ting er, at det
returnerer gyldige indeks.

1354
01:03:38,340 --> 01:03:40,220
Vi bragt op, at tidligere.

1355
01:03:40,220 --> 01:03:41,860
Denne hash-funktion -

1356
01:03:41,860 --> 01:03:43,710
oh boy -

1357
01:03:43,710 --> 01:03:46,840
en hash-funktion skal
returnere gyldige indeks.

1358
01:03:46,840 --> 01:03:47,740
Så sige -

1359
01:03:47,740 --> 01:03:48,990
lad os gå tilbage til dette eksempel.

1360
01:03:48,990 --> 01:03:52,580

1361
01:03:52,580 --> 01:03:57,540
Min hash funktion tæller op
bogstaverne i ordet.

1362
01:03:57,540 --> 01:03:58,380
Det er hash-funktionen.

1363
01:03:58,380 --> 01:03:59,740
Og returnerer det heltal.

1364
01:03:59,740 --> 01:04:04,280
Så hvis jeg har ordet A, er det
kommer til at vende tilbage en.

1365
01:04:04,280 --> 01:04:06,900
Og det kommer til at sætte en lige her.

1366
01:04:06,900 --> 01:04:09,430
Hvad hvis jeg sætter i ordet bat?

1367
01:04:09,430 --> 01:04:11,310
Det kommer til at vende tilbage tre.

1368
01:04:11,310 --> 01:04:12,560
Hvor bliver bat hen?

1369
01:04:12,560 --> 01:04:18,730

1370
01:04:18,730 --> 01:04:19,750
>> Det passer ikke.

1371
01:04:19,750 --> 01:04:21,000
Men det skal gå et eller andet sted.

1372
01:04:21,000 --> 01:04:23,340
Dette er min hash tabellen efter alle, og
alt skal gå et sted.

1373
01:04:23,340 --> 01:04:24,590
Så hvor skal bat hen?

1374
01:04:24,590 --> 01:04:28,020

1375
01:04:28,020 --> 01:04:28,710
Nogen tanker?

1376
01:04:28,710 --> 01:04:29,450
Gæt?

1377
01:04:29,450 --> 01:04:30,280
Gode ​​gæt?

1378
01:04:30,280 --> 01:04:31,220
>> PUBLIKUM: Zero.

1379
01:04:31,220 --> 01:04:32,120
>> JASON HIRSCHHORN: Hvorfor nul?

1380
01:04:32,120 --> 01:04:35,990
>> PUBLIKUM: Da tre
modulo tre er nul?

1381
01:04:35,990 --> 01:04:38,620
>> JASON HIRSCHHORN: Tre
modulo tre er nul.

1382
01:04:38,620 --> 01:04:40,810
Det er en stor gæt,
og det er korrekt.

1383
01:04:40,810 --> 01:04:43,870
Så i dette tilfælde skal
sandsynligvis gå på nul.

1384
01:04:43,870 --> 01:04:51,080
Så en god måde at sikre, at denne hash
Funktionen returnerer kun gyldige indekser

1385
01:04:51,080 --> 01:04:54,580
at modulo det af størrelsen af ​​tabellen.

1386
01:04:54,580 --> 01:04:57,360
Hvis du modulo Hvad det afkast ved
tre, er du altid kommer til at få

1387
01:04:57,360 --> 01:05:00,930
noget mellem nul, en og to.

1388
01:05:00,930 --> 01:05:05,160
Og hvis det returnerer altid syv, og
du altid modulo af tre, er du

1389
01:05:05,160 --> 01:05:06,030
altid vil få den samme ting.

1390
01:05:06,030 --> 01:05:09,270
>> Så det er stadig deterministiske
hvis du modulo.

1391
01:05:09,270 --> 01:05:11,420
Men der vil sikre, at du
aldrig få noget -

1392
01:05:11,420 --> 01:05:12,940
en ugyldig industri.

1393
01:05:12,940 --> 01:05:16,840
Generelt bør der modulo ske
inde i din hash funktion.

1394
01:05:16,840 --> 01:05:18,240
Så du behøver ikke at bekymre dig om dette.

1395
01:05:18,240 --> 01:05:20,555
Du skal bare kan sikre, at
dette er en gyldig Index.

1396
01:05:20,555 --> 01:05:23,700

1397
01:05:23,700 --> 01:05:26,700
Eventuelle spørgsmål vedrørende denne
potentiel faldgrube?

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
Og der går vi.

1401
01:05:40,290 --> 01:05:42,890
Næste potentiel faldgrube, og
dette er den store.

1402
01:05:42,890 --> 01:05:46,880
Hvad hvis to taster kort
til den samme værdi?

1403
01:05:46,880 --> 01:05:49,350
Så der er to måder at håndtere dette.

1404
01:05:49,350 --> 01:05:53,140

1405
01:05:53,140 --> 01:05:56,020
Den første hedder lineær
sondering, som jeg er

1406
01:05:56,020 --> 01:05:57,300
ikke kommer til at gå over.

1407
01:05:57,300 --> 01:06:01,120
Men du skal være fortrolig med, hvordan
der virker, og hvad det er.

1408
01:06:01,120 --> 01:06:05,610
>> Den anden jeg kommer til at gå over
fordi det er den, der mange

1409
01:06:05,610 --> 01:06:08,290
mennesker vil sandsynligvis ende med at beslutte
at bruge i deres problem sæt.

1410
01:06:08,290 --> 01:06:09,820
Selvfølgelig behøver du ikke at.

1411
01:06:09,820 --> 01:06:15,280
Men problemet sæt mange mennesker
en tendens til at vælge at oprette en hash tabel

1412
01:06:15,280 --> 01:06:17,950
med separat kæde til at gennemføre
deres ordbog.

1413
01:06:17,950 --> 01:06:21,390
Så vi kommer til at gå over, hvad det betyder
at skabe en hash tabel med

1414
01:06:21,390 --> 01:06:23,890
separat kæde.

1415
01:06:23,890 --> 01:06:26,260
>> Så jeg sat i græskar.

1416
01:06:26,260 --> 01:06:29,560
Den returnerer nul.

1417
01:06:29,560 --> 01:06:31,410
Og jeg sætter græskar her.

1418
01:06:31,410 --> 01:06:35,880

1419
01:06:35,880 --> 01:06:37,930
Derefter sætte jeg i -

1420
01:06:37,930 --> 01:06:39,922
hvad er en anden Halloween-tema ting?

1421
01:06:39,922 --> 01:06:42,200
>> PUBLIKUM: Candy.

1422
01:06:42,200 --> 01:06:42,770
>> JASON HIRSCHHORN: Candy!

1423
01:06:42,770 --> 01:06:43,910
Det er en stor en.

1424
01:06:43,910 --> 01:06:47,760
Jeg sætter i slik og slik
giver mig også nul.

1425
01:06:47,760 --> 01:06:49,350
Hvad gør jeg?

1426
01:06:49,350 --> 01:06:51,940
Nogen idéer?

1427
01:06:51,940 --> 01:06:53,940
Fordi du alle slags kender
hvad separat kæde er.

1428
01:06:53,940 --> 01:06:55,190
Så nogen ideer hvad man skal gøre?

1429
01:06:55,190 --> 01:06:58,170

1430
01:06:58,170 --> 01:06:59,110
Ja.

1431
01:06:59,110 --> 01:07:03,810
>> PUBLIKUM: Sætte strengen
faktisk i hash tabellen.

1432
01:07:03,810 --> 01:07:08,910
>> JASON HIRSCHHORN: Så vi kommer til at
trække den gode idé herovre.

1433
01:07:08,910 --> 01:07:09,340
OK.

1434
01:07:09,340 --> 01:07:12,290
>> PUBLIKUM: Have Hashtable
[Uhørligt]

1435
01:07:12,290 --> 01:07:16,640
markøren, der peger på
begyndelsen af ​​en liste.

1436
01:07:16,640 --> 01:07:20,930
Og så har græskar være den første værdi
i det linkede liste og slik være

1437
01:07:20,930 --> 01:07:22,800
den anden værdi i den linkede liste.

1438
01:07:22,800 --> 01:07:23,420
>> JASON HIRSCHHORN: OK.

1439
01:07:23,420 --> 01:07:24,670
Marcus, der var udestående.

1440
01:07:24,670 --> 01:07:26,160
Jeg har tænkt mig at bryde ned.

1441
01:07:26,160 --> 01:07:28,890
Marcus siger ikke
overskrive græskar.

1442
01:07:28,890 --> 01:07:30,660
Det ville være dårligt.

1443
01:07:30,660 --> 01:07:33,640
Må ikke sætte slik et andet sted.

1444
01:07:33,640 --> 01:07:35,390
Vi kommer til at sætte dem begge på nul.

1445
01:07:35,390 --> 01:07:37,770
Men vi kommer til at beskæftige sig med
sætte dem på nul ved

1446
01:07:37,770 --> 01:07:39,395
oprette en liste på nul.

1447
01:07:39,395 --> 01:07:42,430
Og vi kommer til at oprette en liste over
alt, hvad der kortlagt til nul.

1448
01:07:42,430 --> 01:07:47,960
Og den bedste måde, vi har lært at skabe
en liste, der kan vokse og krympe

1449
01:07:47,960 --> 01:07:49,840
dynamisk ikke er inden for
andet array.

1450
01:07:49,840 --> 01:07:51,510
Så ikke en multi-dimensional array.

1451
01:07:51,510 --> 01:07:54,080
Men bare at oprette en sammenkædet liste.

1452
01:07:54,080 --> 01:07:55,330
>> Så hvad han foreslog -

1453
01:07:55,330 --> 01:07:57,950

1454
01:07:57,950 --> 01:07:59,200
Jeg har tænkt mig at få en ny -

1455
01:07:59,200 --> 01:08:15,380

1456
01:08:15,380 --> 01:08:19,689
er at skabe et array med pointere,
en vifte af pegepinde.

1457
01:08:19,689 --> 01:08:20,580
OK.

1458
01:08:20,580 --> 01:08:24,180
Enhver idé eller hint, hvad den type
af denne pointers skal være?

1459
01:08:24,180 --> 01:08:26,290
Marcus?

1460
01:08:26,290 --> 01:08:27,250
>> PUBLIKUM: Tip til at -

1461
01:08:27,250 --> 01:08:28,609
>> JASON HIRSCHHORN: Fordi du
sagde en sammenkædet liste, så -

1462
01:08:28,609 --> 01:08:29,520
>> PUBLIKUM: Node pointers?

1463
01:08:29,520 --> 01:08:30,670
>> JASON HIRSCHHORN: Node pointers.

1464
01:08:30,670 --> 01:08:32,830
Hvis de ting i vores knyttet
listen er knudepunkter, så de

1465
01:08:32,830 --> 01:08:34,370
bør være node pointers.

1466
01:08:34,370 --> 01:08:35,939
Og hvad gør de lige i begyndelsen?

1467
01:08:35,939 --> 01:08:36,990
>> PUBLIKUM: 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
Så der er vores tomme ting.

1471
01:08:46,080 --> 01:08:47,170
Græskar returnerer nul.

1472
01:08:47,170 --> 01:08:48,569
Hvad gør vi?

1473
01:08:48,569 --> 01:08:49,609
Walk mig igennem det?

1474
01:08:49,609 --> 01:08:50,810
Faktisk, Marcus allerede gav mig.

1475
01:08:50,810 --> 01:08:52,439
Nogen ellers gå mig igennem det.

1476
01:08:52,439 --> 01:08:54,760
Hvad vi gør, når vi -

1477
01:08:54,760 --> 01:08:56,609
dette ligner meget
hvad vi bare gør.

1478
01:08:56,609 --> 01:08:57,396
Avi.

1479
01:08:57,396 --> 01:08:59,090
>> PUBLIKUM: Jeg har tænkt mig at tage et gæt.

1480
01:08:59,090 --> 01:09:01,250
Så når du får slik.

1481
01:09:01,250 --> 01:09:01,640
>> JASON HIRSCHHORN: Ja.

1482
01:09:01,640 --> 01:09:03,120
Godt, vi fik græskar.

1483
01:09:03,120 --> 01:09:03,870
Lad os få vores første.

1484
01:09:03,870 --> 01:09:04,324
Vi fik græskar.

1485
01:09:04,324 --> 01:09:04,779
>> PUBLIKUM: OK.

1486
01:09:04,779 --> 01:09:05,880
Græskar returnerer nul.

1487
01:09:05,880 --> 01:09:08,770
Så du sætte det i det.

1488
01:09:08,770 --> 01:09:10,810
Eller faktisk, du sætter det
i den linkede liste.

1489
01:09:10,810 --> 01:09:13,550
>> JASON HIRSCHHORN: Hvordan kan vi
sætte det i den linkede liste?

1490
01:09:13,550 --> 01:09:15,479
>> PUBLIKUM: Åh, det faktiske syntaks?

1491
01:09:15,479 --> 01:09:16,240
>> JASON HIRSCHHORN: Bare gå -

1492
01:09:16,240 --> 01:09:16,740
sige mere.

1493
01:09:16,740 --> 01:09:19,310
Hvad gør vi?

1494
01:09:19,310 --> 01:09:22,100
>> PUBLIKUM: Du skal bare indsætte
den som det første knudepunkt.

1495
01:09:22,100 --> 01:09:22,675
>> JASON HIRSCHHORN: OK.

1496
01:09:22,675 --> 01:09:29,069
Så vi har vores knude, græskar.

1497
01:09:29,069 --> 01:09:31,560
Og nu, hvordan indsætter jeg det?

1498
01:09:31,560 --> 01:09:34,590

1499
01:09:34,590 --> 01:09:37,090
>> PUBLIKUM: Du tildeler
det af markøren.

1500
01:09:37,090 --> 01:09:37,970
>> JASON HIRSCHHORN: Hvilket pointer?

1501
01:09:37,970 --> 01:09:39,620
>> PUBLIKUM: Markøren på nul.

1502
01:09:39,620 --> 01:09:41,420
>> JASON HIRSCHHORN: Så hvor
gør dette punkt?

1503
01:09:41,420 --> 01:09:42,810
>> PUBLIKUM: At null lige nu.

1504
01:09:42,810 --> 01:09:43,529
>> JASON HIRSCHHORN: Jamen,
det peger til null.

1505
01:09:43,529 --> 01:09:44,499
Men jeg lægger i græskar.

1506
01:09:44,499 --> 01:09:46,053
Så hvor skal det pege?

1507
01:09:46,053 --> 01:09:46,880
>> PUBLIKUM: At græskar.

1508
01:09:46,880 --> 01:09:47,399
>> JASON HIRSCHHORN: At græskar.

1509
01:09:47,399 --> 01:09:48,760
Præcis.

1510
01:09:48,760 --> 01:09:50,010
Så dette peger på græskar.

1511
01:09:50,010 --> 01:09:52,500

1512
01:09:52,500 --> 01:09:54,250
Og hvor gør dette pointer
i græskar punkt?

1513
01:09:54,250 --> 01:09:57,986

1514
01:09:57,986 --> 01:09:58,340
Til

1515
01:09:58,340 --> 01:09:58,590
>> PUBLIKUM: Null.

1516
01:09:58,590 --> 01:09:59,210
>> JASON HIRSCHHORN: At null.

1517
01:09:59,210 --> 01:10:00,460
Præcis.

1518
01:10:00,460 --> 01:10:03,570

1519
01:10:03,570 --> 01:10:05,140
Så vi lige har indsat noget
i den linkede liste.

1520
01:10:05,140 --> 01:10:07,210
Vi har lige skrev denne kode til at gøre dette.

1521
01:10:07,210 --> 01:10:09,520
Næsten vi næsten fik det
helt revnet.

1522
01:10:09,520 --> 01:10:10,790
Nu indsætter vi slik.

1523
01:10:10,790 --> 01:10:13,480
Vores slik går også til nul.

1524
01:10:13,480 --> 01:10:16,100
Så hvad gør vi med slik?

1525
01:10:16,100 --> 01:10:18,790
>> PUBLIKUM: Det afhænger af, hvorvidt
ikke vi prøver at sortere det.

1526
01:10:18,790 --> 01:10:19,640
>> JASON HIRSCHHORN: Det er
helt rigtigt.

1527
01:10:19,640 --> 01:10:21,070
Det afhænger af, hvorvidt
vi forsøger at sortere det.

1528
01:10:21,070 --> 01:10:22,660
Lad os antage, at vi ikke er
kommer til at sortere det.

1529
01:10:22,660 --> 01:10:24,880
>> PUBLIKUM: Nå da, da vi diskuterede
før, er det enkleste bare at sætte det

1530
01:10:24,880 --> 01:10:28,590
lige i starten, så markøren
fra nul point til slik.

1531
01:10:28,590 --> 01:10:29,020
>> JASON HIRSCHHORN: OK.

1532
01:10:29,020 --> 01:10:29,380
Hold ud.

1533
01:10:29,380 --> 01:10:30,630
Lad mig skabe slik lige her.

1534
01:10:30,630 --> 01:10:34,030

1535
01:10:34,030 --> 01:10:35,150
Så denne pointer -

1536
01:10:35,150 --> 01:10:37,590
>> PUBLIKUM: Yeah, bør nu
være at pege på slik.

1537
01:10:37,590 --> 01:10:40,580
Har derefter markøren fra
slik point til græskar.

1538
01:10:40,580 --> 01:10:43,140

1539
01:10:43,140 --> 01:10:44,560
>> JASON HIRSCHHORN: Ligesom det?

1540
01:10:44,560 --> 01:10:47,380
Og sige, vi fik en anden
ting at kortlægge til nul?

1541
01:10:47,380 --> 01:10:48,660
>> PUBLIKUM: Nå, du lige
gøre det samme?

1542
01:10:48,660 --> 01:10:50,290
>> JASON HIRSCHHORN: Gør det samme.

1543
01:10:50,290 --> 01:10:53,700
Så i dette tilfælde, hvis vi ikke gør
ønsker at holde det sorteret det

1544
01:10:53,700 --> 01:10:55,270
lyder temmelig simpelt.

1545
01:10:55,270 --> 01:10:59,920
Vi tager markøren i indice
afgivet vores hash-funktionen.

1546
01:10:59,920 --> 01:11:03,830
Vi har dette punkt til vores nye node.

1547
01:11:03,830 --> 01:11:07,830
Og så hvad det pegede
til tidligere -

1548
01:11:07,830 --> 01:11:10,620
i dette tilfælde nul i
andet tilfælde græskar -

1549
01:11:10,620 --> 01:11:15,310
at uanset hvad det er at pege på
tidligere, tilføjer vi ind i den næste af

1550
01:11:15,310 --> 01:11:17,810
vores nye knudepunkt.

1551
01:11:17,810 --> 01:11:19,650
Vi indsætter noget
i begyndelsen.

1552
01:11:19,650 --> 01:11:22,900
I virkeligheden er dette en meget enklere end
forsøger at holde listen sorteres.

1553
01:11:22,900 --> 01:11:25,340
Men igen, vil søgningen blive
mere kompliceret på her.

1554
01:11:25,340 --> 01:11:28,300
Vi vil altid nødt til at gå til slutningen.

1555
01:11:28,300 --> 01:11:29,650
>> OK.

1556
01:11:29,650 --> 01:11:32,750
Eventuelle spørgsmål om separate chaining?

1557
01:11:32,750 --> 01:11:34,690
Hvordan det virker?

1558
01:11:34,690 --> 01:11:35,820
Spørg dem nu.

1559
01:11:35,820 --> 01:11:39,260
Jeg virkelig ønsker at sikre, at du hele
forstå dette, før vi hovedet ud.

1560
01:11:39,260 --> 01:11:48,410

1561
01:11:48,410 --> 01:11:52,060
>> PUBLIKUM: Hvorfor kan du sætte græskar
og slik i den samme

1562
01:11:52,060 --> 01:11:54,108
en del af hash bordet?

1563
01:11:54,108 --> 01:11:55,860
>> JASON HIRSCHHORN: Godt spørgsmål.

1564
01:11:55,860 --> 01:11:59,140
Hvorfor har vi sætte dem i samme
en del af hash bordet?

1565
01:11:59,140 --> 01:12:03,200
Tja, i dette tilfælde vores hash funktion
returnerer nul for dem begge.

1566
01:12:03,200 --> 01:12:05,310
Så de har brug for at gå på indice nul
fordi det er her vi kommer til at

1567
01:12:05,310 --> 01:12:07,420
lede efter dem, hvis vi nogensinde
ønsker at se dem op.

1568
01:12:07,420 --> 01:12:11,750
Igen, med en lineær sondering fremgangsmåde
vi ville ikke sætte dem begge på nul.

1569
01:12:11,750 --> 01:12:13,900
Men i den separate kæde fremgangsmåde
vi kommer til at sætte dem begge på nul

1570
01:12:13,900 --> 01:12:16,620
og derefter oprette en liste fra nul.

1571
01:12:16,620 --> 01:12:20,140
>> Og vi ønsker ikke at overskrive græskar
blot for at fordi så vil vi

1572
01:12:20,140 --> 01:12:21,860
antager, at græskar var
indsættes aldrig.

1573
01:12:21,860 --> 01:12:25,230
Hvis vi bare holde én ting i
placering, der ville være slemt.

1574
01:12:25,230 --> 01:12:28,590
Så ville der ikke være nogen
chance af os nogensinde -

1575
01:12:28,590 --> 01:12:31,660
hvis vi nogensinde haft en to eksemplarer, så vi
ville blot slette vores oprindelige værdi.

1576
01:12:31,660 --> 01:12:34,090
Så det er derfor gør vi denne fremgangsmåde.

1577
01:12:34,090 --> 01:12:36,580
Eller det er derfor vi har valgt - men igen, vi
valgte separat sammenkædning fremgangsmåde

1578
01:12:36,580 --> 01:12:39,670
hvor der er mange andre metoder
man kunne vælge.

1579
01:12:39,670 --> 01:12:41,185
Besvarer det dit spørgsmål?

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
Lineær probing ville indebære -

1584
01:12:47,720 --> 01:12:51,913
hvis vi fandt en kollision på nul, vi
ville se i den næste sted at se, om

1585
01:12:51,913 --> 01:12:54,310
det var åbent og sætte det der.

1586
01:12:54,310 --> 01:12:57,320
Og så ser vi i den næste sport og
se, om det var åben, og sætte det der.

1587
01:12:57,320 --> 01:12:59,780
Så finder vi den næste tilgængelige
åbne stedet og sætte det der.

1588
01:12:59,780 --> 01:13:02,580

1589
01:13:02,580 --> 01:13:03,890
Andre spørgsmål?

1590
01:13:03,890 --> 01:13:05,370
Ja, Avi.

1591
01:13:05,370 --> 01:13:07,490
>> PUBLIKUM: Som en opfølgning på det,
hvad mener du med næste plet?

1592
01:13:07,490 --> 01:13:10,250
I hash tabellen eller på en linket liste.

1593
01:13:10,250 --> 01:13:12,100
>> JASON HIRSCHHORN: Til lineær
programmering, ingen hægtede lister.

1594
01:13:12,100 --> 01:13:13,400
Det næste sted på hash tabellen.

1595
01:13:13,400 --> 01:13:13,820
>> PUBLIKUM: OK.

1596
01:13:13,820 --> 01:13:17,570
Så hash tabel ville være
initialiseres til størrelse -

1597
01:13:17,570 --> 01:13:19,560
ligesom antallet af strenge
at du var at indsætte?

1598
01:13:19,560 --> 01:13:22,170
>> JASON HIRSCHHORN: Du ville
ønsker det skal være rigtig stort.

1599
01:13:22,170 --> 01:13:23,910
Ja.

1600
01:13:23,910 --> 01:13:27,900
Her er et billede af, hvad vi
bare trak på tavlen.

1601
01:13:27,900 --> 01:13:29,470
Igen har vi en kollision lige her.

1602
01:13:29,470 --> 01:13:30,710
på 152.

1603
01:13:30,710 --> 01:13:33,570
Og du vil se vi skabt
en sammenkædet liste ud af det.

1604
01:13:33,570 --> 01:13:38,200

1605
01:13:38,200 --> 01:13:41,850
Igen, hash tabellen særskilt kæde
fremgangsmåde er ikke den, du

1606
01:13:41,850 --> 01:13:45,590
nødt til at tage for problemer indstillet
seks, men er en, en masse

1607
01:13:45,590 --> 01:13:47,100
studerende har tendens til at tage.

1608
01:13:47,100 --> 01:13:51,140
Så på dette notat, lad os tale kortvarigt
før vi hovedet ud af om problemet seks,

1609
01:13:51,140 --> 01:13:52,160
og så vil jeg dele en historie med dig.

1610
01:13:52,160 --> 01:13:55,120
Vi har tre minutter.

1611
01:13:55,120 --> 01:13:55,750
>> Problem sæt seks.

1612
01:13:55,750 --> 01:13:57,790
Du har fire funktioner -

1613
01:13:57,790 --> 01:14:02,430
belastning, check, størrelse og losse.

1614
01:14:02,430 --> 01:14:03,380
Load -

1615
01:14:03,380 --> 01:14:07,120
godt, vi har stået
over belastning lige nu.

1616
01:14:07,120 --> 01:14:09,330
Vi trak belastning på tavlen.

1617
01:14:09,330 --> 01:14:13,230
Og vi selv begyndte kodning en masse
indsættelse i en sammenkædet liste.

1618
01:14:13,230 --> 01:14:18,020
Så belastningen ikke er meget mere end
hvad vi har netop gjort.

1619
01:14:18,020 --> 01:14:21,070
>> Check er, når du har
noget indlæst.

1620
01:14:21,070 --> 01:14:22,580
Det er den samme proces som denne.

1621
01:14:22,580 --> 01:14:26,845
De samme to første dele, hvor du smider
noget i hash-funktionen

1622
01:14:26,845 --> 01:14:29,190
og få sin værdi.

1623
01:14:29,190 --> 01:14:30,700
Men nu er vi ikke at indsætte det.

1624
01:14:30,700 --> 01:14:33,350
Nu leder vi efter det.

1625
01:14:33,350 --> 01:14:37,130
Jeg har prøve kode skrevet til at finde
noget i en sammenkædet liste.

1626
01:14:37,130 --> 01:14:38,250
Jeg vil opfordre dig til at praktisere det.

1627
01:14:38,250 --> 01:14:43,000
Men intuitivt at finde noget
temmelig ligner indsætte noget.

1628
01:14:43,000 --> 01:14:46,540
Faktisk vi tegnede et billede for at finde
noget i en sammenkædet liste, flytter

1629
01:14:46,540 --> 01:14:48,910
igennem, indtil du fik til slutningen.

1630
01:14:48,910 --> 01:14:52,430
Og hvis du fik til slutningen og kunne ikke
finde den, så er det der ikke.

1631
01:14:52,430 --> 01:14:55,400
Så det er check, hovedsageligt.

1632
01:14:55,400 --> 01:14:57,030
>> Næste er størrelse.

1633
01:14:57,030 --> 01:14:57,910
Lad os springe størrelse.

1634
01:14:57,910 --> 01:15:00,040
Endelig har du losser.

1635
01:15:00,040 --> 01:15:02,890
Unload er, vi har ikke draget
på tavlen eller kodet endnu.

1636
01:15:02,890 --> 01:15:05,990
Men jeg vil opfordre dig til at prøve kodning det
i vores prøve linket liste eksempel.

1637
01:15:05,990 --> 01:15:11,440
Men losse intuitivt
svarer til fri -

1638
01:15:11,440 --> 01:15:14,010
eller jeg mener ligner kontrollere.

1639
01:15:14,010 --> 01:15:17,350
Bortset fra nu, hver gang du går
igennem, du er ikke blot at markere at

1640
01:15:17,350 --> 01:15:19,090
se om du har din værdi der.

1641
01:15:19,090 --> 01:15:22,490
Men du tager denne node og
frigøre det væsentlige.

1642
01:15:22,490 --> 01:15:23,610
Det er, hvad unload beder dig om at gøre.

1643
01:15:23,610 --> 01:15:24,670
Gratis alt hvad du har malloced.

1644
01:15:24,670 --> 01:15:27,480
Så du går igennem hele listen
igen, går gennem hele hash

1645
01:15:27,480 --> 01:15:27,760
bord igen.

1646
01:15:27,760 --> 01:15:29,240
Denne gang ikke kontrollere
for at se, hvad der er.

1647
01:15:29,240 --> 01:15:31,080
Bare gratis hvad der er.

1648
01:15:31,080 --> 01:15:33,260
>> Og endelig størrelse.

1649
01:15:33,260 --> 01:15:34,350
Størrelse bør gennemføres.

1650
01:15:34,350 --> 01:15:35,590
Hvis du ikke gennemfører størrelse -

1651
01:15:35,590 --> 01:15:36,250
Jeg vil sige det sådan her.

1652
01:15:36,250 --> 01:15:39,740
Hvis du ikke gennemfører størrelse på præcis
én linje kode, herunder

1653
01:15:39,740 --> 01:15:43,760
returnere erklæring, du er
gør størrelse forkert.

1654
01:15:43,760 --> 01:15:47,170
Så sørg størrelse, fuld design
punkter, så gør du det på præcis én

1655
01:15:47,170 --> 01:15:49,970
linje kode, herunder
afkastet erklæring.

1656
01:15:49,970 --> 01:15:52,450
>> Og du behøver ikke pakke op endnu, Akchar.

1657
01:15:52,450 --> 01:15:53,700
Eager Beaver.

1658
01:15:53,700 --> 01:15:55,820

1659
01:15:55,820 --> 01:16:01,300
Jeg ville sige tak gutter
for at komme til afsnittet.

1660
01:16:01,300 --> 01:16:02,550
Har en Happy Halloween.

1661
01:16:02,550 --> 01:16:05,300

1662
01:16:05,300 --> 01:16:05,960
Dette er mit kostume.

1663
01:16:05,960 --> 01:16:08,850
Jeg vil være iført dette på torsdag
hvis jeg ser dig på kontortid.

1664
01:16:08,850 --> 01:16:14,640
Og hvis du er nysgerrig om nogle mere
baggrund som på dette kostume, føle

1665
01:16:14,640 --> 01:16:19,135
til at tjekke 2011 Afsnit
til en historie om, hvorfor jeg er

1666
01:16:19,135 --> 01:16:20,900
iført græskar kostume.

1667
01:16:20,900 --> 01:16:23,680
Og det er en trist historie.

1668
01:16:23,680 --> 01:16:27,050
Så sørg for at du har
nogle væv i nærheden.

1669
01:16:27,050 --> 01:16:28,680
Men den, hvis du har nogen
spørgsmål, jeg vil holde rundt

1670
01:16:28,680 --> 01:16:29,960
udenfor efter afsnit.

1671
01:16:29,960 --> 01:16:31,510
Held og lykke på problemet sæt seks.

1672
01:16:31,510 --> 01:16:33,540
Og som altid, hvis du har nogen
spørgsmål, så lad mig det vide.

1673
01:16:33,540 --> 01:16:35,584