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

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

3
00:00:05,380 --> 00:00:08,210
>> ANDI Peng: Welkom in week 6 van de sectie.

4
00:00:08,210 --> 00:00:11,620
We afgeweken van onze standaard
sectie tijd van dinsdag

5
00:00:11,620 --> 00:00:14,130
middag om deze mooie zondagochtend.

6
00:00:14,130 --> 00:00:17,330
Dank u voor iedereen die
toegetreden mij vandaag, maar serieus,

7
00:00:17,330 --> 00:00:18,170
een applaus.

8
00:00:18,170 --> 00:00:20,600
>> Dat is een vrij grote inspanning.

9
00:00:20,600 --> 00:00:23,600
Ik bijna niet maken het zelfs
in de tijd, maar het was ok.

10
00:00:23,600 --> 00:00:27,520
Dus ik weet dat jullie allemaal
hebben het gewoon aan de quiz.

11
00:00:27,520 --> 00:00:30,370
Allereerst van harte welkom om
de keerzijde van dat.

12
00:00:30,370 --> 00:00:32,917
>> Ten tweede, zullen we over praten.

13
00:00:32,917 --> 00:00:34,000
We praten over de quiz.

14
00:00:34,000 --> 00:00:35,700
We zullen praten over hoe
je doet in de klas.

15
00:00:35,700 --> 00:00:36,550
Je zult wel goed.

16
00:00:36,550 --> 00:00:39,080
Ik heb je quizzen voor
u eind hier

17
00:00:39,080 --> 00:00:42,120
dus als jullie willen nemen
een naar kijken, helemaal prima.

18
00:00:42,120 --> 00:00:46,590
>> Zo snel voordat we beginnen, de
agenda voor vandaag als volgt.

19
00:00:46,590 --> 00:00:48,430
Zoals u kunt zien, zijn we
in principe een snelle afvuren

20
00:00:48,430 --> 00:00:52,120
door middel van een hele hoop van datastructuren
echt, echt, echt snel.

21
00:00:52,120 --> 00:00:54,380
Dus als zodanig, zal het niet worden
super interactief vandaag.

22
00:00:54,380 --> 00:00:59,620
Het zal aan mij liggen soort schreeuwen
dingen die je, en als ik verwarren,

23
00:00:59,620 --> 00:01:02,680
als ik ga te snel, laat het me weten.

24
00:01:02,680 --> 00:01:05,200
Ze zijn gewoon verschillende data
structuren en kader

25
00:01:05,200 --> 00:01:07,070
van PSET deze
komende week, zult u

26
00:01:07,070 --> 00:01:10,340
worden gevraagd om een ​​van hen uit te voeren,
misschien twee them-- beiden

27
00:01:10,340 --> 00:01:12,319
in uw PSET.

28
00:01:12,319 --> 00:01:14,610
OK, dus ik ga gewoon
beginnen met een aantal aankondigingen.

29
00:01:14,610 --> 00:01:19,070
We zullen gaan over stacks en wachtrijen meer in
diepte dan wat we voor de quiz deden.

30
00:01:19,070 --> 00:01:20,990
We zullen gaan over gekoppelde
lijst opnieuw, nogmaals,

31
00:01:20,990 --> 00:01:23,899
meer in de diepte dan wat
we hadden voor de quiz.

32
00:01:23,899 --> 00:01:26,440
En dan zullen we praten over hash
tafels, bomen en probeert die

33
00:01:26,440 --> 00:01:28,890
zijn allemaal erg nodig zijn voor uw PSET.

34
00:01:28,890 --> 00:01:32,925
En dan gaan we over een aantal
handige tips voor pset5.

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

36
00:01:37,360 --> 00:01:41,090
Het gemiddelde was 58%.

37
00:01:41,090 --> 00:01:45,370
Het was erg laag, en dus jullie allemaal
deed zeer, zeer goed in overeenstemming

38
00:01:45,370 --> 00:01:46,510
met dat.

39
00:01:46,510 --> 00:01:49,970
>> Vrij veel, vuistregel is als je
binnen een standaarddeviatie van het gemiddelde

40
00:01:49,970 --> 00:01:52,990
vooral omdat we in een minder
comfortabele sectie, je bent helemaal prima.

41
00:01:52,990 --> 00:01:54,120
Je bent op het juiste spoor.

42
00:01:54,120 --> 00:01:55,190
Het leven is goed.

43
00:01:55,190 --> 00:01:58,952
>> Ik weet dat het eng om te denken dat
Ik heb als een 40% op deze quiz.

44
00:01:58,952 --> 00:02:00,160
Ik ga deze klasse mislukken.

45
00:02:00,160 --> 00:02:02,243
Ik beloof je, je bent niet
naar de klasse mislukken.

46
00:02:02,243 --> 00:02:03,680
Je bent helemaal prima.

47
00:02:03,680 --> 00:02:06,850
>> Voor degenen onder u die dan kreeg
het gemiddelde, indrukwekkend, indrukwekkend,

48
00:02:06,850 --> 00:02:08,780
als, serieus goed gedaan.

49
00:02:08,780 --> 00:02:09,689
Ik heb ze bij me.

50
00:02:09,689 --> 00:02:11,730
Voel je vrij om te komen hen
aan het eind van de sectie.

51
00:02:11,730 --> 00:02:14,520
Laat me weten als je hebt
problemen, vragen hen.

52
00:02:14,520 --> 00:02:17,204
Als we uw score
verkeerd, laat het ons weten.

53
00:02:17,204 --> 00:02:21,240
>> OK, dus pset5, dit is echt een
rare week voor Yale in de zin

54
00:02:21,240 --> 00:02:24,240
dat onze PSET is te wijten
Woensdag op de middag met inbegrip

55
00:02:24,240 --> 00:02:27,317
het einde van de dag, dus het is eigenlijk
theoretisch verschuldigde dinsdag op de middag.

56
00:02:27,317 --> 00:02:29,150
Waarschijnlijk niemand klaar
op dinsdag op de middag.

57
00:02:29,150 --> 00:02:30,830
Dat is helemaal prima.

58
00:02:30,830 --> 00:02:33,700
We gaan kantooruren
vanavond evenals maandagavond.

59
00:02:33,700 --> 00:02:36,810
En alle van de secties deze week
daadwerkelijk worden omgezet in workshops,

60
00:02:36,810 --> 00:02:38,800
dus voel je vrij om pop in
elke sectie die u wilt,

61
00:02:38,800 --> 00:02:42,810
en ze zullen soort mini-PSET zijn
workshops voor hulp op dat.

62
00:02:42,810 --> 00:02:45,620
Dus als zodanig, dit is de enige sectie
waar we lesmateriaal.

63
00:02:45,620 --> 00:02:49,220
Alle andere afdelingen zal worden gericht
uitsluitend op de hulp van de PSET.

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

65
00:02:50,146 --> 00:02:52,000
>> Publiek: Waar zijn de kantooruren?

66
00:02:52,000 --> 00:02:56,120
>> ANDI Peng: Spreekuur
tonight-- oh, goede vraag.

67
00:02:56,120 --> 00:03:00,580
Ik denk dat de kantooruren vanavond
zijn in Wintertaling of Commons.

68
00:03:00,580 --> 00:03:02,984
Als u online CS50 controleren
en ga je naar de kantooruren,

69
00:03:02,984 --> 00:03:05,650
Er moet een schema dat
vertelt u waar ze allemaal zijn.

70
00:03:05,650 --> 00:03:07,954
>> Ik weet ook vanavond
of morgen is wintertaling,

71
00:03:07,954 --> 00:03:10,120
en ik denk dat we hebben
commons voor de andere nacht.

72
00:03:10,120 --> 00:03:11,020
Ik weet het niet zeker.

73
00:03:11,020 --> 00:03:11,700
Goede vraag.

74
00:03:11,700 --> 00:03:14,430
Controleer op CS50.

75
00:03:14,430 --> 00:03:18,780
>> Koele, vragen over de
schema voor de komende als drie dagen?

76
00:03:18,780 --> 00:03:21,690
Ik beloof jullie als David
zei, dit is de top van de heuvel.

77
00:03:21,690 --> 00:03:23,050
Jullie zijn er bijna.

78
00:03:23,050 --> 00:03:24,644
Slechts drie dagen.

79
00:03:24,644 --> 00:03:26,310
Krijgen daar, en dan gaan we allemaal naar beneden komen.

80
00:03:26,310 --> 00:03:28,114
We zullen een mooie CS-vrije pauze.

81
00:03:28,114 --> 00:03:28,780
Welkom terug.

82
00:03:28,780 --> 00:03:30,779
We zullen een duik nemen in het web
programmering en ontwikkeling,

83
00:03:30,779 --> 00:03:35,150
dingen die zijn erg leuk in vergelijking
een aantal van de andere psets.

84
00:03:35,150 --> 00:03:37,974
En het zal chill, en
We zullen veel plezier hebben.

85
00:03:37,974 --> 00:03:38,890
We zullen meer snoep te hebben.

86
00:03:38,890 --> 00:03:39,730
Sorry voor snoep.

87
00:03:39,730 --> 00:03:40,945
Ik vergat snoep.

88
00:03:40,945 --> 00:03:43,310
Het was een ruwe ochtend.

89
00:03:43,310 --> 00:03:46,340
Dus jullie zijn er bijna,
en ik ben echt trots op jullie.

90
00:03:46,340 --> 00:03:49,570
>> OK, dus stapelt.

91
00:03:49,570 --> 00:03:53,331
Die hield de vraag over Jack
en zijn kleding op de quiz?

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

93
00:03:53,830 --> 00:03:56,500
Oke dat is goed.

94
00:03:56,500 --> 00:04:00,200
>> Dus in wezen als je kunt
foto Jack, deze man hier,

95
00:04:00,200 --> 00:04:03,350
houdt om de kleding te nemen
uit de bovenkant van de stapel,

96
00:04:03,350 --> 00:04:05,750
en hij zet het terug op
de stapel nadat hij heeft gedaan.

97
00:04:05,750 --> 00:04:07,600
Dus op deze manier, hij nooit
lijkt te zijn om

98
00:04:07,600 --> 00:04:10,090
aan de onderkant van de
stapelen in zijn kleding.

99
00:04:10,090 --> 00:04:12,600
Dus dit soort beschrijft
de basisgegevens structuur

100
00:04:12,600 --> 00:04:16,610
hoe een stack is geïmplementeerd.

101
00:04:16,610 --> 00:04:20,060
>> Wezen, denk aan een
stack eventuele stapel voorwerpen

102
00:04:20,060 --> 00:04:24,900
waar je dingen op de top, en
ze dan pop je uit de top.

103
00:04:24,900 --> 00:04:28,600
Dus LIFO is de afkorting we graag
om use-- Last In, First Out.

104
00:04:28,600 --> 00:04:32,480
En zo lang op de top van de
stack is de eerste die naar buiten komt.

105
00:04:32,480 --> 00:04:34,260
En zo de twee termen
we willen associëren

106
00:04:34,260 --> 00:04:36,190
met die push en pop genoemd.

107
00:04:36,190 --> 00:04:39,790
Als je iets op het duwen
stapelen, en je pop een back-up.

108
00:04:39,790 --> 00:04:43,422
>> En dus ik denk dat dit soort van een
abstract concept voor degenen onder u

109
00:04:43,422 --> 00:04:45,630
die willen zien als een
daadwerkelijke uitvoering van deze

110
00:04:45,630 --> 00:04:46,740
in de echte wereld.

111
00:04:46,740 --> 00:04:50,170
Hoeveel van jullie hebben een essay geschreven
misschien als een uur voordat het te wijten was,

112
00:04:50,170 --> 00:04:54,510
en je per ongeluk verwijderd een enorme
deel van het, zoals per ongeluk?

113
00:04:54,510 --> 00:04:58,560
En wat aanvangen
we gebruiken om het terug te zetten?

114
00:04:58,560 --> 00:05:00,030
Controle-Z, ja?

115
00:05:00,030 --> 00:05:03,640
Controle-Z, dus het aantal keren
dat Controle-Z mijn leven heeft gered,

116
00:05:03,640 --> 00:05:08,820
heeft mijn kont opgeslagen, elke keer
dat is uitgevoerd door middel van een stapel.

117
00:05:08,820 --> 00:05:13,020
>> In wezen alle informatie
dat is op uw Word-document,

118
00:05:13,020 --> 00:05:15,080
het wordt geduwd en dook op wil.

119
00:05:15,080 --> 00:05:19,460
En dus in wezen wanneer u
alles verwijderen, je pop een back-up.

120
00:05:19,460 --> 00:05:22,820
En dan, als je het nodig hebt weer op, u
duw het, dat is wat de Control-C doet.

121
00:05:22,820 --> 00:05:26,770
En zo echte wereld functie
hoe eenvoudige datastructuur

122
00:05:26,770 --> 00:05:28,690
kan helpen met uw dagelijks leven.

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

124
00:05:31,710 --> 00:05:40,150
>> Dus een structuur is de manier waarop
we eigenlijk creëren een stapel.

125
00:05:40,150 --> 00:05:44,720
We typen definiëren structuur, en vervolgens
we noemen het stapelen op de bodem.

126
00:05:44,720 --> 00:05:47,440
En binnen de stack,
hebben we twee parameters

127
00:05:47,440 --> 00:05:51,580
welke wij in essentie manipuleren
dus we hebben char ster strijkers capaciteit.

128
00:05:51,580 --> 00:05:55,150
>> Alles wat zij doet
creëert een array

129
00:05:55,150 --> 00:05:58,835
dat we kunnen opslaan wat je wilt
waarbij we de capaciteit kan bepalen.

130
00:05:58,835 --> 00:06:01,990
Capaciteit is gewoon de max hoeveelheid
artikelen die wij in deze serie kan zetten.

131
00:06:01,990 --> 00:06:05,660
int grootte is de teller die blijft
bijhouden hoeveel items zijn

132
00:06:05,660 --> 00:06:07,850
in de stack.

133
00:06:07,850 --> 00:06:11,860
Dus dan kunnen we bijhouden, A,
zowel hoe groot de werkelijke stapel,

134
00:06:11,860 --> 00:06:14,850
en, B, hoeveel van die stapel
we gevuld omdat wij niet willen

135
00:06:14,850 --> 00:06:18,800
over te overstromen wat onze capaciteit.

136
00:06:18,800 --> 00:06:24,340
>> Dus bijvoorbeeld, deze mooie
vraag was op de quiz.

137
00:06:24,340 --> 00:06:28,160
In wezen hoe kunnen we duwen
op de bovenkant van een stapel.

138
00:06:28,160 --> 00:06:28,830
Vrij eenvoudig.

139
00:06:28,830 --> 00:06:30,621
Als je er naar kijkt,
we lopen door dit.

140
00:06:30,621 --> 00:06:32,640
Als [onverstaanbaar] omvang--
vergeet niet, wanneer u

141
00:06:32,640 --> 00:06:35,300
wilt een toegang
parameter binnen een structuur,

142
00:06:35,300 --> 00:06:40,320
je doet de naam van de struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> In dit geval, s
de naam van onze stack.

144
00:06:42,720 --> 00:06:46,230
Wij willen toegang tot de grootte
van het, dus we doen s.size.

145
00:06:46,230 --> 00:06:50,280
Dus zolang de grootte is niet
gelijk aan de capaciteit of zolang

146
00:06:50,280 --> 00:06:52,940
want het is minder dan de capaciteit,
ofwel zou hier werken.

147
00:06:52,940 --> 00:06:57,180
>> U wilt toegang tot de binnenkant
van je stack, zo s.strings,

148
00:06:57,180 --> 00:07:00,790
en je gaat naar dat nieuwe nummer gezet
dat u wilt invoegen in daar.

149
00:07:00,790 --> 00:07:05,030
Laten we zeggen dat we willen
Steek int n op de stapel,

150
00:07:05,030 --> 00:07:08,905
we konden s.strings doen,
beugels, s.size gelijk aan n.

151
00:07:08,905 --> 00:07:11,030
Omdat de grootte is waar we
Momenteel zijn er in de stapel

152
00:07:11,030 --> 00:07:14,590
als we gaan om te duwen
het op, wij slechts toegang

153
00:07:14,590 --> 00:07:17,370
waar de grootte, de
huidige volheid van de stack,

154
00:07:17,370 --> 00:07:21,729
en duwen we de int n op het.

155
00:07:21,729 --> 00:07:24,770
En dan willen we ervoor zorgen dat
We zijn ook het verhogen van de grootte van de n,

156
00:07:24,770 --> 00:07:27,436
dus we kunnen bijhouden we hebben
Een extra ding toegevoegd aan de stack.

157
00:07:27,436 --> 00:07:29,660
Nu hebben we een grotere omvang.

158
00:07:29,660 --> 00:07:33,196
Betekent dit hier te maken zin om
iedereen, hoe logisch het werkt?

159
00:07:33,196 --> 00:07:34,160
Het was een beetje snel.

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

161
00:07:39,535 --> 00:07:42,160
PUBLIEK: Kunt u gaan over
de s.stringss.strings [s.size] weer?

162
00:07:42,160 --> 00:07:45,808
ANDI Peng: Tuurlijk, dus wat doet
s.size ons momenteel te geven?

