1
00:00:00,000 --> 00:00:03,423
>> [Musik spiller]

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

3
00:00:05,380 --> 00:00:08,210
>> ANDI Peng: Velkommen til uge 6 i afsnittet.

4
00:00:08,210 --> 00:00:11,620
Vi afveg fra vores standard
sektion tid tirsdag

5
00:00:11,620 --> 00:00:14,130
eftermiddag til denne dejlige søndag morgen.

6
00:00:14,130 --> 00:00:17,330
Tak til alle, der
sluttede sig til mig i dag, men alvorligt,

7
00:00:17,330 --> 00:00:18,170
en runde af bifald.

8
00:00:18,170 --> 00:00:20,600
>> Det er en temmelig stor indsats.

9
00:00:20,600 --> 00:00:23,600
Jeg næsten ikke engang gøre det
op i tid, men det var OK.

10
00:00:23,600 --> 00:00:27,520
Så jeg ved, at alle jer
har netop gjort det til quizzen.

11
00:00:27,520 --> 00:00:30,370
Først og fremmest, velkommen til
bagsiden af ​​dette.

12
00:00:30,370 --> 00:00:32,917
>> For det andet vil vi tale om det.

13
00:00:32,917 --> 00:00:34,000
Vi taler om quizzen.

14
00:00:34,000 --> 00:00:35,700
Vi taler om, hvordan
du laver i klassen.

15
00:00:35,700 --> 00:00:36,550
Du vil være fint.

16
00:00:36,550 --> 00:00:39,080
Jeg har dine quizzer for
dig i slutningen af ​​her,

17
00:00:39,080 --> 00:00:42,120
så hvis du fyre ønsker at tage
et kig på det, helt fint.

18
00:00:42,120 --> 00:00:46,590
>> Så hurtigt, før vi begynder, den
dagsorden for i dag, er som følger.

19
00:00:46,590 --> 00:00:48,430
Som du kan se, er vi
dybest set hurtig fyring

20
00:00:48,430 --> 00:00:52,120
gennem en hel masse datastrukturer
virkelig, virkelig, virkelig hurtigt.

21
00:00:52,120 --> 00:00:54,380
Så som sådan, vil det ikke være
Super interaktive dag.

22
00:00:54,380 --> 00:00:59,620
Det vil bare være mig slags råbe
ting, som du, og hvis jeg forvirre dig,

23
00:00:59,620 --> 00:01:02,680
hvis jeg går for hurtigt, så lad mig det vide.

24
00:01:02,680 --> 00:01:05,200
De er bare forskellige data
strukturer, og som en del

25
00:01:05,200 --> 00:01:07,070
af din pset for denne
kommende uge, vil du

26
00:01:07,070 --> 00:01:10,340
blive bedt om at gennemføre en af ​​dem,
måske to af them-- to af dem

27
00:01:10,340 --> 00:01:12,319
i dit pset.

28
00:01:12,319 --> 00:01:14,610
OK, så jeg bare kommer til at
starte med nogle annonceringer.

29
00:01:14,610 --> 00:01:19,070
Vi vil gå over stakke og køer mere i
dybde end hvad vi gjorde før quizzen.

30
00:01:19,070 --> 00:01:20,990
Vi vil gå over knyttet
listen igen, endnu en gang,

31
00:01:20,990 --> 00:01:23,899
mere i dybden end hvad
vi havde før quizzen.

32
00:01:23,899 --> 00:01:26,440
Og så vil vi tale om hash
borde, træer og forsøger, som

33
00:01:26,440 --> 00:01:28,890
er alle temmelig nødvendigt for din pset.

34
00:01:28,890 --> 00:01:32,925
Og så vil vi gå over nogle
nyttige tips til pset5.

35
00:01:32,925 --> 00:01:37,360
>> OK, så quiz 0.

36
00:01:37,360 --> 00:01:41,090
Gennemsnittet var en 58%.

37
00:01:41,090 --> 00:01:45,370
Det var meget lav, og så jer alle
gjorde meget, meget godt i overensstemmelse

38
00:01:45,370 --> 00:01:46,510
med det.

39
00:01:46,510 --> 00:01:49,970
>> Temmelig meget, tommelfingerregel er, hvis du er
inden en standardafvigelse på middelværdien

40
00:01:49,970 --> 00:01:52,990
især da vi er i en mindre
comfy sektion, er du helt fint.

41
00:01:52,990 --> 00:01:54,120
Du er på rette spor.

42
00:01:54,120 --> 00:01:55,190
Livet er godt.

43
00:01:55,190 --> 00:01:58,952
>> Jeg ved det er skræmmende at tænke, at
Jeg fik ligesom en 40% på denne quiz.

44
00:01:58,952 --> 00:02:00,160
Jeg har tænkt mig at svigte denne klasse.

45
00:02:00,160 --> 00:02:02,243
Jeg lover dig, du er ikke
vil mislykkes klassen.

46
00:02:02,243 --> 00:02:03,680
Du er helt fint.

47
00:02:03,680 --> 00:02:06,850
>> For dem af jer, der fik over
middelværdien, imponerende, imponerende,

48
00:02:06,850 --> 00:02:08,780
lignende, alvorligt godt gået.

49
00:02:08,780 --> 00:02:09,689
Jeg har dem med mig.

50
00:02:09,689 --> 00:02:11,730
Du er velkommen til at komme få dem
i slutningen af ​​afsnittet.

51
00:02:11,730 --> 00:02:14,520
Lad mig vide, hvis du har nogen
problemer, spørgsmål med dem.

52
00:02:14,520 --> 00:02:17,204
Hvis vi tilføje op din score
forkert, så lad os det vide.

53
00:02:17,204 --> 00:02:21,240
>> OK, så pset5, dette er en virkelig
underlig uge for Yale i den forstand

54
00:02:21,240 --> 00:02:24,240
at vores pset skyldes
Onsdag ved middagstid, herunder

55
00:02:24,240 --> 00:02:27,317
den sene dag, så er det faktisk
teoretisk grund tirsdag ved middagstid.

56
00:02:27,317 --> 00:02:29,150
Sandsynligvis ingen færdig
på tirsdag ved middagstid.

57
00:02:29,150 --> 00:02:30,830
Det er helt fint.

58
00:02:30,830 --> 00:02:33,700
Vi kommer til at have kontortid
i aften samt mandag aften.

59
00:02:33,700 --> 00:02:36,810
Og alle afsnittene i denne uge vil
faktisk blive til workshops,

60
00:02:36,810 --> 00:02:38,800
så er du velkommen til at pop i
alle afsnit, du ønsker,

61
00:02:38,800 --> 00:02:42,810
og de vil være slags mini-pset
workshops for hjælp på det.

62
00:02:42,810 --> 00:02:45,620
Så som sådan, det er den eneste sektion
hvor vi undervisningsmateriale.

63
00:02:45,620 --> 00:02:49,220
Alle de andre sektioner vil fokusere
udelukkende på hjælp til pset.

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

65
00:02:50,146 --> 00:02:52,000
>> PUBLIKUM: Hvor er kontortid?

66
00:02:52,000 --> 00:02:56,120
>> ANDI Peng: Kontortid
tonight-- åh, godt spørgsmål.

67
00:02:56,120 --> 00:03:00,580
Jeg tror kontortid i aften
er i Teal eller i Commons.

68
00:03:00,580 --> 00:03:02,984
Hvis du tjekke online CS50
og du går til kontortid,

69
00:03:02,984 --> 00:03:05,650
der bør være en tidsplan,
fortæller dig, hvor alle af dem er.

70
00:03:05,650 --> 00:03:07,954
>> Jeg kender enten i aften
eller i morgen er krikand,

71
00:03:07,954 --> 00:03:10,120
og jeg tror, ​​vi kan have
overdrev for den anden aften.

72
00:03:10,120 --> 00:03:11,020
Jeg er ikke sikker.

73
00:03:11,020 --> 00:03:11,700
Godt spørgsmål.

74
00:03:11,700 --> 00:03:14,430
Tjek på CS50.

75
00:03:14,430 --> 00:03:18,780
>> Cool, spørgsmål til
tidsplan for den næste ligesom tre dage?

76
00:03:18,780 --> 00:03:21,690
Jeg lover jer som David
sagde, det er toppen af ​​bakken.

77
00:03:21,690 --> 00:03:23,050
Du fyre er der næsten.

78
00:03:23,050 --> 00:03:24,644
Blot tre dage mere.

79
00:03:24,644 --> 00:03:26,310
Komme dertil, og så vil vi alle komme ned.

80
00:03:26,310 --> 00:03:28,114
Vi vil have en dejlig CS-fri pause.

81
00:03:28,114 --> 00:03:28,780
Velkommen tilbage.

82
00:03:28,780 --> 00:03:30,779
Vi vil dykke ned i web
programmering og udvikling,

83
00:03:30,779 --> 00:03:35,150
ting, som er meget sjovt sammenlignet
at nogle af de andre psets.

84
00:03:35,150 --> 00:03:37,974
Og det vil være chill, og
Vi vil have masser af sjov.

85
00:03:37,974 --> 00:03:38,890
Vi vil have mere slik.

86
00:03:38,890 --> 00:03:39,730
Sorry for slik.

87
00:03:39,730 --> 00:03:40,945
Jeg glemte slik.

88
00:03:40,945 --> 00:03:43,310
Det var et groft morgen.

89
00:03:43,310 --> 00:03:46,340
Så du fyre er næsten der,
og jeg er virkelig stolt af jer.

90
00:03:46,340 --> 00:03:49,570
>> OK, så stakke.

91
00:03:49,570 --> 00:03:53,331
Hvem elskede spørgsmål om Jack
og hans tøj på quizzen?

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

93
00:03:53,830 --> 00:03:56,500
OK, det er fint.

94
00:03:56,500 --> 00:04:00,200
>> Så det væsentlige, som du kan
billede Jack, denne fyr her,

95
00:04:00,200 --> 00:04:03,350
elsker at tage tøj
ud af toppen af ​​stakken,

96
00:04:03,350 --> 00:04:05,750
og han udtrykker det tilbage på
stakken efter at han har gjort.

97
00:04:05,750 --> 00:04:07,600
Så på denne måde, han aldrig
synes at være at få

98
00:04:07,600 --> 00:04:10,090
til bunden af
stak i hans tøj.

99
00:04:10,090 --> 00:04:12,600
Så denne slags beskriver
den grundlæggende datastruktur

100
00:04:12,600 --> 00:04:16,610
på, hvordan en stabel implementeres.

101
00:04:16,610 --> 00:04:20,060
>> Væsentlige, tænk på en
stable så enhver stak af objekter

102
00:04:20,060 --> 00:04:24,900
hvor du lægger tingene på toppen, og
så du pop dem ud fra toppen.

103
00:04:24,900 --> 00:04:28,600
Så LIFO er akronymet vi gerne
at use-- Sidste In, First Out.

104
00:04:28,600 --> 00:04:32,480
Og så holde i den øverste del af
stakken er den første, der kommer ud.

105
00:04:32,480 --> 00:04:34,260
Og så de to begreber
vi gerne knytte

106
00:04:34,260 --> 00:04:36,190
med der kaldes skub og pop.

107
00:04:36,190 --> 00:04:39,790
Når du skubber noget på
stak, og du pop det op igen.

108
00:04:39,790 --> 00:04:43,422
>> Og så jeg tror det er sådan en
abstrakt begreb for dem af jer

109
00:04:43,422 --> 00:04:45,630
der ønsker at se som en
faktiske gennemførelse af dette

110
00:04:45,630 --> 00:04:46,740
i den virkelige verden.

111
00:04:46,740 --> 00:04:50,170
Hvor mange af jer har skrevet et essay
måske som en time før det var på grund af,

112
00:04:50,170 --> 00:04:54,510
og du ved et uheld slettet en enorm
bid af det, ligesom et uheld?

113
00:04:54,510 --> 00:04:58,560
Og hvad så kontrol gøre
vi bruger til at sætte det tilbage?

114
00:04:58,560 --> 00:05:00,030
Kontrol-Z, ikke?

115
00:05:00,030 --> 00:05:03,640
Ctrl-Z, så mængden af ​​gange
at ctrl-Z har reddet mit liv,

116
00:05:03,640 --> 00:05:08,820
har reddet min røv, hver gang
der er gennemført ved hjælp af en stak.

117
00:05:08,820 --> 00:05:13,020
>> Væsentlige alle de oplysninger
der er på dit Word-dokument,

118
00:05:13,020 --> 00:05:15,080
det bliver skubbet dukkede efter behag.

119
00:05:15,080 --> 00:05:19,460
Og så væsentligt, når du
slette noget, du pop den op igen.

120
00:05:19,460 --> 00:05:22,820
Og så hvis du har brug for den igen, du
skubbe det, hvilket er, hvad Control-C gør.

121
00:05:22,820 --> 00:05:26,770
Og så virkelige verden funktion
af, hvor nemt datastruktur

122
00:05:26,770 --> 00:05:28,690
kan hjælpe med din hverdag.

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

124
00:05:31,710 --> 00:05:40,150
>> Så en struct er den måde,
vi faktisk skabe en stak.

125
00:05:40,150 --> 00:05:44,720
Vi skriver definere struct, og derefter
vi kalder det stable nederst.

126
00:05:44,720 --> 00:05:47,440
Og inden for stakken,
vi har to parametre

127
00:05:47,440 --> 00:05:51,580
at vi kan hovedsagelig manipulere,
så vi har char stjerne strings kapacitet.

128
00:05:51,580 --> 00:05:55,150
>> Alt, hvad det gør
skaber et array

129
00:05:55,150 --> 00:05:58,835
at vi kan gemme, hvad du ønsker
som vi kan bestemme sin kapacitet.

130
00:05:58,835 --> 00:06:01,990
Kapacitet er bare max beløb af
emner, vi kan sætte ind i denne række.

131
00:06:01,990 --> 00:06:05,660
int størrelse er tælleren, der holder
styr på, hvor mange emner er i øjeblikket

132
00:06:05,660 --> 00:06:07,850
i stablen.

133
00:06:07,850 --> 00:06:11,860
Så kan vi holde styr på, A,
både hvor stor den faktiske stakken er,

134
00:06:11,860 --> 00:06:14,850
og B, hvor meget af denne stak
vi fyldt fordi vi ikke ønsker

135
00:06:14,850 --> 00:06:18,800
til overløb over, hvad vores kapacitet er.

136
00:06:18,800 --> 00:06:24,340
>> Så for eksempel denne dejlige
Spørgsmålet var på din quiz.

137
00:06:24,340 --> 00:06:28,160
Hovedsagelig hvordan gør vi skubbe
på toppen af ​​en stabel.

138
00:06:28,160 --> 00:06:28,830
Temmelig enkel.

139
00:06:28,830 --> 00:06:30,621
Hvis man ser på det,
vi vil gå gennem dette.

140
00:06:30,621 --> 00:06:32,640
Hvis [uhørligt] size--
Husk, når du

141
00:06:32,640 --> 00:06:35,300
ønsker at få adgang til alle
parameter inden for en struct,

142
00:06:35,300 --> 00:06:40,320
du gør navnet på struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> I dette tilfælde, s er
navnet på vores stack.

144
00:06:42,720 --> 00:06:46,230
Vi ønsker at få adgang til størrelse
af det, så gør vi s.size.

145
00:06:46,230 --> 00:06:50,280
Så længe størrelsen ikke er
lig med kapaciteten eller så længe

146
00:06:50,280 --> 00:06:52,940
da det er mindre end kapaciteten,
enten ville arbejde her.

147
00:06:52,940 --> 00:06:57,180
>> Du ønsker at få adgang til indersiden
af din stack, så s.strings,

148
00:06:57,180 --> 00:07:00,790
og du kommer til at sætte det nye nummer
at du ønsker at indsætte i der.

149
00:07:00,790 --> 00:07:05,030
Lad os bare sige, at vi gerne vil
Indsæt int n på stakken,

150
00:07:05,030 --> 00:07:08,905
vi kunne gøre s.strings,
beslag, s.size lig n.

151
00:07:08,905 --> 00:07:11,030
Fordi størrelse er, hvor vi
øjeblikket er i stakken

152
00:07:11,030 --> 00:07:14,590
hvis vi kommer til at skubbe
det på, vi bare få adgang

153
00:07:14,590 --> 00:07:17,370
hvor størrelsen er, jo
nuværende fylde af stakken,

154
00:07:17,370 --> 00:07:21,729
og vi skubbe int n på det.

155
00:07:21,729 --> 00:07:24,770
Og så vil vi sørge for, at
vi også forøge størrelsen af ​​n,

156
00:07:24,770 --> 00:07:27,436
så vi kan holde styr på vi har
tilføjet en ekstra ting at stakken.

157
00:07:27,436 --> 00:07:29,660
Nu har vi en større størrelse.

158
00:07:29,660 --> 00:07:33,196
Betyder det her mening at
alle, hvor logisk virker det?

159
00:07:33,196 --> 00:07:34,160
Det var slags hurtig.

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