163
00:07:45,808 --> 00:07:47,440
Publiek: Het is de huidige omvang.

164
00:07:47,440 --> 00:07:50,890
ANDI Peng: Precies, dus het
huidige index die onze omvang is,

165
00:07:50,890 --> 00:07:57,780
en dus willen we de nieuwe integer zetten
die we willen invoegen in s.size.

166
00:07:57,780 --> 00:07:58,760
Slaat dat ergens op?

167
00:07:58,760 --> 00:08:01,110
Omdat s.strings, dat alles
is de naam van de array.

168
00:08:01,110 --> 00:08:03,510
Al is het is de toegang tot
serie in onze structuur,

169
00:08:03,510 --> 00:08:06,030
en dus als we willen
plaatsen n in die index,

170
00:08:06,030 --> 00:08:09,651
kunnen we gewoon toegang toe
met behulp van beugels s.size.

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

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

173
00:08:13,580 --> 00:08:18,916
>> Oké, pop, ik pseudocode het uit
voor jullie, maar vergelijkbaar concept.

174
00:08:18,916 --> 00:08:19,790
Slaat dat ergens op?

175
00:08:19,790 --> 00:08:22,310
Als de grootte groter
dan nul, dan heb je

176
00:08:22,310 --> 00:08:25,350
weet dat je iets wilt nemen
omdat als het formaat is niet

177
00:08:25,350 --> 00:08:27,620
groter dan nul, dan heb je
hebben niets in de stapel.

178
00:08:27,620 --> 00:08:29,840
>> Zodat u alleen wilt uitvoeren
Deze code, het kan alleen maar

179
00:08:29,840 --> 00:08:32,320
pop als er iets te knallen.

180
00:08:32,320 --> 00:08:35,830
Dus als de grootte is groter
dan 0, we min de grootte.

181
00:08:35,830 --> 00:08:40,020
We verlagen de grootte en dan terug
wat is de binnenkant van het omdat

182
00:08:40,020 --> 00:08:42,710
door knallen, we willen
toegang welke wordt opgeslagen

183
00:08:42,710 --> 00:08:45,694
de index van de top van de stack.

184
00:08:45,694 --> 00:08:46,610
Alles zinvol?

185
00:08:46,610 --> 00:08:49,693
Als ik jullie dit schrijf uit,
zouden jullie in staat zijn om het uit te schrijven?

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

187
00:08:52,029 --> 00:08:53,570
Oké, jullie kunnen rond spelen.

188
00:08:53,570 --> 00:08:55,252
Geen zorgen als je niet krijgen.

189
00:08:55,252 --> 00:08:57,460
We hebben geen tijd om code
het vandaag, want we hebben

190
00:08:57,460 --> 00:08:59,959
kreeg veel van deze structuren
om door te gaan, maar in wezen

191
00:08:59,959 --> 00:09:02,214
pseudocode, zeer, zeer vergelijkbaar te duwen.

192
00:09:02,214 --> 00:09:03,380
Volg gewoon langs de logica.

193
00:09:03,380 --> 00:09:06,092
Zorg ervoor dat je toegang tot alle
functies van uw structuur correct.

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

195
00:09:06,574 --> 00:09:09,282
>> PUBLIEK: Zal ​​deze dia's en
deze hele zaak vandaag-ish?

196
00:09:09,282 --> 00:09:11,586
ANDI Peng: Altijd, yep.

197
00:09:11,586 --> 00:09:13,710
Ik ga proberen om te zetten
dit op als een uur na.

198
00:09:13,710 --> 00:09:16,626
Ik zal e-mail David, zal David proberen
zet het op als een uur na dit.

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

200
00:09:20,040 --> 00:09:25,470
>> OK, dus dan gaan we naar deze andere
mooie gegevensstructuur genaamd een wachtrij.

201
00:09:25,470 --> 00:09:30,140
Zoals jullie hier kunt zien, een
wachtrij, voor de Britten onder ons,

202
00:09:30,140 --> 00:09:32,010
al is het een lijn.

203
00:09:32,010 --> 00:09:34,680
Dus in tegenstelling tot wat
je denkt dat een stapel,

204
00:09:34,680 --> 00:09:37,750
een wachtrij is precies wat
logisch je denkt dat het is.

205
00:09:37,750 --> 00:09:41,914
Het is in het bezit van de regels van FIFO,
dat is First In, First Out.

206
00:09:41,914 --> 00:09:43,705
Als je de eerste
één op de lijn, je bent

207
00:09:43,705 --> 00:09:46,230
de eerste die
komt uit de lijn.

208
00:09:46,230 --> 00:09:49,680
>> Dus wat we willen noemen dit
wordt dequeueing en enqueueing.

209
00:09:49,680 --> 00:09:52,380
Als we iets willen toevoegen
onze wachtrij, we enqueue.

210
00:09:52,380 --> 00:09:55,690
Als we willen dequeue, of neem
iets weg, we dequeue.

211
00:09:55,690 --> 00:10:03,350
>> Zodat hetzelfde gevoel dat we soort
creëren van vaste grootte elementen die we

212
00:10:03,350 --> 00:10:06,500
kunnen bepaalde opslaan
dingen, maar we kunnen ook

213
00:10:06,500 --> 00:10:10,100
veranderen waar we plaatsen
parameters binnenkant van hen

214
00:10:10,100 --> 00:10:13,140
gebaseerd op wat voor soort
functionaliteit die we willen.

215
00:10:13,140 --> 00:10:16,700
Dus stacks, wilden we de laatste
een, N de eerste buiten te zijn.

216
00:10:16,700 --> 00:10:19,800
Wachtrij is willen we het eerste ding
in om het eerste ding uit zijn.

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

218
00:10:22,510 --> 00:10:26,710
>> Zodat de structuur-type
definiëren, zoals u kunt zien,

219
00:10:26,710 --> 00:10:29,470
het is een beetje anders
van wat de stack was

220
00:10:29,470 --> 00:10:33,120
omdat we niet alleen moeten blijven
spoor van waar de grootte van dit moment is,

221
00:10:33,120 --> 00:10:37,420
we willen ook spoor van het hoofd houden
evenals waar we nu zijn.

222
00:10:37,420 --> 00:10:39,580
Dus ik denk dat het makkelijker
als ik trek deze omhoog.

223
00:10:39,580 --> 00:10:53,270
Dus laten we denken dat we een wachtrij gekregen,
dus laten we zeggen dat het hoofd is hier.

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

225
00:10:55,811 --> 00:10:58,310
Het hoofd van de lijn, laat
gewoon zeggen dat er op dit moment,

226
00:10:58,310 --> 00:11:01,809
en we willen invoegen
iets in de wachtrij.

227
00:11:01,809 --> 00:11:04,350
Ik ga op maat wezen bellen
is hetzelfde als de staart,

228
00:11:04,350 --> 00:11:06,314
het einde van waar uw wachtrij.

229
00:11:06,314 --> 00:11:07,730
Laten we zeggen dat de grootte is hier.

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

231
00:11:14,380 --> 00:11:18,400
>> Dus hoe werkt een haalbare
Steek iets in een wachtrij?

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

233
00:11:21,000 --> 00:11:24,130
Wat index willen we plaatsen
waar we willen invoegen in.

234
00:11:24,130 --> 00:11:29,320
Als dit het begin van
wachtrij en dit is het einde ervan

235
00:11:29,320 --> 00:11:31,860
of de grootte van het, waar doen we
wil naar het volgende object toe te voegen?

236
00:11:31,860 --> 00:11:32,920
>> PUBLIEK: [onverstaanbaar]

237
00:11:32,920 --> 00:11:35,920
ANDI Peng: Precies, je wilt toevoegen
is afhankelijk heb je het geschreven.

238
00:11:35,920 --> 00:11:37,840
Of deze leeg is of dat is leeg.

239
00:11:37,840 --> 00:11:42,630
Dus je wilt het waarschijnlijk toe te voegen
hier, want als de grootte is--

240
00:11:42,630 --> 00:11:50,540
als deze zijn allemaal vol, je wilt
om het hier toe, toch?

241
00:11:50,540 --> 00:11:57,150
>> En dat is dus, terwijl het heel erg
eenvoudige, niet helemaal altijd correct

242
00:11:57,150 --> 00:12:00,690
omdat de belangrijkste verschil
tussen een wachtrij en een stapel

243
00:12:00,690 --> 00:12:04,350
dat de wachtrij kan
daadwerkelijk gemanipuleerd

244
00:12:04,350 --> 00:12:06,980
zodat de kop verandert
afhankelijk van waar u wilt

245
00:12:06,980 --> 00:12:08,650
het begin van uw cue om te beginnen.

246
00:12:08,650 --> 00:12:11,900
En als gevolg, je staart
Ook gaat veranderen.

247
00:12:11,900 --> 00:12:14,770
En zo een kijkje nemen op
deze code nu.

248
00:12:14,770 --> 00:12:18,620
Zoals jullie ook gevraagd
schrijf op de quiz, enqueue.

249
00:12:18,620 --> 00:12:22,580
Misschien zullen we door waarom praten
het antwoord was wat het was.

250
00:12:22,580 --> 00:12:26,790
>> Ik kon niet helemaal fit deze lijn op een,
maar in wezen dit stukje code

251
00:12:26,790 --> 00:12:29,030
moet op één lijn.

252
00:12:29,030 --> 00:12:30,140
Breng als 30 seconden.

253
00:12:30,140 --> 00:12:33,000
Neem een ​​kijkje en zie waarom
Dit is de manier waarop het is.

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

255
00:12:50,030 --> 00:12:55,420
>> Zeer, zeer vergelijkbare structuur, zeer, zeer
gelijkaardige structuur als de vorige

256
00:12:55,420 --> 00:12:58,090
stack behalve misschien
een regel code.

257
00:12:58,090 --> 00:13:01,190
En dat een regel code
bepaalt de functionaliteit.

258
00:13:01,190 --> 00:13:03,900
En het is echt onderscheidt
een wachtrij van een stapel.

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

260
00:13:18,510 --> 00:13:22,010
>> Iedereen wil een gooi te nemen
uit te leggen waarom je hebt

261
00:13:22,010 --> 00:13:24,980
kreeg deze ingewikkelde ding hier?

262
00:13:24,980 --> 00:13:27,845
We zien de terugkeer van onze
prachtige vriend modulus.

263
00:13:27,845 --> 00:13:31,020
Zoals jullie binnenkort zullen komen
te herkennen in de programmering,

264
00:13:31,020 --> 00:13:34,910
bijna elke keer als u iets nodig hebt
te wikkelen rond iets,

265
00:13:34,910 --> 00:13:36,850
modulus gaat om de manier te doen.

266
00:13:36,850 --> 00:13:40,510
Dus weten dat doet iedereen wil
om te proberen uit te leggen dat de regel code?

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

268
00:13:44,060 --> 00:13:47,507
Ja, alle antwoorden zijn
geaccepteerde en welkom.

269
00:13:47,507 --> 00:13:48,840
Publiek: Heb je het tegen mij?

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

271
00:13:49,506 --> 00:13:56,200
PUBLIEK: Oh, nee sorry.

272
00:13:56,200 --> 00:14:00,250
ANDI Peng: OK, dus laten we
lopen door deze code.

273
00:14:00,250 --> 00:14:03,642
Dus als je probeert om
iets toe te voegen aan een wachtrij,

274
00:14:03,642 --> 00:14:08,510
in de mooie geval dat het hoofd gebeurt
om hier te zijn, het is erg makkelijk voor ons

275
00:14:08,510 --> 00:14:10,960
om gewoon naar het einde
Steek iets, toch?

276
00:14:10,960 --> 00:14:14,690
Maar het hele punt van een wachtrij is
dat het hoofd daadwerkelijk kan dynamisch

277
00:14:14,690 --> 00:14:17,280
veranderen afhankelijk van waar we
wil het begin van onze q te zijn,

278
00:14:17,280 --> 00:14:19,880
en als zodanig, de staart
Ook gaat veranderen.

279
00:14:19,880 --> 00:14:31,100
>> En dus stellen dat dit niet was
wachtrij, maar dit was de wachtrij.

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

281
00:14:37,900 --> 00:14:39,330
Laten we zeggen dat het hoofd is hier.

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

283
00:14:54,900 --> 00:14:56,980
Laten we zeggen dat onze wachtrij leek dit.

284
00:14:56,980 --> 00:15:00,190
Als we wilden verplaatsen, waar
het begin van de lijn is,

285
00:15:00,190 --> 00:15:03,400
laten we zeggen dat we verschoven hoofd
op deze manier en maten hier.

286
00:15:03,400 --> 00:15:07,100
>> Nu willen we iets aan toe te voegen
deze wachtrij, maar zoals jullie kunnen zien,

287
00:15:07,100 --> 00:15:11,150
het is niet zo simpel als gewoon
toevoegen wat is na de grootte

288
00:15:11,150 --> 00:15:13,630
want dan uit lopen we
grenzen van onze huidige array.

289
00:15:13,630 --> 00:15:16,190
Waar we willen echt toe is hier.

290
00:15:16,190 --> 00:15:18,610
Dat is het mooie van een wachtrij
is dat voor ons, visueel is

291
00:15:18,610 --> 00:15:22,380
lijkt alsof de lijn gaat als volgt,
maar wanneer opgeslagen in een gegevensstructuur,

292
00:15:22,380 --> 00:15:29,370
ze geven het als als een cyclus.

293
00:15:29,370 --> 00:15:32,360
Het wraps soort rond
aan de achterkant dezelfde manier

294
00:15:32,360 --> 00:15:34,780
dat een lijn kan ook wrap
rond, afhankelijk van waar u

295
00:15:34,780 --> 00:15:36,279
willen begin van de regel te zijn.

296
00:15:36,279 --> 00:15:38,630
En dus als we een
kijk hier naar beneden, laten we

297
00:15:38,630 --> 00:15:40,880
zeggen dat we wilde een te creëren
functie genaamd enqueue.

298
00:15:40,880 --> 00:15:43,980
We wilden int n toe te voegen in die q.

299
00:15:43,980 --> 00:15:49,250
Als q.size q-- we noemen dat onze gegevens
structure-- als onze queue.size niet

300
00:15:49,250 --> 00:15:52,520
gelijk aan de capaciteit of
het is minder dan de capaciteit,

301
00:15:52,520 --> 00:15:55,120
q.strings is de matrix in onze q.

302
00:15:55,120 --> 00:15:58,380
We gaan om te stellen
dat gelijk is aan q.heads,

303
00:15:58,380 --> 00:16:02,730
dat is hier, plus q.size
modulus van de capaciteit, die

304
00:16:02,730 --> 00:16:04,290
wrap ons terug hier in de buurt.

305
00:16:04,290 --> 00:16:08,040
>> In dit voorbeeld, index
van het hoofd is 1, toch?

306
00:16:08,040 --> 00:16:11,480
De index van grootte 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Dus we kunnen 1 plus 4 modulus doen
door onze capaciteit dat is 5.

308
00:16:19,500 --> 00:16:20,920
Wat betekent dat ons?

309
00:16:20,920 --> 00:16:23,270
Wat is de index die
komt uit deze?

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

311
00:16:24,080 --> 00:16:27,870
>> ANDI Peng: 0, die
gebeurt om hier te zijn,

312
00:16:27,870 --> 00:16:30,640
en dus willen we in staat zijn
te voegen in hier.

313
00:16:30,640 --> 00:16:34,730
En dus deze vergelijking hier soort
van alleen werkt met alle nummers

314
00:16:34,730 --> 00:16:36,750
afhankelijk van waar je
hoofd en uw maat zijn.

315
00:16:36,750 --> 00:16:38,541
Als je weet wat die
dingen zijn, weet je

316
00:16:38,541 --> 00:16:43,170
precies waar u wilt invoegen
wat is na uw wachtrij.

317
00:16:43,170 --> 00:16:44,640
Heeft dat zin om iedereen?

318
00:16:44,640 --> 00:16:48,560
>> Ik weet dat soort van een brein
teaser vooral omdat dit

319
00:16:48,560 --> 00:16:50,512
kwam in de nasleep van uw quiz.

320
00:16:50,512 --> 00:16:52,220
Maar hopelijk iedereen
nu kan begrijpen

321
00:16:52,220 --> 00:16:57,800
waarom deze oplossing of dit
functie is de manier waarop het is.

322
00:16:57,800 --> 00:16:59,840
Iedereen die een beetje onduidelijk over dat?

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
>> En nu, als je
wilde dequeue deze

327
00:17:09,970 --> 00:17:15,240
is waar ons hoofd zou verschuiven
want als we dequeue,

328
00:17:15,240 --> 00:17:17,030
we niet opstijgen het einde van de q.

329
00:17:17,030 --> 00:17:19,130
We willen het hoofd af te nemen, toch?

330
00:17:19,130 --> 00:17:24,260
Dus als gevolg, is het hoofd gaat veranderen,
en dat is de reden waarom als je enqueue,

331
00:17:24,260 --> 00:17:26,800
je hebt om bij te houden
waar uw hoofd en uw maat

332
00:17:26,800 --> 00:17:29,450
zijn te kunnen voegen
in de juiste positie.

333
00:17:29,450 --> 00:17:32,740
>> En dus als je dequeue,
Ik Pseudocode het ook uit.

334
00:17:32,740 --> 00:17:35,480
Voel je vrij om als je wilt
om te proberen codering dit uit.

335
00:17:35,480 --> 00:17:36,980
U wilt het hoofd te bewegen, toch?

336
00:17:36,980 --> 00:17:39,320
Als ik wilde dequeue, I
zou het hoofd bewegen over.

337
00:17:39,320 --> 00:17:40,800
Dit zou het hoofd zijn.

338
00:17:40,800 --> 00:17:45,617
>> En onze huidige omvang zou
aftrekken omdat we niet langer

339
00:17:45,617 --> 00:17:46,950
vier elementen in de array.

340
00:17:46,950 --> 00:17:51,370
We hebben slechts drie, en dan willen we
terug welke binnen opgeslagen

341
00:17:51,370 --> 00:17:56,260
van het hoofd omdat we willen deze nemen
waarde uit dus sterk op de stack.

342
00:17:56,260 --> 00:17:58,010
Gewoon je neemt
vanuit een andere plaats,

343
00:17:58,010 --> 00:18:01,770
en je moet je wijzer toewijzen
verschillende plaats als gevolg.

344
00:18:01,770 --> 00:18:03,890
Logisch, iedereen volgen?

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

346
00:18:05,690 --> 00:18:10,156
>> OK, dus we gaan een beetje praten
meer in de diepte over gelinkte lijsten

347
00:18:10,156 --> 00:18:13,280
omdat ze zeer, zeer waardevol zal zijn
voor u in de loop van deze week

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

349
00:18:14,964 --> 00:18:17,130
Gelinkte lijsten, zoals jullie
kan herinneren, alles wat ze zijn

350
00:18:17,130 --> 00:18:22,570
knooppunten knooppunten die bepaalde
waarden van zowel een waarde en een pointer

351
00:18:22,570 --> 00:18:26,290
die met elkaar zijn verbonden
door die pointers.

352
00:18:26,290 --> 00:18:29,880
En zo de structuur van hoe
creëren we een knooppunt hier is dat we

353
00:18:29,880 --> 00:18:33,569
hebben int n, die ongeacht
de waarde in een winkel of tekenreeks n

354
00:18:33,569 --> 00:18:35,610
of wat je wilt
noemen, de char ster n.

355
00:18:35,610 --> 00:18:41,482
Struct knooppunt ster, die de wijzer
dat u wilt hebben in elk knooppunt,

356
00:18:41,482 --> 00:18:43,690
je gaat die moeten
wijzer punt in de richting van de volgende.

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

358
00:18:48,207 --> 00:18:50,040
Je zult het hoofd hebben
van een gekoppelde lijst die is

359
00:18:50,040 --> 00:18:53,140
zal wijzen op de rest van
de waarden enzovoorts enzovoorts

360
00:18:53,140 --> 00:18:55,290
totdat je uiteindelijk het einde bereikt.

361
00:18:55,290 --> 00:18:58,040
En dit laatste knooppunt is gewoon
naar een pointer hebben.

362
00:18:58,040 --> 00:18:59,952
Het gaat om te wijzen op
null, en dat is wanneer

363
00:18:59,952 --> 00:19:01,910
je weet dat je hebt geraakt het
einde van uw gelinkte lijst

364
00:19:01,910 --> 00:19:04,076
is wanneer uw laatste pointer
niet wijzen op iets.

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

366
00:19:06,670 --> 00:19:10,990
>> Dus gaan we een beetje meer in te gaan
diepgaande over hoe men zou eventueel

367
00:19:10,990 --> 00:19:12,400
zoek een gekoppelde lijst.

368
00:19:12,400 --> 00:19:15,460
Onthoud wat zijn enkele van de
nadelen van de gekoppelde lijsten

369
00:19:15,460 --> 00:19:19,340
verzen een serie over zoekopdrachten.

370
00:19:19,340 --> 00:19:22,565
Een array kun je binair zoeken, maar
waarom kan je niet doen in een gekoppelde lijst?

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

372
00:19:26,834 --> 00:19:30,320
>> Publiek: Omdat ze allemaal zijn aangesloten,
maar je weet niet precies weten waar

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

374
00:19:31,330 --> 00:19:34,600
>> ANDI Peng: Ja, precies zo onthouden
dat de schittering van een array

375
00:19:34,600 --> 00:19:37,190
was het feit dat we hadden
willekeurig toegankelijk geheugen waarin

376
00:19:37,190 --> 00:19:41,580
als ik wilde de waarde van de index
zes, ik kon alleen maar zeggen index zes,

377
00:19:41,580 --> 00:19:42,407
geef mij die waarde.

378
00:19:42,407 --> 00:19:45,240
En dat komt omdat arrays zijn gesorteerd
in een aaneengesloten ruimte van het geheugen

379
00:19:45,240 --> 00:19:48,020
op één plek, terwijl
soort gekoppelde lijsten

380
00:19:48,020 --> 00:19:52,820
willekeurig afgewisseld rondom,
en de enige manier waarop je kunt er een te vinden

381
00:19:52,820 --> 00:19:56,890
is door middel van een pointer die je vertelt
het adres van de plaats waar die volgende knooppunt.

382
00:19:56,890 --> 00:20:00,290
>> Dus als gevolg dat de enige manier
om door middel van een gekoppelde lijst

383
00:20:00,290 --> 00:20:01,560
is lineair zoeken.

384
00:20:01,560 --> 00:20:05,890
Omdat ik niet precies weet waar
12 waarde in de gekoppelde lijst,

385
00:20:05,890 --> 00:20:08,780
Ik moet het geheel doorkruisen
van die gelinkte lijst één

386
00:20:08,780 --> 00:20:12,450
één van de kop met het eerste knooppunt,
het tweede knooppunt aan het derde knooppunt

387
00:20:12,450 --> 00:20:17,690
helemaal naar beneden totdat ik eindelijk
waar dat knooppunt Ik ben op zoek naar is.

388
00:20:17,690 --> 00:20:22,110
En dus in die zin, zoeken
op een gekoppelde lijst is altijd n.

389
00:20:22,110 --> 00:20:23,040
Het is altijd n.

390
00:20:23,040 --> 00:20:25,690
Het is altijd in lineaire tijd.

391
00:20:25,690 --> 00:20:28,470
>> En dus is de code in die
implementeren we dit, en dit

392
00:20:28,470 --> 00:20:32,620
is een beetje nieuw voor jullie, omdat je
jongens hebben niet echt over gesproken of ooit

393
00:20:32,620 --> 00:20:35,000
gezien wijzers in hoe
zoeken door middel van pointers,

394
00:20:35,000 --> 00:20:37,670
dus we zullen doorkruisen
dit zeer, zeer langzaam.

395
00:20:37,670 --> 00:20:40,200
Dus bool zoeken, rechts,
Laten we veronderstellen we willen

396
00:20:40,200 --> 00:20:42,820
een functie genaamd creëren
search dat true retourneert

397
00:20:42,820 --> 00:20:46,820
als u een waarde in de gekoppelde gevonden
lijst, en keert anders false.

398
00:20:46,820 --> 00:20:50,030
Knooppunt ster lijst
momenteel alleen de pointer

399
00:20:50,030 --> 00:20:52,960
naar het eerste item in de gekoppelde lijst.

400
00:20:52,960 --> 00:20:56,700
int n is de waarde die je
zoekt in die lijst.

401
00:20:56,700 --> 00:20:58,770
>> Dus knooppunt ster pointer gelijk lijst.

402
00:20:58,770 --> 00:21:00,970
Dat betekent dat we het instellen bent
en creëren van een pointer

403
00:21:00,970 --> 00:21:03,592
om die eerste knooppunt in de lijst.

404
00:21:03,592 --> 00:21:04,300
Iedereen met mij?

405
00:21:04,300 --> 00:21:06,530
Dus als we waren te gaan
hier terug, zou ik

406
00:21:06,530 --> 00:21:13,850
geïnitialiseerd een pointer die naar
het hoofd van welke die lijst is.

407
00:21:13,850 --> 00:21:18,600
>> En dan als je hier beneden,
terwijl de pointer is niet gelijk aan nul,

408
00:21:18,600 --> 00:21:22,160
dus dat is de lus waarin we
zal vervolgens worden doorkruisen

409
00:21:22,160 --> 00:21:25,940
de rest van onze lijst omdat wat
gebeurt er als aanwijzer gelijk aan nul?

410
00:21:25,940 --> 00:21:27,550
We weten dat we have--

411
00:21:27,550 --> 00:21:28,450
>> PUBLIEK: [onverstaanbaar]

412
00:21:28,450 --> 00:21:31,491
>> ANDI Peng: Precies, dus we weten dat
we hebben het einde van de lijst bereikt, toch?

413
00:21:31,491 --> 00:21:34,470
Als je hier terug te gaan, elk knooppunt
moeten wijzen naar een ander knooppunt

414
00:21:34,470 --> 00:21:36,550
enzovoort
totdat je uiteindelijk hit

415
00:21:36,550 --> 00:21:41,589
de staart van uw gelinkte lijst,
waarbij een pointer heeft die net

416
00:21:41,589 --> 00:21:43,130
niet ergens anders dan geen wijzen.

417
00:21:43,130 --> 00:21:47,510
En dus je eigenlijk weet dat
de lijst is er nog steeds

418
00:21:47,510 --> 00:21:50,900
totdat wijzer is niet gelijk
null, want zodra het is gelijk aan nul,

419
00:21:50,900 --> 00:21:53,310
je weet dat er geen spullen meer.

420
00:21:53,310 --> 00:21:56,930
>> Dus dat is de lus waarin we
gaan naar de werkelijke zoeken hebben.

421
00:21:56,930 --> 00:22:01,690
En als de pointer-- zie je
dat soort pijl functie daar?

422
00:22:01,690 --> 00:22:06,930
Dus als wijzer punten n, indien
de pointer aan n gelijk gelijk is aan n,

423
00:22:06,930 --> 00:22:09,180
dat betekent dat als
de aanwijzer dat je

424
00:22:09,180 --> 00:22:13,420
zoekt op het einde van elke
node feite gelijk aan de waarde

425
00:22:13,420 --> 00:22:15,990
je zoekt, dan is
u wilt echte terugkeren.

426
00:22:15,990 --> 00:22:19,280
Dus eigenlijk, als je op een knooppunt dat
heeft de waarde die u zoekt,

427
00:22:19,280 --> 00:22:23,550
weet je dat je bent geweest
in staat om succesvol te zoeken.

428
00:22:23,550 --> 00:22:27,150
>> Anders, u wilt instellen
aanwijzer naar het volgende knooppunt.

429
00:22:27,150 --> 00:22:28,850
Dat is wat die lijn hier doet.

430
00:22:28,850 --> 00:22:31,750
Wijzer gelijk wijzer naast.

431
00:22:31,750 --> 00:22:33,360
Iedereen zien hoe dat werkt?

432
00:22:33,360 --> 00:22:36,580
>> En in wezen je gaat gewoon
doorkruisen het geheel van de lijst,

433
00:22:36,580 --> 00:22:41,920
resetten van uw wijzer telkens tot
je uiteindelijk raakte het einde van de lijst.

434
00:22:41,920 --> 00:22:45,030
En je weet dat er geen
meer knooppunten te zoeken door,

435
00:22:45,030 --> 00:22:47,999
en dan kun je return false
omdat je weet dat, oh, nou ja,

436
00:22:47,999 --> 00:22:50,540
Als ik in staat om te zoeken geweest
door het geheel van de lijst.

437
00:22:50,540 --> 00:22:54,530
Als in dit voorbeeld, als ik wilde
te kijken naar de waarde van 10,

438
00:22:54,530 --> 00:22:57,250
en ik begin aan het hoofd, en
Ik zoek helemaal naar beneden,

439
00:22:57,250 --> 00:23:00,550
en ik kreeg uiteindelijk tot dit, dat
een pointer die wijst op null,

440
00:23:00,550 --> 00:23:04,415
Ik weet dat, onzin, ik denk dat 10 is niet in
deze lijst want ik kon het niet vinden.

441
00:23:04,415 --> 00:23:06,520
En ik ben aan het eind van de lijst.

442
00:23:06,520 --> 00:23:11,040
En in dat geval weet je
Ik ga return false.

443
00:23:11,040 --> 00:23:12,900
>> Laat dat weken in voor een klein beetje.

444
00:23:12,900 --> 00:23:17,350
Dit zal vrij zijn
belangrijk voor uw PSET.

445
00:23:17,350 --> 00:23:21,140
De logica is zeer eenvoudig, misschien
syntactisch gewoon de uitvoering ervan.

446
00:23:21,140 --> 00:23:23,365
Jullie willen maken
zeker van zijn dat je het begrijpt.

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

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

449
00:23:27,650 --> 00:23:32,560
>> OK, dus hoe zouden we
invoegen van knooppunten, rechts,

450
00:23:32,560 --> 00:23:35,380
in een lijst, omdat onthouden
wat zijn de wat van de voordelen

451
00:23:35,380 --> 00:23:39,230
van het hebben van een gekoppelde lijst versus
een reeks in termen van opslag?

452
00:23:39,230 --> 00:23:41,110
>> Publiek: Het is dynamisch,
zodat het makkelijker to--

453
00:23:41,110 --> 00:23:43,180
>> ANDI Peng: Precies,
dus het is dynamisch, die

454
00:23:43,180 --> 00:23:46,880
betekent dat het kan uitzetten en krimpen
afhankelijk van de behoeften van de gebruiker.

455
00:23:46,880 --> 00:23:56,570
En ja, in deze zin, we hoeven niet
onnodige geheugen te verspillen, omdat ik

456
00:23:56,570 --> 00:24:00,850
als ik weet niet hoeveel waarden Ik wil
op te slaan, heeft het geen zin voor mij

457
00:24:00,850 --> 00:24:04,310
om een ​​array te creëren, omdat
als ik wil 10 waarden op te slaan

458
00:24:04,310 --> 00:24:08,380
en ik maak een serie van 1000, dat is
een hoop verspilde geheugen toegewezen.

459
00:24:08,380 --> 00:24:11,180
Daarom willen we gebruik maken van een gekoppelde
lijst kunnen dynamisch

460
00:24:11,180 --> 00:24:13,860
wijzigen of te krimpen onze omvang.

461
00:24:13,860 --> 00:24:17,040
>> En dus dat maakt het inbrengen
een beetje meer ingewikkeld.

462
00:24:17,040 --> 00:24:20,810
Aangezien wij kunnen niet willekeurig toegang elementen
de manier waarop we een array zou van.

463
00:24:20,810 --> 00:24:24,270
Als ik wil een element in te voegen
in de zevende index

464
00:24:24,270 --> 00:24:26,930
Ik kan het gewoon invoegen
in de zevende index.

465
00:24:26,930 --> 00:24:30,020
Op een gekoppelde lijst, het niet
vrij werk zo gemakkelijk,

466
00:24:30,020 --> 00:24:34,947
en dus als we wilden voegen
het hier in de gekoppelde lijst,

467
00:24:34,947 --> 00:24:36,280
visueel, het is heel gemakkelijk om te zien.

468
00:24:36,280 --> 00:24:39,363
We willen alleen maar om het daar in te voegen,
aan het begin van de lijst,

469
00:24:39,363 --> 00:24:40,840
direct na het hoofd.

470
00:24:40,840 --> 00:24:44,579
>> Maar de manier waarop we moeten toewijzen
de wijzers is een beetje ingewikkeld

471
00:24:44,579 --> 00:24:47,620
of, logischerwijs, is het zinvol, maar
wilt u ervoor zorgen dat je het hebt

472
00:24:47,620 --> 00:24:50,250
helemaal naar beneden, omdat
het laatste wat je wilt

473
00:24:50,250 --> 00:24:52,990
is een pointer het toewijzen
manier dat we hier doen.

474
00:24:52,990 --> 00:24:58,170
Als u de dereferentie
pointer van kop tot 1,

475
00:24:58,170 --> 00:25:01,086
dan ineens de
rest van uw gelinkte lijst

476
00:25:01,086 --> 00:25:04,680
is verloren omdat je eigenlijk niet
creëerde een tijdelijk iets.

477
00:25:04,680 --> 00:25:06,220
Dat wees naar de 2.

478
00:25:06,220 --> 00:25:10,080
Als u de aanwijzer, dan is het toewijzen
rest van de lijst is totaal verloren.

479
00:25:10,080 --> 00:25:13,310
Dus je wilt zijn
heel, heel voorzichtig hier

480
00:25:13,310 --> 00:25:17,010
naar de eerste wijzen de
wijzer uit wat je

481
00:25:17,010 --> 00:25:20,150
wilt invoegen in waar
je wilt, en dan moet je

482
00:25:20,150 --> 00:25:22,710
kan dereference de rest van de lijst.

483
00:25:22,710 --> 00:25:25,250
>> Dus dit geldt voor overal
je probeert in te voegen in.

484
00:25:25,250 --> 00:25:27,520
Als u wilt invoegen op de
hoofd, als je hier wilt beantwoorden,

485
00:25:27,520 --> 00:25:29,455
Als u wilt invoegen op
het einde, goed, het einde I

486
00:25:29,455 --> 00:25:30,910
denk dat je zou gewoon
hebben geen wijzer, maar u