161
00:07:39,535 --> 00:07:42,160
PUBLIKUM: Kan du gå over
de s.stringss.strings [s.size] igen?

162
00:07:42,160 --> 00:07:45,808
ANDI Peng: Sure, så hvad betyder
s.size øjeblikket give os?

163
00:07:45,808 --> 00:07:47,440
PUBLIKUM: Det er den nuværende størrelse.

164
00:07:47,440 --> 00:07:50,890
ANDI Peng: Præcis, så
aktuelle indeks, som vores størrelse er på,

165
00:07:50,890 --> 00:07:57,780
og så vi ønsker at sætte den nye heltal
at vi ønsker at indsætte i s.size.

166
00:07:57,780 --> 00:07:58,760
Giver det mening?

167
00:07:58,760 --> 00:08:01,110
Fordi s.strings, alt,
er er navnet på arrayet.

168
00:08:01,110 --> 00:08:03,510
Alt det er er adgang til
vifte inden for vores struct,

169
00:08:03,510 --> 00:08:06,030
og så hvis vi ønsker at
placere n ind i det indeks,

170
00:08:06,030 --> 00:08:09,651
Vi kan bare få adgang til det
ved hjælp af beslag s.size.

171
00:08:09,651 --> 00:08:10,150
Afkøle.

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

173
00:08:13,580 --> 00:08:18,916
>> Okay, pop, jeg pseudokode det ud
til jer, men lignende koncept.

174
00:08:18,916 --> 00:08:19,790
Giver det mening?

175
00:08:19,790 --> 00:08:22,310
Hvis størrelsen er større
end nul, så er du

176
00:08:22,310 --> 00:08:25,350
ved, at du ønsker at tage noget
ud, fordi hvis størrelse ikke er

177
00:08:25,350 --> 00:08:27,620
større end nul, så er du
har intet i stakken.

178
00:08:27,620 --> 00:08:29,840
>> Så du kun ønsker at udføre
denne kode, kan det kun

179
00:08:29,840 --> 00:08:32,320
pop hvis der er noget til pop.

180
00:08:32,320 --> 00:08:35,830
Så hvis størrelsen er større
end 0, vi minus størrelse.

181
00:08:35,830 --> 00:08:40,020
Vi formindske størrelsen og derefter vende tilbage
hvad der er inde i det, fordi

182
00:08:40,020 --> 00:08:42,710
ved popping, ønsker vi at
adgang uanset er gemt

183
00:08:42,710 --> 00:08:45,694
i indekset af toppen af ​​stakken.

184
00:08:45,694 --> 00:08:46,610
Alt mening?

185
00:08:46,610 --> 00:08:49,693
Hvis jeg gjorde jer skrive det ud,
ville du fyre kunne skrive det ud?

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

187
00:08:52,029 --> 00:08:53,570
OK, kan du fyre lege med det.

188
00:08:53,570 --> 00:08:55,252
Ingen bekymringer, hvis du ikke får det.

189
00:08:55,252 --> 00:08:57,460
Vi har ikke tid til at kode
det ud i dag, fordi vi har

190
00:08:57,460 --> 00:08:59,959
fik en masse af disse strukturer
til at gå igennem, men hovedsagelig

191
00:08:59,959 --> 00:09:02,214
pseudokode, meget, meget lig skubbe.

192
00:09:02,214 --> 00:09:03,380
Bare følg langs logik.

193
00:09:03,380 --> 00:09:06,092
Sørg for, at du får adgang alle de
funktionerne i din struct korrekt.

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

195
00:09:06,574 --> 00:09:09,282
>> PUBLIKUM: Vil disse lysbilleder og
hele denne ting være op i dag-ish?

196
00:09:09,282 --> 00:09:11,586
ANDI Peng: Altid, jep.

197
00:09:11,586 --> 00:09:13,710
Jeg har tænkt mig at prøve at sætte
dette op som en time efter.

198
00:09:13,710 --> 00:09:16,626
Jeg e-mailer David, vil David forsøge at
sætte det op som en time efter dette.

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

200
00:09:20,040 --> 00:09:25,470
>> OK, så da vi bevæger os ind i denne anden
dejlige datastruktur kaldes en kø.

201
00:09:25,470 --> 00:09:30,140
Som du fyre kan se her, en
kø, for briterne blandt os,

202
00:09:30,140 --> 00:09:32,010
alt det er er en linje.

203
00:09:32,010 --> 00:09:34,680
Så i modsætning til hvad
du mener en stak er,

204
00:09:34,680 --> 00:09:37,750
en kø er præcis, hvad
logisk du tror det er.

205
00:09:37,750 --> 00:09:41,914
Det er holdt af reglerne i FIFO,
som er First In, First Out.

206
00:09:41,914 --> 00:09:43,705
Hvis du er den første
én i rækken, er du

207
00:09:43,705 --> 00:09:46,230
den første, som
kommer ud af linjen.

208
00:09:46,230 --> 00:09:49,680
>> Så det, vi kan lide at kalde dette
er dequeueing og enqueueing.

209
00:09:49,680 --> 00:09:52,380
Hvis vi ønsker at tilføje noget
til vores kø, vi enqueue.

210
00:09:52,380 --> 00:09:55,690
Hvis vi ønsker at dequeue, eller tage
noget væk, vi dequeue.

211
00:09:55,690 --> 00:10:03,350
>> Så samme forstand, at vi er sådan
skabe fast størrelse elementer, som vi

212
00:10:03,350 --> 00:10:06,500
kan lagre visse
ting, men vi kan også

213
00:10:06,500 --> 00:10:10,100
ændre, hvor vi placerer
parametre inde i dem

214
00:10:10,100 --> 00:10:13,140
baseret på, hvad type
funktionalitet, vi ønsker.

215
00:10:13,140 --> 00:10:16,700
Så stakke, vi ønskede det sidste
én, N for at være den første ud.

216
00:10:16,700 --> 00:10:19,800
Kø er vi ønsker den første ting
i at være den første ting ud.

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

218
00:10:22,510 --> 00:10:26,710
>> Så struct-typen
definere, som du kan se,

219
00:10:26,710 --> 00:10:29,470
det er en lille smule anderledes
fra det stakken var

220
00:10:29,470 --> 00:10:33,120
fordi ikke alene har vi nødt til at holde
styr på, hvor størrelsen øjeblikket,

221
00:10:33,120 --> 00:10:37,420
Vi ønsker også at holde styr på hovedet
samt hvor vi i øjeblikket er.

222
00:10:37,420 --> 00:10:39,580
Så jeg tror, ​​det er nemmere
hvis jeg trækker det op.

223
00:10:39,580 --> 00:10:53,270
Så lad os forestille os, vi har fået en kø,
så lad os sige hovedet er lige her.

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

225
00:10:55,811 --> 00:10:58,310
Lederen af ​​den linje, lad os
bare sige, at der aktuelt er der,

226
00:10:58,310 --> 00:11:01,809
og vi ønsker at indsætte
noget ind i køen.

227
00:11:01,809 --> 00:11:04,350
Jeg har tænkt mig at ringe størrelse væsentlige
er det samme som hale,

228
00:11:04,350 --> 00:11:06,314
I slutningen af ​​hvor end din kø er.

229
00:11:06,314 --> 00:11:07,730
Lad os bare sige størrelse er lige her.

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

231
00:11:14,380 --> 00:11:18,400
>> Så hvordan gør man indpasses
indsætte noget i en kø?

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

233
00:11:21,000 --> 00:11:24,130
Hvad indeks ønsker vi at placere
hvor vi ønsker at indsætte i.

234
00:11:24,130 --> 00:11:29,320
Hvis dette er begyndelsen af ​​din
kø og dette er enden på det

235
00:11:29,320 --> 00:11:31,860
eller størrelsen af ​​det, hvor skal vi
ønsker at tilføje det næste objekt?

236
00:11:31,860 --> 00:11:32,920
>> PUBLIKUM: [uhørligt]

237
00:11:32,920 --> 00:11:35,920
ANDI Peng: Præcis, du ønsker at tilføje
det afhængigt af du har skrevet den.

238
00:11:35,920 --> 00:11:37,840
Enten det er tomt, eller som er tomt.

239
00:11:37,840 --> 00:11:42,630
Så du ønsker at tilføje det sandsynligvis
her, fordi hvis størrelsen is--

240
00:11:42,630 --> 00:11:50,540
hvis disse er alle fulde, du ønsker
at tilføje det her, ikke?

241
00:11:50,540 --> 00:11:57,150
>> Og så det er, mens meget, meget
enkle, ikke helt altid er korrekte

242
00:11:57,150 --> 00:12:00,690
fordi den vigtigste forskel
mellem en kø og en stak

243
00:12:00,690 --> 00:12:04,350
er, at køen kan
faktisk manipuleres

244
00:12:04,350 --> 00:12:06,980
således at hovedet ændringer
afhængigt af hvor du ønsker

245
00:12:06,980 --> 00:12:08,650
begyndelsen af ​​din cue til at starte.

246
00:12:08,650 --> 00:12:11,900
Og som et resultat, din hale
også kommer til at ændre sig.

247
00:12:11,900 --> 00:12:14,770
Og så tage et kig på
denne kode lige nu.

248
00:12:14,770 --> 00:12:18,620
Som jer også blev bedt om at
skrive ud på quizzen, enqueue.

249
00:12:18,620 --> 00:12:22,580
Måske vil vi tale igennem, hvorfor
svaret var, hvad det var.

250
00:12:22,580 --> 00:12:26,790
>> Jeg kunne ikke helt passe denne linje på et,
men hovedsagelig dette stykke kode

251
00:12:26,790 --> 00:12:29,030
bør være på én linie.

252
00:12:29,030 --> 00:12:30,140
Tilbring ligesom 30 sekunder.

253
00:12:30,140 --> 00:12:33,000
Tag et kig, og se, hvorfor
det er den måde, at det er.

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

255
00:12:50,030 --> 00:12:55,420
>> Meget, meget lignende struct, meget, meget
lignende struktur som den tidligere

256
00:12:55,420 --> 00:12:58,090
stable undtagen måske
én linje kode.

257
00:12:58,090 --> 00:13:01,190
Og at en linje kode
bestemmer funktionaliteten.

258
00:13:01,190 --> 00:13:03,900
Og det er virkelig adskiller
en kø fra en stabel.

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

260
00:13:18,510 --> 00:13:22,010
>> Nogen ønsker at tage et stik
til at forklare, hvorfor du har

261
00:13:22,010 --> 00:13:24,980
fik denne komplicerede ting i her?

262
00:13:24,980 --> 00:13:27,845
Vi ser tilbagelevering af vores
vidunderlige ven modul.

263
00:13:27,845 --> 00:13:31,020
Som du fyre snart vil komme
at erkende i programmering,

264
00:13:31,020 --> 00:13:34,910
næsten når som helst du har brug for noget
til wrap omkring noget,

265
00:13:34,910 --> 00:13:36,850
modul vil være måden at gøre det.

266
00:13:36,850 --> 00:13:40,510
Så vel vidende, at, er der nogen ønsker
at forsøge at forklare denne linje kode?

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

268
00:13:44,060 --> 00:13:47,507
Ja, alle svar er
accepteret og velkommen.

269
00:13:47,507 --> 00:13:48,840
PUBLIKUM: Taler du til mig?

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

271
00:13:49,506 --> 00:13:56,200
PUBLIKUM: Åh, nej undskyld.

272
00:13:56,200 --> 00:14:00,250
ANDI Peng: OK, så lad os
gå gennem denne kode.

273
00:14:00,250 --> 00:14:03,642
Så når du forsøger at
tilføje noget på en kø,

274
00:14:03,642 --> 00:14:08,510
i den dejlige tilfælde, at hovedet sker
at være lige her, det er meget let for os

275
00:14:08,510 --> 00:14:10,960
bare gå til slutningen
indsætte noget, ikke?

276
00:14:10,960 --> 00:14:14,690
Men hele pointen med en kø er
at hovedet kan faktisk dynamisk

277
00:14:14,690 --> 00:14:17,280
ændre sig afhængigt af, hvor vi
ønsker starten af ​​vores q at være,

278
00:14:17,280 --> 00:14:19,880
og som sådan, halen
også kommer til at ændre sig.

279
00:14:19,880 --> 00:14:31,100
>> Og så forestille sig, at dette ikke var den
kø, men snarere var køen.

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

281
00:14:37,900 --> 00:14:39,330
Lad os sige, hovedet er lige her.

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

283
00:14:54,900 --> 00:14:56,980
Lad os sige vores kø lignede dette.

284
00:14:56,980 --> 00:15:00,190
Hvis vi ønskede at flytte, hvor
begyndelsen af ​​linjen er,

285
00:15:00,190 --> 00:15:03,400
Lad os sige, at vi skiftede hoved
denne måde og størrelser her.

286
00:15:03,400 --> 00:15:07,100
>> Nu ønsker vi at tilføje noget til
denne kø, men da du fyre kan se,

287
00:15:07,100 --> 00:15:11,150
det er ikke så simpelt som at bare
tilføje, hvad der er efter størrelse

288
00:15:11,150 --> 00:15:13,630
fordi så vi løber tør for
grænserne for vores faktiske matrix.

289
00:15:13,630 --> 00:15:16,190
Hvor vi vil virkelig tilføje, er her.

290
00:15:16,190 --> 00:15:18,610
Det er skønheden i en kø
er, at for os, visuelt det

291
00:15:18,610 --> 00:15:22,380
ligner den linje går sådan her,
men når de opbevares i en datastruktur,

292
00:15:22,380 --> 00:15:29,370
de giver det som som en cyklus.

293
00:15:29,370 --> 00:15:32,360
Den slags ombrydes omkring
til fronten på samme måde

294
00:15:32,360 --> 00:15:34,780
at en linje også kan pakke
rundt, afhængigt af hvor du

295
00:15:34,780 --> 00:15:36,279
vil begyndelsen af ​​linjen for at være.

296
00:15:36,279 --> 00:15:38,630
Og så hvis vi tager en
se ned her, lad os

297
00:15:38,630 --> 00:15:40,880
siger vi ønskede at skabe et
funktion kaldet Sæt i kø.

298
00:15:40,880 --> 00:15:43,980
Vi ønskede at tilføje int n ind at q.

299
00:15:43,980 --> 00:15:49,250
Hvis q.size q-- vi vil kalde, at vores data
structure-- hvis vores queue.size ikke

300
00:15:49,250 --> 00:15:52,520
lig med kapaciteten eller hvis
det er mindre end kapaciteten,

301
00:15:52,520 --> 00:15:55,120
q.strings er grupperingen i vores q.

302
00:15:55,120 --> 00:15:58,380
Vi kommer til at sætte
at svare til q.heads,

303
00:15:58,380 --> 00:16:02,730
som er lige her, plus q.size
modul af kapaciteten, hvilket

304
00:16:02,730 --> 00:16:04,290
wrap os tilbage her omkring.

305
00:16:04,290 --> 00:16:08,040
>> Så i dette eksempel indeks
af hoved er 1, ikke?

306
00:16:08,040 --> 00:16:11,480
Indekset for størrelse er 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Så vi kan gøre 1 plus 4 modul
af vores kapacitet, der er 5.

308
00:16:19,500 --> 00:16:20,920
Hvad betyder, at give os?

309
00:16:20,920 --> 00:16:23,270
Hvad er det indeks, der
kommer ud af dette?

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

311
00:16:24,080 --> 00:16:27,870
>> ANDI Peng: 0, hvilket
sker for at være lige her,

312
00:16:27,870 --> 00:16:30,640
og så vi vil være i stand
at indsætte i lige her.

313
00:16:30,640 --> 00:16:34,730
Og så denne ligning her slags
for bare fungerer med nogen tal

314
00:16:34,730 --> 00:16:36,750
afhængigt af, hvor din
hoved og din størrelse er.

315
00:16:36,750 --> 00:16:38,541
Hvis du ved, hvad de
ting er, du ved

316
00:16:38,541 --> 00:16:43,170
præcis, hvor du vil indsætte
hvad er efter din kø.

317
00:16:43,170 --> 00:16:44,640
Giver det mening for alle?

318
00:16:44,640 --> 00:16:48,560
>> Jeg kender sådan en hjerne
teaser især da dette

319
00:16:48,560 --> 00:16:50,512
kom i kølvandet på din quiz.

320
00:16:50,512 --> 00:16:52,220
Men forhåbentlig alle
nu kan forstå

321
00:16:52,220 --> 00:16:57,800
hvorfor denne opløsning eller dette
funktion er den måde, det er.

322
00:16:57,800 --> 00:16:59,840
Nogen lidt uklart om det?

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

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

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

326
00:17:07,109 --> 00:17:09,970
>> Og så nu, hvis du
ønskede at dequeue, dette

327
00:17:09,970 --> 00:17:15,240
er, hvor vores hoved ville være at flytte
fordi hvis vi skulle dequeue,

328
00:17:15,240 --> 00:17:17,030
vi ikke tage ud i slutningen af ​​q.