487
00:25:30,910 --> 00:25:33,830
willen ervoor zorgen dat je niet
verliest de rest van de lijst.

488
00:25:33,830 --> 00:25:36,640
Je wilt altijd om ervoor te zorgen
uw nieuwe knooppunt wijst

489
00:25:36,640 --> 00:25:39,330
in de richting van wat je
wilt invoegen in,

490
00:25:39,330 --> 00:25:42,170
en dan kun je voeg de chaining op.

491
00:25:42,170 --> 00:25:43,330
Iedereen duidelijk?

492
00:25:43,330 --> 00:25:45,427
>> Dit gaat worden
een van de echte problemen.

493
00:25:45,427 --> 00:25:48,010
Een van de meest belangrijke kwesties
je gaat op je PSET

494
00:25:48,010 --> 00:25:51,340
is dat je gaat proberen te creëren
een gelinkte lijst en insert dingen

495
00:25:51,340 --> 00:25:53,340
maar dan gewoon verliest de
rest van uw gekoppelde lijst.

496
00:25:53,340 --> 00:25:54,900
En je gaat te zijn zoals ik
weet niet waarom dit gebeurt?

497
00:25:54,900 --> 00:25:58,040
En het is een pijn om te gaan door
en doorzoeken van uw pointers.

498
00:25:58,040 --> 00:26:02,100
>> En ik garandeer je op deze PSET,
schrijven en tekenen deze knooppunten uit

499
00:26:02,100 --> 00:26:03,344
zal zeer, zeer behulpzaam.

500
00:26:03,344 --> 00:26:06,010
Dus je kunt helemaal bijhouden
van waar al je pointers zijn,

501
00:26:06,010 --> 00:26:08,540
wat er fout gaat,
waarbij alle knopen,

502
00:26:08,540 --> 00:26:12,660
wat je moet doen om toegang te krijgen of
invoegen of verwijderen of een van hen.

503
00:26:12,660 --> 00:26:14,550
Iedereen goed met dat?

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

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

506
00:26:19,300 --> 00:26:22,600
>> Dus als we wilden kijken naar de code?

507
00:26:22,600 --> 00:26:24,470
Oh, ik weet niet of we
kan the-- OK zien, dus

508
00:26:24,470 --> 00:26:27,940
aan de top al is het een functie
genoemd insert waar we willen

509
00:26:27,940 --> 00:26:31,365
int n om in te voegen in de gekoppelde lijst.

510
00:26:31,365 --> 00:26:32,740
We gaan lopen door dit.

511
00:26:32,740 --> 00:26:34,770
Het is een stuk van de code, een heleboel nieuwe syntaxis.

512
00:26:34,770 --> 00:26:36,220
We zullen OK.

513
00:26:36,220 --> 00:26:39,120
>> Dus op naar boven, wanneer
we willen iets maken

514
00:26:39,120 --> 00:26:42,380
wat hebben we nodig om te doen, vooral als je
wil het niet worden opgeslagen op de stapel

515
00:26:42,380 --> 00:26:43,920
maar in de heap?

516
00:26:43,920 --> 00:26:45,460
We gaan naar een malloc, toch?

517
00:26:45,460 --> 00:26:48,240
Dus we gaan naar een pointer te creëren.

518
00:26:48,240 --> 00:26:52,074
Knoop, wijzer, nieuwe gelijken
malloc het formaat van een knooppunt

519
00:26:52,074 --> 00:26:53,740
want we willen dat knooppunt te worden gemaakt.

520
00:26:53,740 --> 00:26:56,720
We willen dat de hoeveelheid
geheugen dat een knooppunt neemt

521
00:26:56,720 --> 00:26:59,300
toe te wijzen voor de
creatie van het nieuwe knooppunt.

522
00:26:59,300 --> 00:27:02,270
>> En dan gaan we controleren
zien of er nieuwe gelijken gelijk aan nul.

523
00:27:02,270 --> 00:27:03,370
Weet je nog wat we zeiden?

524
00:27:03,370 --> 00:27:06,470
Wat je malloc,
Wat moet je altijd doen?

525
00:27:06,470 --> 00:27:09,490
Je moet altijd controleren om te zien
ongeacht of dat is nul.

526
00:27:09,490 --> 00:27:13,620
>> Bijvoorbeeld, als uw besturingssysteem
systeem was helemaal vol,

527
00:27:13,620 --> 00:27:17,060
als je had geen meer geheugen aan
allen en je probeert te malloc,

528
00:27:17,060 --> 00:27:18,410
het zou null voor u terug.

529
00:27:18,410 --> 00:27:21,094
En dus als je probeert om het te gebruiken
toen het wees op null,

530
00:27:21,094 --> 00:27:23,260
je bent niet van plan om in staat
toegang tot die informatie.

531
00:27:23,260 --> 00:27:27,010
Dus als zodanig, wilden we ervoor
zeker van dat wanneer je mallocing,

532
00:27:27,010 --> 00:27:30,500
je bent altijd te controleren om te zien of
die herinnering aan u gegeven is null.

533
00:27:30,500 --> 00:27:33,670
En als het niet, dan kunnen we verhuizen
op met de rest van onze code.

534
00:27:33,670 --> 00:27:36,140
>> Dus we gaan
initialiseren van het nieuwe knooppunt.

535
00:27:36,140 --> 00:27:39,050
We gaan doen nieuwe n gelijk is aan n.

536
00:27:39,050 --> 00:27:42,390
En dan gaan we doen
set nieuwe de aanwijzer op nieuwe

537
00:27:42,390 --> 00:27:46,900
null want nu doen we niet
wil iets voor het te wijzen.

538
00:27:46,900 --> 00:27:48,755
We hebben geen idee waar
het gaat om u,

539
00:27:48,755 --> 00:27:50,630
en dan als we willen
plaatst u deze aan het hoofd,

540
00:27:50,630 --> 00:27:53,820
dan kunnen we toewijzen
de aanwijzer naar het hoofd.

541
00:27:53,820 --> 00:27:58,530
Heeft iedereen volgt de logica
waar dat gebeurt?

542
00:27:58,530 --> 00:28:02,502
>> Alles wat we doen is het creëren van een nieuw
knooppunt, het instellen van de wijzer op null,

543
00:28:02,502 --> 00:28:04,210
en dan opnieuw toewijzen
het aan de kop als we

544
00:28:04,210 --> 00:28:06,320
weten we willen voegen aan het hoofd.

545
00:28:06,320 --> 00:28:09,420
En dan de kop gaat
wijzen naar die nieuwe knooppunt.

546
00:28:09,420 --> 00:28:11,060
Iedereen OK met dat?

547
00:28:11,060 --> 00:28:12,380
>> Dus het is een proces van twee stappen.

548
00:28:12,380 --> 00:28:14,760
Je moet eerst toewijzen
wat u maakt.

549
00:28:14,760 --> 00:28:18,260
Stel dat aanwijzer naar de
referentie, en dan moet je

550
00:28:18,260 --> 00:28:21,400
kan soort dereferentie
de eerste pointer

551
00:28:21,400 --> 00:28:22,972
en richt deze naar het nieuwe knooppunt.

552
00:28:22,972 --> 00:28:25,680
Waar u het wilt invoegen,
die logica gaat om waar te houden.

553
00:28:25,680 --> 00:28:27,530
>> Het is net zoiets als het toekennen
tijdelijke variabelen.

554
00:28:27,530 --> 00:28:28,700
Vergeet niet, je hebt
om ervoor te zorgen dat u

555
00:28:28,700 --> 00:28:30,346
niet bijhouden als je ruilt niet verliezen.

556
00:28:30,346 --> 00:28:33,470
Wilt u ervoor zorgen dat u een
tijdelijke variabele die soort houdt

557
00:28:33,470 --> 00:28:35,620
spoor waar dat ding
wordt opgeslagen, zodat u

558
00:28:35,620 --> 00:28:41,190
geen waarde te verliezen in de loop
van zoals knoeien met het.

559
00:28:41,190 --> 00:28:42,710
>> OK, dus code zal hier zijn.

560
00:28:42,710 --> 00:28:45,020
Jullie een kijkje nemen na sectie.

561
00:28:45,020 --> 00:28:48,060
Het zal er zijn.

562
00:28:48,060 --> 00:28:50,280
>> Dus ik denk dat hoe werkt
deze verschillen als we wilden

563
00:28:50,280 --> 00:28:52,300
in te voegen in het midden of het einde?

564
00:28:52,300 --> 00:28:57,892
Heeft iemand een idee van wat de
pseudocode als logische referentie

565
00:28:57,892 --> 00:29:00,350
dat we zouden nemen als we wilden
om deze te plaatsen in het midden?

566
00:29:00,350 --> 00:29:03,391
Dus als we wilden het te voegen bij de
hoofd, alles wat we doen is het creëren van een nieuw knooppunt.

567
00:29:03,391 --> 00:29:06,311
We zetten de wijzer van dat
nieuw knooppunt aan wat het hoofd,

568
00:29:06,311 --> 00:29:08,310
en dan zetten we het hoofd
naar het nieuwe knooppunt, toch?

569
00:29:08,310 --> 00:29:11,560
Als we wilden om deze te plaatsen in het midden
van de lijst, wat zouden we moeten doen?

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

571
00:29:14,108 --> 00:29:16,110
>> PUBLIEK: het zou nog steeds
zijn een soortgelijk proces

572
00:29:16,110 --> 00:29:19,114
zoals het toekennen van pointer en
het toewijzen die pointer,

573
00:29:19,114 --> 00:29:20,530
maar we zouden hebben om er te vinden.

574
00:29:20,530 --> 00:29:23,560
>> ANDI Peng: Precies, dus precies
hetzelfde proces behalve dat je

575
00:29:23,560 --> 00:29:27,820
moeten waar precies lokaliseren u
wil dat de nieuwe aanwijzer in te gaan,

576
00:29:27,820 --> 00:29:44,790
dus als ik wil invoegen in
het midden van gekoppelde list-- OK,

577
00:29:44,790 --> 00:29:46,370
laten we zeggen dat is onze gelinkte lijst.

578
00:29:46,370 --> 00:29:49,500
Als we willen het hier in te voegen,
we gaan naar een nieuw knooppunt te maken.

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

580
00:29:50,520 --> 00:29:52,220
We gaan naar een nieuw knooppunt te maken.

581
00:29:52,220 --> 00:29:55,940
We gaan naar het toewijzen
wijzer van dit knooppunt hier.

582
00:29:55,940 --> 00:29:58,335
>> Maar het probleem dat afwijkt
waar het hoofd is

583
00:29:58,335 --> 00:30:00,490
is dat we precies wisten
waarbij het hoofd is.

584
00:30:00,490 --> 00:30:01,930
Het was vlak bij het eerste, toch?

585
00:30:01,930 --> 00:30:04,870
Maar hier hebben we te houden
van waar we deze in.

586
00:30:04,870 --> 00:30:07,930
Als we het plaatsen van onze
knooppunt hier, we hebben

587
00:30:07,930 --> 00:30:12,270
om ervoor te zorgen dat de
men vóór dit knooppunt

588
00:30:12,270 --> 00:30:14,172
is degene die de wijzer opnieuw toewijst.

589
00:30:14,172 --> 00:30:16,380
Dus dan moet je soort
bijhouden van twee dingen.

590
00:30:16,380 --> 00:30:19,420
Als je bijhouden waar dit houden
knooppunt momenteel invoegen in.

591
00:30:19,420 --> 00:30:23,280
Je moet ook bijhouden waar houden
de vorige knooppunt dat u zoekt op

592
00:30:23,280 --> 00:30:24,340
was er ook.

593
00:30:24,340 --> 00:30:25,830
Iedereen goed met dat?

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

595
00:30:26,500 --> 00:30:28,000
>> Hoe zit het invoegen in het einde?

596
00:30:28,000 --> 00:30:34,220
Als ik wilde het toevoegen hier-- als ik wilde
een nieuw knooppunt toe te voegen aan het eind van een lijst,

597
00:30:34,220 --> 00:30:37,009
hoe zou ik over dat doen?

598
00:30:37,009 --> 00:30:39,300
Publiek: Dus op dit moment, de
laatste's wees op null.

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

600
00:30:40,960 --> 00:30:43,560
Precies, dus dit
momenteel is gericht weten,

601
00:30:43,560 --> 00:30:46,720
en zo denk ik, in deze zin, het is
zeer eenvoudig toe te voegen aan het einde van de lijst.

602
00:30:46,720 --> 00:30:51,810
Alles wat je hoeft te doen is het instellen
gelijk aan nul en dan boom.

603
00:30:51,810 --> 00:30:53,070
Daar, zeer eenvoudig.

604
00:30:53,070 --> 00:30:53,960
Erg makkelijk.

605
00:30:53,960 --> 00:30:56,430
>> Zeer vergelijkbaar met de
hoofd, maar logischerwijs u

606
00:30:56,430 --> 00:30:59,690
willen ervoor zorgen dat de stappen
neemt u in de richting van een van dit te doen,

607
00:30:59,690 --> 00:31:01,500
je volgt samen.

608
00:31:01,500 --> 00:31:04,420
Het is heel gemakkelijk om, in het midden
van je code, verstrikt raken op,

609
00:31:04,420 --> 00:31:05,671
oh, ik heb zo veel pointers.

610
00:31:05,671 --> 00:31:07,461
Ik weet niet waar
niets wijst.

611
00:31:07,461 --> 00:31:09,170
Ik weet niet eens weten welke knoop ik ben op.

612
00:31:09,170 --> 00:31:11,490
Wat is er aan de hand?

613
00:31:11,490 --> 00:31:13,620
>> Ontspannen, te kalmeren, haal diep adem.

614
00:31:13,620 --> 00:31:15,530
Trek uw gekoppelde lijst.

615
00:31:15,530 --> 00:31:18,800
Als je zegt, ik weet waar precies
Ik moet dit in te voegen in

616
00:31:18,800 --> 00:31:22,970
en ik weet precies hoe mijn toewijzen
pointers, veel, veel gemakkelijker om foto

617
00:31:22,970 --> 00:31:27,200
out-- veel, veel makkelijker om niet
verdwalen in de bugs van uw code.

618
00:31:27,200 --> 00:31:29,410
Iedereen OK met dat?

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

620
00:31:31,380 --> 00:31:35,120
>> Dus ik denk dat een concept dat we niet
echt over gesproken vóór nu,

621
00:31:35,120 --> 00:31:38,131
en ik denk dat je waarschijnlijk
zal niet tegenkomen veel yet--

622
00:31:38,131 --> 00:31:40,880
het is een soort van een geavanceerde concept--
is dat we eigenlijk een data

623
00:31:40,880 --> 00:31:43,900
structuur heet een dubbel gelinkte lijst.

624
00:31:43,900 --> 00:31:46,390
Dus zoals jullie kunnen zien,
alles wat we doen is het creëren van

625
00:31:46,390 --> 00:31:50,400
een werkelijke waarde, een extra
aanwijzer op elk van onze knooppunten

626
00:31:50,400 --> 00:31:52,660
die wijst ook naar het vorige knooppunt.

627
00:31:52,660 --> 00:31:58,170
Dus niet alleen hebben we onze
nodes verwijzen naar de volgende.

628
00:31:58,170 --> 00:32:01,430
Ze wijzen ook op de vorige.

629
00:32:01,430 --> 00:32:04,310
Ik ga om te negeren deze twee nu.

630
00:32:04,310 --> 00:32:06,740
>> Dus dan heb je een keten
dat kan in beide richtingen bewegen,

631
00:32:06,740 --> 00:32:09,630
en dan is het een stuk makkelijker
logisch volgen langs.

632
00:32:09,630 --> 00:32:11,896
Zoals hier, in plaats van
het bijhouden van, oh, ik

633
00:32:11,896 --> 00:32:14,520
moet weten dat dit knooppunt
degene die ik moet toewijzen,

634
00:32:14,520 --> 00:32:17,532
Ik kan gewoon gaan hier en
trek gewoon de vorige.

635
00:32:17,532 --> 00:32:19,490
Dan weet ik precies waar
dat is, en dan moet je

636
00:32:19,490 --> 00:32:21,130
hoeft de traverse
onderdelen van de gekoppelde lijst.

637
00:32:21,130 --> 00:32:22,180
Het is een beetje makkelijker.

638
00:32:22,180 --> 00:32:24,960
>> Maar als zodanig, dubbel u
de hoeveelheid pointers,

639
00:32:24,960 --> 00:32:26,960
Dat is het dubbele van de hoeveelheid geheugen.

640
00:32:26,960 --> 00:32:28,950
Het is een stuk van de aanwijzingen bij te houden.

641
00:32:28,950 --> 00:32:32,140
Het is een beetje ingewikkelder, maar het is
een beetje gebruiksvriendelijker afhankelijk

642
00:32:32,140 --> 00:32:34,080
van wat je probeert te bereiken.

643
00:32:34,080 --> 00:32:36,910
>> Dus dit soort gegevens
structuur volledig bestaat,

644
00:32:36,910 --> 00:32:40,280
de structuur is het heel erg
eenvoudige behalve alles wat je hebt met is,

645
00:32:40,280 --> 00:32:43,850
in plaats van alleen een pointer naar de volgende,
je moet ook een verwijzing naar de vorige.

646
00:32:43,850 --> 00:32:45,940
Dat is alles wat het verschil was.

647
00:32:45,940 --> 00:32:47,740
Iedereen goed met dat?

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

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

650
00:32:50,940 --> 00:32:53,280
>> Oke, dus nu ben ik
echt waarschijnlijk te besteden

651
00:32:53,280 --> 00:32:56,870
zoals 15 tot 20 minuten of bulk
van de rest van de tijd in sectie

652
00:32:56,870 --> 00:32:58,360
over hash tabellen.

653
00:32:58,360 --> 00:33:02,590
Hoeveel van jullie
pset5 spec hebben gelezen?

654
00:33:02,590 --> 00:33:03,620
Oké, goed.

655
00:33:03,620 --> 00:33:06,160
Dat is hoger dan de 50% van normaal.

656
00:33:06,160 --> 00:33:07,560
Het is ok.

657
00:33:07,560 --> 00:33:10,345
>> Dus zoals jullie zullen zien,
je uitdaging in pset5

658
00:33:10,345 --> 00:33:16,790
zal een woordenboek implementeren
waar je laadt meer dan 140.000 woorden

659
00:33:16,790 --> 00:33:20,610
dat wij u en spellingcontrole
tegen alle tekst.

660
00:33:20,610 --> 00:33:22,580
Wij geven u willekeurige
stukken literatuur.

661
00:33:22,580 --> 00:33:23,520
Wij geven je de Odyssee.

662
00:33:23,520 --> 00:33:24,561
Wij geven je de Ilias.

663
00:33:24,561 --> 00:33:26,350
Wij geven je Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> En uw uitdaging
zal zijn om controle te spellen

665
00:33:28,220 --> 00:33:31,760
elk woord in alle
van deze woordenboeken

666
00:33:31,760 --> 00:33:34,960
wezen met onze spellingcontrole.

667
00:33:34,960 --> 00:33:38,620
En dus is er een paar onderdelen
van het creëren van deze PSET,

668
00:33:38,620 --> 00:33:41,970
eerst je wilt zijn
in staat om daadwerkelijk te laden

669
00:33:41,970 --> 00:33:43,970
alle woorden in uw
woordenboek, en dan moet je

670
00:33:43,970 --> 00:33:45,530
willen in staat zijn om
spellingcontrole allemaal.

671
00:33:45,530 --> 00:33:48,780
En dus als zodanig, je gaat te eisen
een gegevensstructuur die deze snel kan doen

672
00:33:48,780 --> 00:33:50,790
en efficiënt en dynamisch.

673
00:33:50,790 --> 00:33:52,900
>> Dus ik veronderstel dat de makkelijkste
manier om dit te doen, moet je

674
00:33:52,900 --> 00:33:55,010
zou waarschijnlijk een array, toch?

675
00:33:55,010 --> 00:33:58,910
De eenvoudigste manier van opslag is u
kan een reeks van 140.000 woorden te creëren

676
00:33:58,910 --> 00:34:03,400
en ze gewoon alle plaatsen daar en
Vervolgens doorkruisen ze door binaire zoekopdracht

677
00:34:03,400 --> 00:34:06,780
of door selecties of niet--
jammer dat is het sorteren.

678
00:34:06,780 --> 00:34:10,729
Je kunt ze sorteren en dan doorkruisen ze
door binaire zoeken of gewoon lineair zoeken

679
00:34:10,729 --> 00:34:13,730
en net laatste woorden, maar dat
neemt een enorme hoeveelheid geheugen,

680
00:34:13,730 --> 00:34:15,190
en het is niet erg efficiënt.

681
00:34:15,190 --> 00:34:18,350
>> En dus gaan we om te beginnen
over manieren om

682
00:34:18,350 --> 00:34:20,110
onze lopende tijd efficiënter.

683
00:34:20,110 --> 00:34:23,190
En ons doel is om
constante tijd waar

684
00:34:23,190 --> 00:34:25,810
het is bijna alsof arrays, waarbij
je hebt onmiddellijke toegang.

685
00:34:25,810 --> 00:34:28,560
Als ik op zoek naar iets,
Ik wil in staat zijn om gewoon,

686
00:34:28,560 --> 00:34:30,810
boom, vind het precies, en trek hem uit.

687
00:34:30,810 --> 00:34:34,100
Zo een structuur waarin
zullen we steeds zeer dicht

688
00:34:34,100 --> 00:34:37,569
in staat zijn om toegang te krijgen tot een constante
tijd, deze heilige graal

689
00:34:37,569 --> 00:34:41,370
in de programmering van de constante
tijd wordt een hash tabel.

690
00:34:41,370 --> 00:34:45,370
En dus David eerder vermeld de
[Onverstaanbaar] een beetje in collegezaal,

691
00:34:45,370 --> 00:34:49,100
maar we gaan echt
duiken in diep deze week

692
00:34:49,100 --> 00:34:51,780
op een stuk dat is over
hoe een hash-tabel werkt.

693
00:34:51,780 --> 00:34:53,949
>> Dus de wijze waarop een hash
tafel werken, bijvoorbeeld,

694
00:34:53,949 --> 00:35:00,230
als ik wilde een bos van woorden op te slaan, een
bos van woorden in het Engels,

695
00:35:00,230 --> 00:35:02,940
Ik kon in theorie zetten
banaan, appel, kiwi, mango, paar,

696
00:35:02,940 --> 00:35:04,980
en meloen allemaal op slechts een array.

697
00:35:04,980 --> 00:35:07,044
Ze konden allemaal passen en te vinden.

698
00:35:07,044 --> 00:35:09,210
Het zou een soort van pijn aan
doorzoeken en toegang,

699
00:35:09,210 --> 00:35:12,920
maar eenvoudiger manier hiervoor is
dat we eigenlijk kunnen creëren een structuur

700
00:35:12,920 --> 00:35:15,680
riep een hash tafel waar we hash.

701
00:35:15,680 --> 00:35:19,880
We lopen al onze sleutels door middel van
een hashfunctie, een vergelijking,

702
00:35:19,880 --> 00:35:22,600
dat maakt ze allemaal in
een soort van een waarde

703
00:35:22,600 --> 00:35:28,740
die vervolgens kan slaan we op
in wezen een reeks van gekoppelde lijst.

704
00:35:28,740 --> 00:35:32,570
>> En dus even, als we wilden
naar Engels woorden op te slaan,

705
00:35:32,570 --> 00:35:37,250
we konden potentieel gewoon, ik niet
weet, zet al de eerste letters

706
00:35:37,250 --> 00:35:39,630
in een soort van een getal.

707
00:35:39,630 --> 00:35:43,140
En zo, bijvoorbeeld, als ik wilde
Een synoniem zijn met apple--

708
00:35:43,140 --> 00:35:47,460
of met de index van 0, en
B synoniem met 1 te zijn,

709
00:35:47,460 --> 00:35:51,030
kunnen we 26 inzendingen
dat kan gewoon opslaan

710
00:35:51,030 --> 00:35:53,610
alle letters van het
alfabet dat we zullen beginnen.

711
00:35:53,610 --> 00:35:56,130
En dan kunnen we
appel op de index van 0.

712
00:35:56,130 --> 00:35:59,160
We kunnen banaan hebben bij de index van
1, cantaloupe de index van 2,

713
00:35:59,160 --> 00:36:00,540
enzovoort.

714
00:36:00,540 --> 00:36:04,460
En zo als ik wilde om te zoeken
mijn hash tafel en toegang appel,

715
00:36:04,460 --> 00:36:07,560
Ik weet dat Apple begint met
een A, en ik weet precies

716
00:36:07,560 --> 00:36:10,860
dat het moet de hash
tafel bij index 0, omdat

717
00:36:10,860 --> 00:36:13,620
van de functie eerder toegewezen.

718
00:36:13,620 --> 00:36:16,572
>> Dus ik weet het niet, we zijn
een gebruiker programma waarin

719
00:36:16,572 --> 00:36:18,780
u zult worden belast met
arbitrarily-- niet willekeurig,

720
00:36:18,780 --> 00:36:22,530
met het proberen om bedachtzaam
denk aan goede vergelijkingen

721
00:36:22,530 --> 00:36:25,460
kunnen verspreiden
al je waarden

722
00:36:25,460 --> 00:36:29,370
op een manier die ze gemakkelijk toegang
zij later met als een vergelijking

723
00:36:29,370 --> 00:36:31,130
dat u zelf weten.

724
00:36:31,130 --> 00:36:35,210
Dus in die zin als ik wilde naar
mango, ik weet het, oh, het begint met m.

725
00:36:35,210 --> 00:36:37,134
Het moet de index van 12.

726
00:36:37,134 --> 00:36:38,800
Ik hoef niet te zoeken door iets.

727
00:36:38,800 --> 00:36:42,080
Ik weet exactly-- ik kon naar
de index van 12 en trek dat uit.

728
00:36:42,080 --> 00:36:45,520
>> Iedereen duidelijk over hoe een
functie hash tafel werkt?

729
00:36:45,520 --> 00:36:48,380
Het is een soort van slechts een meer complexe reeks.

730
00:36:48,380 --> 00:36:50,010
Dat is alles wat het is.

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

732
00:36:51,630 --> 00:36:57,690
>> Dus ik denk dat we tegenkomen
deze kwestie van wat

733
00:36:57,690 --> 00:37:06,390
gebeurt als je meerdere dingen
dat geeft je dezelfde index?

734
00:37:06,390 --> 00:37:10,570
Dus zeggen dat onze functie al
deed was dat de eerste letter

735
00:37:10,570 --> 00:37:14,490
en zet die in een
respectievelijk 0 tot 25 index.

736
00:37:14,490 --> 00:37:17,137
Dat is helemaal prima als
je hebt slechts één van elk.

737
00:37:17,137 --> 00:37:18,970
Maar de tweede u begint
met meer, je bent

738
00:37:18,970 --> 00:37:20,910
gaat te hebben wat een botsing genoemd.

739
00:37:20,910 --> 00:37:25,580
>> Dus als ik probeer in te voegen te begraven in een hash
tabel die al heeft banaan op het,

740
00:37:25,580 --> 00:37:27,870
wat er gaat gebeuren als
je probeert in te voegen dat?

741
00:37:27,870 --> 00:37:30,930
Slechte dingen omdat banaan
reeds binnen de index bestaat

742
00:37:30,930 --> 00:37:33,800
dat u wilt opslaan in.

743
00:37:33,800 --> 00:37:35,560
Berry soort is als, ah, wat moet ik doen?

744
00:37:35,560 --> 00:37:37,080
Ik weet niet waar te gaan.

745
00:37:37,080 --> 00:37:38,410
Hoe kan ik dit oplossen?

746
00:37:38,410 --> 00:37:41,150
>> En dus je jongens zullen soort
zien we dit lastige zaak

747
00:37:41,150 --> 00:37:44,810
waar we kunnen soort eigenlijk
creëren gekoppelde lijst in onze arrays.

748
00:37:44,810 --> 00:37:46,840
En dus is de makkelijkste manier
om na te denken over dit,

749
00:37:46,840 --> 00:37:50,830
alle hash tabel is een
reeks van gekoppelde lijsten.

750
00:37:50,830 --> 00:37:55,670
En ja, in die zin, je hebt
dit prachtige array van pointers,

751
00:37:55,670 --> 00:37:58,740
en vervolgens elke aanwijzer in
die waarde in die index,

752
00:37:58,740 --> 00:38:00,740
daadwerkelijk kan verwijzen naar andere dingen.

753
00:38:00,740 --> 00:38:05,720
En dus moet je al deze afzonderlijke
kettingen komende uit van een grote reeks.

754
00:38:05,720 --> 00:38:07,960
>> En dus even, als ik
wilde bessen voegen,

755
00:38:07,960 --> 00:38:11,220
Ik weet het, OK, ik ga ingang
het door mijn hash-functie.

756
00:38:11,220 --> 00:38:15,070
Ik ga om te eindigen met de index van
1, en dan ga ik om te kunnen hebben

757
00:38:15,070 --> 00:38:20,410
slechts een kleine subset van deze
giant 140.000 woord woordenboek.

758
00:38:20,410 --> 00:38:24,220
En dan kan ik alleen kijken
door middel van 1/26 van dat.

759
00:38:24,220 --> 00:38:27,910
>> En dus dan kan ik gewoon te voegen
bessen voor of na banaan

760
00:38:27,910 --> 00:38:28,820
in dit geval?

761
00:38:28,820 --> 00:38:29,700
Na, toch?

762
00:38:29,700 --> 00:38:33,920
En dus je gaat te willen
Steek dit knooppunt na banaan,

763
00:38:33,920 --> 00:38:36,667
en dus je gaat voegen
aan de staart van die gelinkte lijst.

764
00:38:36,667 --> 00:38:38,500
Ik ga terug te gaan
deze vorige dia,

765
00:38:38,500 --> 00:38:40,680
zodat jullie kunnen zien hoe
hash-functie werkt.

766
00:38:40,680 --> 00:38:43,980
>> Dus hash-functie is deze vergelijking
dat je draait soort uw input

767
00:38:43,980 --> 00:38:46,940
door middel van te krijgen wat index
wilt u het naar toe te wijzen.

768
00:38:46,940 --> 00:38:51,130
Dus, in dit voorbeeld alle we wilden
te doen was de eerste letter,

769
00:38:51,130 --> 00:38:55,890
Zet dat in een index, dan zijn we
kan slaan dat in onze hash-functie.

770
00:38:55,890 --> 00:39:00,160
Alles wat we hier doen is dat we
omzetten van de eerste letter.

771
00:39:00,160 --> 00:39:04,770
Dus KeyKey [0] is slechts de eerste letter
van welke snaar we hebben,

772
00:39:04,770 --> 00:39:05,720
we passeren in.

773
00:39:05,720 --> 00:39:09,740
We omzetten die aan de bovenste en
we trekken door hoofdletters A,

774
00:39:09,740 --> 00:39:11,740
dus alles wat doet
geeft ons een aantal

775
00:39:11,740 --> 00:39:13,670
waarin we onze waarden hash op.

776
00:39:13,670 --> 00:39:16,550
>> En dan gaan we
terug hash modulus SIZE.

777
00:39:16,550 --> 00:39:19,340
Heel, heel voorzichtig
omdat theoretisch, here

778
00:39:19,340 --> 00:39:21,870
je hash-waarde zou kunnen zijn oneindig.

779
00:39:21,870 --> 00:39:23,660
Het zou gewoon gaan op en op en op.

780
00:39:23,660 --> 00:39:26,080
Het zou echt een aantal,
echt grote waarde,

781
00:39:26,080 --> 00:39:29,849
maar omdat je hash tafel
u hebt gemaakt, heeft slechts 26 indexen,

782
00:39:29,849 --> 00:39:31,890
wilt u ervoor zorgen dat uw
modulusing zodat u

783
00:39:31,890 --> 00:39:33,848
niet run-- het is hetzelfde
zoiets als je queue--

784
00:39:33,848 --> 00:39:36,320
zodat je niet lopen van de
onderkant van de hash-functie.

785
00:39:36,320 --> 00:39:39,210
>> U wilt het rond wikkelen terug
Op dezelfde manier in [onverstaanbaar] bij

786
00:39:39,210 --> 00:39:41,750
je had als een zeer,
zeer grote brief, u

787
00:39:41,750 --> 00:39:43,740
niet dat dat
net vandoor het einde.

788
00:39:43,740 --> 00:39:46,948
Hetzelfde hier, wilt u ervoor zorgen
Het loopt niet uit het einde van wikkelen

789
00:39:46,948 --> 00:39:48,330
rond de bovenkant van de tabel.

790
00:39:48,330 --> 00:39:50,530
Dus dit is slechts een zeer
eenvoudige hash-functie.

791
00:39:50,530 --> 00:39:56,570
Al dat deed was de eerste
letter van wat onze inbreng was

792
00:39:56,570 --> 00:40:01,660
en zet die in een index die
we konden in onze hash tafel.

793
00:40:01,660 --> 00:40:05,450
>> Ja, en dus zoals ik al zei,
de manier waarop we conflicten op te lossen

794
00:40:05,450 --> 00:40:09,330
in onze hash tabellen hebben,
wat wij noemen, chaining.

795
00:40:09,330 --> 00:40:13,860
Dus als u probeert meerdere invoegen
woorden die beginnen met het zelfde ding,

796
00:40:13,860 --> 00:40:16,145
je gaat om een ​​hash-waarde hebben.

797
00:40:16,145 --> 00:40:18,770
Avocado en appel, als je hebt
lopen via onze hash-functie,

798
00:40:18,770 --> 00:40:21,450
gaat u op te geven
hetzelfde nummer, het aantal 0.

799
00:40:21,450 --> 00:40:24,550
En dus is de manier waarop we op te lossen dat is
dat we kunnen eigenlijk wel te koppelen

800
00:40:24,550 --> 00:40:27,010
elkaar via gelinkte lijsten.

801
00:40:27,010 --> 00:40:29,600
>> Dus in die zin,
kunnen jullie soort te zien

802
00:40:29,600 --> 00:40:32,640
hoe data structuren die
we zijn het instellen van eerder

803
00:40:32,640 --> 00:40:35,870
als een rozijn gelinkte lijst soort
van elkaar kunnen komen tot één.