329
00:17:17,030 --> 00:17:19,130
Vi ønsker at tage ud i hovedet, ikke?

330
00:17:19,130 --> 00:17:24,260
Så som et resultat, er hovedet kommer til at ændre,
og det er derfor, når du enqueue,

331
00:17:24,260 --> 00:17:26,800
you got at holde styr på
hvor dit hoved og din størrelse

332
00:17:26,800 --> 00:17:29,450
skal være i stand til at indsætte
i den korrekte position.

333
00:17:29,450 --> 00:17:32,740
>> Og så når du dequeue,
Jeg har også pseudokode det ud.

334
00:17:32,740 --> 00:17:35,480
Du er velkommen til, hvis du vil
at forsøge kodning det ud.

335
00:17:35,480 --> 00:17:36,980
Du ønsker at flytte hovedet, ikke?

336
00:17:36,980 --> 00:17:39,320
Hvis jeg ønskede at dequeue, jeg
ville flytte hovedet over.

337
00:17:39,320 --> 00:17:40,800
Dette ville være hovedet.

338
00:17:40,800 --> 00:17:45,617
>> Og vores nuværende størrelse ville
trække, fordi vi ikke længere

339
00:17:45,617 --> 00:17:46,950
har fire elementer i arrayet.

340
00:17:46,950 --> 00:17:51,370
Vi har kun tre, og så vil vi
at returnere uanset var gemt inde

341
00:17:51,370 --> 00:17:56,260
af hovedet, fordi vi ønsker at tage dette
værdi ud, så meget lig stakken.

342
00:17:56,260 --> 00:17:58,010
Bare du tager
fra et andet sted,

343
00:17:58,010 --> 00:18:01,770
og du er nødt til at overflytte Deres pointer
til andet sted som følge heraf.

344
00:18:01,770 --> 00:18:03,890
Logisk set alle følge?

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

346
00:18:05,690 --> 00:18:10,156
>> OK, så vi kommer til at tale lidt
mere i dybden om hægtede lister

347
00:18:10,156 --> 00:18:13,280
fordi de vil være meget, meget værdifuldt
for dig i løbet af denne uges

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

349
00:18:14,964 --> 00:18:17,130
Hægtede lister, som du fyre
kan huske, alle de er

350
00:18:17,130 --> 00:18:22,570
er knuder, som knudepunkter i visse
værdier af både en værdi og en pointer

351
00:18:22,570 --> 00:18:26,290
der er bundet sammen
disse pointere.

352
00:18:26,290 --> 00:18:29,880
Og så struct om, hvordan
skaber vi en node her er vi

353
00:18:29,880 --> 00:18:33,569
har int n, som er hvad
værdien i en butik eller snor n

354
00:18:33,569 --> 00:18:35,610
eller hvad du ønsker at
kalder det, char stjerne n.

355
00:18:35,610 --> 00:18:41,482
Struct node stjerne, som er markøren
at du ønsker at have i hvert knudepunkt,

356
00:18:41,482 --> 00:18:43,690
du kommer til at have det
pointer peger næste.

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

358
00:18:48,207 --> 00:18:50,040
Du får hovedet
en sammenkædet liste, der er

359
00:18:50,040 --> 00:18:53,140
kommer til at pege på resten af
værdierne så videre og så videre

360
00:18:53,140 --> 00:18:55,290
indtil du til sidst når til slutningen.

361
00:18:55,290 --> 00:18:58,040
Og denne sidste node er bare
vil ikke have en pointer.

362
00:18:58,040 --> 00:18:59,952
Det kommer til at pege på
null, og det er når

363
00:18:59,952 --> 00:19:01,910
du ved, du har ramt
slutningen af ​​din linkede liste

364
00:19:01,910 --> 00:19:04,076
er, når din sidste pointer
ikke pege på noget.

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

366
00:19:06,670 --> 00:19:10,990
>> Så vi kommer til at gå lidt mere i
dybde med hensyn til, hvordan man ville muligvis

367
00:19:10,990 --> 00:19:12,400
søger en sammenkædet liste.

368
00:19:12,400 --> 00:19:15,460
Husk, hvad er nogle af de
ulemper ved de hægtede lister

369
00:19:15,460 --> 00:19:19,340
vers et array med hensyn søgninger.

370
00:19:19,340 --> 00:19:22,565
Et array kan du binær søgning, men
Hvorfor kan du ikke gøre det i en linket liste?

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

372
00:19:26,834 --> 00:19:30,320
>> PUBLIKUM: Fordi de alle er tilsluttet,
men du ved ikke helt, hvor

373
00:19:30,320 --> 00:19:31,330
[Uhørligt].

374
00:19:31,330 --> 00:19:34,600
>> ANDI Peng: Ja, præcis så husk
at glans af et array

375
00:19:34,600 --> 00:19:37,190
var, at vi havde
random access memory, hvor

376
00:19:37,190 --> 00:19:41,580
hvis jeg ønskede at værdien fra indeks
seks, kunne jeg bare sige indeks seks,

377
00:19:41,580 --> 00:19:42,407
give mig denne værdi.

378
00:19:42,407 --> 00:19:45,240
Og det er fordi arrays sorteres
i en sammenhængende plads hukommelse

379
00:19:45,240 --> 00:19:48,020
på ét sted, mens
slags hægtede lister

380
00:19:48,020 --> 00:19:52,820
er tilfældigt afbrudt hele vejen rundt,
og den eneste måde du kan finde en

381
00:19:52,820 --> 00:19:56,890
er gennem en pointer, der fortæller dig
adressen på, hvor denne næste knudepunkt er.

382
00:19:56,890 --> 00:20:00,290
>> Og så et resultat, den eneste måde
at søge gennem en sammenkædet liste

383
00:20:00,290 --> 00:20:01,560
er lineær søgning.

384
00:20:01,560 --> 00:20:05,890
Fordi jeg ikke præcist ved, hvor
12. værdi i linkede liste er,

385
00:20:05,890 --> 00:20:08,780
Jeg er nødt til at krydse helhed
af den linkede liste én

386
00:20:08,780 --> 00:20:12,450
efter én fra hovedet til det første knudepunkt,
til det andet knudepunkt, til den tredje knudepunkt,

387
00:20:12,450 --> 00:20:17,690
hele vejen ned, indtil jeg endelig får
til hvor at node jeg leder efter er.

388
00:20:17,690 --> 00:20:22,110
Og så i denne forstand, søg
på en sammenkædet liste er altid n.

389
00:20:22,110 --> 00:20:23,040
Det er altid n.

390
00:20:23,040 --> 00:20:25,690
Det er altid i lineær tid.

391
00:20:25,690 --> 00:20:28,470
>> Og så den kode, hvori
vi gennemfører dette, og dette

392
00:20:28,470 --> 00:20:32,620
er en smule nyt for jer, siden du
fyre har ikke rigtig talt om eller nogensinde

393
00:20:32,620 --> 00:20:35,000
set pejlemærker i, hvordan man
søge gennem pointere,

394
00:20:35,000 --> 00:20:37,670
så vi vil gå gennem
denne meget, meget langsomt.

395
00:20:37,670 --> 00:20:40,200
Så bool søgning, højre,
lad os forestille os, vi ønsker

396
00:20:40,200 --> 00:20:42,820
at skabe en funktion kaldet
søgning, der returnerer true

397
00:20:42,820 --> 00:20:46,820
hvis du har fundet en værdi inde i linket
listen, og den returnerer falsk ellers.

398
00:20:46,820 --> 00:20:50,030
Node stjerne listen er
i øjeblikket bare markøren

399
00:20:50,030 --> 00:20:52,960
til det første emne i din linkede liste.

400
00:20:52,960 --> 00:20:56,700
int n er den værdi, du er
søger efter på listen.

401
00:20:56,700 --> 00:20:58,770
>> Så node stjerne pointer lig listen.

402
00:20:58,770 --> 00:21:00,970
Det betyder, at vi sætte
og skabe en pointer

403
00:21:00,970 --> 00:21:03,592
denne første knudepunkt inde i listen.

404
00:21:03,592 --> 00:21:04,300
Alle med mig?

405
00:21:04,300 --> 00:21:06,530
Så hvis vi skulle gå
tilbage her, ville jeg have

406
00:21:06,530 --> 00:21:13,850
initialiseret en pegepind, der peger på
lederen af ​​hvad det så listen er.

407
00:21:13,850 --> 00:21:18,600
>> Og så når du får hernede,
mens markøren ikke er lig nul,

408
00:21:18,600 --> 00:21:22,160
så det er løkken, hvor vi er
kommer til at være efterfølgende gennemkører

409
00:21:22,160 --> 00:21:25,940
resten af ​​vores liste, fordi hvad
sker, når markøren er lig nul?

410
00:21:25,940 --> 00:21:27,550
Vi ved, at vi have--

411
00:21:27,550 --> 00:21:28,450
>> PUBLIKUM: [uhørligt]

412
00:21:28,450 --> 00:21:31,491
>> ANDI Peng: Præcis, så vi ved, at
vi har nået enden af ​​listen, ikke?

413
00:21:31,491 --> 00:21:34,470
Hvis du går tilbage her, hver node
skal pege til en anden node

414
00:21:34,470 --> 00:21:36,550
og så videre og så videre
indtil du rammer til sidst

415
00:21:36,550 --> 00:21:41,589
halen af ​​din linkede liste,
som har en pointer, der bare

416
00:21:41,589 --> 00:21:43,130
peger ikke andre steder end ingen.

417
00:21:43,130 --> 00:21:47,510
Og så du dybest set ved, at
din liste er der stadig op

418
00:21:47,510 --> 00:21:50,900
indtil markøren er ikke lig
null fordi når det er lig nul,

419
00:21:50,900 --> 00:21:53,310
du ved, at der er ikke flere ting.

420
00:21:53,310 --> 00:21:56,930
>> Så det er den løkke, hvor vi er
vil have den faktiske søgning.

421
00:21:56,930 --> 00:22:01,690
Og hvis pointer-- ser du
den slags pil funktion der?

422
00:22:01,690 --> 00:22:06,930
Så hvis peger mod n, hvis
markøren ved n lig lig n,

423
00:22:06,930 --> 00:22:09,180
så betyder, at hvis
markøren, at du er

424
00:22:09,180 --> 00:22:13,420
efter på udgangen af ​​hvert
node er faktisk lig med værdien

425
00:22:13,420 --> 00:22:15,990
du leder efter, så
du ønsker at returnere sandt.

426
00:22:15,990 --> 00:22:19,280
Så dybest set, hvis du er på en node,
har den værdi, du leder efter,

427
00:22:19,280 --> 00:22:23,550
du ved, at du har været
i stand til at søge.

428
00:22:23,550 --> 00:22:27,150
>> Ellers du vil indstille
markøren til den næste node.

429
00:22:27,150 --> 00:22:28,850
Det er, hvad denne linje her gør.

430
00:22:28,850 --> 00:22:31,750
Pointer lig pointer næste.

431
00:22:31,750 --> 00:22:33,360
Alle se, hvordan det fungerer?

432
00:22:33,360 --> 00:22:36,580
>> Og hovedsagelig du vil bare
krydse helhed af listen,

433
00:22:36,580 --> 00:22:41,920
nulstille din pointer hver gang, indtil
du i sidste ende ramte i slutningen af ​​listen.

434
00:22:41,920 --> 00:22:45,030
Og du ved, at der ikke er nogen
flere noder for at søge igennem,

435
00:22:45,030 --> 00:22:47,999
og derefter kan du returnere false
fordi du ved, at, åh, ja,

436
00:22:47,999 --> 00:22:50,540
hvis jeg har været i stand til at søge
gennem helheden af ​​listen.

437
00:22:50,540 --> 00:22:54,530
Hvis i dette eksempel, hvis jeg ønskede
at kigge efter den værdi af 10,

438
00:22:54,530 --> 00:22:57,250
og jeg starter i spidsen, og
Jeg søger hele vejen ned,

439
00:22:57,250 --> 00:23:00,550
og jeg fik til sidst til dette, hvilket
en pointer, der peger til null,

440
00:23:00,550 --> 00:23:04,415
Jeg ved, at, lort, jeg gætte 10 ikke er i
denne liste, fordi jeg ikke kunne finde den.

441
00:23:04,415 --> 00:23:06,520
Og jeg er i slutningen af ​​listen.

442
00:23:06,520 --> 00:23:11,040
Og i hvilket tilfælde du vide
Jeg har tænkt mig at vende tilbage falsk.

443
00:23:11,040 --> 00:23:12,900
>> Lad der lægges i blød i for en lille smule.

444
00:23:12,900 --> 00:23:17,350
Dette vil være temmelig
vigtigt for din pset.

445
00:23:17,350 --> 00:23:21,140
Logikken i det er meget simpelt, måske
syntaktisk bare gennemføre det.

446
00:23:21,140 --> 00:23:23,365
Du fyre ønsker at gøre
sikker på, at du forstår.

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

448
00:23:25,870 --> 00:23:27,650
Afkøle.

449
00:23:27,650 --> 00:23:32,560
>> OK, så hvordan vi ville være
indsætte noder, højre,

450
00:23:32,560 --> 00:23:35,380
i en liste, fordi huske
hvad er hvad af de fordele

451
00:23:35,380 --> 00:23:39,230
for at have en sammenkædet liste versus
et array i form af lagerplads?

452
00:23:39,230 --> 00:23:41,110
>> PUBLIKUM: Det er dynamisk,
så det er nemmere at--

453
00:23:41,110 --> 00:23:43,180
>> ANDI Peng: Præcis,
så det er dynamisk, hvilket

454
00:23:43,180 --> 00:23:46,880
betyder, at det kan udvide og krympe
afhængigt af brugerens behov.

455
00:23:46,880 --> 00:23:56,570
Og så, i denne forstand, at vi ikke har brug for
at spilde unødvendig hukommelse, fordi jeg

456
00:23:56,570 --> 00:24:00,850
hvis jeg ikke ved, hvor mange værdier, jeg ønsker
til butik, giver det ikke mening for mig

457
00:24:00,850 --> 00:24:04,310
at skabe et array, fordi
hvis jeg ønsker at gemme 10 værdier

458
00:24:04,310 --> 00:24:08,380
og jeg skabe en række på 1.000, det er
en masse spildt hukommelse, tildeles.

459
00:24:08,380 --> 00:24:11,180
Det er derfor, vi ønsker at bruge en sammenkædet
listen at kunne dynamisk

460
00:24:11,180 --> 00:24:13,860
ændre eller skrumpe vores størrelse.

461
00:24:13,860 --> 00:24:17,040
>> Og så gør indsættelse
en smule mere kompliceret.

462
00:24:17,040 --> 00:24:20,810
Da vi ikke tilfældigt kan få adgang til elementer
den måde, at vi ville af et array.

463
00:24:20,810 --> 00:24:24,270
Hvis jeg ønsker at indsætte et element
i den syvende indeks,

464
00:24:24,270 --> 00:24:26,930
Jeg kan bare indsætte det
i den syvende indeks.

465
00:24:26,930 --> 00:24:30,020
På en sammenkædet liste, ikke det gør
ganske arbejde så let,

466
00:24:30,020 --> 00:24:34,947
og så hvis vi ønskede at indsætte
den ene her i den linkede liste,

467
00:24:34,947 --> 00:24:36,280
visuelt, det er meget nemt at se.

468
00:24:36,280 --> 00:24:39,363
Vi ønsker blot at indsætte det lige der,
lige i starten af ​​listen,

469
00:24:39,363 --> 00:24:40,840
lige efter hovedet.

470
00:24:40,840 --> 00:24:44,579
>> Men den måde, som vi er nødt til at overflytte
de pejlemærker er lidt komplicerede

471
00:24:44,579 --> 00:24:47,620
eller logisk, det giver mening, men
du vil være sikker på, at du har det

472
00:24:47,620 --> 00:24:50,250
helt ned, fordi
det sidste, du ønsker

473
00:24:50,250 --> 00:24:52,990
er at overflytte en pegepind den
måde, at vi laver her.

474
00:24:52,990 --> 00:24:58,170
Hvis du dereference den
pointer fra hoved til 1,

475
00:24:58,170 --> 00:25:01,086
så lige pludselig det
resten af ​​dit linkede liste

476
00:25:01,086 --> 00:25:04,680
er tabt, fordi du har faktisk ikke
oprettet et midlertidigt noget.

477
00:25:04,680 --> 00:25:06,220
Der er peget på 2.

478
00:25:06,220 --> 00:25:10,080
Hvis De overflytter markøren, så den
Resten af ​​din liste er helt tabt.

479
00:25:10,080 --> 00:25:13,310
Så du ønsker at være
meget, meget forsigtige her

480
00:25:13,310 --> 00:25:17,010
først tildele
pointer fra hvad du

481
00:25:17,010 --> 00:25:20,150
vil indsætte i overalt, hvor
du ønsker, og så skal du

482
00:25:20,150 --> 00:25:22,710
kan dereference resten af ​​din liste.

483
00:25:22,710 --> 00:25:25,250
>> Så det gælder uanset hvor
du forsøger at indsætte i.

484
00:25:25,250 --> 00:25:27,520
Hvis du vil indsætte på
hoved, hvis du ønsker at besvare her,

485
00:25:27,520 --> 00:25:29,455
Hvis du vil indsætte på
enden, ja, enden jeg

486
00:25:29,455 --> 00:25:30,910
gætte du ville bare
have nogen pointer, men du

487
00:25:30,910 --> 00:25:33,830
vil være sikker på, at du ikke gør
mister resten af ​​din liste.

488
00:25:33,830 --> 00:25:36,640
Du ønsker altid at sørge for
din nye node peger

489
00:25:36,640 --> 00:25:39,330
mod hvad du
vil indsætte i,

490
00:25:39,330 --> 00:25:42,170
og så kan du tilføje den kæde på.

491
00:25:42,170 --> 00:25:43,330
Alle klar?

492
00:25:43,330 --> 00:25:45,427
>> Dette vil være
en af ​​de virkelige problemer.

493
00:25:45,427 --> 00:25:48,010
En af de mest vigtige spørgsmål
du kommer til at have på din pset

494
00:25:48,010 --> 00:25:51,340
er, at du vil forsøge at skabe
en linket liste og indsætte ting

495
00:25:51,340 --> 00:25:53,340
men så bare tabe
resten af ​​dit linkede liste.

496
00:25:53,340 --> 00:25:54,900
Og du kommer til at være ligesom, jeg
ved ikke, hvorfor dette sker?

497
00:25:54,900 --> 00:25:58,040
Og det er en smerte at gå gennem
og søg alle dine pointere.

498
00:25:58,040 --> 00:26:02,100
>> Og jeg garanterer dig på denne pset,
skrive og tegne disse knudepunkter ud

499
00:26:02,100 --> 00:26:03,344
vil være meget, meget hjælpsomme.

500
00:26:03,344 --> 00:26:06,010
Så du kan helt holde styr
af hvor alle dine pointere er,

501
00:26:06,010 --> 00:26:08,540
hvad der går galt,
hvor alle dine noder er,

502
00:26:08,540 --> 00:26:12,660
hvad du skal gøre for at få adgang til eller
indsætte eller slette eller nogen af ​​dem.

503
00:26:12,660 --> 00:26:14,550
Alle godt med det?

504
00:26:14,550 --> 00:26:15,050
Afkøle.

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

506
00:26:19,300 --> 00:26:22,600
>> Så hvis vi ønskede at se på koden?

507
00:26:22,600 --> 00:26:24,470
Åh, jeg ved ikke, om vi
kan se til-- OK, så

508
00:26:24,470 --> 00:26:27,940
øverst alt er det er en funktion
opkaldt indsats, hvor vi ønsker

509
00:26:27,940 --> 00:26:31,365
at indsætte int n i linkede liste.

510
00:26:31,365 --> 00:26:32,740
Vi kommer til at gå gennem dette.

511
00:26:32,740 --> 00:26:34,770
Det er en masse kode, en masse nye syntaks.

512
00:26:34,770 --> 00:26:36,220
Vi vil være OK.

513
00:26:36,220 --> 00:26:39,120
>> Så op på toppen, når
vi ønsker at skabe noget

514
00:26:39,120 --> 00:26:42,380
hvad skal vi gøre, især hvis du
ønsker, at det ikke gemmes på stakken

515
00:26:42,380 --> 00:26:43,920
men i den bunke?

516
00:26:43,920 --> 00:26:45,460
Vi går til en malloc, ikke?

517
00:26:45,460 --> 00:26:48,240
Så vi kommer til at skabe en pegepind.

518
00:26:48,240 --> 00:26:52,074
Node, pointer, nye ligemænd
malloc størrelsen af ​​et knudepunkt

519
00:26:52,074 --> 00:26:53,740
fordi vi ønsker, at node, der skal oprettes.

520
00:26:53,740 --> 00:26:56,720
Vi ønsker, at mængden af
hukommelse, en knude optager

521
00:26:56,720 --> 00:26:59,300
skal tildeles til
oprettelsen af ​​den nye node.

522
00:26:59,300 --> 00:27:02,270
>> Og så vil vi kontrollere,
se, om nye ligemænd lig nul.

523
00:27:02,270 --> 00:27:03,370
Husk, hvad vi sagde?

524
00:27:03,370 --> 00:27:06,470
Uanset hvad du malloc,
hvad skal du altid gøre?

525
00:27:06,470 --> 00:27:09,490
Du skal altid kontrollere at se
uanset om det er nul.

526
00:27:09,490 --> 00:27:13,620
>> For eksempel, hvis dit operativsystem
Systemet var helt fuld,

527
00:27:13,620 --> 00:27:17,060
hvis du havde ikke mere hukommelse på
alle og du forsøger at malloc,

528
00:27:17,060 --> 00:27:18,410
det ville returnere null for dig.

529
00:27:18,410 --> 00:27:21,094
Og så hvis du forsøger at bruge det
da det blev peger til null,

530
00:27:21,094 --> 00:27:23,260
du kommer ikke til at kunne
at få adgang til disse oplysninger.

531
00:27:23,260 --> 00:27:27,010
Og så som sådan, vi ønskede at gøre
sikker på, at når du mallocing,

532
00:27:27,010 --> 00:27:30,500
du altid kontrollere at se, om
at hukommelsen givet til dig er nul.

533
00:27:30,500 --> 00:27:33,670
Og hvis det ikke er, så vi kan flytte
videre med resten af ​​vores kode.

534
00:27:33,670 --> 00:27:36,140
>> Så vi kommer til at
initialisere den nye node.

535
00:27:36,140 --> 00:27:39,050
Vi vil gøre nye n er lig med n.

536
00:27:39,050 --> 00:27:42,390
Og så vil vi gøre
sætte nyt markøren på nye

537
00:27:42,390 --> 00:27:46,900
til nul fordi lige nu har vi ikke
ønsker noget for det til at pege på.

538
00:27:46,900 --> 00:27:48,755
Vi har ingen idé om, hvor
det kommer til at sætte dig,

539
00:27:48,755 --> 00:27:50,630
og derefter, hvis vi ønsker at
indsætte det i spidsen,

540
00:27:50,630 --> 00:27:53,820
så kan vi overflytte
markøren til hovedet.

541
00:27:53,820 --> 00:27:58,530
Har alle følge den logik
hvor der sker?

542
00:27:58,530 --> 00:28:02,502
>> Alt vi gør, er at skabe en ny
node, indstilling markøren til null,

543
00:28:02,502 --> 00:28:04,210
og derefter omfordeling
det i hovedet, hvis vi

544
00:28:04,210 --> 00:28:06,320
ved, at vi ønsker at indsætte den på hovedet.

545
00:28:06,320 --> 00:28:09,420
Og derefter hovedet kommer til at
peger i retning af, at nye node.

546
00:28:09,420 --> 00:28:11,060
Alle OK med det?

547
00:28:11,060 --> 00:28:12,380
>> Så det er en to-trins proces.

548
00:28:12,380 --> 00:28:14,760
Du bliver nødt til først tildele
uanset hvad du opretter.

549
00:28:14,760 --> 00:28:18,260
Indstil, at markøren til
reference, og så skal du

550
00:28:18,260 --> 00:28:21,400
kan slags dereference
den første pointer

551
00:28:21,400 --> 00:28:22,972
og pege mod nye node.

552
00:28:22,972 --> 00:28:25,680
Uanset hvor du ønsker at indsætte det,
at logik kommer til at holde stik.

553
00:28:25,680 --> 00:28:27,530
>> Det er lidt ligesom at tildele
midlertidige variabler.

554
00:28:27,530 --> 00:28:28,700
Husk, du har fået
at sikre, at du

555
00:28:28,700 --> 00:28:30,346
ikke mister overblikket over, hvis du bytte.

556
00:28:30,346 --> 00:28:33,470
Du ønsker at sikre, at du har en
midlertidig variabel den slags holder

557
00:28:33,470 --> 00:28:35,620
styr på, hvor at ting
lagres så du

558
00:28:35,620 --> 00:28:41,190
ikke mister nogen værdi i løbet
ligesom rode rundt med det.

559
00:28:41,190 --> 00:28:42,710
>> OK, så koden vil være her.

560
00:28:42,710 --> 00:28:45,020
Du fyre kigger efter sektion.

561
00:28:45,020 --> 00:28:48,060
Det vil være der.

562
00:28:48,060 --> 00:28:50,280
>> Så jeg gætte hvordan gør
dette adskiller hvis vi ønskede

563
00:28:50,280 --> 00:28:52,300
at indsætte i midten eller slutningen?

564
00:28:52,300 --> 00:28:57,892
Er der nogen der har en idé om, hvad der er den
pseudokode som den logiske henvisning

565
00:28:57,892 --> 00:29:00,350
at vi ville tage, hvis vi ønskede
at indsætte det i midten?

566
00:29:00,350 --> 00:29:03,391
Så hvis vi ønskede at indsætte det på
hoved, alt vi gør, er at oprette en ny knude.

567
00:29:03,391 --> 00:29:06,311
Vi sætter markøren af ​​denne
ny node til uanset hovedet,

568
00:29:06,311 --> 00:29:08,310
og så har vi sat hovedet
til den nye node, ikke?

569
00:29:08,310 --> 00:29:11,560
Hvis vi ønskede at indsætte det i midten
på listen, hvad ville vi gøre?

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

571
00:29:14,108 --> 00:29:16,110
>> PUBLIKUM: Det ville stadig
være en lignende proces

572
00:29:16,110 --> 00:29:19,114
ligesom tildele pointer og
derefter tildele den pointer,

573
00:29:19,114 --> 00:29:20,530
men vi ville have til at lokalisere der.

574
00:29:20,530 --> 00:29:23,560
>> ANDI Peng: Præcis, så præcist
den samme proces undtagen dig

575
00:29:23,560 --> 00:29:27,820
nødt til at lokalisere præcis, hvor du
ønsker, at nye pointer til at gå ind i,

576
00:29:27,820 --> 00:29:44,790
så hvis jeg ønsker at indsætte i
midt i tilknytning list-- OK,

577
00:29:44,790 --> 00:29:46,370
lad os sige det er vores linkede liste.

578
00:29:46,370 --> 00:29:49,500
Hvis vi ønsker at indsætte det lige her,
vi vil oprette en ny knude.

579
00:29:49,500 --> 00:29:50,520
Vi kommer til at malloc.

580
00:29:50,520 --> 00:29:52,220
Vi kommer til at oprette en ny knude.

581
00:29:52,220 --> 00:29:55,940
Vi kommer til at tildele
pointer af denne node her.

582
00:29:55,940 --> 00:29:58,335
>> Men problemet, der adskiller sig
fra hvor hovedet er

583
00:29:58,335 --> 00:30:00,490
er, at vi vidste præcis
hvor hovedet er.

584
00:30:00,490 --> 00:30:01,930
Det var lige på det første, ikke?

585
00:30:01,930 --> 00:30:04,870
Men her har vi at holde styr
af, hvor vi indsætter det i.

586
00:30:04,870 --> 00:30:07,930
Hvis vi indsætter vores
node her har vi

587
00:30:07,930 --> 00:30:12,270
for at sikre, at
én tidligere til dette knudepunkt

588
00:30:12,270 --> 00:30:14,172
er den, der gentildeler markøren.

589
00:30:14,172 --> 00:30:16,380
Så er du nødt til at slags
holde styr på to ting.

590
00:30:16,380 --> 00:30:19,420
Hvis du holder styr på, hvor dette
node øjeblikket indsættelse ind.

591
00:30:19,420 --> 00:30:23,280
Du er også nødt til at holde styr på, hvor
den forrige node, du kigger på

592
00:30:23,280 --> 00:30:24,340
var også der.

593
00:30:24,340 --> 00:30:25,830
Alle godt med det?

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

595
00:30:26,500 --> 00:30:28,000
>> Hvad med at indsætte ind i enden?

596
00:30:28,000 --> 00:30:34,220
Hvis jeg ønskede at føje det her-- hvis jeg ønskede
at tilføje et nyt knudepunkt til slutningen af ​​en liste,

597
00:30:34,220 --> 00:30:37,009
hvordan kan jeg gå om at gøre det?

598
00:30:37,009 --> 00:30:39,300
PUBLIKUM: Så i øjeblikket, det
sidste ens pegede på nul.

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

600
00:30:40,960 --> 00:30:43,560
Præcis, så dette
øjeblikket bliver peget på ved,

601
00:30:43,560 --> 00:30:46,720
og så jeg gætte, i denne forstand, er det
meget nemt at tilføje til slutningen af ​​en liste.

602
00:30:46,720 --> 00:30:51,810
Alt du skal gøre er at sætte den
svarende til null og derefter boom.

603
00:30:51,810 --> 00:30:53,070
Lige der, meget let.

604
00:30:53,070 --> 00:30:53,960
Meget enkel.

605
00:30:53,960 --> 00:30:56,430
>> Meget lig den
hoved, men logisk du

606
00:30:56,430 --> 00:30:59,690
ønsker at sikre, at de skridt,
du tager i retning af at gøre noget af dette,

607
00:30:59,690 --> 00:31:01,500
du følger med.

608
00:31:01,500 --> 00:31:04,420
Det er meget let at, i midten
af din kode, blive fanget op på,

609
00:31:04,420 --> 00:31:05,671
Åh, jeg har så mange pointere.

610
00:31:05,671 --> 00:31:07,461
Jeg ved ikke, hvor
noget peger på.

611
00:31:07,461 --> 00:31:09,170
Jeg ved ikke engang, hvilken node jeg er på.

612
00:31:09,170 --> 00:31:11,490
Hvad sker der?

613
00:31:11,490 --> 00:31:13,620
>> Slap af, falde til ro, tage en dyb indånding.

614
00:31:13,620 --> 00:31:15,530
Tegn din linkede liste.

615
00:31:15,530 --> 00:31:18,800
Hvis du siger, jeg ved, hvor præcist
Jeg har brug for at indsætte dette i

616
00:31:18,800 --> 00:31:22,970
og jeg ved præcis, hvordan man overflytte min
pointere, meget, meget nemmere at forestille

617
00:31:22,970 --> 00:31:27,200
out-- meget, meget lettere at ikke
fare vild i de fejl i din kode.

618
00:31:27,200 --> 00:31:29,410
Alle OK med det?

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

620
00:31:31,380 --> 00:31:35,120
>> Så jeg gætter et koncept, som vi ikke har
virkelig talte om før nu,

621
00:31:35,120 --> 00:31:38,131
og jeg gætter du sandsynligvis
vil ikke støde meget yet--

622
00:31:38,131 --> 00:31:40,880
det er sådan en avanceret concept--
er, at vi faktisk har en data

623
00:31:40,880 --> 00:31:43,900
struktur, der kaldes en dobbelt linket liste.

624
00:31:43,900 --> 00:31:46,390
Så som du fyre kan se,
alt vi gør er at skabe

625
00:31:46,390 --> 00:31:50,400
en faktisk værdi, en ekstra
pointer på hver af vores knudepunkter

626
00:31:50,400 --> 00:31:52,660
der peger også på forudgående knudepunkt.

627
00:31:52,660 --> 00:31:58,170
Så ikke nok med at vi har vores
knudepunkter peger på den næste.

628
00:31:58,170 --> 00:32:01,430
De peger også på den foregående.

629
00:32:01,430 --> 00:32:04,310
Jeg har tænkt mig at ignorere disse to lige nu.

630
00:32:04,310 --> 00:32:06,740
>> Så har du en kæde
der kan bevæge sig begge veje,

631
00:32:06,740 --> 00:32:09,630
og så er det lidt nemmere
til logisk følge med.

632
00:32:09,630 --> 00:32:11,896
Som her, i stedet for
holde styr på, åh, jeg

633
00:32:11,896 --> 00:32:14,520
nødt til at vide, at denne node er
den, som jeg er nødt til at overflytte,

634
00:32:14,520 --> 00:32:17,532
Jeg kan bare gå her og
bare trække den forrige.

635
00:32:17,532 --> 00:32:19,490
Så jeg ved præcis, hvor
der er, og så skal du

636
00:32:19,490 --> 00:32:21,130
behøver ikke at krydse
hele den linkede liste.

637
00:32:21,130 --> 00:32:22,180
Det er lidt lettere.

638
00:32:22,180 --> 00:32:24,960
>> Men som sådan, har du dobbelt
mængden af ​​pegepinde,

639
00:32:24,960 --> 00:32:26,960
det er dobbelt så meget hukommelse.

640
00:32:26,960 --> 00:32:28,950
Det er en masse pointere at holde styr på.

641
00:32:28,950 --> 00:32:32,140
Det er lidt mere kompliceret, men det er
lidt mere brugervenlig, afhængigt

642
00:32:32,140 --> 00:32:34,080
om, hvad du forsøger at opnå.

643
00:32:34,080 --> 00:32:36,910
>> Så denne type data
struktur helt eksisterer,