804
00:40:35,870 --> 00:40:38,860
En dan kan je ver creëren
efficiëntere datastructuren

805
00:40:38,860 --> 00:40:43,350
die kunnen grotere hoeveelheden te behandelen
data, die dynamisch vergroten of verkleinen, afhankelijk

806
00:40:43,350 --> 00:40:44,870
op uw behoeften.

807
00:40:44,870 --> 00:40:45,620
Iedereen duidelijk?

808
00:40:45,620 --> 00:40:47,580
Iedereen soort duidelijke
wat hier gebeurt?

809
00:40:47,580 --> 00:40:52,110
>> Als ik wilde insert-- wat is een
fruit dat begint met, ik weet het niet,

810
00:40:52,110 --> 00:40:54,726
B, met uitzondering van bessen, banaan.

811
00:40:54,726 --> 00:40:55,710
>> Publiek: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI Peng: Blackberry, blackberry.

813
00:40:57,910 --> 00:41:00,530
Waar gaat blackberry gaan hier?

814
00:41:00,530 --> 00:41:04,251
Nou, we hebben eigenlijk niet gesorteerd
dit nog niet, maar in theorie

815
00:41:04,251 --> 00:41:06,250
als we wilden dit hebben
in alfabetische volgorde,

816
00:41:06,250 --> 00:41:07,944
waar moet blackberry gaan?

817
00:41:07,944 --> 00:41:09,210
>> PUBLIEK: [onverstaanbaar]

818
00:41:09,210 --> 00:41:11,100
>> ANDI PENG: Precies, na hier, toch?

819
00:41:11,100 --> 00:41:14,950
Maar omdat het is erg moeilijk om
reorder-- Ik denk dat het is aan jullie.

820
00:41:14,950 --> 00:41:17,920
Jullie kunnen helemaal
implementeren wat je wilt.

821
00:41:17,920 --> 00:41:20,730
De efficiëntere wijze
dit misschien doen

822
00:41:20,730 --> 00:41:24,570
zou zijn om te sorteren uw gekoppelde
een lijst in alfabetische volgorde,

823
00:41:24,570 --> 00:41:26,520
en dus als je
invoegen van dingen, je wilt

824
00:41:26,520 --> 00:41:28,632
om zeker te zijn om ze te voegen
in alfabetische volgorde

825
00:41:28,632 --> 00:41:30,590
zodat dan wanneer je bent
proberen om ze te zoeken,

826
00:41:30,590 --> 00:41:32,410
je hoeft niet alles te doorkruisen.

827
00:41:32,410 --> 00:41:35,290
Je weet precies waar
het is, en het is makkelijker.

828
00:41:35,290 --> 00:41:39,100
>> Maar als je het soort hebt
dingen willekeurig afgewisseld,

829
00:41:39,100 --> 00:41:41,420
je bent nog steeds te hebben
om het anyways doorkruisen.

830
00:41:41,420 --> 00:41:44,990
En dus als ik wilde gewoon
Steek blackberry hier

831
00:41:44,990 --> 00:41:47,470
en ik wilde om te zoeken naar
het, ik weet het, oh, blackberry

832
00:41:47,470 --> 00:41:52,012
moet beginnen met de index van 1, dus ik
weet ogenblikkelijk gewoon zoeken op 1.

833
00:41:52,012 --> 00:41:53,970
En dan kan ik soort
doorkruisen de gelinkte lijst

834
00:41:53,970 --> 00:41:56,120
totdat ik op Blackberry,
en then-- ja?

835
00:41:56,120 --> 00:41:59,550
>> Publiek: Als je probeert te create--
Ik denk dat als dit is een zeer eenvoudige hash

836
00:41:59,550 --> 00:42:00,050
functie.

837
00:42:00,050 --> 00:42:02,835
En als we wilden doen
meerdere lagen zoals die,

838
00:42:02,835 --> 00:42:05,870
OK, we willen scheiden in
net als alle alfabetische letters

839
00:42:05,870 --> 00:42:09,040
en dan weer naar een andere set graag
van alfabetische brieven binnen die,

840
00:42:09,040 --> 00:42:11,715
we zetten als een hash
tabel in een hash-tabel,

841
00:42:11,715 --> 00:42:13,256
of als een functie binnen een functie?

842
00:42:13,256 --> 00:42:14,880
Of is dat--

843
00:42:14,880 --> 00:42:17,510
>> ANDI PENG: Dus je hash
function-- uw hash table

844
00:42:17,510 --> 00:42:19,360
kan zo groot zijn als u dat wilt.

845
00:42:19,360 --> 00:42:21,930
Dus in die zin, dacht ik
Het was erg makkelijk, erg

846
00:42:21,930 --> 00:42:25,320
eenvoudig voor mij om gewoon soort gebaseerde
op brieven van het eerste woord.

847
00:42:25,320 --> 00:42:28,690
En dus is er slechts 26 opties.

848
00:42:28,690 --> 00:42:32,650
Ik kan alleen maar 26 opties
0-25 omdat zij alleen kunnen

849
00:42:32,650 --> 00:42:36,510
start van A tot Z. Maar als je wilde
toevoegen, misschien meer complexiteit

850
00:42:36,510 --> 00:42:39,260
of sneller lopen tijd om uw
hash table, u absoluut

851
00:42:39,260 --> 00:42:40,760
kunnen allerlei dingen doen.

852
00:42:40,760 --> 00:42:43,330
U kunt uw eigen te maken
vergelijking die je geeft

853
00:42:43,330 --> 00:42:48,000
meer spreiding in uw
woorden, dan wanneer u zoekt,

854
00:42:48,000 --> 00:42:49,300
het gaat sneller.

855
00:42:49,300 --> 00:42:52,100
>> Het is helemaal aan jullie
hoe je wilt implementeren dat.

856
00:42:52,100 --> 00:42:55,140
Zie het als gewoon emmers.

857
00:42:55,140 --> 00:42:57,376
Als ik wilde hebben
26 emmers, ik ga

858
00:42:57,376 --> 00:42:59,420
om dingen in die emmers afstand.

859
00:42:59,420 --> 00:43:02,980
Maar ik ga een heleboel hebben
dingen in elke emmer,

860
00:43:02,980 --> 00:43:05,890
dus als je wilt om het te maken
sneller en efficiënter

861
00:43:05,890 --> 00:43:07,190
laat me honderd emmers.

862
00:43:07,190 --> 00:43:09,290
>> Maar dan moet je uitzoeken een
manier om dingen te sorteren, zodat zij

863
00:43:09,290 --> 00:43:11,040
in de juiste bak ze zouden moeten zijn in.

864
00:43:11,040 --> 00:43:13,331
Maar dan als je daadwerkelijk
willen kijken naar die emmer,

865
00:43:13,331 --> 00:43:16,410
het is een stuk sneller omdat er
minder spullen in elke emmer.

866
00:43:16,410 --> 00:43:20,250
En zo ja, dat is eigenlijk
de truc voor jullie in pset5

867
00:43:20,250 --> 00:43:22,360
is dat je in
uitgedaagd om gewoon te creëren

868
00:43:22,360 --> 00:43:26,170
wat is de meest efficiënte
functie die je kunt bedenken zijn

869
00:43:26,170 --> 00:43:28,520
in staat om op te slaan en laat deze waarden.

870
00:43:28,520 --> 00:43:30,840
>> Helemaal aan jullie
maar u wilt doen,

871
00:43:30,840 --> 00:43:32,229
maar dat is een heel goed punt.

872
00:43:32,229 --> 00:43:34,520
Dat de aard van de logica u
willen gaan nadenken over

873
00:43:34,520 --> 00:43:37,236
is, nou ja, waarom niet ik meer emmers.

874
00:43:37,236 --> 00:43:39,527
En dan moet ik zoeken
minder dingen, en dan misschien I

875
00:43:39,527 --> 00:43:41,640
een andere hashfunctie.

876
00:43:41,640 --> 00:43:45,500
>> Ja, er is een heleboel manieren om dit te doen
PSET, sommige zijn sneller dan anderen.

877
00:43:45,500 --> 00:43:50,630
Ik ben helemaal ga gewoon zien hoe
snel was de snelste je jongens zullen

878
00:43:50,630 --> 00:43:55,170
in staat zijn om hun functies te werken.

879
00:43:55,170 --> 00:43:58,176
Oké, iedereen goed op
chaining en hash tabellen?

880
00:43:58,176 --> 00:44:00,800
Het is eigenlijk net als een zeer eenvoudige
Het concept als je erover nadenkt.

881
00:44:00,800 --> 00:44:05,160
Al is het is het scheiden van wat
uw ingangen zijn in emmers,

882
00:44:05,160 --> 00:44:10,670
ze te sorteren, en dan zoeken op het
geeft dat er is gekoppeld.

883
00:44:10,670 --> 00:44:11,852
>> Koel.

884
00:44:11,852 --> 00:44:18,160
Oké, nu hebben we een ander soort
data structuur die heet een boom.

885
00:44:18,160 --> 00:44:20,850
Laten we verder gaan en praten over pogingen
die duidelijk verschillend,

886
00:44:20,850 --> 00:44:22,330
maar in dezelfde categorie.

887
00:44:22,330 --> 00:44:29,010
Wezen, al een boom is in plaats
organiseren data op de lineair

888
00:44:29,010 --> 00:44:32,560
dat een hash tafel does-- u
weet, het heeft een top en een bodem

889
00:44:32,560 --> 00:44:37,900
en dan heb je soort koppelen off van het-- een
De boom heeft een top die je de wortel noemen,

890
00:44:37,900 --> 00:44:40,220
en dan heeft het blad rondom.

891
00:44:40,220 --> 00:44:42,390
>> En dus alles wat je hier
is slechts de top knooppunt

892
00:44:42,390 --> 00:44:45,980
die naar andere knooppunten, die punten
meer nodes, enzovoort, enzovoort.

893
00:44:45,980 --> 00:44:48,130
En dus moet je gewoon splitsen takken.

894
00:44:48,130 --> 00:44:53,255
Het is gewoon een andere manier van organiseren
data, en omdat we noemen het een boom,

895
00:44:53,255 --> 00:44:56,270
jullie gewoon-- het is gewoon
gemodelleerd naar uitzien als een boom.

896
00:44:56,270 --> 00:44:57,670
Dat is waarom we noemen het bomen.

897
00:44:57,670 --> 00:44:59,370
>> Hash tafel lijkt op een tafel.

898
00:44:59,370 --> 00:45:01,310
Een boom ziet eruit als een boom.

899
00:45:01,310 --> 00:45:03,300
Alle het is is een aparte
manier van organiseren knooppunten

900
00:45:03,300 --> 00:45:06,020
afhankelijk van wat uw wensen zijn.

901
00:45:06,020 --> 00:45:11,810
>> Dus je hebt een wortel en
dan heb je bladeren.

902
00:45:11,810 --> 00:45:15,380
De manier waarop we kunnen met name
denken over het is een binaire boom,

903
00:45:15,380 --> 00:45:18,150
een binaire boom is slechts een
bepaald type boom

904
00:45:18,150 --> 00:45:22,450
waarbij elk knooppunt alleen punten
tot op max, twee andere knooppunten.

905
00:45:22,450 --> 00:45:25,434
En dus even je duidelijk hebt
symmetrie in uw boom

906
00:45:25,434 --> 00:45:28,600
dat maakt het makkelijker om soort kijken
op welke waarden je bent, want dan heb je

907
00:45:28,600 --> 00:45:30,150
hebben altijd een links of rechts.

908
00:45:30,150 --> 00:45:33,150
Er is nooit als een linker derde van
links of een vierde van links.

909
00:45:33,150 --> 00:45:36,358
Het is gewoon je een linker en een rechter
en u kunt zoeken een van deze twee.

910
00:45:36,358 --> 00:45:38,980
En dus waarom is dit nuttig?

911
00:45:38,980 --> 00:45:40,980
De manier waarop dit
handig is als u op zoek bent

912
00:45:40,980 --> 00:45:42,890
om door middel van waarden, toch?

913
00:45:42,890 --> 00:45:45,640
In plaats van uitvoering binaire
zoeken in een fout array,

914
00:45:45,640 --> 00:45:49,260
als je wilde om te kunnen knopen voegen
en neem knooppunten weg op wil en ook

915
00:45:49,260 --> 00:45:52,185
het behoud van de zoekopdracht
capaciteiten van binaire zoeken.

916
00:45:52,185 --> 00:45:54,560
Dus op deze manier, we zijn soort
tricking-- herinneren wanneer we

917
00:45:54,560 --> 00:45:56,530
zei gekoppelde lijsten kan niet binary search?

918
00:45:56,530 --> 00:46:01,700
We soort van het creëren van een datastructuur
dat de trucs die in het beroepsleven.

919
00:46:01,700 --> 00:46:05,034
>> En omdat gelinkte lijsten zijn lineair,
zij slechts verbinden na elkaar.

920
00:46:05,034 --> 00:46:06,950
We kunnen soort hebben
ander soort pointers

921
00:46:06,950 --> 00:46:09,408
dat punt naar verschillende knooppunten
die ons kunnen helpen met zoeken.

922
00:46:09,408 --> 00:46:12,590
En dus even, als ik wilde
hebben een binaire zoekboom,

923
00:46:12,590 --> 00:46:14,090
Ik weet dat mijn middelvinger als 55.

924
00:46:14,090 --> 00:46:18,280
Ik ga gewoon te creëren dat
zoals mijn midden, zoals mijn wortel,

925
00:46:18,280 --> 00:46:20,770
en dan ga ik heb
waarden spin-off van het.

926
00:46:20,770 --> 00:46:25,610
>> Dus hier, als ik ga op zoek naar
de waarde van 66, kan ik beginnen bij 55.

927
00:46:25,610 --> 00:46:27,310
Het is 66 groter dan 55?

928
00:46:27,310 --> 00:46:30,970
Ja het is, dus ik weet dat ik mus zoeken
i n de juiste wijzer van deze boom.

929
00:46:30,970 --> 00:46:32,440
Ik ga naar 77.

930
00:46:32,440 --> 00:46:35,367
OK, is 66 kleiner of groter dan 77?

931
00:46:35,367 --> 00:46:37,950
Het is minder dan, zodat u weet, oh,
dat bij de linker node.

932
00:46:37,950 --> 00:46:41,410
>> En dus even we soort van het behoud
alle van de grote dingen over arrays,

933
00:46:41,410 --> 00:46:44,420
dus als dynamisch vergroten of verkleinen
voorwerpen, die

934
00:46:44,420 --> 00:46:49,530
in staat om in te voegen en te verwijderen op wil,
zonder zich zorgen te maken over de vaste

935
00:46:49,530 --> 00:46:50,370
hoeveelheid ruimte.

936
00:46:50,370 --> 00:46:52,820
We hebben nog steeds alles te behouden
die prachtige dingen

937
00:46:52,820 --> 00:46:57,140
terwijl ook in staat om het te behouden
log en zoek de tijd van binaire zoekopdracht

938
00:46:57,140 --> 00:47:00,450
die we eerder waren slechts
in staat om een ​​zin te krijgen.

939
00:47:00,450 --> 00:47:06,310
>> Koele datastructuur, soort
moeilijk uitvoerbaar, het knooppunt.

940
00:47:06,310 --> 00:47:08,311
Zoals u kunt zien, al
is de structuur van het knooppunt

941
00:47:08,311 --> 00:47:10,143
is dat u een links
en rechteraanwijzer.

942
00:47:10,143 --> 00:47:11,044
Dat is alles wat het is.

943
00:47:11,044 --> 00:47:12,960
Dus in plaats van alleen
met een X of een eerdere.

944
00:47:12,960 --> 00:47:15,920
Je hebt een links of rechts, en dan
u kunt soort koppelen ze samen

945
00:47:15,920 --> 00:47:16,836
Maar je daarvoor kiezen.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, we eigenlijk gaan
slechts een paar minuten duren.

948
00:47:24,270 --> 00:47:25,790
Dus we gaan om hier terug te gaan.

949
00:47:25,790 --> 00:47:28,270
Zoals ik al eerder zei,
Ik soort uitgelegd

950
00:47:28,270 --> 00:47:31,520
de logica achter hoe we
zou zoeken door middel van deze.

951
00:47:31,520 --> 00:47:33,860
We gaan proberen
pseudocoding dit uit te zien

952
00:47:33,860 --> 00:47:38,000
als we soort kunnen toepassen
Dezelfde logica van binaire zoekopdracht

953
00:47:38,000 --> 00:47:40,055
een ander type gegevensstructuur.

954
00:47:40,055 --> 00:47:45,049
Als jullie willen nemen als een paar
minuten om gewoon na te denken over dit.

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
Oké, ik ga
eigenlijk alleen maar geef je geen the--,

958
00:48:51,407 --> 00:48:52,990
we over de pseudocode praten eerste.

959
00:48:52,990 --> 00:48:56,580
Dus doet iedereen wil
een steek op te geven wat

960
00:48:56,580 --> 00:49:02,100
het eerste wat je wilt doen als
je begint uit te zoeken is?

961
00:49:02,100 --> 00:49:04,460
Als we op zoek naar
de waarde van 66, wat is

962
00:49:04,460 --> 00:49:07,940
het eerste wat we willen doen als
we willen binary search deze boom?

963
00:49:07,940 --> 00:49:10,760
>> PUBLIEK: U wilt naar rechts kijken
en kijk links en zie [onverstaanbaar]

964
00:49:10,760 --> 00:49:11,230
groter aantal.

965
00:49:11,230 --> 00:49:12,271
>> ANDI Peng: Ja, precies.

966
00:49:12,271 --> 00:49:15,350
Dus je gaat kijken naar uw wortel.

967
00:49:15,350 --> 00:49:18,180
Er zijn veel manieren waarop u kunt bellen
het, je ouders knooppunt mensen zeggen.

968
00:49:18,180 --> 00:49:21,317
Ik wil wortel zeggen, want
dat is net als de wortel van de boom.

969
00:49:21,317 --> 00:49:23,400
Je gaat kijken naar
je root-knooppunt, en je bent

970
00:49:23,400 --> 00:49:26,940
gaan zien is 66 groter
of kleiner dan 55.

971
00:49:26,940 --> 00:49:30,360
En als het groter is dan, nou ja, het is
groter dan, waar willen we naar kijken?

972
00:49:30,360 --> 00:49:32,000
Waar willen we zoeken nu, toch?

973
00:49:32,000 --> 00:49:34,340
Wij willen het zoeken
rechter helft van deze boom.

974
00:49:34,340 --> 00:49:38,390
>> Dus we hebben, gunstig, een
pointer die wijst naar rechts.

975
00:49:38,390 --> 00:49:44,325
En dus dan kunnen we stellen
onze nieuwe root te zijn 77.

976
00:49:44,325 --> 00:49:46,450
We kunnen gewoon gaan naar waar
de wijzer wijst.

977
00:49:46,450 --> 00:49:49,100
Nou, oh, hier zijn we beginnen
op 77, en we kunnen alleen maar

978
00:49:49,100 --> 00:49:51,172
Dit doen recursief opnieuw en opnieuw.

979
00:49:51,172 --> 00:49:52,880
Op deze manier, je soort
van een functie.

980
00:49:52,880 --> 00:49:57,430
Je hebt een manier van zoeken die je
kan gewoon herhalen over en over en over,

981
00:49:57,430 --> 00:50:02,720
afhankelijk van waar u wilt kijken
totdat je uiteindelijk de waarde

982
00:50:02,720 --> 00:50:04,730
die u zoekt.

983
00:50:04,730 --> 00:50:05,230
Zin?

984
00:50:05,230 --> 00:50:07,800
>> Ik sta op het punt om te laten zien van de werkelijke
code, en het is een veel code.

985
00:50:07,800 --> 00:50:08,674
Geen behoefte om freak out.

986
00:50:08,674 --> 00:50:09,910
We praten er doorheen.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Eigenlijk niet.

989
00:50:14,020 --> 00:50:15,061
Dat was gewoon pseudocode.

990
00:50:15,061 --> 00:50:17,860
OK, dat was gewoon de pseudocode,
dat is een beetje ingewikkeld,

991
00:50:17,860 --> 00:50:19,751
maar het is helemaal prima.

992
00:50:19,751 --> 00:50:21,000
Iedereen volgt samen hier?

993
00:50:21,000 --> 00:50:24,260
Als de wortel is null, rendement
valse want dat betekent

994
00:50:24,260 --> 00:50:26,850
je hoeft niet eens iets hebben daar.

995
00:50:26,850 --> 00:50:31,376
>> Als wortel n is de waarde, dus als het
gebeurt er met degene die je zoekt op zijn,

996
00:50:31,376 --> 00:50:34,000
dan zul je ware terug
omdat je weet dat je het gevonden.

997
00:50:34,000 --> 00:50:36,250
Maar als de waarde minder
dan wortel van n, je bent

998
00:50:36,250 --> 00:50:38,332
gaat naar de linkerzijde
kind of de linker blad,

999
00:50:38,332 --> 00:50:39,540
wat je ook wilt noemen.

1000
00:50:39,540 --> 00:50:41,750
Als deze waarde groter is dan wortel,
je gaat naar de juiste boom zoeken,

1001
00:50:41,750 --> 00:50:44,610
dan gewoon de functie run
door middel van zoeken weer.

1002
00:50:44,610 --> 00:50:48,037
>> En als wortel is null, dat
betekent dat je het einde hebt bereikt?

1003
00:50:48,037 --> 00:50:50,120
Dat betekent dat je geen
meer meer bladeren om te zoeken,

1004
00:50:50,120 --> 00:50:52,230
dan weet je, oh, ik
denk dat het niet hier

1005
00:50:52,230 --> 00:50:55,063
want nadat ik keek door
de hele zaak en het is niet hier,

1006
00:50:55,063 --> 00:50:56,930
het misschien gewoon niet hier.

1007
00:50:56,930 --> 00:50:58,350
>> Heeft dat zin om iedereen?

1008
00:50:58,350 --> 00:51:03,230
Dus het is net als binary search behoud
de mogelijkheden van gekoppelde lijsten.

1009
00:51:03,230 --> 00:51:09,200
Cool, en dus het tweede type
van datastructuur jullie

1010
00:51:09,200 --> 00:51:13,180
kunt implementeren op uw PSET,
je hoeft maar één te kiezen.

1011
00:51:13,180 --> 00:51:19,430
Maar misschien een alternatieve methode om
de hash-tabel is wat wij een trie noemen.

1012
00:51:19,430 --> 00:51:24,080
>> Allemaal een trie is een
specifieke boomsoort die

1013
00:51:24,080 --> 00:51:28,600
heeft waarden die naar andere waarden.

1014
00:51:28,600 --> 00:51:31,450
Dus in plaats van een binaire
structuur in die zin dat enige

1015
00:51:31,450 --> 00:51:35,940
wat kan wijzen op twee, kunt u
een ding punt aan vele, vele dingen.

1016
00:51:35,940 --> 00:51:39,450
Je hebt in wezen arrays
de binnenkant van die u opslaat

1017
00:51:39,450 --> 00:51:41,790
pointers die naar andere arrays.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Dus het knooppunt van de manier waarop we
zou trie definiëren

1020
00:51:49,460 --> 00:51:52,590
is dat we willen hebben
Boolean, c woord, toch?

1021
00:51:52,590 --> 00:51:54,920
Zodat de node Boolean
als waar of onwaar,

1022
00:51:54,920 --> 00:51:58,490
allereerst aan het hoofd van
die array, is dit een woord?

1023
00:51:58,490 --> 00:52:03,620
Ten tweede, wil je pointers hebben
naar wat de rest van hen zijn.

1024
00:52:03,620 --> 00:52:07,470
Een beetje ingewikkeld, een beetje abstract, maar
Ik zal wat dat alle middelen uit te leggen.

1025
00:52:07,470 --> 00:52:13,800
>> Dus hier bovenaan, als je
hebben een scala verklaarde al,

1026
00:52:13,800 --> 00:52:17,040
een knooppunt waar u een Boole
opgeslagen waarde aan de voorzijde

1027
00:52:17,040 --> 00:52:19,490
dat vertelt u is dit een woord?

1028
00:52:19,490 --> 00:52:20,520
Is dit niet een woord?

1029
00:52:20,520 --> 00:52:23,240
En dan heb je de
rest van uw array die

1030
00:52:23,240 --> 00:52:26,040
eigenlijk slaat alle
mogelijkheden wat het kan zijn.

1031
00:52:26,040 --> 00:52:28,660
Dus, bijvoorbeeld, als
aan de top heb je

1032
00:52:28,660 --> 00:52:32,140
het eerste ding dat waar of zegt
onwaar, ja of nee, dit is een woord.

1033
00:52:32,140 --> 00:52:38,130
>> En dan heb je 0 tot en met 26 van
de letters die u kunt opslaan.

1034
00:52:38,130 --> 00:52:42,790
Als ik hier wilde zoeken
voor bat, ga ik naar de top

1035
00:52:42,790 --> 00:52:49,200
en ik kijk naar B. Ik vind B in mijn
array, en zo weet ik, OK, is B een woord?

1036
00:52:49,200 --> 00:52:53,010
B is geen woord, zodat daarmee
Ik moet blijven zoeken.

1037
00:52:53,010 --> 00:52:56,410
Ik ga van B, en ik kijk naar de
pointer die wijst naar B

1038
00:52:56,410 --> 00:53:00,900
en ik zie een andere array van informatie,
dezelfde structuur die we eerder hadden.

1039
00:53:00,900 --> 00:53:05,240
>> En hier-- oh, de volgende
brief in [onverstaanbaar] A.

1040
00:53:05,240 --> 00:53:07,210
Dus we kijken in die array.

1041
00:53:07,210 --> 00:53:10,860
Wij vinden de achtste waarde,
en dan kijken we om te zien, oh,

1042
00:53:10,860 --> 00:53:12,840
hey, is dat een woord, is B-A een woord?

1043
00:53:12,840 --> 00:53:13,807
Het is geen woord.

1044
00:53:13,807 --> 00:53:14,890
We moeten blijven kijken.

1045
00:53:14,890 --> 00:53:17,850
>> En dus dan kijken we naar de plaats waar
de wijzer van A punten

1046
00:53:17,850 --> 00:53:21,130
en het wijst op een andere manier
die we hebben meer waarde opgeslagen.

1047
00:53:21,130 --> 00:53:24,150
En uiteindelijk komen we bij
B-A-T, dat een woord.

1048
00:53:24,150 --> 00:53:25,970
En dus de volgende keer
je kijkt, je gaat

1049
00:53:25,970 --> 00:53:30,850
dat controle van, ja hebben,
deze Boolean functie is waar.

1050
00:53:30,850 --> 00:53:35,450
En zo in de zin dat we soort
van een boom met arrays.

1051
00:53:35,450 --> 00:53:39,890
>> Dus dan kun je soort zoeken naar beneden.

1052
00:53:39,890 --> 00:53:43,650
In plaats van een hashing-functie en
toekennen van waarden door gelinkte lijst,

1053
00:53:43,650 --> 00:53:49,190
je kunt gewoon uitvoeren van een
trie dat downwords zoekt.

1054
00:53:49,190 --> 00:53:50,850
Echt, echt ingewikkeld spul.

1055
00:53:50,850 --> 00:53:54,060
Niet gemakkelijk om te denken, want ik ben net als
spugen zoveel datastructuren uit

1056
00:53:54,060 --> 00:53:58,710
op je af, maar doet iedereen soort
begrijpen hoe de logica van dit werkt?

1057
00:53:58,710 --> 00:54:01,920
>> OK, cool.

1058
00:54:01,920 --> 00:54:05,600
Dus B-A-T, en dan
je gaat zoeken.

1059
00:54:05,600 --> 00:54:07,940
De volgende keer dat je gaat
te zien, oh, hey, het is waar,

1060
00:54:07,940 --> 00:54:09,273
dus ik weet dat dit moet een woord zijn.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Hetzelfde voor de dierentuin.

1063
00:54:13,770 --> 00:54:17,960
Dus hier is het ding nu, als we
wilde om te zoeken naar de dierentuin, op dit moment,

1064
00:54:17,960 --> 00:54:20,780
momenteel dierentuin is niet een
woord in ons woordenboek

1065
00:54:20,780 --> 00:54:25,300
omdat, zoals jullie kunnen zien, de
eerste plaats dat we een Boolean

1066
00:54:25,300 --> 00:54:28,590
return true is aan het eind van de zoom.

1067
00:54:28,590 --> 00:54:30,430
We hebben Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> En dus even, we eigenlijk niet hebben
het woord, dierentuin, in ons woordenboek

1069
00:54:33,900 --> 00:54:36,070
omdat dit selectievakje is niet aangevinkt.

1070
00:54:36,070 --> 00:54:39,540
Zodat de computer niet
weten dat de dierentuin is een woord

1071
00:54:39,540 --> 00:54:42,430
omdat de manier waarop we hebben
opgeslagen het, alleen een zoom hier

1072
00:54:42,430 --> 00:54:44,920
heeft eigenlijk een Booleaanse waarde
die is gedraaid waar.

1073
00:54:44,920 --> 00:54:49,380
Dus als we willen het invoegen
woord, dierentuin, in ons woordenboek,

1074
00:54:49,380 --> 00:54:51,770
hoe zouden we gaan dat doen?

1075
00:54:51,770 --> 00:54:55,960
Wat moeten we doen om ervoor te zorgen dat onze
computer weet dat Z-O-O is een woord

1076
00:54:55,960 --> 00:54:58,130
en niet het eerste woord is Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> PUBLIEK: [onverstaanbaar]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI Peng: Precies, we
willen ervoor zorgen dat deze

1079
00:55:01,450 --> 00:55:07,890
Hier, dat Booleaanse waarde
afgevinkt dat het waar is.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, dan gaan we controleren of,
zodat we precies weten, he, dierentuin is een woord.

1081
00:55:13,297 --> 00:55:15,380
Ik ga het vertellen
computer dat het een woord zo

1082
00:55:15,380 --> 00:55:18,000
dat wanneer de computer controleert,
het weet dat de dierentuin is een woord.

1083
00:55:18,000 --> 00:55:21,269
>> Want vergeet niet al deze gegevens
structuren, het is erg makkelijk voor ons

1084
00:55:21,269 --> 00:55:22,310
te zeggen, oh, vleermuis is een woord.

1085
00:55:22,310 --> 00:55:22,851
Zoo is een woord.

1086
00:55:22,851 --> 00:55:23,611
Zoom is een woord.

1087
00:55:23,611 --> 00:55:25,860
Maar als je bouwen,
de computer heeft geen idee.

1088
00:55:25,860 --> 00:55:28,619
>> Dus je moet het precies vertellen
op welk punt is dat een woord?

1089
00:55:28,619 --> 00:55:29,910
Op welk punt is het niet een woord?

1090
00:55:29,910 --> 00:55:31,784
En op welk moment moet ik
nodig hebt om dingen te zoeken,

1091
00:55:31,784 --> 00:55:34,000
en op welk moment moet ik naast gaan?

1092
00:55:34,000 --> 00:55:37,010
Iedereen duidelijk dat?

1093
00:55:37,010 --> 00:55:39,540
Koel.

1094
00:55:39,540 --> 00:55:42,530
>> En dus dan komt het
probleem hoe zouden we

1095
00:55:42,530 --> 00:55:45,560
gaan over het plaatsen van iets
dat is eigenlijk niet?

1096
00:55:45,560 --> 00:55:49,090
Dus laten we gewoon zeggen dat we willen invoegen
het woord, bad, in onze trie.

1097
00:55:49,090 --> 00:55:53,589
Zoals jullie kunnen zien, zoals momenteel
alles wat we nu hebben, is B-A-T,

1098
00:55:53,589 --> 00:55:55,630
en deze nieuwe datastructuur
er had een pint die

1099
00:55:55,630 --> 00:55:59,740
wees op null omdat we aannemen
dat, oh, er is geen woorden na de B-A-T,

1100
00:55:59,740 --> 00:56:02,530
waarom hebben we nodig om te blijven
die dingen na die T.

1101
00:56:02,530 --> 00:56:06,581
>> Maar het probleem ontstaat als we u doen
willen een woord dat komt na hebben

1102
00:56:06,581 --> 00:56:07,080
de T's.

1103
00:56:07,080 --> 00:56:09,500
Als je bad, je bent
gaan naar een H rechts wilt.

1104
00:56:09,500 --> 00:56:13,290
En dus is de manier waarop we dat doen is
we gaan een apart knooppunt te maken.

1105
00:56:13,290 --> 00:56:16,840
We zijn niet toe te wijzen wat voor bedrag
geheugen voor deze nieuwe array,

1106
00:56:16,840 --> 00:56:20,720
en we gaan pointers toewijzen.

1107
00:56:20,720 --> 00:56:22,947
>> We gaan naar het toewijzen
H, allereerst dit null,

1108
00:56:22,947 --> 00:56:24,030
we gaan om zich te ontdoen van.

1109
00:56:24,030 --> 00:56:26,590
We gaan te hebben
het H-punt naar beneden.

1110
00:56:26,590 --> 00:56:30,600
Als we een H, we willen het
om te gaan naar ergens anders.

1111
00:56:30,600 --> 00:56:33,910
>> Hier kunnen we dan controleren ja uit.

1112
00:56:33,910 --> 00:56:38,170
Als we een H hit na de T, oh,
dan weten we dat dit een woord.

1113
00:56:38,170 --> 00:56:41,110
De Booleaanse gaat om waar te keren.

1114
00:56:41,110 --> 00:56:42,950
Iedereen duidelijk over de manier waarop dat gebeurde?

1115
00:56:42,950 --> 00:56:45,110
OK.

1116
00:56:45,110 --> 00:56:47,214
>> Dus in wezen allemaal
Deze gegevensstructuren

1117
00:56:47,214 --> 00:56:50,130
dat we dan vandaag de dag zijn gegaan, ik heb
echt, echt snel gegaan over hen

1118
00:56:50,130 --> 00:56:52,192
en niet te veel
detail, en dat is OK.

1119
00:56:52,192 --> 00:56:53,900
Zodra u begint knoeien
met het, zult u

1120
00:56:53,900 --> 00:56:55,733
het bijhouden van de plaats waar
alle pointers zijn,