644
00:32:36,910 --> 00:32:40,280
og strukturen for er meget, meget
enkel undtagen alt du har, er,

645
00:32:40,280 --> 00:32:43,850
i stedet for blot en pegepind til næste,
har du også en pointer til forrige.

646
00:32:43,850 --> 00:32:45,940
Det er hele forskellen var.

647
00:32:45,940 --> 00:32:47,740
Alle godt med det?

648
00:32:47,740 --> 00:32:48,240
Afkøle.

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

650
00:32:50,940 --> 00:32:53,280
>> Okay, så nu er jeg
til virkelig at tilbringe nok

651
00:32:53,280 --> 00:32:56,870
som 15 til 20 minutter eller hovedparten
af resten af ​​tiden i afsnittet

652
00:32:56,870 --> 00:32:58,360
taler om hash tabeller.

653
00:32:58,360 --> 00:33:02,590
Hvor mange af jer
har læst pset5 spec?

654
00:33:02,590 --> 00:33:03,620
Okay, godt.

655
00:33:03,620 --> 00:33:06,160
Der er højere end 50% af normalt.

656
00:33:06,160 --> 00:33:07,560
Det er ok.

657
00:33:07,560 --> 00:33:10,345
>> Så som du fyre vil se,
du er udfordringen i pset5

658
00:33:10,345 --> 00:33:16,790
vil være at gennemføre en ordbog
hvor du lægger mere end 140.000 ord

659
00:33:16,790 --> 00:33:20,610
at vi giver dig og stavekontrol
den mod hele teksten.

660
00:33:20,610 --> 00:33:22,580
Vi giver dig tilfældige
stykker af litteratur.

661
00:33:22,580 --> 00:33:23,520
Vi giver dig Odysseen.

662
00:33:23,520 --> 00:33:24,561
Vi giver dig Iliaden.

663
00:33:24,561 --> 00:33:26,350
Vi giver dig Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> Og din udfordring
vil være at stavekontrol

665
00:33:28,220 --> 00:33:31,760
hvert eneste ord i alt
af disse ordbøger

666
00:33:31,760 --> 00:33:34,960
hovedsageligt med vores stavekontrol.

667
00:33:34,960 --> 00:33:38,620
Og så der er et par dele
at skabe denne pset,

668
00:33:38,620 --> 00:33:41,970
først du ønsker at være
stand til rent faktisk at indlæse

669
00:33:41,970 --> 00:33:43,970
alle ordene i din
ordbog, og så skal du

670
00:33:43,970 --> 00:33:45,530
vil være i stand til
stavekontrol dem alle.

671
00:33:45,530 --> 00:33:48,780
Og så som sådan, er du nødt til at kræve
en datastruktur, der kan gøre dette hurtigt

672
00:33:48,780 --> 00:33:50,790
og effektivt og dynamisk.

673
00:33:50,790 --> 00:33:52,900
>> Så jeg formoder det nemmeste
måde at gøre dette, du

674
00:33:52,900 --> 00:33:55,010
ville sandsynligvis skabe en række, ikke?

675
00:33:55,010 --> 00:33:58,910
Den nemmeste måde at lagring er dig
kan skabe en række 140.000 ord

676
00:33:58,910 --> 00:34:03,400
og bare placere dem alle der, og
derefter krydse dem ved binær søgning

677
00:34:03,400 --> 00:34:06,780
eller ved valg eller not--
ked, der er sortering.

678
00:34:06,780 --> 00:34:10,729
Du kan sortere dem og derefter krydse dem
ved binær søgning eller bare lineær søgning

679
00:34:10,729 --> 00:34:13,730
og bare sidste ord, men at
tager en enorm mængde hukommelse,

680
00:34:13,730 --> 00:34:15,190
og det er ikke særlig effektiv.

681
00:34:15,190 --> 00:34:18,350
>> Og så vil vi starte
taler om måder at gøre

682
00:34:18,350 --> 00:34:20,110
vores køretid mere effektiv.

683
00:34:20,110 --> 00:34:23,190
Og vores mål er at få
konstant tid, hvor

684
00:34:23,190 --> 00:34:25,810
det er næsten som arrays, hvor
har du øjeblikkelig adgang til.

685
00:34:25,810 --> 00:34:28,560
Hvis jeg ønskede at søge efter noget,
Jeg ønsker at være i stand til bare,

686
00:34:28,560 --> 00:34:30,810
boom, finde det præcist, og træk den ud.

687
00:34:30,810 --> 00:34:34,100
Og så en struktur, hvor
vi vil blive meget tæt

688
00:34:34,100 --> 00:34:37,569
at være i stand til at få adgang til konstant
tid, denne hellige gral

689
00:34:37,569 --> 00:34:41,370
i programmering af konstant
tidspunkt kaldes en hash tabel.

690
00:34:41,370 --> 00:34:45,370
Og så David tidligere nævnt
[Uhørlig] en lille smule i foredrag,

691
00:34:45,370 --> 00:34:49,100
men vi vil virkelig
dykke i dyb denne uge

692
00:34:49,100 --> 00:34:51,780
på et stykke, der er med hensyn til
hvordan en hash tabel fungerer.

693
00:34:51,780 --> 00:34:53,949
>> Så den måde, at en hash
tabelværker, f.eks

694
00:34:53,949 --> 00:35:00,230
hvis jeg ønskede at gemme en masse ord, en
bundt af ord i det engelske sprog,

695
00:35:00,230 --> 00:35:02,940
Jeg kunne i teorien sætte
banan, æble, kiwi, mango, par,

696
00:35:02,940 --> 00:35:04,980
og cantaloupe alle på blot et array.

697
00:35:04,980 --> 00:35:07,044
De kunne alle passer ind og være finde.

698
00:35:07,044 --> 00:35:09,210
Det ville være slags en smerte at
søge gennem og adgang,

699
00:35:09,210 --> 00:35:12,920
men den nemmere måde at gøre dette er
at vi kan skabe faktisk en struktur

700
00:35:12,920 --> 00:35:15,680
kaldes en hash tabel, hvor vi hash.

701
00:35:15,680 --> 00:35:19,880
Vi kører alle vores nøgler gennem
en hash-funktion, en ligning,

702
00:35:19,880 --> 00:35:22,600
der forvandler dem alle i
en slags værdi

703
00:35:22,600 --> 00:35:28,740
at så kan vi gemme på
hovedsagelig en matrix af linkede liste.

704
00:35:28,740 --> 00:35:32,570
>> Og så her, hvis vi ønskede
at lagre engelske ord,

705
00:35:32,570 --> 00:35:37,250
vi kunne potentielt bare, det gør jeg ikke
kender, slå alle de første bogstaver

706
00:35:37,250 --> 00:35:39,630
til en slags et nummer.

707
00:35:39,630 --> 00:35:43,140
Og så, for eksempel, hvis jeg ønskede
En til at være synonymt med apple--

708
00:35:43,140 --> 00:35:47,460
eller til indekset på 0, og
B at være synonymt med 1,

709
00:35:47,460 --> 00:35:51,030
vi kan have 26 indgange
der kan bare gemme

710
00:35:51,030 --> 00:35:53,610
alle bogstaver i
alfabet, som vi vil starte med.

711
00:35:53,610 --> 00:35:56,130
Og så kan vi have
Apple på indekset for 0.

712
00:35:56,130 --> 00:35:59,160
Vi kan have bananer på indekset for
1, cantaloupe på indekset for 2,

713
00:35:59,160 --> 00:36:00,540
og så videre og så videre.

714
00:36:00,540 --> 00:36:04,460
Og således hvis jeg ønskede at søge
min hash tabellen og adgang æble,

715
00:36:04,460 --> 00:36:07,560
Jeg kender æble starter med
en A, og jeg ved præcis

716
00:36:07,560 --> 00:36:10,860
at det skal være og hash
bord på indeks 0, fordi

717
00:36:10,860 --> 00:36:13,620
af funktionen tidligere tildelt.

718
00:36:13,620 --> 00:36:16,572
>> Så ved jeg ikke, vi er
en bruger program, hvor

719
00:36:16,572 --> 00:36:18,780
du vil blive opkrævet med
arbitrarily-- ikke vilkårligt,

720
00:36:18,780 --> 00:36:22,530
med at forsøge at omtanke
tænke på gode ligninger

721
00:36:22,530 --> 00:36:25,460
at kunne sprede
ud af alle dine værdier

722
00:36:25,460 --> 00:36:29,370
på en måde, de nemt kan få adgang
det senere med som en ligning

723
00:36:29,370 --> 00:36:31,130
at du, selv, kender.

724
00:36:31,130 --> 00:36:35,210
Så i den forstand, hvis jeg ønskede at gå til
mango, jeg ved, åh, begynder med m det.

725
00:36:35,210 --> 00:36:37,134
Det skal være indekset for 12.

726
00:36:37,134 --> 00:36:38,800
Jeg behøver ikke at søge gennem noget.

727
00:36:38,800 --> 00:36:42,080
Jeg ved exactly-- jeg kunne bare gå til
indekset på 12 og træk det ud.

728
00:36:42,080 --> 00:36:45,520
>> Alle klar over, hvordan en
hash tabellen funktion virker?

729
00:36:45,520 --> 00:36:48,380
Det er sådan bare en mere kompleks array.

730
00:36:48,380 --> 00:36:50,010
Det er alt det er.

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

732
00:36:51,630 --> 00:36:57,690
>> Så jeg tror vi løber ind
dette spørgsmål om, hvad

733
00:36:57,690 --> 00:37:06,390
sker der, hvis du har flere ting
at give dig det samme indeks?

734
00:37:06,390 --> 00:37:10,570
Så siger vores funktion, alle det
gjorde var tage det første bogstav

735
00:37:10,570 --> 00:37:14,490
og vende det til en
respektive 0 til 25 indekset.

736
00:37:14,490 --> 00:37:17,137
Det er helt fint, hvis
du kun har en af ​​hver.

737
00:37:17,137 --> 00:37:18,970
Men det andet du starter
have mere, er du

738
00:37:18,970 --> 00:37:20,910
vil have, hvad der kaldes en kollision.

739
00:37:20,910 --> 00:37:25,580
>> Så hvis jeg forsøger at indsætte begrave ind i en hash
tabel, der allerede har banan på det,

740
00:37:25,580 --> 00:37:27,870
hvad der kommer til at ske, når
du forsøger at indsætte det?

741
00:37:27,870 --> 00:37:30,930
Dårlige ting fordi banan
findes den allerede i indekset

742
00:37:30,930 --> 00:37:33,800
at du ønsker at gemme det i.

743
00:37:33,800 --> 00:37:35,560
Berry slags er ligesom, ah, hvad gør jeg?

744
00:37:35,560 --> 00:37:37,080
Jeg ved ikke, hvor de skal gå.

745
00:37:37,080 --> 00:37:38,410
Hvordan kan jeg løse dette?

746
00:37:38,410 --> 00:37:41,150
>> Og så du fyre vil slags
se vi gør det vanskelig ting

747
00:37:41,150 --> 00:37:44,810
hvor vi kan slags faktisk
oprette linket liste i vore arrays.

748
00:37:44,810 --> 00:37:46,840
Og så den nemmeste måde
at tænke over dette,

749
00:37:46,840 --> 00:37:50,830
al hash tabel er en
vifte af hægtede lister.

750
00:37:50,830 --> 00:37:55,670
Og så, i den forstand, har du
denne smukke vifte af pegepinde,

751
00:37:55,670 --> 00:37:58,740
og derefter hver pointer i
denne værdi, i nævnte indeks,

752
00:37:58,740 --> 00:38:00,740
kan faktisk pege på andre ting.

753
00:38:00,740 --> 00:38:05,720
Og så har du alle disse særskilte
kæder kommer ud af en stor matrix.

754
00:38:05,720 --> 00:38:07,960
>> Og så her, hvis jeg
ønskede at indsætte bær,

755
00:38:07,960 --> 00:38:11,220
Jeg ved, OK, jeg har tænkt mig at input
det gennem min hash-funktionen.

756
00:38:11,220 --> 00:38:15,070
Jeg har tænkt mig at ende op med indekset for
1, og så jeg har tænkt mig at være i stand til at have

757
00:38:15,070 --> 00:38:20,410
kun en mindre delmængde af denne
gigant 140.000 ord ordbog.

758
00:38:20,410 --> 00:38:24,220
Og så kan jeg bare se
gennem 1/26 af det.

759
00:38:24,220 --> 00:38:27,910
>> Og så kan jeg bare indsætte
bær enten før eller efter banan

760
00:38:27,910 --> 00:38:28,820
I dette tilfælde?

761
00:38:28,820 --> 00:38:29,700
Efter, ikke?

762
00:38:29,700 --> 00:38:33,920
Og så du vil ønsker at
indsætte denne node efter banan,

763
00:38:33,920 --> 00:38:36,667
og så du kommer til at indsætte
på halen af ​​den linkede liste.

764
00:38:36,667 --> 00:38:38,500
Jeg har tænkt mig at gå tilbage
til denne forrige dias,

765
00:38:38,500 --> 00:38:40,680
så du fyre kan se, hvordan
hash-funktionen fungerer.

766
00:38:40,680 --> 00:38:43,980
>> Så hash-funktionen er denne ligning
at du kører slags dit input

767
00:38:43,980 --> 00:38:46,940
igennem for at få uanset indeks
du vil tildele mod.

768
00:38:46,940 --> 00:38:51,130
Og så, i dette eksempel, alle vi ønskede
at gøre, var at tage det første bogstav,

769
00:38:51,130 --> 00:38:55,890
vende det til et indeks, så er vi
kan gemme disse i vores hash-funktionen.

770
00:38:55,890 --> 00:39:00,160
Alt vi laver her er vi
omdannelse af første bogstav.

771
00:39:00,160 --> 00:39:04,770
Så keykey [0] er blot det første bogstav
uanset snor vi har,

772
00:39:04,770 --> 00:39:05,720
vi passerer i.

773
00:39:05,720 --> 00:39:09,740
Vi konverterer det til øverste, og
vi fratrække med store bogstaver A,

774
00:39:09,740 --> 00:39:11,740
så alt, hvad der gør
giver os en række

775
00:39:11,740 --> 00:39:13,670
hvor vi kan hash vores værdier på.

776
00:39:13,670 --> 00:39:16,550
>> Og så vil vi
returnere hash modul størrelse.

777
00:39:16,550 --> 00:39:19,340
Være meget, meget forsigtig
fordi, teoretisk, her

778
00:39:19,340 --> 00:39:21,870
din hashværdi kunne være uendelig.

779
00:39:21,870 --> 00:39:23,660
Det kunne bare blive ved og ved og ved.

780
00:39:23,660 --> 00:39:26,080
Det kunne være nogle virkelig,
virkelig store værdi,

781
00:39:26,080 --> 00:39:29,849
men fordi din hash tabel,
du har oprettet kun har 26 indekser,

782
00:39:29,849 --> 00:39:31,890
du vil sikre dig din
modulusing så du

783
00:39:31,890 --> 00:39:33,848
ikke run-- det er det samme
ting som din queue--

784
00:39:33,848 --> 00:39:36,320
så du ikke løber væk fra
bunden af ​​din hash-funktionen.

785
00:39:36,320 --> 00:39:39,210
>> Du ønsker at pak det tilbage omkring
på samme måde i [uhørligt], når

786
00:39:39,210 --> 00:39:41,750
du havde som en meget,
meget store bogstav, du

787
00:39:41,750 --> 00:39:43,740
ønskede ikke, at for at
bare køre ud i slutningen.

788
00:39:43,740 --> 00:39:46,948
Samme ting her, du vil være sikker på
det ikke løber ud i slutningen af ​​indpakning

789
00:39:46,948 --> 00:39:48,330
rundt til øverst i tabellen.

790
00:39:48,330 --> 00:39:50,530
Så dette er blot en meget
simple hash-funktionen.

791
00:39:50,530 --> 00:39:56,570
Alle, der gjorde var at tage den første
brev af uanset vores input var

792
00:39:56,570 --> 00:40:01,660
og vende det til et indeks,
vi kunne sætte ind i vores hash tabellen.

793
00:40:01,660 --> 00:40:05,450
>> Ja, og så som jeg sagde før,
den måde, vi løser kollisioner

794
00:40:05,450 --> 00:40:09,330
i vores hash tabeller har,
hvad vi kalder, kæde.

795
00:40:09,330 --> 00:40:13,860
Så hvis du forsøger at indsætte flere
ord, der starter med det samme,

796
00:40:13,860 --> 00:40:16,145
du kommer til at have en hash-værdi.

797
00:40:16,145 --> 00:40:18,770
Avocado og æble, hvis du har
køre det gennem vores hash-funktionen,

798
00:40:18,770 --> 00:40:21,450
kommer til at give dig den
samme nummer, antallet af 0.

799
00:40:21,450 --> 00:40:24,550
Og så den måde, vi løser, der er
at vi kan faktisk slags linke dem

800
00:40:24,550 --> 00:40:27,010
sammen via hægtede lister.

801
00:40:27,010 --> 00:40:29,600
>> Og så i denne forstand,
du fyre kan se slags

802
00:40:29,600 --> 00:40:32,640
på, hvordan datastrukturer,
vi har været indstilling tidligere

803
00:40:32,640 --> 00:40:35,870
som en rosin sammenkædet liste art
af kan komme sammen i én.

804
00:40:35,870 --> 00:40:38,860
Og så kan du oprette langt
mere effektive datastrukturer

805
00:40:38,860 --> 00:40:43,350
der kan håndtere større mængder
data, der dynamisk ændrer størrelse afhængigt

806
00:40:43,350 --> 00:40:44,870
på dine behov.

807
00:40:44,870 --> 00:40:45,620
Alle klar?

808
00:40:45,620 --> 00:40:47,580
Alle slags klart
på, hvad der sker her?

809
00:40:47,580 --> 00:40:52,110
>> Hvis jeg ønskede at insert-- hvad er en
frugt, der starter med, ved jeg ikke,

810
00:40:52,110 --> 00:40:54,726
B, bortset fra bær, bananer.

811
00:40:54,726 --> 00:40:55,710
>> PUBLIKUM: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI Peng: Blackberry, brombær.

813
00:40:57,910 --> 00:41:00,530
Hvor kommer brombær gå her?

814
00:41:00,530 --> 00:41:04,251
Nå, vi faktisk har ikke sorteres
dette endnu, men i teorien

815
00:41:04,251 --> 00:41:06,250
hvis vi ønskede at have denne
i alfabetisk rækkefølge,

816
00:41:06,250 --> 00:41:07,944
hvor skal blackberry hen?

817
00:41:07,944 --> 00:41:09,210
>> PUBLIKUM: [uhørligt]

818
00:41:09,210 --> 00:41:11,100
>> ANDI Peng: Præcis, efter her, ikke?

819
00:41:11,100 --> 00:41:14,950
Men da det er meget vanskeligt at
reorder-- Jeg tror det er op til jer.

820
00:41:14,950 --> 00:41:17,920
Du fyre kan helt
gennemføre hvad du vil.

821
00:41:17,920 --> 00:41:20,730
Jo mere effektiv måde
at gøre dette måske

822
00:41:20,730 --> 00:41:24,570
ville være at sortere dit forbundet
listen i alfabetisk rækkefølge,

823
00:41:24,570 --> 00:41:26,520
og så når du er
indsætte ting, du ønsker

824
00:41:26,520 --> 00:41:28,632
være sikker på at indsætte dem
i alfabetisk rækkefølge

825
00:41:28,632 --> 00:41:30,590
så så, når du er
forsøger at søge dem,

826
00:41:30,590 --> 00:41:32,410
du behøver ikke at krydse alt.

827
00:41:32,410 --> 00:41:35,290
Du ved præcis, hvor
det er, og det er lettere.

828
00:41:35,290 --> 00:41:39,100
>> Men hvis du slags har
ting indflettet tilfældigt,

829
00:41:39,100 --> 00:41:41,420
du stadig vil have
til at krydse det anyways.

830
00:41:41,420 --> 00:41:44,990
Og så hvis jeg ønskede at bare
Indsæt blackberry her

831
00:41:44,990 --> 00:41:47,470
og jeg ønskede at søge efter
det, jeg ved, åh, brombær

832
00:41:47,470 --> 00:41:52,012
skal starte med indekset på 1, så jeg
kender øjeblikkeligt bare søge ved 1.

833
00:41:52,012 --> 00:41:53,970
Og så kan jeg slags
krydse sammenkædet liste

834
00:41:53,970 --> 00:41:56,120
indtil jeg kommer til Blackberry,
og then-- ikke?

835
00:41:56,120 --> 00:41:59,550
>> PUBLIKUM: Hvis du forsøger at create--
Jeg gætter ligesom dette er en meget simpel hash

836
00:41:59,550 --> 00:42:00,050
fungere.

837
00:42:00,050 --> 00:42:02,835
Og hvis vi ønskede at gøre
flere lag af denne lignende,

838
00:42:02,835 --> 00:42:05,870
OK, vi ønsker at adskille i
ligesom alle de alfabetiske bogstaver

839
00:42:05,870 --> 00:42:09,040
og derefter igen at kunne lide et andet sæt
af alfabetiske bogstaver inden for denne,

840
00:42:09,040 --> 00:42:11,715
sætter vi gerne en hash
tabel i en hash tabel,

841
00:42:11,715 --> 00:42:13,256
eller som en funktion i en funktion?

842
00:42:13,256 --> 00:42:14,880
Eller er at--

843
00:42:14,880 --> 00:42:17,510
>> ANDI Peng: Så din hash
function-- din hash tabel

844
00:42:17,510 --> 00:42:19,360
kan være så stor som du ønsker det.

845
00:42:19,360 --> 00:42:21,930
Så i den forstand, tænkte jeg
det var meget let, meget

846
00:42:21,930 --> 00:42:25,320
nemt for mig at bare slags baserede
på breve i det første ord.

847
00:42:25,320 --> 00:42:28,690
Og så der er kun 26 muligheder.

848
00:42:28,690 --> 00:42:32,650
Jeg kan kun få 26 muligheder fra
0 til 25, fordi de kun kan

849
00:42:32,650 --> 00:42:36,510
starte fra A til Z. men hvis du ønskede
at tilføje, måske, mere kompleksitet

850
00:42:36,510 --> 00:42:39,260
eller hurtigere køre tid til din
hash tabellen, du absolut

851
00:42:39,260 --> 00:42:40,760
kan gøre alle mulige ting.

852
00:42:40,760 --> 00:42:43,330
Du kan lave din egen
ligning, der giver dig

853
00:42:43,330 --> 00:42:48,000
mere distribution i din
ord, så når du søger,

854
00:42:48,000 --> 00:42:49,300
det vil være hurtigere.

855
00:42:49,300 --> 00:42:52,100
>> Det er helt op til jer
hvordan du ønsker at gennemføre det.

856
00:42:52,100 --> 00:42:55,140
Tænk på det som bare spande.

857
00:42:55,140 --> 00:42:57,376
Hvis jeg ønskede at have
26 spande, jeg vil

858
00:42:57,376 --> 00:42:59,420
at sortere ting i disse spande.

859
00:42:59,420 --> 00:43:02,980
Men jeg har tænkt mig at have en flok
ting i hver spand,

860
00:43:02,980 --> 00:43:05,890
så hvis du ønsker at gøre det
hurtigere og mere effektiv,

861
00:43:05,890 --> 00:43:07,190
lad mig få hundrede spande.

862
00:43:07,190 --> 00:43:09,290
>> Men så er du nødt til at finde ud af en
måde at sortere tingene, så de er

863
00:43:09,290 --> 00:43:11,040
i den rigtige bucket de skal være i.

864
00:43:11,040 --> 00:43:13,331
Men så når du rent faktisk
ønsker at se på den spand,

865
00:43:13,331 --> 00:43:16,410
Det er meget hurtigere, fordi der er
mindre ting i hver spand.

866
00:43:16,410 --> 00:43:20,250
Og så, ja, det er faktisk
det trick for jer i pset5

867
00:43:20,250 --> 00:43:22,360
er, at du vil være
udfordret til bare oprette

868
00:43:22,360 --> 00:43:26,170
hvad der er den mest effektive
funktion, du kan tænke på at være

869
00:43:26,170 --> 00:43:28,520
i stand til at lagre og kontrollere disse værdier.

870
00:43:28,520 --> 00:43:30,840
>> Helt op til jer
men du ønsker at gøre det,

871
00:43:30,840 --> 00:43:32,229
men det er en rigtig god pointe.

872
00:43:32,229 --> 00:43:34,520
At den slags logiske dig
ønsker at begynde at tænke over

873
00:43:34,520 --> 00:43:37,236
er, godt, hvorfor jeg ikke lave flere spande.

874
00:43:37,236 --> 00:43:39,527
Og så er jeg nødt til at søge
mindre ting, og så måske jeg

875
00:43:39,527 --> 00:43:41,640
har en anden hash-funktionen.

876
00:43:41,640 --> 00:43:45,500
>> Ja, der er en masse måder at gøre dette
pset, nogle er hurtigere end andre.

877
00:43:45,500 --> 00:43:50,630
Jeg helt vil bare se, hvordan
hurtig var den hurtigste du fyre vil

878
00:43:50,630 --> 00:43:55,170
være i stand til at få funktioner til at arbejde.

879
00:43:55,170 --> 00:43:58,176
OK, alle godt på
CHAINING og hash tabeller?

880
00:43:58,176 --> 00:44:00,800
Det er faktisk ligesom en meget enkel
koncept, hvis man tænker over det.

881
00:44:00,800 --> 00:44:05,160
Alt det er at adskille, hvad
dine input er i spande,

882
00:44:05,160 --> 00:44:10,670
sortere dem, og derefter søge på
lister, der er forbundet med.

883
00:44:10,670 --> 00:44:11,852
>> Afkøle.

884
00:44:11,852 --> 00:44:18,160
Okay, nu har vi en anden slags
af datastruktur, der kaldes et træ.

885
00:44:18,160 --> 00:44:20,850
Lad os gå på og tale om forsøg
som er tydeligt forskellige,

886
00:44:20,850 --> 00:44:22,330
men i samme kategori.

887
00:44:22,330 --> 00:44:29,010
Væsentlige alle et træ er stedet
for at organisere data i den lineære måde

888
00:44:29,010 --> 00:44:32,560
at en hash-tabel does-- dig
kender, er det fik en top og en bund

889
00:44:32,560 --> 00:44:37,900
og så du slags linke ud af det-- en
Træet har en top, som du kalder roden,

890
00:44:37,900 --> 00:44:40,220
og så har det blade rundt omkring det.

891
00:44:40,220 --> 00:44:42,390
>> Og så alt hvad du har her
er kun den øverste node

892
00:44:42,390 --> 00:44:45,980
som peger på andre knudepunkter, der peger
til flere noder, og så videre og så videre.

893
00:44:45,980 --> 00:44:48,130
Og så skal du bare opdele filialer.

894
00:44:48,130 --> 00:44:53,255
Det er bare en anden måde at organisere
data, og fordi vi kalder det et træ,

895
00:44:53,255 --> 00:44:56,270
jer bare-- det er bare
modelleret ud til at ligne et træ.

896
00:44:56,270 --> 00:44:57,670
Det er derfor, vi kalder det træer.

897
00:44:57,670 --> 00:44:59,370
>> Hash tabel ligner et bord.

898
00:44:59,370 --> 00:45:01,310
Et træ bare ligner et træ.

899
00:45:01,310 --> 00:45:03,300
Alt det er er en separat
måde at organisere knuder

900
00:45:03,300 --> 00:45:06,020
afhængigt af, hvad dine behov er.

901
00:45:06,020 --> 00:45:11,810
>> Så du har en rod og
så har du blade.

902
00:45:11,810 --> 00:45:15,380
Den måde, vi kan især
tænker over det er et binært træ,

903
00:45:15,380 --> 00:45:18,150
et binært træ er blot en
specifik type af et træ

904
00:45:18,150 --> 00:45:22,450
hvor hver node eneste punkter
til, ved max, to andre knuder.

905
00:45:22,450 --> 00:45:25,434
Og så her har du distinkt
symmetri i dit træ

906
00:45:25,434 --> 00:45:28,600
der gør det lettere at slags se
på hvilke værdier du er, fordi du derefter

907
00:45:28,600 --> 00:45:30,150
har altid en venstre eller en højre.

908
00:45:30,150 --> 00:45:33,150
Der er aldrig ligesom en venstre tredjedel fra
venstre eller en fjerde fra venstre.

909
00:45:33,150 --> 00:45:36,358
Det er bare du har en venstre og en højre
og du kan søge en af ​​disse to.

910
00:45:36,358 --> 00:45:38,980
Og så hvorfor er det nyttigt?

911
00:45:38,980 --> 00:45:40,980
Den måde, at dette er
nyttigt, er, hvis du søger

912
00:45:40,980 --> 00:45:42,890
at søge gennem værdier, ikke?

913
00:45:42,890 --> 00:45:45,640
Snarere end at gennemføre binær
søge i en fejl array,

914
00:45:45,640 --> 00:45:49,260
hvis du ønsker at være i stand til at indsætte noder
og tage væk knuder på vilje, og også

915
00:45:49,260 --> 00:45:52,185
bevare søgning
kapacitet binær søgning.

916
00:45:52,185 --> 00:45:54,560
Så på den måde, vi er slags
tricking-- huske, når vi

917
00:45:54,560 --> 00:45:56,530
sagde hægtede lister ikke kan binær søgning?

918
00:45:56,530 --> 00:46:01,700
Vi slags skabe en datastruktur
at tricks, der i arbejdslivet.

919
00:46:01,700 --> 00:46:05,034
>> Og så fordi hægtede lister er lineære,
de kun forbinde den ene efter den anden.

920
00:46:05,034 --> 00:46:06,950
Vi kan slags har
anden slags pejlemærker

921
00:46:06,950 --> 00:46:09,408
der peger på forskellige noder
der kan hjælpe os med søgning.

922
00:46:09,408 --> 00:46:12,590
Og så her, hvis jeg ønskede at
har en binær søgning træ,

923
00:46:12,590 --> 00:46:14,090
Jeg ved, at mit mellemnavn, hvis 55.

924
00:46:14,090 --> 00:46:18,280
Jeg er bare kommer til at skabe den
som mit mellemnavn, som min rod,

925
00:46:18,280 --> 00:46:20,770
og så vil jeg have
værdier spin off af det.

926
00:46:20,770 --> 00:46:25,610
>> Så her, hvis jeg har tænkt mig at søge efter
værdien af ​​66, kan jeg starte på 55.

927
00:46:25,610 --> 00:46:27,310
Det er 66 mere end 55?

928
00:46:27,310 --> 00:46:30,970
Ja, det er, så jeg ved, at jeg kødstykke søge
I n højre pointer dette træ.

929
00:46:30,970 --> 00:46:32,440
Jeg går til 77.

930
00:46:32,440 --> 00:46:35,367
OK, er 66 mindre end eller større end 77?

931
00:46:35,367 --> 00:46:37,950
Det er mindre end, så du ved, åh,
der skal være venstre node.

932
00:46:37,950 --> 00:46:41,410
>> Og så her er vi slags bevare
alle de store ting om arrays,

933
00:46:41,410 --> 00:46:44,420
så ligesom dynamisk resizing
af genstande, som er

934
00:46:44,420 --> 00:46:49,530
i stand til at indsætte og slette efter behag,
uden at skulle bekymre sig om den faste

935
00:46:49,530 --> 00:46:50,370
mængde plads.

936
00:46:50,370 --> 00:46:52,820
Vi bevarer stadig alle
disse vidunderlige ting

937
00:46:52,820 --> 00:46:57,140
samtidig være i stand til at bevare den
log og søg tidspunktet for binær søgning

938
00:46:57,140 --> 00:47:00,450
at vi var kun tidligere
stand til at få en sætning.

939
00:47:00,450 --> 00:47:06,310
>> Cool datastruktur, slags
komplekse at gennemføre, knudepunktet.

940
00:47:06,310 --> 00:47:08,311
Som du kan se, alt det
er struct knudepunktets

941
00:47:08,311 --> 00:47:10,143
er, at du har en venstre
og en højre pointer.

942
00:47:10,143 --> 00:47:11,044
Det er alt det er.

943
00:47:11,044 --> 00:47:12,960
Så snarere end blot
have en x eller en tidligere.

944
00:47:12,960 --> 00:47:15,920
Du har en venstre eller en højre og derefter
du kan slags linke dem sammen

945
00:47:15,920 --> 00:47:16,836
men du så vælger.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, vi rent faktisk vil
bare tage et par minutter.

948
00:47:24,270 --> 00:47:25,790
Så vi kommer til at gå tilbage her.

949
00:47:25,790 --> 00:47:28,270
Som jeg sagde tidligere,
Jeg forklarede slags

950
00:47:28,270 --> 00:47:31,520
logikken bag hvordan vi
vil søge gennem dette.

951
00:47:31,520 --> 00:47:33,860
Vi kommer til at prøve
pseudocoding dette ud for at se

952
00:47:33,860 --> 00:47:38,000
hvis vi slags kan anvende den
samme logik binær søgning

953
00:47:38,000 --> 00:47:40,055
til en anden type datastruktur.

954
00:47:40,055 --> 00:47:45,049
Hvis du fyre ønsker at tage som et par
minutter til bare at tænke over dette.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
OK.

957
00:48:46,925 --> 00:48:51,407
Okay, jeg har tænkt mig at
faktisk bare give dig til-- nej,

958
00:48:51,407 --> 00:48:52,990
Vi vil tale om pseudokoden først.

959
00:48:52,990 --> 00:48:56,580
Så er der nogen ønsker
at give et stik på, hvad

960
00:48:56,580 --> 00:49:02,100
den første ting du vil gøre, når
du starter ud søgning er?

961
00:49:02,100 --> 00:49:04,460
Hvis vi leder efter
værdien af ​​66, hvad er