1121
00:56:55,733 --> 00:56:58,060
wat er gaande is in uw
gegevensstructuren, et cetera.

1122
00:56:58,060 --> 00:56:59,810
Ze zullen zeer nuttig zijn,
en het is aan jou

1123
00:56:59,810 --> 00:57:03,890
jongens om volledig uit te zoeken hoe
je dingen wilt implementeren.

1124
00:57:03,890 --> 00:57:07,650
>> En zo pset4, van 5-- oh, dat is verkeerd.

1125
00:57:07,650 --> 00:57:10,140
Pset5 is spelfouten.

1126
00:57:10,140 --> 00:57:13,710
Zoals ik al eerder zei, je gaat, zodra
weer, downloaden broncode van ons.

1127
00:57:13,710 --> 00:57:16,210
Er gaat drie zijn
dingen die je zult downloaden.

1128
00:57:16,210 --> 00:57:18,470
Je zult woordenboeken downloaden
kers, en teksten.

1129
00:57:18,470 --> 00:57:21,660
>> Al die dingen zijn zijn
ofwel woordenboeken woorden

1130
00:57:21,660 --> 00:57:25,190
dat we willen dat je om te controleren
of het testen van gegevens

1131
00:57:25,190 --> 00:57:26,930
dat we willen dat je check spellen.

1132
00:57:26,930 --> 00:57:29,670
En zo de woordenboeken
Wij geven je gaat

1133
00:57:29,670 --> 00:57:34,870
je werkelijke woorden die we willen geven
om ergens slaan op een manier die

1134
00:57:34,870 --> 00:57:36,530
efficiënter dan een array.

1135
00:57:36,530 --> 00:57:38,470
En dan de teksten
gaat worden wat we

1136
00:57:38,470 --> 00:57:43,900
vraag je om de spelling controleren om er zeker
alle woorden zijn er echte woorden.

1137
00:57:43,900 --> 00:57:47,970
>> En zo de drie blokken van
programma's die we je geven

1138
00:57:47,970 --> 00:57:51,130
dictionary.c worden genoemd,
dictionary.h en speller.c.

1139
00:57:51,130 --> 00:57:56,500
En zo alle dictionary.c doet is
wat je gevraagd wordt te implementeren.

1140
00:57:56,500 --> 00:57:57,880
Het laadt woorden.

1141
00:57:57,880 --> 00:58:02,000
Het te spellen controles hen, en het zorgt ervoor dat
dat alles goed geplaatst.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h is gewoon een bibliotheek bestand
dat verklaart al die functies.

1143
00:58:05,180 --> 00:58:07,650
En speller.c, we gaan u.

1144
00:58:07,650 --> 00:58:09,290
U hoeft niet een van te wijzigen.

1145
00:58:09,290 --> 00:58:14,290
Alle speller.c doet is te nemen dat,
laadt, controleert de snelheid ervan,

1146
00:58:14,290 --> 00:58:19,190
test de benchmark van als hoe
snel ben je in staat om dingen te doen.

1147
00:58:19,190 --> 00:58:20,410
>> Het is een speller.

1148
00:58:20,410 --> 00:58:23,920
Gewoon niet knoeien met het, maar maak
ervoor dat je begrijpt wat het doet.

1149
00:58:23,920 --> 00:58:28,090
We maken gebruik van een functie genaamd getrusage dat
test de prestaties van uw spell

1150
00:58:28,090 --> 00:58:28,590
checker.

1151
00:58:28,590 --> 00:58:32,200
Alles wat het doet is eigenlijk het testen van de
de tijd van alles in je woordenboek,

1152
00:58:32,200 --> 00:58:33,680
dus zorg ervoor dat je het begrijpt.

1153
00:58:33,680 --> 00:58:36,660
Wees voorzichtig om niet knoeien met het of
anders dingen niet goed lopen.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> En het grootste deel van deze uitdaging is voor
jullie echt dictionary.c wijzigen.

1156
00:58:44,170 --> 00:58:48,526
We gaan u
140.000 woorden in een woordenboek.

1157
00:58:48,526 --> 00:58:50,900
We gaan u een tekst te geven
bestand dat die woorden heeft,

1158
00:58:50,900 --> 00:58:54,840
en we willen dat je in staat zijn om te organiseren
ze in een hash tabel of een trie

1159
00:58:54,840 --> 00:58:58,140
want als wij vragen u te spellen
check-- stel als je spell

1160
00:58:58,140 --> 00:59:00,690
zoals het controleren van de Odyssee van Homerus.

1161
00:59:00,690 --> 00:59:03,010
Het is als deze enorme, enorme beproeving.

1162
00:59:03,010 --> 00:59:05,190
>> Stel je voor dat elke
word je moest kijken

1163
00:59:05,190 --> 00:59:08,100
door middel van een reeks van 140.000 waarden.

1164
00:59:08,100 --> 00:59:10,350
Dat zou een eeuwigheid duren
voor uw machine te draaien.

1165
00:59:10,350 --> 00:59:14,490
Daarom willen we onze organisatie
data naar efficiëntere datastructuren

1166
00:59:14,490 --> 00:59:17,270
zoals een hash tafel of een trie.

1167
00:59:17,270 --> 00:59:20,700
En dan kunnen jullie soort
wanneer je toegang zoeken

1168
00:59:20,700 --> 00:59:22,570
dingen makkelijker en sneller.

1169
00:59:22,570 --> 00:59:24,934
>> En dus wees voorzichtig om botsingen te lossen.

1170
00:59:24,934 --> 00:59:27,350
Je gaat om een ​​bos te krijgen
van woorden die beginnen met A.

1171
00:59:27,350 --> 00:59:29,957
Je gaat naar een bos woorden krijgen
die beginnen met B. Tot u

1172
00:59:29,957 --> 00:59:31,290
jongens hoe je wilt het op te lossen.

1173
00:59:31,290 --> 00:59:34,144
Misschien is er meer
efficiënte hash-functie

1174
00:59:34,144 --> 00:59:36,810
dan alleen de eerste letter van
iets, en dat is aan jou

1175
00:59:36,810 --> 00:59:38,190
jongens soort doen wat je wilt.

1176
00:59:38,190 --> 00:59:40,148
>> Misschien dat u wilt toevoegen
alle letters bij elkaar.

1177
00:59:40,148 --> 00:59:43,410
Misschien wil je graag doen rare dingen
het aantal letters account,

1178
00:59:43,410 --> 00:59:43,970
boeiend.

1179
00:59:43,970 --> 00:59:45,386
Tot jullie hoe je wilt doen.

1180
00:59:45,386 --> 00:59:49,262
Als u wilt een hash tafel te doen, als je
willen een trie proberen, helemaal aan jou.

1181
00:59:49,262 --> 00:59:52,470
Ik zal je op voorhand te waarschuwen voor de tijd dat de
trie is meestal een beetje moeilijker

1182
00:59:52,470 --> 00:59:54,520
gewoon omdat er veel
Meer tips om bij te houden.

1183
00:59:54,520 --> 00:59:55,645
Maar helemaal aan jullie.

1184
00:59:55,645 --> 00:59:58,742
Het is veel efficiënter
in de meeste gevallen.

1185
00:59:58,742 --> 01:00:01,450
Je wilt echt te kunnen blijven
spoor al uw pointers.

1186
01:00:01,450 --> 01:00:03,850
Net hetzelfde doen
dat ik hier aan het doen.

1187
01:00:03,850 --> 01:00:06,871
Wanneer je probeert in te voegen
waarden in een hash tabel of te verwijderen,

1188
01:00:06,871 --> 01:00:08,620
zorg ervoor dat je bent
echt bijhouden

1189
01:00:08,620 --> 01:00:11,860
van waar alles is omdat
het is echt makkelijk voor als ik

1190
01:00:11,860 --> 01:00:14,727
proberen in te voegen als het woord, andy.

1191
01:00:14,727 --> 01:00:16,810
Laten we zeggen dat het een
echt woord, het woord, andy,

1192
01:00:16,810 --> 01:00:19,640
in een gigantische lijst van A woorden.

1193
01:00:19,640 --> 01:00:22,450
>> Als ik toevallig toewijzen
een pointer fout, oops,

1194
01:00:22,450 --> 01:00:24,940
daar gaat het geheel van
de rest van mijn gekoppelde lijst.

1195
01:00:24,940 --> 01:00:26,897
Nu is het enige woord dat ik
hebben is andy, en nu

1196
01:00:26,897 --> 01:00:29,230
alle andere woorden
woordenboek zijn verloren gegaan.

1197
01:00:29,230 --> 01:00:31,370
En dus wilt u ervoor zorgen dat u
bijhouden van al uw pointers

1198
01:00:31,370 --> 01:00:33,661
of anders je gaat krijgen
grote problemen in uw code.

1199
01:00:33,661 --> 01:00:35,840
Trekken dingen zorgvuldig stap voor stap.

1200
01:00:35,840 --> 01:00:37,870
Het maakt het een stuk makkelijker om te bedenken.

1201
01:00:37,870 --> 01:00:40,910
>> En tot slot, wil je in staat zijn om
test uw prestaties van uw programma

1202
01:00:40,910 --> 01:00:41,618
op het grote bord.

1203
01:00:41,618 --> 01:00:43,710
Als jullie nemen
kijk naar CS50 nu,

1204
01:00:43,710 --> 01:00:45,210
wij hebben wat heet de groot bord.

1205
01:00:45,210 --> 01:00:50,200
Het is het scoreblad van de snelste
spellingscontrole keer in al CS50

1206
01:00:50,200 --> 01:00:55,720
nu, ik denk dat de top, zoals 10
keren dat ik denk dat acht van hen zijn medewerkers.

1207
01:00:55,720 --> 01:00:57,960
We willen dat jullie ons verslaan.

1208
01:00:57,960 --> 01:01:00,870
>> Ieder van ons probeerden uit te voeren
de snelste code mogelijk.

1209
01:01:00,870 --> 01:01:04,880
We willen dat jullie proberen aan te vechten
ons en implementeren sneller dan ons allemaal

1210
01:01:04,880 --> 01:01:05,550
kan.

1211
01:01:05,550 --> 01:01:07,970
En dus dit is echt
de eerste keer dat we

1212
01:01:07,970 --> 01:01:12,680
vragen jullie om een ​​PSET doen
kan je echt doen in welke methode

1213
01:01:12,680 --> 01:01:13,760
jij wil.

1214
01:01:13,760 --> 01:01:17,730
>> Ik zeg altijd, dit is meer verwant
een echte oplossing, toch?

1215
01:01:17,730 --> 01:01:19,550
Ik zeg, hey, ik heb je nodig om dit te doen.

1216
01:01:19,550 --> 01:01:21,380
Bouwen van een programma dat dit doet voor mij.

1217
01:01:21,380 --> 01:01:22,630
Doe het zoals u dat wilt.

1218
01:01:22,630 --> 01:01:24,271
Ik weet alleen dat ik wil vasten.

1219
01:01:24,271 --> 01:01:25,770
Dat is jouw uitdaging voor deze week.

1220
01:01:25,770 --> 01:01:27,531
Jongens, we gaan
om u een taak.

1221
01:01:27,531 --> 01:01:29,030
We gaan om u een uitdaging te geven.

1222
01:01:29,030 --> 01:01:31,559
En dan is het aan jullie
volledig gewoon uitzoeken

1223
01:01:31,559 --> 01:01:34,100
wat is de snelste en meest
efficiënte manier om dit te implementeren.

1224
01:01:34,100 --> 01:01:34,600
Ja?

1225
01:01:34,600 --> 01:01:37,476
>> Publiek: Mogen we als
wilde snellere manieren onderzoeken

1226
01:01:37,476 --> 01:01:40,821
om hash tabellen online doen, kunnen we doen
en dat noemen de code van iemand anders?

1227
01:01:40,821 --> 01:01:42,070
ANDI Peng: Ja, helemaal prima.

1228
01:01:42,070 --> 01:01:44,320
Dus als lezen jullie de
spec, is er een lijn

1229
01:01:44,320 --> 01:01:48,310
in de spec dat jullie zegt
zijn volledig vrij om hash onderzoek

1230
01:01:48,310 --> 01:01:51,070
functies op wat zijn sommige
van de snellere hash functies

1231
01:01:51,070 --> 01:01:54,720
om dingen te lopen door als
Zolang je die code noemen.

1232
01:01:54,720 --> 01:01:57,220
Dus sommige mensen al hebben
bedacht snelle manieren

1233
01:01:57,220 --> 01:02:00,250
van het doen van spellingcontrole, van snelle
manieren opslaan van informatie.

1234
01:02:00,250 --> 01:02:02,750
Helemaal aan jullie als je
willen gewoon dat, toch?

1235
01:02:02,750 --> 01:02:04,045
Zorg ervoor dat je citeert.

1236
01:02:04,045 --> 01:02:06,170
De uitdaging hier echt
dat we proberen om te testen

1237
01:02:06,170 --> 01:02:09,750
is ervoor te zorgen dat je weet
je weg pointers.

1238
01:02:09,750 --> 01:02:12,700
Voor zover u de uitvoering
de werkelijke hashfunctie

1239
01:02:12,700 --> 01:02:15,070
en komen met als
de wiskunde om dat te doen,

1240
01:02:15,070 --> 01:02:17,570
jullie kunnen onderzoeken wat
methoden online jullie willen.

1241
01:02:17,570 --> 01:02:17,996
Ja?

1242
01:02:17,996 --> 01:02:19,700
>> Publiek: Kunnen we citeren net
met behulp van de [onverstaanbaar]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI PENG: Ja.

1244
01:02:20,120 --> 01:02:22,328
Je kunt gewoon in uw commentaar,
U kunt noemen zoals, oh,

1245
01:02:22,328 --> 01:02:26,127
genomen van yada, yada,
yada, hash-functie.

1246
01:02:26,127 --> 01:02:27,210
Iemand nog vragen?

1247
01:02:27,210 --> 01:02:29,694
We eigenlijk breezed
door middel van sectie vandaag.

1248
01:02:29,694 --> 01:02:31,610
Ik zal hier zijn om
vragen te beantwoorden als goed.

1249
01:02:31,610 --> 01:02:36,570
>> Ook, zoals ik al zei, kantoor
uur vanavond en morgen.

1250
01:02:36,570 --> 01:02:40,307
De specificatie van deze week is eigenlijk
super makkelijk en super kort te lezen.

1251
01:02:40,307 --> 01:02:43,140
Ik stel het nemen van een kijkje, net
Lees de onderdelen ervan.

1252
01:02:43,140 --> 01:02:45,730
>> En Zamyla eigenlijk loopt u
door elk van de functies

1253
01:02:45,730 --> 01:02:49,796
je nodig hebt om te implementeren, en dus is het
heel, heel duidelijk hoe om alles te doen.

1254
01:02:49,796 --> 01:02:51,920
Gewoon om ervoor te zorgen dat u bent
het bijhouden van pointers.

1255
01:02:51,920 --> 01:02:53,650
Dit is een zeer uitdagende PSET.

1256
01:02:53,650 --> 01:02:56,744
>> Het is niet uitdagend want zoals,
oh, de begrippen zijn zo veel meer

1257
01:02:56,744 --> 01:02:59,160
moeilijk, of je moet leren
zo veel nieuwe syntaxis de weg

1258
01:02:59,160 --> 01:03:00,650
dat je deed voor de laatste PSET.

1259
01:03:00,650 --> 01:03:03,320
Dit PSET is moeilijk, omdat
er zijn zo veel pointers,

1260
01:03:03,320 --> 01:03:06,980
en dan is het heel, heel gemakkelijk om een ​​keer
je hebt een fout in uw code niet kunnen

1261
01:03:06,980 --> 01:03:08,315
te vinden waar dat fout is.

1262
01:03:08,315 --> 01:03:13,200
>> En zo volslagen vertrouwen in u
jongens in staat zijn om onze [onverstaanbaar] verslaan

1263
01:03:13,200 --> 01:03:13,700
spellingen.

1264
01:03:13,700 --> 01:03:16,640
Ik heb eigenlijk geen schriftelijke mijne
nog niet, maar ik ben op het punt om de mijne te schrijven.

1265
01:03:16,640 --> 01:03:19,070
Dus terwijl je schrijft
van jou, zal ik schrijven de mijne.

1266
01:03:19,070 --> 01:03:21,070
Ik ga proberen te maken
mijne sneller dan de jouwe.

1267
01:03:21,070 --> 01:03:23,940
We zullen zien wie de snelste is.

1268
01:03:23,940 --> 01:03:27,340
>> En ja, ik zal alles zien
jullie hier op dinsdag.

1269
01:03:27,340 --> 01:03:29,510
Ik zal een soort als een PSET workshop draaien.

1270
01:03:29,510 --> 01:03:32,640
Alle secties deze
week zijn PSET workshops,

1271
01:03:32,640 --> 01:03:36,690
Dus jullie hebben veel kansen
voor hulp, kantooruren zoals altijd,

1272
01:03:36,690 --> 01:03:41,330
en ik kijk uit naar
het lezen van al uw jongens 'code.

1273
01:03:41,330 --> 01:03:44,160
Ik heb quizzen hier als u
jongens willen komen halen die.

1274
01:03:44,160 --> 01:03:45,880
Dat is alles.

1275
01:03:45,880 --> 01:03:48,180