962
00:49:04,460 --> 00:49:07,940
den første ting, vi ønsker at gøre, hvis
vi ønsker at binær søgning dette træ?

963
00:49:07,940 --> 00:49:10,760
>> PUBLIKUM: Du ønsker at se lige
og ser til venstre og se [uhørligt]

964
00:49:10,760 --> 00:49:11,230
større antal.

965
00:49:11,230 --> 00:49:12,271
>> ANDI Peng: Ja, præcis.

966
00:49:12,271 --> 00:49:15,350
Så du kommer til at se på din rod.

967
00:49:15,350 --> 00:49:18,180
Der er masser af måder, du kan ringe til
det, siger dine forældre node mennesker.

968
00:49:18,180 --> 00:49:21,317
Jeg gerne sige rod, fordi
det er ligesom roden af ​​træet.

969
00:49:21,317 --> 00:49:23,400
Du kommer til at se på
din root node, og du er

970
00:49:23,400 --> 00:49:26,940
kommer til at se er 66 større
eller mindre end 55.

971
00:49:26,940 --> 00:49:30,360
Og hvis det er større end, ja, det er
større end, hvor vi ønsker at se?

972
00:49:30,360 --> 00:49:32,000
Hvor ønsker vi at søge nu, ikke?

973
00:49:32,000 --> 00:49:34,340
Vi ønsker at søge på
højre halvdel af dette træ.

974
00:49:34,340 --> 00:49:38,390
>> Så vi har, bekvemt, en
pointer, der peger til højre.

975
00:49:38,390 --> 00:49:44,325
Og så kan vi sætte
vores nye rod at være 77.

976
00:49:44,325 --> 00:49:46,450
Vi kan bare gå derhen, hvor
markøren peger.

977
00:49:46,450 --> 00:49:49,100
Nå, åh, her vi starter
på 77, og vi kan bare

978
00:49:49,100 --> 00:49:51,172
gøre dette rekursivt igen og igen.

979
00:49:51,172 --> 00:49:52,880
På den måde du slags
af en funktion.

980
00:49:52,880 --> 00:49:57,430
Du har en mulighed for at søge, at du
kan bare gentage igen og igen og igen,

981
00:49:57,430 --> 00:50:02,720
afhængigt af hvor du ønsker at se
indtil du til sidst kommer til den værdi,

982
00:50:02,720 --> 00:50:04,730
at du søger efter.

983
00:50:04,730 --> 00:50:05,230
Give mening?

984
00:50:05,230 --> 00:50:07,800
>> Jeg er ved at vise dig den faktiske
kode, og det er en masse kode.

985
00:50:07,800 --> 00:50:08,674
Ingen grund til at flipper ud.

986
00:50:08,674 --> 00:50:09,910
Vi taler igennem det.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Faktisk, nr.

989
00:50:14,020 --> 00:50:15,061
Det var bare pseudokode.

990
00:50:15,061 --> 00:50:17,860
OK, det var bare pseudokode,
som er en smule kompliceret,

991
00:50:17,860 --> 00:50:19,751
men det er helt fint.

992
00:50:19,751 --> 00:50:21,000
Alle følger sammen her?

993
00:50:21,000 --> 00:50:24,260
Hvis roden er null, afkast
falsk, fordi det betyder

994
00:50:24,260 --> 00:50:26,850
du behøver ikke engang noget der.

995
00:50:26,850 --> 00:50:31,376
>> Hvis rod n er værdien, så hvis det
sker for at være den, du kigger på,

996
00:50:31,376 --> 00:50:34,000
så du kommer til at returnere sandt
fordi du ved, du fandt den.

997
00:50:34,000 --> 00:50:36,250
Men hvis værdien er mindre
end roden af ​​n, er du

998
00:50:36,250 --> 00:50:38,332
kommer til at søge venstre
barn eller venstre blad,

999
00:50:38,332 --> 00:50:39,540
uanset hvad du vil kalde det.

1000
00:50:39,540 --> 00:50:41,750
Og hvis værdien er større end root,
du kommer til at søge den rigtige træet,

1001
00:50:41,750 --> 00:50:44,610
så bare køre funktionen
gennem søgning igen.

1002
00:50:44,610 --> 00:50:48,037
>> Og hvis rod er nul, at denne
betyder, at du har nået slutningen?

1003
00:50:48,037 --> 00:50:50,120
Det betyder, at du ikke har nogen
mere flere blade til at søge,

1004
00:50:50,120 --> 00:50:52,230
så ved du, åh, jeg
gætte det er ikke herinde

1005
00:50:52,230 --> 00:50:55,063
fordi efter jeg har kigget igennem
det hele og det er ikke her,

1006
00:50:55,063 --> 00:50:56,930
det måske bare ikke være her.

1007
00:50:56,930 --> 00:50:58,350
>> Giver det mening for alle?

1008
00:50:58,350 --> 00:51:03,230
Så det er ligesom binær søgning bevare
mulighederne i hægtede lister.

1009
00:51:03,230 --> 00:51:09,200
Cool, og så den anden type
af data struktur jer

1010
00:51:09,200 --> 00:51:13,180
kan prøve at gennemføre på dit pset,
du kun nødt til at vælge en metode.

1011
00:51:13,180 --> 00:51:19,430
Men måske en alternativ metode til
hash tabellen er, hvad vi kalder en trie.

1012
00:51:19,430 --> 00:51:24,080
>> Alle en trie er en
bestemt type træ,

1013
00:51:24,080 --> 00:51:28,600
har værdier, der går til andre værdier.

1014
00:51:28,600 --> 00:51:31,450
Så i stedet for at have en binær
træ i den forstand, at kun én

1015
00:51:31,450 --> 00:51:35,940
ting kan pege på to, kan du få
én ting peger på mange, mange ting.

1016
00:51:35,940 --> 00:51:39,450
Du hovedsageligt har arrays
inde som du gemmer

1017
00:51:39,450 --> 00:51:41,790
pointere, der peger på andre arrays.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Så knudepunktet, hvordan vi
ville definere en trie

1020
00:51:49,460 --> 00:51:52,590
er, vi ønsker at have en
Boolean c ord, ikke?

1021
00:51:52,590 --> 00:51:54,920
Så knuden er boolesk
ligesom sandt eller falsk,

1022
00:51:54,920 --> 00:51:58,490
først og fremmest i spidsen for
den opstilling, er det et ord?

1023
00:51:58,490 --> 00:52:03,620
For det andet, du ønsker at have pejlemærker
til, hvad resten af ​​dem er.

1024
00:52:03,620 --> 00:52:07,470
En smule kompliceret, lidt abstrakt, men
Jeg vil forklare, hvad at alle midler.

1025
00:52:07,470 --> 00:52:13,800
>> Så her, i toppen, hvis du
har en array erklæret allerede

1026
00:52:13,800 --> 00:52:17,040
en node, hvor du har en boolesk
lagret på forsiden

1027
00:52:17,040 --> 00:52:19,490
der fortæller dig, er det et ord?

1028
00:52:19,490 --> 00:52:20,520
Er det ikke et ord?

1029
00:52:20,520 --> 00:52:23,240
Og så har du
resten af ​​dit array,

1030
00:52:23,240 --> 00:52:26,040
faktisk gemmer alle
mulighederne for, hvad det kunne være.

1031
00:52:26,040 --> 00:52:28,660
Så for eksempel, som
øverst du har

1032
00:52:28,660 --> 00:52:32,140
den første ting, der siger sandt eller
falsk, ja eller nej, det er et ord.

1033
00:52:32,140 --> 00:52:38,130
>> Og så har du 0 gennem 26
de bogstaver, som du kan gemme.

1034
00:52:38,130 --> 00:52:42,790
Hvis jeg ønskede at søge her
for flagermus, jeg gå til toppen

1035
00:52:42,790 --> 00:52:49,200
og jeg ser for B. Jeg finde B i min
array, og så ved jeg, OK, er B et ord?

1036
00:52:49,200 --> 00:52:53,010
B er ikke et ord, så derfor
Jeg må holde søger.

1037
00:52:53,010 --> 00:52:56,410
Jeg går fra B, og jeg ser til
pointer, at B peger i retning af

1038
00:52:56,410 --> 00:53:00,900
og jeg ser en anden vifte af information,
den samme struktur, som vi havde før.

1039
00:53:00,900 --> 00:53:05,240
>> Og her-- åh, den næste
bogstav i [uhørligt] er A.

1040
00:53:05,240 --> 00:53:07,210
Så vi ser i dette array.

1041
00:53:07,210 --> 00:53:10,860
Vi finder den ottende værdi,
og derefter se vi at se, åh,

1042
00:53:10,860 --> 00:53:12,840
hey, er, at et ord, er B-A et ord?

1043
00:53:12,840 --> 00:53:13,807
Det er ikke et ord.

1044
00:53:13,807 --> 00:53:14,890
Vi har fået at holde udkig.

1045
00:53:14,890 --> 00:53:17,850
>> Og så så ser vi på, hvor
markøren over A-punkter,

1046
00:53:17,850 --> 00:53:21,130
og den peger på en anden måde i
hvor vi har mere værdi gemt.

1047
00:53:21,130 --> 00:53:24,150
Og til sidst, vi får at
B-A-T, som er et ord.

1048
00:53:24,150 --> 00:53:25,970
Og så næste gang
du ser, er du nødt

1049
00:53:25,970 --> 00:53:30,850
at have denne kontrol af, ja,
denne Boolesk funktion er sandt.

1050
00:53:30,850 --> 00:53:35,450
Og så i den forstand er vi slags
for at have et træ med arrays.

1051
00:53:35,450 --> 00:53:39,890
>> Så kan du slags søge ned.

1052
00:53:39,890 --> 00:53:43,650
Snarere end hashing en funktion og
tildele værdier ved linket liste,

1053
00:53:43,650 --> 00:53:49,190
kan du bare gennemføre en
Trie, der søger downwords.

1054
00:53:49,190 --> 00:53:50,850
Virkelig, virkelig kompliceret ting.

1055
00:53:50,850 --> 00:53:54,060
Ikke let at tænke over, fordi jeg er ligesom
spytte så mange datastrukturer ud

1056
00:53:54,060 --> 00:53:58,710
på dig, men gør alle slags
forstå, hvordan logikken i dette fungerer?

1057
00:53:58,710 --> 00:54:01,920
>> OK, cool.

1058
00:54:01,920 --> 00:54:05,600
Så B-A-T, og derefter
du kommer til at søge.

1059
00:54:05,600 --> 00:54:07,940
Næste gang du går
at se, åh, hey, det er sandt,

1060
00:54:07,940 --> 00:54:09,273
derfor jeg ved, at dette skal være et ord.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Samme for zoo.

1063
00:54:13,770 --> 00:54:17,960
Så her er de ting lige nu, hvis vi
ønskede at søge efter zoo, lige nu,

1064
00:54:17,960 --> 00:54:20,780
øjeblikket zoo er ikke en
ord i vores ordbog

1065
00:54:20,780 --> 00:54:25,300
fordi, som du fyre kan se,
første sted, at vi har en boolesk

1066
00:54:25,300 --> 00:54:28,590
returnere sandt er i slutningen af ​​zoom.

1067
00:54:28,590 --> 00:54:30,430
Vi har Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> Og så her, vi faktisk ikke har
ordet, zoo, i vores ordbog

1069
00:54:33,900 --> 00:54:36,070
fordi dette afkrydsningsfelt ikke er markeret.

1070
00:54:36,070 --> 00:54:39,540
Så computeren ikke
ved, at zoo er et ord

1071
00:54:39,540 --> 00:54:42,430
fordi den måde, at vi har
gemt det, kun en zoom her

1072
00:54:42,430 --> 00:54:44,920
faktisk har en boolesk værdi
der er blevet vendt rigtigt.

1073
00:54:44,920 --> 00:54:49,380
Så hvis vi ønsker at indsætte
ord, zoo, ind i vores ordbog,

1074
00:54:49,380 --> 00:54:51,770
hvordan ville vi gå om at gøre det?

1075
00:54:51,770 --> 00:54:55,960
Hvad skal vi gøre for at sikre vores
computer ved, at Z-O-O er et ord

1076
00:54:55,960 --> 00:54:58,130
og ikke det første ord er Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> PUBLIKUM: [uhørligt]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI Peng: Præcis, vi
ønsker at sikre, at denne

1079
00:55:01,450 --> 00:55:07,890
her, at Boolesk værdi
afkrydset, at det er sandt.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, så vi kommer til at kontrollere, at,
så vi ved præcis, hey, zoo er et ord.

1081
00:55:13,297 --> 00:55:15,380
Jeg har tænkt mig at fortælle
computer, det er et ord, så

1082
00:55:15,380 --> 00:55:18,000
at når computeren checks,
det ved, at zoo er et ord.

1083
00:55:18,000 --> 00:55:21,269
>> Fordi huske alle disse data
strukturer, er det meget let for os

1084
00:55:21,269 --> 00:55:22,310
at sige, åh, bat er et ord.

1085
00:55:22,310 --> 00:55:22,851
Zoo er et ord.

1086
00:55:22,851 --> 00:55:23,611
Zoom er et ord.

1087
00:55:23,611 --> 00:55:25,860
Men når du bygger det,
computeren har ingen idé.

1088
00:55:25,860 --> 00:55:28,619
>> Så du er nødt til at fortælle det nøjagtigt
på hvilket tidspunkt er det et ord?

1089
00:55:28,619 --> 00:55:29,910
På hvilket tidspunkt er det ikke et ord?

1090
00:55:29,910 --> 00:55:31,784
Og på hvilket tidspunkt gør jeg
nødt til at søge ting,

1091
00:55:31,784 --> 00:55:34,000
og på hvilket tidspunkt har jeg brug for at gå næste?

1092
00:55:34,000 --> 00:55:37,010
Enhver fri af det?

1093
00:55:37,010 --> 00:55:39,540
Afkøle.

1094
00:55:39,540 --> 00:55:42,530
>> Og så så kommer den
problemet med, hvordan ville vi

1095
00:55:42,530 --> 00:55:45,560
gå om at indsætte noget
det er faktisk ikke der?

1096
00:55:45,560 --> 00:55:49,090
Så lad os bare sige, at vi ønsker at indsætte
ordet, bad, ind i vores trie.

1097
00:55:49,090 --> 00:55:53,589
Som du fyre kan se som i øjeblikket
alle vi har nu, er B-A-T,

1098
00:55:53,589 --> 00:55:55,630
og denne nye datastruktur
der havde en fadøl, der

1099
00:55:55,630 --> 00:55:59,740
pegede på nul, fordi vi antager
at, åh, er der ingen ord efter B-A-T,

1100
00:55:59,740 --> 00:56:02,530
hvorfor har vi brug for at holde
have tingene efter denne T.

1101
00:56:02,530 --> 00:56:06,581
>> Men problemet opstår, hvis vi gør du
ønsker at have et ord, der kommer efter

1102
00:56:06,581 --> 00:56:07,080
T s.

1103
00:56:07,080 --> 00:56:09,500
Hvis du har bad, er du
vil ønsker en H højre.

1104
00:56:09,500 --> 00:56:13,290
Og så den måde, vi kommer til at gøre det er
vi kommer til at oprette en separat node.

1105
00:56:13,290 --> 00:56:16,840
Vi er ikke tildele uanset mængde
hukommelse for denne nye array,

1106
00:56:16,840 --> 00:56:20,720
og vi kommer til at overflytte pointere.

1107
00:56:20,720 --> 00:56:22,947
>> Vi kommer til at tildele
H, Først og fremmest, dette null,

1108
00:56:22,947 --> 00:56:24,030
vi kommer til at slippe af med.

1109
00:56:24,030 --> 00:56:26,590
Vi kommer til at have
H-punktet nedad.

1110
00:56:26,590 --> 00:56:30,600
Hvis vi ser et H, vi ønsker det
at gå til et andet sted.

1111
00:56:30,600 --> 00:56:33,910
>> Herinde kan vi derefter kontrollere ud ja.

1112
00:56:33,910 --> 00:56:38,170
Hvis vi rammer et H efter T, åh,
så ved vi, at dette er et ord.

1113
00:56:38,170 --> 00:56:41,110
Den boolesk kommer til at returnere sandt.

1114
00:56:41,110 --> 00:56:42,950
Alle klar på, hvordan det skete?

1115
00:56:42,950 --> 00:56:45,110
OK.

1116
00:56:45,110 --> 00:56:47,214
>> Så det væsentlige, alle
disse datastrukturer

1117
00:56:47,214 --> 00:56:50,130
at vi har gået over i dag, jeg har
gået over dem virkelig, virkelig hurtigt

1118
00:56:50,130 --> 00:56:52,192
og ikke på meget
detaljer, og det er OK.

1119
00:56:52,192 --> 00:56:53,900
Når du begynder at rode
med det, vil du være

1120
00:56:53,900 --> 00:56:55,733
holde styr på, hvor
alle pejlemærker er,

1121
00:56:55,733 --> 00:56:58,060
hvad der foregår i dit
datastrukturer, et cetera.

1122
00:56:58,060 --> 00:56:59,810
De vil være meget nyttigt,
og det er op til dig

1123
00:56:59,810 --> 00:57:03,890
fyre til helt finde ud af hvordan
du ønsker at gennemføre tingene.

1124
00:57:03,890 --> 00:57:07,650
>> Og så pset4, af 5-- åh, det er forkert.

1125
00:57:07,650 --> 00:57:10,140
Pset5 er stavefejl.

1126
00:57:10,140 --> 00:57:13,710
Som jeg sagde før, er du nødt til, når
igen, hente kildekoden fra os.

1127
00:57:13,710 --> 00:57:16,210
Der kommer til at være tre vigtigste
ting, du skal downloade.

1128
00:57:16,210 --> 00:57:18,470
Du vil downloade ordbøger,
KERS, og tekster.

1129
00:57:18,470 --> 00:57:21,660
>> Alle disse ting er er
enten ordbøger af ord

1130
00:57:21,660 --> 00:57:25,190
at vi vil have dig til at tjekke
eller test af oplysninger

1131
00:57:25,190 --> 00:57:26,930
at vi vil have dig til stavekontrol.

1132
00:57:26,930 --> 00:57:29,670
Og så ordbøgerne
vi giver du vil

1133
00:57:29,670 --> 00:57:34,870
at give dig faktiske ord, vi ønsker
dig at gemme en eller anden måde på en måde, der er

1134
00:57:34,870 --> 00:57:36,530
mere effektiv end et array.

1135
00:57:36,530 --> 00:57:38,470
Og så teksterne er
kommer til at være, hvad vi er

1136
00:57:38,470 --> 00:57:43,900
beder dig om at stave tjekke for at sikre
alle de ord der er reelle ord.

1137
00:57:43,900 --> 00:57:47,970
>> Og så de tre blokke af
programmer, som vi vil give dig

1138
00:57:47,970 --> 00:57:51,130
kaldes dictionary.c,
dictionary.h og speller.c.

1139
00:57:51,130 --> 00:57:56,500
Og så alle dictionary.c gør er
hvad du bedt om at gennemføre.

1140
00:57:56,500 --> 00:57:57,880
Den indlæser ord.

1141
00:57:57,880 --> 00:58:02,000
Det stave checks dem, og det gør sikker
at alt er indsat korrekt.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h er bare et bibliotek fil
der erklærer alle disse funktioner.

1143
00:58:05,180 --> 00:58:07,650
Og speller.c, vi vil give dig.

1144
00:58:07,650 --> 00:58:09,290
Du behøver ikke at ændre noget af det.

1145
00:58:09,290 --> 00:58:14,290
Alle speller.c gør, er at tage det,
belastninger det, kontrollerer hastigheden af ​​det,

1146
00:58:14,290 --> 00:58:19,190
tester benchmark ligesom hvordan
hurtigt du er i stand til at gøre ting.

1147
00:58:19,190 --> 00:58:20,410
>> Det er en speller.

1148
00:58:20,410 --> 00:58:23,920
Bare ikke rode med det, men gør
at du forstår hvad det gør.

1149
00:58:23,920 --> 00:58:28,090
Vi bruger en funktion kaldet getrusage som
tester effektiviteten af ​​din magi

1150
00:58:28,090 --> 00:58:28,590
checker.

1151
00:58:28,590 --> 00:58:32,200
Alt det gør, er dybest set teste
tid af alt i din ordbog,

1152
00:58:32,200 --> 00:58:33,680
så sørg for at forstå det.

1153
00:58:33,680 --> 00:58:36,660
Vær omhyggelig med ikke at rode med det, eller
ellers ting vil ikke køre ordentligt.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> Og hovedparten af ​​denne udfordring er for
du fyre til virkelig ændre dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Vi vil give dig
140.000 ord i en ordbog.

1157
00:58:48,526 --> 00:58:50,900
Vi vil give dig en tekst
fil, der har disse ord,

1158
00:58:50,900 --> 00:58:54,840
og vi ønsker at du skal være i stand til at organisere
dem i en hash tabel eller en trie

1159
00:58:54,840 --> 00:58:58,140
fordi når vi beder dig om at stave
check-- forestille mig, hvis du er magi

1160
00:58:58,140 --> 00:59:00,690
kontrol ligesom Homers Odysseen.

1161
00:59:00,690 --> 00:59:03,010
Det er ligesom denne enorme, enorme test.

1162
00:59:03,010 --> 00:59:05,190
>> Tænk, hvis hver eneste
ord, du var nødt til at se

1163
00:59:05,190 --> 00:59:08,100
gennem en række værdier 140.000.

1164
00:59:08,100 --> 00:59:10,350
Det ville tage for evigt
til din maskine til at køre.

1165
00:59:10,350 --> 00:59:14,490
Det er derfor, vi ønsker at organisere vores
data i mere effektive datastrukturer

1166
00:59:14,490 --> 00:59:17,270
såsom en hash bord eller et trie.

1167
00:59:17,270 --> 00:59:20,700
Og så du fyre kan slags
på, når du søger adgang

1168
00:59:20,700 --> 00:59:22,570
tingene lettere og hurtigere.

1169
00:59:22,570 --> 00:59:24,934
>> Og så vær omhyggelig med at løse kollisioner.

1170
00:59:24,934 --> 00:59:27,350
Du kommer til at få en masse
af ord, der starter med A.

1171
00:59:27,350 --> 00:59:29,957
Du kommer til at få en masse ord
at starte med B. Op til dig

1172
00:59:29,957 --> 00:59:31,290
fyre hvordan du vil løse det.

1173
00:59:31,290 --> 00:59:34,144
Måske er der mere
effektiv hashfunktion

1174
00:59:34,144 --> 00:59:36,810
end blot det første bogstav i
noget, og så det er op til dig

1175
00:59:36,810 --> 00:59:38,190
fyre at slags gøre hvad du vil.

1176
00:59:38,190 --> 00:59:40,148
>> Måske du ønsker at tilføje
alle bogstaver sammen.

1177
00:59:40,148 --> 00:59:43,410
Måske du ønsker at lide at gøre underlige ting
at redegøre antallet af bogstaver,

1178
00:59:43,410 --> 00:59:43,970
hvad end.

1179
00:59:43,970 --> 00:59:45,386
Op til jer, hvordan du ønsker at gøre.

1180
00:59:45,386 --> 00:59:49,262
Hvis du ønsker at gøre en hash tabel, hvis du
ønsker at prøve en trie, helt op til dig.

1181
00:59:49,262 --> 00:59:52,470
Jeg vil advare dig på forhånd, at den
Trie er typisk en smule mere vanskeligt

1182
00:59:52,470 --> 00:59:54,520
bare fordi der er en masse
flere pointere at holde styr på.

1183
00:59:54,520 --> 00:59:55,645
Men helt op til jer.

1184
00:59:55,645 --> 00:59:58,742
Det er langt mere effektiv
i de fleste tilfælde.

1185
00:59:58,742 --> 01:00:01,450
Du vil virkelig være i stand til at holde
styr på alle dine pointere.

1186
01:00:01,450 --> 01:00:03,850
Ligesom gøre det samme
at jeg gjorde her.

1187
01:00:03,850 --> 01:00:06,871
Når du forsøger at indsætte
værdier ind i en hash tabel eller slette,

1188
01:00:06,871 --> 01:00:08,620
sørg for, at du er
virkelig holde styr

1189
01:00:08,620 --> 01:00:11,860
hvor alt er fordi
det er virkelig nemt for hvis jeg

1190
01:00:11,860 --> 01:00:14,727
forsøger at indsætte ligesom ordet, andy.

1191
01:00:14,727 --> 01:00:16,810
Lad os bare sige, det er en
virkelige ord, det ord, andy,

1192
01:00:16,810 --> 01:00:19,640
til en gigantisk liste over et ord.

1193
01:00:19,640 --> 01:00:22,450
>> Hvis jeg bare tilfældigvis overflytte
en pointer forkert, Ups,

1194
01:00:22,450 --> 01:00:24,940
der går i sin helhed
resten af ​​min sammenkædet liste.

1195
01:00:24,940 --> 01:00:26,897
Nu det eneste ord, jeg
har, er Andy, og nu

1196
01:00:26,897 --> 01:00:29,230
alle de andre ord i
ordbog er gået tabt.

1197
01:00:29,230 --> 01:00:31,370
Og så du vil være sikker på, du
holde styr på alle dine pegepinde

1198
01:00:31,370 --> 01:00:33,661
eller andet, du vil få
store problemer i din kode.

1199
01:00:33,661 --> 01:00:35,840
Tegn tingene ud forsigtigt skridt for skridt.

1200
01:00:35,840 --> 01:00:37,870
Det gør det meget lettere at tænke på.

1201
01:00:37,870 --> 01:00:40,910
>> Og endelig, du ønsker at være i stand til
teste din præstation af dit program

1202
01:00:40,910 --> 01:00:41,618
på den store bord.

1203
01:00:41,618 --> 01:00:43,710
Hvis du fyre tage en
se på CS50 lige nu,

1204
01:00:43,710 --> 01:00:45,210
Vi har, hvad der kaldes den store bord.

1205
01:00:45,210 --> 01:00:50,200
Det er scoren ark af den hurtigste
stave gange kontrol på tværs af alle CS50

1206
01:00:50,200 --> 01:00:55,720
lige nu, tror jeg toppen ligesom 10
gange jeg tror otte af dem er personale.

1207
01:00:55,720 --> 01:00:57,960
Vi virkelig ønsker jer til at slå os.

1208
01:00:57,960 --> 01:01:00,870
>> Alle os forsøgte at gennemføre
den hurtigste kode som muligt.

1209
01:01:00,870 --> 01:01:04,880
Vi ønsker jer til at prøve at udfordre
os og gennemføre hurtigere end alle os

1210
01:01:04,880 --> 01:01:05,550
kan.

1211
01:01:05,550 --> 01:01:07,970
Og så dette er virkelig
første gang, at vi er

1212
01:01:07,970 --> 01:01:12,680
beder jer til at gøre en pset der
du virkelig kan gøre i uanset metode

1213
01:01:12,680 --> 01:01:13,760
du vil have.

1214
01:01:13,760 --> 01:01:17,730
>> Jeg siger altid, det er mere beslægtet
til en real-life løsning, ikke?

1215
01:01:17,730 --> 01:01:19,550
Jeg siger, hey, jeg har brug for dig til at gøre dette.

1216
01:01:19,550 --> 01:01:21,380
Byg et program, der gør dette for mig.

1217
01:01:21,380 --> 01:01:22,630
Gør det dog, du ønsker.

1218
01:01:22,630 --> 01:01:24,271
Jeg ved bare, at jeg vil til at faste.

1219
01:01:24,271 --> 01:01:25,770
Det er din udfordring for denne uge.

1220
01:01:25,770 --> 01:01:27,531
Du gutter, vi kommer
at give dig en opgave.

1221
01:01:27,531 --> 01:01:29,030
Vi vil give dig en udfordring.

1222
01:01:29,030 --> 01:01:31,559
Og så er det op til jer
til helt at bare regne ud

1223
01:01:31,559 --> 01:01:34,100
hvad er den hurtigste og mest
effektiv måde at gennemføre dette.

1224
01:01:34,100 --> 01:01:34,600
Ja?

1225
01:01:34,600 --> 01:01:37,476
>> PUBLIKUM: Er vi lov til, hvis
ønskede at forske hurtigere måder

1226
01:01:37,476 --> 01:01:40,821
at gøre hash tabeller online, kan vi gøre
det og citere en andens kode?

1227
01:01:40,821 --> 01:01:42,070
ANDI Peng: Ja, helt fint.

1228
01:01:42,070 --> 01:01:44,320
Så hvis du fyre læser
spec, der er en linje

1229
01:01:44,320 --> 01:01:48,310
i spec, der siger jer
er helt gratis at forske hash

1230
01:01:48,310 --> 01:01:51,070
funktioner på hvad er nogle
af de hurtigere hashfunktioner

1231
01:01:51,070 --> 01:01:54,720
at køre tingene igennem som
længe du nævner denne kode.

1232
01:01:54,720 --> 01:01:57,220
Så nogle mennesker har allerede
regnet ud hurtige måder

1233
01:01:57,220 --> 01:02:00,250
gøre stavekontrol, af hurtige
måder at lagring af oplysninger.

1234
01:02:00,250 --> 01:02:02,750
Helt op til jer, hvis du
bare ønsker at tage den, ikke?

1235
01:02:02,750 --> 01:02:04,045
Sørg for, at du citerer.

1236
01:02:04,045 --> 01:02:06,170
Udfordringen her virkelig
at vi prøver at teste

1237
01:02:06,170 --> 01:02:09,750
er at sikre, at du ved
din vej rundt pointere.

1238
01:02:09,750 --> 01:02:12,700
Så langt som du gennemføre
den faktiske hash-funktionen

1239
01:02:12,700 --> 01:02:15,070
og kommer op med lignende
matematik til at gøre det,

1240
01:02:15,070 --> 01:02:17,570
du fyre kan forskning, hvad
metoder online jer ønsker.

1241
01:02:17,570 --> 01:02:17,996
Ja?

1242
01:02:17,996 --> 01:02:19,700
>> PUBLIKUM: Kan vi nævne bare
ved hjælp af [uhørligt]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI Peng: Ja.

1244
01:02:20,120 --> 01:02:22,328
Du kan bare i din kommentar,
du kan citere ligesom, åh,

1245
01:02:22,328 --> 01:02:26,127
taget fra yada, yada,
yada, hash-funktionen.

1246
01:02:26,127 --> 01:02:27,210
Nogen der har nogen spørgsmål?

1247
01:02:27,210 --> 01:02:29,694
Vi har faktisk breezed
gennem afsnit dag.

1248
01:02:29,694 --> 01:02:31,610
Jeg vil være op her til
besvare spørgsmål så godt.

1249
01:02:31,610 --> 01:02:36,570
>> Også, som jeg sagde, kontor
timer i aften og i morgen.

1250
01:02:36,570 --> 01:02:40,307
Den spec denne uge er faktisk
super let og super kort at læse.

1251
01:02:40,307 --> 01:02:43,140
Jeg vil foreslå at tage et kig, bare
læse helhed af det.

1252
01:02:43,140 --> 01:02:45,730
>> Og Zamyla faktisk fører dig
gennem hver af de funktioner

1253
01:02:45,730 --> 01:02:49,796
du har brug for at gennemføre, og så det er
meget, meget klart, hvordan at gøre alt.

1254
01:02:49,796 --> 01:02:51,920
Blot for at sikre, at du er
holde styr på pointers.

1255
01:02:51,920 --> 01:02:53,650
Dette er en meget udfordrende pset.

1256
01:02:53,650 --> 01:02:56,744
>> Det er ikke udfordrende, fordi lignende,
Åh, de begreber er så meget mere

1257
01:02:56,744 --> 01:02:59,160
svært, eller du nødt til at lære
så meget ny syntaks vejen

1258
01:02:59,160 --> 01:03:00,650
at du gjorde for den sidste pset.

1259
01:03:00,650 --> 01:03:03,320
Denne pset er vanskeligt, fordi
der er så mange markører,

1260
01:03:03,320 --> 01:03:06,980
og så er det meget, meget let til en gang
du har en fejl i din kode ikke være i stand

1261
01:03:06,980 --> 01:03:08,315
at finde, hvor at fejlen er.

1262
01:03:08,315 --> 01:03:13,200
>> Og så fuldstændig og totalt tro på dig
fyre at være i stand til at slå vores [uhørligt]

1263
01:03:13,200 --> 01:03:13,700
stavemåder.

1264
01:03:13,700 --> 01:03:16,640
Jeg har faktisk ikke nogen skriftlig miner
endnu, men jeg er ved at skrive mine.

1265
01:03:16,640 --> 01:03:19,070
Så mens du skriver
dit, jeg vil skrive mine.

1266
01:03:19,070 --> 01:03:21,070
Jeg har tænkt mig at forsøge at gøre
mine hurtigere end din.

1267
01:03:21,070 --> 01:03:23,940
Vi vil se, hvem der har den hurtigste.

1268
01:03:23,940 --> 01:03:27,340
>> Og ja, jeg vil se alle
jer her på tirsdag.

1269
01:03:27,340 --> 01:03:29,510
Jeg vil køre en form som en pset værksted.

1270
01:03:29,510 --> 01:03:32,640
Alle sektionerne denne
uge er pset workshops,

1271
01:03:32,640 --> 01:03:36,690
så du fyre har masser af muligheder
om hjælp, kontortid som altid,

1272
01:03:36,690 --> 01:03:41,330
og jeg ser virkelig frem til
læse alle dine guys kode.

1273
01:03:41,330 --> 01:03:44,160
Jeg har quizzer op her, hvis du
fyre ønsker at komme få dem.

1274
01:03:44,160 --> 01:03:45,880
Det er alt.

1275
01:03:45,880 --> 01:03:48,180