1
00:00:00,000 --> 00:00:02,740
[Powered by Google Translate] [Walkthrough - Probleem Set 5]

2
00:00:02,740 --> 00:00:04,870
[Zamyla Chan - Harvard University]

3
00:00:04,870 --> 00:00:07,190
[Dit is CS50. - CS50.TV]

4
00:00:07,190 --> 00:00:10,400
>> Oke. Hallo, iedereen, en welkom bij Walkthrough 5.

5
00:00:10,400 --> 00:00:17,400
>> Pset5 is Spelfouten, waarin we een spellingcontrole worden maken.

6
00:00:17,400 --> 00:00:21,030
Spell-checkers zijn uiterst belangrijk.

7
00:00:21,030 --> 00:00:23,390
Is dit ooit overkomen?

8
00:00:23,390 --> 00:00:27,170
Je werkt zeer, zeer oppotten op een papier voor een botsing

9
00:00:27,170 --> 00:00:33,120
en dan nog uiteindelijk het krijgen van een zeer gloed rade als een D-of een D =

10
00:00:33,120 --> 00:00:39,390
en dat allemaal omdat je de leverworst spoiler in de walvis breed woord.

11
00:00:39,390 --> 00:00:44,710
Ja, proeflezen uw paprika's is een kwestie van de, de grootst mogelijke impotentie.

12
00:00:44,710 --> 00:00:49,140
Dit is een probleem dat mannelijke, mannelijke studenten beïnvloedt.

13
00:00:49,140 --> 00:00:56,260
Ik werd ooit verteld door mijn sith graad folteraar die ik nooit zou krijgen in een goede collega.

14
00:00:56,260 --> 00:01:00,250
En dat is alles wat ik ooit wilde, dat is alles wat elk kind wil op mijn leeftijd,

15
00:01:00,250 --> 00:01:04,569
gewoon om in een goede collega.

16
00:01:04,569 --> 00:01:12,720
En niet zomaar een collega. Nee, ik wilde naar een Ivory Legal collega.

17
00:01:12,720 --> 00:01:18,360
Dus als ik het niet deed verbetering, zou gegaan zijn mijn dromen van naar Harvard,

18
00:01:18,360 --> 00:01:22,730
Jale, of Gevangenis - je weet wel, in Gevangenis, New Jersey.

19
00:01:22,730 --> 00:01:25,170
Dus ik heb mezelf een spellingcontrole.

20
00:01:25,170 --> 00:01:29,380
Dat is een fragment uit een van mijn favoriete spoken word artiesten, Taylor Mali.

21
00:01:29,380 --> 00:01:34,630
Hoe dan ook, zoals hij zegt, het belang van het hebben van een spellingcontrole is erg belangrijk.

22
00:01:34,630 --> 00:01:39,440
>> Dus welkom om Walkthrough 5, waarin we het zullen hebben over pset5: spelfouten,

23
00:01:39,440 --> 00:01:44,300
waarin wij zal het maken van onze eigen spell-checker.

24
00:01:44,300 --> 00:01:50,880
De toolbox voor deze week, de verdeelsleutel, zal van belang om te kijken naar

25
00:01:50,880 --> 00:01:54,950
alleen maar om de verschillende functies die uw woordenboek zal moeten begrijpen.

26
00:01:54,950 --> 00:02:01,500
We zijn eigenlijk gaan worden het hebben van meerdere. C bestanden die samen onze PSET.

27
00:02:01,500 --> 00:02:05,420
En dus kijken door de verschillende aspecten, hoewel we in feite niet aan het wijzigen

28
00:02:05,420 --> 00:02:10,770
een van de bestanden, speller.c, weten hoe het werkt met betrekking tot dictionary.c,

29
00:02:10,770 --> 00:02:14,100
die we zullen schrijven, zal worden erg belangrijk.

30
00:02:14,100 --> 00:02:16,970
De PSET spec bevat ook veel nuttige informatie

31
00:02:16,970 --> 00:02:21,360
in termen van dingen die je kunt aannemen, regels en dat soort dingen,

32
00:02:21,360 --> 00:02:24,710
dus zorg ervoor dat de PSET spec zorgvuldig te lezen voor tips.

33
00:02:24,710 --> 00:02:29,310
En bij twijfel van een regel of iets dergelijks, dan altijd verwijzen naar de PSET spec

34
00:02:29,310 --> 00:02:31,550
of Bespreek.

35
00:02:31,550 --> 00:02:34,060
Dit PSET gaat sterk afhankelijk zijn van pointers,

36
00:02:34,060 --> 00:02:37,890
dus we willen ervoor zorgen dat we het verschil tussen het toevoegen sterren te begrijpen

37
00:02:37,890 --> 00:02:41,680
voor de naam van de aanwijzer en ampersands, hoe ze te bevrijden, enz.

38
00:02:41,680 --> 00:02:47,550
Dus als een meester van pointers zal zeer nuttig zijn in dit probleem set.

39
00:02:47,550 --> 00:02:50,460
We gaan kijken naar gelinkte lijsten een beetje meer,

40
00:02:50,460 --> 00:02:57,790
waar we elementen we knooppunten die zowel een waarde en een pointer hebben voldoende

41
00:02:57,790 --> 00:03:02,520
naar het volgende knooppunt, en dus in wezen verbinden van verschillende elementen na elkaar.

42
00:03:02,520 --> 00:03:07,190
Er zijn een paar verschillende opties van de uitvoering van uw werkelijke woordenboek.

43
00:03:07,190 --> 00:03:13,150
We gaan kijken naar twee belangrijkste methoden, die hash tabellen en vervolgens probeert.

44
00:03:13,150 --> 00:03:17,660
In deze beide brengen ze een soort begrip verbonden lijst

45
00:03:17,660 --> 00:03:20,790
waar u met elkaar verbonden elementen aan elkaar.

46
00:03:20,790 --> 00:03:25,640
En dus we gaan om te kijken over hoe je zou kunnen werken rond gelinkte lijsten,

47
00:03:25,640 --> 00:03:29,680
deze maken, navigeert u in termen van hoe je, bijvoorbeeld, plaatst u een knooppunt in het

48
00:03:29,680 --> 00:03:32,760
of vrije alle knooppunten ook.

49
00:03:32,760 --> 00:03:34,740
In termen van het vrijmaken van knooppunten, dat is echt belangrijk

50
00:03:34,740 --> 00:03:37,700
dat wanneer we malloc geheugen achteraf, we bevrijden.

51
00:03:37,700 --> 00:03:42,910
Dus we willen ervoor zorgen dat er geen wijzer unfreed gaat, dat we geen geheugenlekken hebben.

52
00:03:42,910 --> 00:03:48,330
We gaan een tool genaamd Valgrind dat uw programma wordt uitgevoerd introduceren

53
00:03:48,330 --> 00:03:52,260
en controleert of al het geheugen dat u toegewezen wordt dan bevrijd.

54
00:03:52,260 --> 00:03:59,080
Uw PSET is pas compleet als het werkt en het heeft volledige functionaliteit,

55
00:03:59,080 --> 00:04:03,990
maar ook, Valgrind je vertelt dat je er is geen geheugenlekken gevonden.

56
00:04:03,990 --> 00:04:06,690
Tot slot, voor deze PSET, ik wil echt benadrukken -

57
00:04:06,690 --> 00:04:11,360
Ik bedoel, zoals gewoonlijk, ik ben zeker een voorstander van het gebruik van pen en papier voor uw probleem sets,

58
00:04:11,360 --> 00:04:14,840
maar voor deze ene, ik denk dat pen en papier gaat worden met name van belang

59
00:04:14,840 --> 00:04:19,000
wanneer u wilt worden tekenen pijlen om dingen en te begrijpen hoe dingen werken.

60
00:04:19,000 --> 00:04:24,440
Dus zeker proberen om pen en papier te gebruiken om dingen te trekken uit voordat u aan de codering

61
00:04:24,440 --> 00:04:26,970
want het kan een beetje rommelig.

62
00:04:26,970 --> 00:04:30,700
>> Laten we eerst eens gaan in gelinkte lijsten een beetje.

63
00:04:30,700 --> 00:04:35,510
Gelinkte lijsten bestaan ​​uit knooppunten, waar elke knoop heeft een waarde die ermee verbonden zijn,

64
00:04:35,510 --> 00:04:39,810
en een pointer naar het volgende knooppunt na.

65
00:04:39,810 --> 00:04:43,680
Een paar dingen van belang bij de gelinkte lijsten zijn die we nodig hebben om te onthouden

66
00:04:43,680 --> 00:04:48,810
waar onze eerste knooppunt is, en dan als we eenmaal weten waar het eerste knooppunt is,

67
00:04:48,810 --> 00:04:52,990
op die manier kunnen we toegang krijgen tot het knooppunt dat het eerste knooppunt wijst naar

68
00:04:52,990 --> 00:04:55,850
en degene daarna en die daarna.

69
00:04:55,850 --> 00:05:00,340
En dan het laatste element in de gelinkte lijst is dat knooppunt wijzer

70
00:05:00,340 --> 00:05:02,340
zal altijd wijzen op NULL.

71
00:05:02,340 --> 00:05:08,230
Wanneer een knooppunt punten op NULL, dan weet je dat je hebt aan het einde van de lijst bereikt,

72
00:05:08,230 --> 00:05:12,320
dat dat knooppunt is de laatste, dat er niets na dat.

73
00:05:12,320 --> 00:05:16,970
Hier in dit schema, zie je dat de pijlen zijn de pointers,

74
00:05:16,970 --> 00:05:20,290
en het blauwe deel is waar de waarde is opgeslagen,

75
00:05:20,290 --> 00:05:24,420
en dan de rode doos met de aanwijzer naar het is de node wijzer

76
00:05:24,420 --> 00:05:27,050
wijst naar het volgende knooppunt na.

77
00:05:27,050 --> 00:05:33,730
En zo zie je hier, zou de D knooppunt wijzen op NULL omdat het het laatste element in de lijst.

78
00:05:33,730 --> 00:05:38,240
>> Laten we eens kijken hoe we misschien een struct te definiëren voor een knooppunt.

79
00:05:38,240 --> 00:05:40,130
En omdat we willen meerdere nodes hebben,

80
00:05:40,130 --> 00:05:43,180
dit gaat om een ​​typedef struct geworden

81
00:05:43,180 --> 00:05:46,870
waarin we gaan naar verschillende gevallen van knooppunten.

82
00:05:46,870 --> 00:05:50,850
En dus hebben we definiëren als een nieuw gegevenstype.

83
00:05:50,850 --> 00:05:53,630
Hier hebben we een typedef struct node.

84
00:05:53,630 --> 00:05:56,160
In dit voorbeeld gaan we te maken met integer knooppunten,

85
00:05:56,160 --> 00:06:00,490
dus we hebben een integer met de naam waarde en dan hebben we nog een pointer,

86
00:06:00,490 --> 00:06:07,390
en in dit geval, het is een pointer naar een node, dus we hebben een struct knoop * genaamd volgende.

87
00:06:07,390 --> 00:06:09,520
En dan zijn we noemen dit alles node.

88
00:06:09,520 --> 00:06:11,110
Zorg ervoor dat u deze syntax volgen.

89
00:06:11,110 --> 00:06:17,940
Merk op dat knooppunt is in feite verwezen up zowel boven als onder de accolades.

90
00:06:17,940 --> 00:06:23,400
Dan bij te houden waar mijn eerste node is in deze gelinkte lijst,

91
00:06:23,400 --> 00:06:29,390
dan heb ik een knoop pointer genaamd hoofd, en ik malloc ruimte genoeg voor de grootte van een knoop.

92
00:06:29,390 --> 00:06:36,240
Notice echter dat hoofd eigenlijk een knooppunt pointer in tegenstelling tot een werkelijke knoop zelf.

93
00:06:36,240 --> 00:06:40,130
Dus het hoofd doet eigenlijk bevat geen waarde,

94
00:06:40,130 --> 00:06:45,590
het wijst alleen naar welke het eerste knooppunt in mijn gelinkte lijst is.

95
00:06:55,080 --> 00:06:58,340
>> Om een ​​beter idee van gekoppelde lijsten te krijgen, want het is heel belangrijk

96
00:06:58,340 --> 00:07:02,220
bij te houden om ervoor te zorgen dat u de ketting te houden,

97
00:07:02,220 --> 00:07:09,990
Ik denk graag dat het als mensen in een lijn hand in hand,

98
00:07:09,990 --> 00:07:14,330
waar elke persoon hand in hand met de volgende.

99
00:07:14,330 --> 00:07:18,350
Je kunt niet zien in deze tekening, maar in principe zijn ze wijzend naar de volgende persoon

100
00:07:18,350 --> 00:07:23,760
die in de keten.

101
00:07:23,760 --> 00:07:29,270
En dus als je wilt een gelinkte lijst waar deze mensen doorkruisen -

102
00:07:29,270 --> 00:07:32,830
stel je al die mensen hebben waarden die met hen

103
00:07:32,830 --> 00:07:36,590
en wijzen ook op de volgende persoon in de rij -

104
00:07:36,590 --> 00:07:40,810
als je wilt de gelinkte lijst doorlopen, bijvoorbeeld, om ofwel de waarden bewerken

105
00:07:40,810 --> 00:07:42,830
of zoeken naar een waarde of iets dergelijks,

106
00:07:42,830 --> 00:07:48,270
dan zul je met een pointer naar de specifieke persoon.

107
00:07:48,270 --> 00:07:52,670
Dus we gaan naar een gegevenstype knooppunt pointer te hebben.

108
00:07:52,670 --> 00:07:55,580
Voor dit geval, is het wel de cursor.

109
00:07:55,580 --> 00:07:59,630
Een andere veel voorkomende manier om dit te noemen zou iterator of iets dergelijks zijn

110
00:07:59,630 --> 00:08:05,130
omdat het itereren over en eigenlijk bewegen welk knooppunt het is te wijzen op.

111
00:08:05,130 --> 00:08:14,410
Dit hier onze cursor.

112
00:08:14,410 --> 00:08:20,180
Onze cursor zal eerst wijzen op het eerste element in onze lijst.

113
00:08:20,180 --> 00:08:26,910
En dus wat we willen doen is dat we zouden in principe worden de voortzetting van de cursor,

114
00:08:26,910 --> 00:08:29,130
verplaatsen van links naar rechts.

115
00:08:29,130 --> 00:08:33,409
In dit geval willen we verplaatsen naar het volgende element in de lijst.

116
00:08:33,409 --> 00:08:38,480
Met arrays, wat we zouden doen is dat we zouden we zeggen dat we de index met 1 te verhogen.

117
00:08:38,480 --> 00:08:46,020
In dit geval is wat we moeten doen eigenlijk vinden welke persoon deze stroom persoon wordt verwezen,

118
00:08:46,020 --> 00:08:48,930
en dat gaat naar de volgende waarde te zijn.

119
00:08:48,930 --> 00:08:53,230
Dus als de cursor bevindt zich op slechts een knooppunt aanwijzer, dan wat we willen doen

120
00:08:53,230 --> 00:08:56,320
is dat we willen krijgen op de waarde die de cursor op.

121
00:08:56,320 --> 00:09:01,350
We willen naar die node en dan, als we op dat knooppunt, vinden waar het naar verwijst.

122
00:09:01,350 --> 00:09:05,820
Om naar de werkelijke knooppunt dat de cursor op,

123
00:09:05,820 --> 00:09:13,160
Meestal geven we aan door (* cursor).

124
00:09:13,160 --> 00:09:19,160
Dat zou geven u de werkelijke knooppunt dat de cursor op.

125
00:09:19,160 --> 00:09:21,730
En dan na dat, wat we willen doen is dat we toegang wilt

126
00:09:21,730 --> 00:09:25,680
wat dat dan ook node volgende waarde is.

127
00:09:25,680 --> 00:09:32,820
Om dat te doen, om de waarden binnenkant van de struct toegang, hebben we de puntoperator.

128
00:09:32,820 --> 00:09:39,530
Dus dan zou het (* cursor). Volgende.

129
00:09:39,530 --> 00:09:44,840
Maar dit is een beetje rommelig in termen van het hebben van de haakjes rond de * cursor,

130
00:09:44,840 --> 00:09:56,800
en dus vervangen we dit hele verklaring met de cursor->.

131
00:09:56,800 --> 00:10:02,700
Dit is een streepje en dan een groter dan teken, dus het maken van een pijl.

132
00:10:02,700 --> 00:10:05,840
cursor-> volgende.

133
00:10:05,840 --> 00:10:12,390
Dat is eigenlijk krijgt u het knooppunt dat de cursor op. Die waarde is van het volgende.

134
00:10:12,390 --> 00:10:16,790
Dus in plaats van de ster en de stip, je vervangt die met een pijl.

135
00:10:16,790 --> 00:10:24,820
Wees erg voorzichtig om ervoor te zorgen dat u probeert om deze syntax te gebruiken.

136
00:10:33,550 --> 00:10:37,620
>> Nu hebben we onze cursor, als we willen dat de waarde toegang te krijgen,

137
00:10:37,620 --> 00:10:40,450
eerder hadden we de cursor-> volgende,

138
00:10:40,450 --> 00:10:46,260
maar om de waarde op het knooppunt dat de cursor om toegang te krijgen, hebben we gewoon zeggen

139
00:10:46,260 --> 00:10:48,070
node-> waarde.

140
00:10:48,070 --> 00:10:53,600
Vanaf daar is het van het gegevenstype wat we hebben de waarden en de knooppunten zijn gedefinieerd.

141
00:10:53,600 --> 00:10:59,620
Als het een int knooppunt, dan cursor-> waarde wordt gewoon een geheel getal zijn.

142
00:10:59,620 --> 00:11:04,870
Dus we kunnen bewerkingen doen op die, controleer gelijkheden, toewijzen verschillende waarden, enz.

143
00:11:04,870 --> 00:11:11,090
Dus wat je wilt doen als je wilt om de cursor te verplaatsen naar de volgende persoon,

144
00:11:11,090 --> 00:11:15,270
je eigenlijk de waarde van de cursor.

145
00:11:15,270 --> 00:11:19,340
Omdat cursor is een knooppunt aanwijzer, wijzigt u de actuele pointer adres

146
00:11:19,340 --> 00:11:23,890
aan het adres van het volgende knooppunt in uw lijst.

147
00:11:23,890 --> 00:11:28,930
Dit is slechts een code waar je kon herhalen.

148
00:11:28,930 --> 00:11:31,230
Waar heb ik de opmerking iets doen,

149
00:11:31,230 --> 00:11:33,850
dat is waar je waarschijnlijk gaan om de waarde te openen

150
00:11:33,850 --> 00:11:37,850
of iets te maken heeft met die specifieke knooppunt.

151
00:11:37,850 --> 00:11:43,050
Om het te beginnen, ik zeg dat mijn cursor in eerste instantie

152
00:11:43,050 --> 00:11:48,430
zal wijzen op het eerste element in de gekoppelde lijst.

153
00:11:48,430 --> 00:11:52,910
En dus verderop, ik gedefinieerd als het hoofd van het knooppunt.

154
00:11:52,910 --> 00:11:57,610
>> Zoals ik al zei, het vrijmaken is echt belangrijk.

155
00:11:57,610 --> 00:12:02,440
U wilt ervoor zorgen dat u elk element vrij in de lijst als je eenmaal klaar bent met het.

156
00:12:02,440 --> 00:12:04,940
Wanneer je hoeft niet meer te verwijzen naar een van deze pointers,

157
00:12:04,940 --> 00:12:10,620
wilt u ervoor zorgen dat u al die verwijzingen te bevrijden.

158
00:12:10,620 --> 00:12:14,460
Maar je wilt hier heel voorzichtig zijn in dat u wilt een geheugen lekkage te voorkomen.

159
00:12:14,460 --> 00:12:25,080
Als u gratis een persoon te vroeg, dan is alle aanwijzingen die die knooppunten te

160
00:12:25,080 --> 00:12:26,900
zullen verloren gaan.

161
00:12:26,900 --> 00:12:32,070
Terug te gaan naar de persoon voorbeeld om het een beetje meer high stakes,

162
00:12:32,070 --> 00:12:49,600
laten we deze mensen, behalve in dit geval worden ze zweven boven een meer met een monster.

163
00:12:49,600 --> 00:12:53,200
We willen ervoor zorgen dat wanneer we vrij, we niet verliezen

164
00:12:53,200 --> 00:12:58,920
en laat elke nodes voordat we echt bevrijd ze.

165
00:12:58,920 --> 00:13:05,730
Bijvoorbeeld, als je gewoon hier te bellen gratis op deze man,

166
00:13:05,730 --> 00:13:15,350
dan zou hij worden vrijgelaten, maar dan al deze jongens zou dan verloren gaan

167
00:13:15,350 --> 00:13:18,450
en ze zouden afdrijven en naar beneden vallen.

168
00:13:18,450 --> 00:13:24,900
Dus we willen ervoor zorgen dat in plaats daarvan willen we een link naar de rest te behouden.

169
00:13:37,630 --> 00:13:42,480
Ons hoofd pointer, die wijst naar het eerste element in de lijst.

170
00:13:42,480 --> 00:13:49,990
Het is een soort van een touw het verankeren van de eerste persoon.

171
00:13:52,870 --> 00:13:57,470
Wat je zou willen doen als je te bevrijden van een lijst hebben -

172
00:13:57,470 --> 00:14:04,520
Als u wilt dat het eerste element eerste vrije, dan kunt u een tijdelijke pointer

173
00:14:04,520 --> 00:14:07,370
die naar wat het eerste element.

174
00:14:07,370 --> 00:14:11,420
Dus je hebt je tijdelijke pointer die wijst hier.

175
00:14:11,420 --> 00:14:15,840
Op die manier hebben we een greep van het eerste knooppunt.

176
00:14:15,840 --> 00:14:18,930
En dan, omdat we weten dat het eerste knooppunt zal worden bevrijd,

177
00:14:18,930 --> 00:14:24,890
dan kunnen we gaan dit touw, dit anker, ons hoofd,

178
00:14:24,890 --> 00:14:31,930
om daadwerkelijk wijzen op wat de eerste wijst.

179
00:14:31,930 --> 00:14:38,760
Dus dit hoofd wijst eigenlijk aan het tweede element nu.

180
00:14:38,760 --> 00:14:43,980
Nu mogen we vrij wat er opgeslagen in temp,

181
00:14:43,980 --> 00:14:53,360
en zo kunnen we wissen dat zonder het in gevaar te brengen alle de andere knooppunten in onze lijst.

182
00:14:54,140 --> 00:15:05,020
Een andere manier die je kan dit niet, dan kan worden

183
00:15:05,020 --> 00:15:08,650
elke keer dat je gewoon vrij het laatste element in de lijst

184
00:15:08,650 --> 00:15:11,010
omdat ze gegarandeerd niet te worden gewezen op wat dan ook.

185
00:15:11,010 --> 00:15:15,570
Dus je zou kunnen gewoon gratis deze ene, dan vrij deze, dan is gratis deze.

186
00:15:15,570 --> 00:15:21,900
Dat is zeker werkt, maar is een beetje trager, omdat door de aard van de gelinkte lijsten,

187
00:15:21,900 --> 00:15:24,670
we kunnen niet zomaar direct naar de laatste.

188
00:15:24,670 --> 00:15:28,030
We moeten elk element doorlopen in de verbonden lijst

189
00:15:28,030 --> 00:15:31,020
en controleer of dat men wijst op NULL, check elke keer,

190
00:15:31,020 --> 00:15:33,780
en dan als we eenmaal aan het einde, dan vrij dat.

191
00:15:33,780 --> 00:15:40,270
Als je aan dit proces te doen, zou je eigenlijk hier controleren,

192
00:15:40,270 --> 00:15:44,190
het controleren van hier, dan het controleren van hier, het vrijmaken van het,

193
00:15:44,190 --> 00:15:47,470
dan terug te gaan, het controleren van hier, het controleren van hier, het vrijmaken van het,

194
00:15:47,470 --> 00:15:49,660
controleren hier en ontdoen.

195
00:15:49,660 --> 00:15:52,880
Dat kost wat meer tijd. Ja.

196
00:15:52,880 --> 00:15:59,060
>> [Student] Zou het mogelijk zijn om een ​​gekoppelde lijst die een exit wijzer slaat naar het einde te maken?

197
00:15:59,060 --> 00:16:01,320
Dat zou zeker mogelijk zijn.

198
00:16:01,320 --> 00:16:08,340
Nogmaals de vraag, is het mogelijk om een ​​gekoppelde lijststructuur

199
00:16:08,340 --> 00:16:12,490
zodat een pointer wijst naar het eind van de verbonden lijst hebben?

200
00:16:12,490 --> 00:16:18,090
Ik zou zeggen dat mogelijk is, en elke keer dat je iets invoegen in uw gelinkte lijst

201
00:16:18,090 --> 00:16:21,470
je zou hebben om die wijzer en dat soort dingen bij te werken.

202
00:16:21,470 --> 00:16:26,640
Je zou een knooppunt * staart, bijvoorbeeld.

203
00:16:26,640 --> 00:16:29,840
Maar als je deze functie uitvoeren, moet u denken aan de trade-offs,

204
00:16:29,840 --> 00:16:32,700
zoals hoe vaak ga ik te itereren over deze,

205
00:16:32,700 --> 00:16:36,100
Hoe moeilijk is het gaat worden voor het bijhouden van de staart en de kop te houden

206
00:16:36,100 --> 00:16:38,400
en mijn iterator, en dat soort dingen.

207
00:16:40,730 --> 00:16:42,480
Is dat -? >> [Student] Ja.

208
00:16:42,480 --> 00:16:48,270
Het is mogelijk, maar in termen van ontwerpbeslissingen, moet u de opties af te wegen.

209
00:16:53,850 --> 00:17:01,090
>> Hier is een skelet van code die laat je toe om elk element te bevrijden in een gelinkte lijst.

210
00:17:01,090 --> 00:17:05,460
Nogmaals, aangezien ik itereren over een gelinkte lijst, ik ga wil een soort van de cursor zijn

211
00:17:05,460 --> 00:17:08,670
of iterator.

212
00:17:08,670 --> 00:17:14,640
We itereren totdat de cursor zich NULL.

213
00:17:14,640 --> 00:17:17,640
Je wilt niet te herhalen wanneer uw cursor NULL

214
00:17:17,640 --> 00:17:20,579
want dat betekent dat er niet iets in de lijst.

215
00:17:20,579 --> 00:17:25,069
Dus dan is hier maak ik een tijdelijke knoop *

216
00:17:25,069 --> 00:17:29,610
wijzen op wat ik overweeg is de eerste van mijn lijst,

217
00:17:29,610 --> 00:17:35,340
en dan verplaats ik mijn cursor vooruit 1 en dan vrij wat ik had in de tijdelijke opslag.

218
00:17:38,460 --> 00:17:43,650
>> Nu komen we bij het invoegen in gekoppelde lijsten.

219
00:18:00,200 --> 00:18:09,660
Ik heb drie knooppunten in mijn gelinkte lijst, en laten we gaan met het eenvoudige geval

220
00:18:09,660 --> 00:18:18,970
waar we willen naar een ander knooppunt te voegen aan het einde van onze gekoppelde lijst.

221
00:18:18,970 --> 00:18:25,980
Om dat te doen, al zouden we doen is dat we doorkruisen zouden

222
00:18:25,980 --> 00:18:32,100
te vinden waar de huidige einde van de gekoppelde lijst is, dus welke knoop wijst op NULL -

223
00:18:32,100 --> 00:18:33,850
dat is deze -

224
00:18:33,850 --> 00:18:37,260
en dan zeggen, eigenlijk, deze is niet van plan om de laatste node;

225
00:18:37,260 --> 00:18:39,830
we eigenlijk naar een andere een te hebben.

226
00:18:39,830 --> 00:18:46,260
Dus zouden we de huidige ene punt naar wat we het plaatsen.

227
00:18:46,260 --> 00:18:50,080
Dus nu deze rode persoon wordt hier het laatste knooppunt in de gelinkte lijst.

228
00:18:50,080 --> 00:18:56,080
En dat de karakteristiek van het laatste knooppunt in de gekoppelde lijst is dat het wijst NULL.

229
00:18:56,080 --> 00:19:09,380
Dus dan wat we zouden moeten doen is deze rode kerel aanwijzer op NULL. Er.

230
00:19:09,380 --> 00:19:25,370
>> Maar wat als we wilden een knooppunt in te voegen in tussen de tweede en derde?

231
00:19:25,370 --> 00:19:28,960
Die ene is niet zo eenvoudig, omdat we willen ervoor zorgen dat

232
00:19:28,960 --> 00:19:34,290
dat we niet laten gaan van een knooppunt in onze gelinkte lijst.

233
00:19:34,290 --> 00:19:43,450
Wat we zouden moeten doen is ervoor te zorgen dat we ons verankeren aan een ieder.

234
00:19:43,450 --> 00:19:49,900
Bijvoorbeeld, laten we noemen dit de tweede.

235
00:19:49,900 --> 00:19:54,390
Als je zei dat de tweede verwijst nu naar deze nieuwe

236
00:19:54,390 --> 00:20:02,520
en je zojuist een pointer daar, dan zou dat leiden tot deze man verloren

237
00:20:02,520 --> 00:20:07,830
want er is geen link naar hem.

238
00:20:07,830 --> 00:20:18,970
In plaats daarvan - Ik zal opnieuw te tekenen dit. Excuseer mijn artistieke capaciteiten.

239
00:20:18,970 --> 00:20:26,570
We weten dat we niet zomaar direct 2 te koppelen aan de nieuwe.

240
00:20:26,570 --> 00:20:30,480
We moeten ervoor zorgen dat we vasthouden aan de laatste.

241
00:20:30,480 --> 00:20:39,200
Wat wij zou willen doen is een tijdelijke pointer

242
00:20:39,200 --> 00:20:42,650
om het element dat gaat worden toegevoegd op.

243
00:20:42,650 --> 00:20:45,140
Dus dan hebben we er een tijdelijke pointer.

244
00:20:45,140 --> 00:20:50,780
Omdat we weten dat dit derde spoor wordt gehouden van,

245
00:20:50,780 --> 00:20:53,680
2 kan nu een link naar onze nieuwe.

246
00:20:53,680 --> 00:20:57,490
En als dit nieuwe rode man zal zijn tussen de 2 en 3,

247
00:20:57,490 --> 00:21:05,550
dan wat is die vent wijzer gaan om te verwijzen naar? >> [Student] Temp.

248
00:21:05,550 --> 00:21:07,490
Temp. Ja.

249
00:21:07,490 --> 00:21:15,430
Dus dan is deze rode kerel volgende waarde gaat worden temp.

250
00:21:26,090 --> 00:21:33,010
Als je het invoegen in gelinkte lijsten, zagen we dat we konden

251
00:21:33,010 --> 00:21:38,260
gemakkelijk iets toevoegen aan het einde van het creëren van een tijdelijke array,

252
00:21:38,260 --> 00:21:42,850
of als we wilden iets toe te voegen in het midden van ons aanbod,

253
00:21:42,850 --> 00:21:46,810
dan zou het een beetje meer schuifelen rond.

254
00:21:46,810 --> 00:21:50,240
Als u wilt, bijvoorbeeld, hebben een gesorteerd gelinkte lijst,

255
00:21:50,240 --> 00:21:54,880
dan moet je soort van wegen de kosten en baten van die

256
00:21:54,880 --> 00:21:59,720
want als je een gesorteerde array hebben, dat betekent dat elke keer dat u in het,

257
00:21:59,720 --> 00:22:01,630
het gaat om een ​​beetje meer tijd in beslag nemen.

258
00:22:01,630 --> 00:22:05,500
Echter, als je wilt later, als we vinden dat we willen,

259
00:22:05,500 --> 00:22:10,280
zoeken door middel van een gekoppelde lijst, dan is het misschien makkelijker als je weet dat alles in orde is.

260
00:22:10,280 --> 00:22:15,340
Dus je zou willen om de kosten en baten van die wegen.

261
00:22:20,150 --> 00:22:27,740
>> Een andere manier om invoegen in een gekoppelde lijst te voegen in het begin van een lijst.

262
00:22:27,740 --> 00:22:34,700
Als we hier trekken ons anker - dit is ons hoofd -

263
00:22:34,700 --> 00:22:40,960
en dan hebben deze mensen daaraan gekoppeld is,

264
00:22:40,960 --> 00:22:48,460
en dan een nieuwe knoop in te voegen in het begin,

265
00:22:48,460 --> 00:22:52,590
dan wat zouden we willen doen?

266
00:22:55,220 --> 00:23:03,580
Wat zou daar mis mee alleen maar te zeggen Ik wil de rode koppelen aan de blauwe,

267
00:23:03,580 --> 00:23:05,790
want dat is de eerste?

268
00:23:05,790 --> 00:23:08,570
Wat zou hier gebeuren?

269
00:23:08,570 --> 00:23:12,130
Al deze drie zou verdwalen.

270
00:23:12,130 --> 00:23:14,140
Dus we willen niet dat te doen.

271
00:23:14,140 --> 00:23:21,430
Nogmaals, hebben we geleerd dat we nodig hebben om een ​​soort van tijdelijke pointer te hebben.

272
00:23:21,430 --> 00:23:34,470
Laten we ervoor kiezen om een ​​tijdelijke punt om deze man te hebben.

273
00:23:34,470 --> 00:23:39,640
Dan kunnen we de blauwe ene punt naar het tijdelijke

274
00:23:39,640 --> 00:23:43,240
en dan de rode punt op de blauwe.

275
00:23:43,240 --> 00:23:47,830
De reden waarom ik ben met behulp van mensen hier is omdat we echt willen visualiseren

276
00:23:47,830 --> 00:23:53,180
vasthouden aan mensen en ervoor te zorgen dat we een link om ze te hebben

277
00:23:53,180 --> 00:23:57,590
voordat we loslaten van een andere hand of iets dergelijks.

278
00:24:05,630 --> 00:24:10,650
>> Nu we hebben een gevoel van gelinkte lijsten - hoe wij een gekoppelde lijst te maken

279
00:24:10,650 --> 00:24:15,090
en creëren structuren die bestaan ​​uit het type definitie voor een knooppunt

280
00:24:15,090 --> 00:24:19,060
en dan ervoor te zorgen dat we een pointer naar het hoofd van die gekoppelde lijst hebben -

281
00:24:19,060 --> 00:24:23,210
keer hebben we dat en we weten hoe we doorkruisen door middel van een array,

282
00:24:23,210 --> 00:24:28,200
toegang tot verschillende elementen, we weten hoe in te voegen en we weten hoe ze te bevrijden,

283
00:24:28,200 --> 00:24:30,260
dan kunnen we krijgen in spelfouten.

284
00:24:30,260 --> 00:24:38,150
Zoals gebruikelijk hebben we een deel van de vragen die u naar operationele gebruikt met gelinkte lijsten

285
00:24:38,150 --> 00:24:41,750
en verschillende structuren zoals wachtrijen en stacks.

286
00:24:41,750 --> 00:24:46,000
Dan kunnen we verhuizen naar spelfouten.

287
00:24:46,000 --> 00:24:55,170
>> Spelfouten heeft in de verdeelsleutel een paar bestanden van belang.

288
00:24:55,170 --> 00:24:58,850
Eerst merken we dat we deze Makefile hier hebben,

289
00:24:58,850 --> 00:25:03,040
die we nog niet echt ontmoet.

290
00:25:03,040 --> 00:25:10,090
Als je keek in de pset5 map, zou je merken dat je een. H-bestand,

291
00:25:10,090 --> 00:25:12,530
dan heb je twee. c-bestanden.

292
00:25:12,530 --> 00:25:18,920
Wat dit doet is Makefile voor, zouden we gewoon typ maken en de naam van het programma

293
00:25:18,920 --> 00:25:25,550
en dan zouden we zien al deze argumenten en vlaggen doorgegeven aan de compiler.

294
00:25:25,550 --> 00:25:30,580
Wat de Makefile doet is stelt ons in staat om meerdere bestanden samen te stellen in een keer

295
00:25:30,580 --> 00:25:34,650
en pas in de vlaggen die we willen.

296
00:25:34,650 --> 00:25:41,300
Hier hebben we gewoon zien dat er hier een header-bestand.

297
00:25:41,300 --> 00:25:43,730
Dan hebben we eigenlijk twee bronbestanden.

298
00:25:43,730 --> 00:25:47,520
We hebben speller.c en dictionary.c.

299
00:25:47,520 --> 00:25:54,560
U bent van harte welkom om de Makefile bewerken als je wilt.

300
00:25:54,560 --> 00:26:03,310
Merk op dat hier als u typt schoon, dan wat het doet is eigenlijk verwijdert alles

301
00:26:03,310 --> 00:26:06,340
dat is de kern.

302
00:26:06,340 --> 00:26:09,190
Als je een segmentatie fout, in principe krijg je een core dump.

303
00:26:09,190 --> 00:26:13,260
Dus dit lelijke kleine bestand wordt weergegeven in uw map met de naam kern.

304
00:26:13,260 --> 00:26:16,310
U wilt te verwijderen die te maken schoon te maken.

305
00:26:16,310 --> 00:26:20,940
Het verwijdert alle exe-bestanden en. O bestanden.

306
00:26:27,900 --> 00:26:30,220
>> Laten we eens een kijkje nemen in dictionary.h.

307
00:26:30,220 --> 00:26:34,410
Dit zegt dat het een woordenboek de functionaliteit verklaart.

308
00:26:34,410 --> 00:26:39,530
We hebben een maximale lengte voor elk woord in het woordenboek.

309
00:26:39,530 --> 00:26:45,130
We zeggen dat dit gaat om de langst mogelijke woord. Het is van lengte 45.

310
00:26:45,130 --> 00:26:48,900
Dus we gaan niet alle woorden die die lengte overschrijden hebben.

311
00:26:48,900 --> 00:26:50,980
Hier hoeven we alleen maar de functie prototypes.

312
00:26:50,980 --> 00:26:55,290
We hebben niet de daadwerkelijke uitvoering, want dat is wat we moeten doen voor deze PSET.

313
00:26:55,290 --> 00:26:59,940
Maar wat dit doet is omdat we te maken hebben met grotere bestanden hier

314
00:26:59,940 --> 00:27:06,650
en functionaliteit op een grotere schaal, is het nuttig om een. h bestand

315
00:27:06,650 --> 00:27:11,290
zodat iemand anders het lezen of het gebruik van de code kan begrijpen wat er gaande is.

316
00:27:11,290 --> 00:27:17,910
En misschien willen ze implementeren probeert als je dat deed hash tabellen of vice versa.

317
00:27:17,910 --> 00:27:21,850
Dan zouden ze zeggen dat mijn lading functie,

318
00:27:21,850 --> 00:27:26,950
de daadwerkelijke uitvoering gaat verschillen, maar dit prototype zal niet veranderen.

319
00:27:26,950 --> 00:27:33,280
Hier hebben we te controleren, dat true retourneert als een bepaald woord in het woordenboek.

320
00:27:33,280 --> 00:27:39,800
Dan hebben we last, die in feite neemt in een woordenboek bestand

321
00:27:39,800 --> 00:27:44,360
en dan laadt het deze in sommige datastructuur.

322
00:27:44,360 --> 00:27:47,500
We hebben grootte, die, als ze worden opgeroepen, de grootte van uw woordenboek terug,

323
00:27:47,500 --> 00:27:50,310
hoeveel woorden worden opgeslagen,

324
00:27:50,310 --> 00:27:54,390
en dan lossen, die bevrijdt van al het geheugen dat u hebt opgenomen

325
00:27:54,390 --> 00:27:57,900
terwijl het maken van uw woordenboek.

326
00:28:01,070 --> 00:28:03,590
>> Laten we eens een kijkje nemen op dictionary.c.

327
00:28:03,590 --> 00:28:10,490
We zien dat het lijkt erg op dictionary.h, behalve nu net heeft al deze Todos in.

328
00:28:10,490 --> 00:28:16,980
En dus dat is je werk. Uiteindelijk zult u het invullen van speller.c met al deze code.

329
00:28:16,980 --> 00:28:21,540
Dictionary.c, wanneer deze wordt uitgevoerd, is niet echt van plan om iets te doen,

330
00:28:21,540 --> 00:28:29,590
dus we kijken naar speller.c aan de daadwerkelijke uitvoering van de spellingcontrole te zien.

331
00:28:29,590 --> 00:28:32,060
Zelfs al ben je niet van plan om te bewerken een van deze code,

332
00:28:32,060 --> 00:28:38,050
is het belangrijk om te lezen, wanneer wordt belasting genoemd begrijpen, als ik bel cheque,

333
00:28:38,050 --> 00:28:42,350
alleen maar om te begrijpen, in kaart het uit, zien hoe de functie werkt.

334
00:28:42,350 --> 00:28:49,860
We zien dat het is het controleren op het juiste gebruik.

335
00:28:49,860 --> 00:28:55,200
In wezen, als iemand speller loopt, geeft dit aan dat het facultatieve is

336
00:28:55,200 --> 00:29:00,950
voor hen door te geven in een woordenboek bestand omdat er gaat een standaard woordenboek bestand zijn.

337
00:29:00,950 --> 00:29:05,410
En dan hebben ze door te geven in de tekst te worden spell-gecontroleerd.

338
00:29:05,410 --> 00:29:11,410
rusage deals met de tijd, omdat een deel van dit PSET die we later zullen behandelen

339
00:29:11,410 --> 00:29:14,790
is niet alleen het krijgen van een goed functionerende spellingcontrole werkt

340
00:29:14,790 --> 00:29:17,190
maar eigenlijk het krijgen van het te snel.

341
00:29:17,190 --> 00:29:22,040
En dus dan is dat waar rusage gaat komen inch

342
00:29:22,040 --> 00:29:28,740
Hier zien we de eerste oproep om een ​​van onze dictionary.c bestanden, die is belast.

343
00:29:28,740 --> 00:29:34,720
Load geeft true of false - waar op succes, vals bij uitval.

344
00:29:34,720 --> 00:29:41,400
Dus als het woordenboek is niet goed geladen, dan is de speller.c terug 1 en stoppen.

345
00:29:41,400 --> 00:29:47,920
Maar als dat zo is de lading goed, dan is het gaan blijven.

346
00:29:47,920 --> 00:29:50,740
We blijven, en we zien een aantal file I / O hier,

347
00:29:50,740 --> 00:29:56,210
waar het gaat om te maken hebben met het openen van het tekstbestand.

348
00:29:56,210 --> 00:30:04,640
Hier, wat dit doet is elk woord in de tekst spell-controles.

349
00:30:04,640 --> 00:30:09,270
Dus wat speller.c wordt hier doet is itereren over elk van de woorden in het tekstbestand

350
00:30:09,270 --> 00:30:12,790
en dan controleren ze in het woordenboek.

351
00:30:24,680 --> 00:30:32,350
Hier hebben we een Boolean verkeerd gespeld die zal kijken of cheque geeft true of niet.

352
00:30:32,350 --> 00:30:37,110
Als het woord eigenlijk in het woordenboek, dan check zal terugkeren waar.

353
00:30:37,110 --> 00:30:39,760
Dat betekent dat het woord niet verkeerd is gespeld.

354
00:30:39,760 --> 00:30:45,330
Dus verkeerd gespeld zou zijn vals, en dat is waarom we de knal daar de indicatie.

355
00:30:45,330 --> 00:30:56,320
We blijven aan de gang, en dan houdt bij hoeveel verkeerd gespelde woorden

356
00:30:56,320 --> 00:30:58,910
er in het bestand.

357
00:30:58,910 --> 00:31:03,870
Het blijft op en sluit het bestand.

358
00:31:03,870 --> 00:31:09,250
Dan hier, rapporteert hoeveel verkeerd gespelde woorden je had.

359
00:31:09,250 --> 00:31:12,680
Het berekent hoeveel tijd die nodig was om het woordenboek te laden,

360
00:31:12,680 --> 00:31:15,080
hoeveel tijd het heeft gekost om het te controleren,

361
00:31:15,080 --> 00:31:18,510
hoeveel tijd die nodig was om de grootte te berekenen,

362
00:31:18,510 --> 00:31:21,260
die, zoals we verder gaan, moet zeer klein zijn,

363
00:31:21,260 --> 00:31:25,390
en dan hoeveel tijd die nodig was om het woordenboek te laden.

364
00:31:25,390 --> 00:31:27,700
Hier boven hebben we de oproep om hier te lossen zien.

365
00:31:27,700 --> 00:31:52,690
Als we hier controleren voor grootte,

366
00:31:52,690 --> 00:31:59,050
dan zien we dat hier de oproep op maat wanneer bepaalt de grootte van het woordenboek.

367
00:32:05,730 --> 00:32:07,100
Awesome.

368
00:32:07,100 --> 00:32:10,920
>> Het is onze taak om deze PSET is het implementeren van belasting, die het woordenboek wordt geladen

369
00:32:10,920 --> 00:32:15,480
datastructuur - Wat u ook kiest, of het nu een hash-tabel of een keer te proberen -

370
00:32:15,480 --> 00:32:18,810
met woorden uit het woordenboek bestand.

371
00:32:18,810 --> 00:32:25,290
Dan heb je grootte, die het aantal woorden terug in het woordenboek.

372
00:32:25,290 --> 00:32:29,860
En als u de uitvoering van belasting op een slimme manier, dan grootte moet vrij eenvoudig.

373
00:32:29,860 --> 00:32:33,860
Dan heb je te controleren, die zal controleren of een bepaald woord in het woordenboek.

374
00:32:33,860 --> 00:32:38,690
Dus speller.c gaat in een string, en dan moet je de vraag of die string controleren

375
00:32:38,690 --> 00:32:41,610
is opgenomen in uw woordenboek.

376
00:32:41,610 --> 00:32:46,750
Merk op dat we in het algemeen standaard woordenboeken,

377
00:32:46,750 --> 00:32:53,020
maar in dit PSET, eigenlijk elke woordenboek doorgegeven in in elke taal.

378
00:32:53,020 --> 00:32:57,040
Dus we kunnen niet zomaar aannemen dat het woord de binnenkant is.

379
00:32:57,040 --> 00:33:03,090
Het woord FOOBAR kan worden gedefinieerd in een bepaalde woordenboek dat we passeren inch

380
00:33:03,090 --> 00:33:07,920
En dan hebben we lossen, die bevrijdt het woordenboek uit het geheugen.

381
00:33:07,920 --> 00:33:11,930
>> Ten eerste, wil ik gaan over de hash-tabel methode

382
00:33:11,930 --> 00:33:14,630
over hoe we zouden kunnen implementeren al die vier functies,

383
00:33:14,630 --> 00:33:18,650
en dan ga ik over de methode probeert, hoe we die vier functies te implementeren,

384
00:33:18,650 --> 00:33:22,720
en aan het eind praten over een aantal algemene tips als je het maken van de PSET

385
00:33:22,720 --> 00:33:27,870
en ook hoe je zou kunnen gebruiken Valgrind om te controleren of het geheugen lekken.

386
00:33:27,870 --> 00:33:30,550
>> Laten we in de hash tabel methode.

387
00:33:30,550 --> 00:33:35,910
Een hash tabel bestaat uit een lijst van emmers.

388
00:33:35,910 --> 00:33:43,010
Elke waarde, elk woord, zal gaan in een van deze bakken.

389
00:33:43,010 --> 00:33:53,200
Een hash table ideaal verdeelt al deze waarden die je voorbij in

390
00:33:53,200 --> 00:33:57,160
en gevuld ze in de emmer zodat elke emmer

391
00:33:57,160 --> 00:34:02,000
heeft ongeveer een gelijk aantal waarden in.

392
00:34:02,000 --> 00:34:09,630
De structuur van een hash-tabel, hebben we een reeks van gelinkte lijsten.

393
00:34:09,630 --> 00:34:17,900
Wat wij doen is als we passeren in een waarde, we kijken waar die waarde moet behoren,

394
00:34:17,900 --> 00:34:23,840
die emmer het behoort, en zet dan weg in de gelinkte lijst die bij die emmer.

395
00:34:23,840 --> 00:34:28,199
Hier, wat ik heb is een hash-functie.

396
00:34:28,199 --> 00:34:31,320
Het is een int hash-tabel.

397
00:34:31,320 --> 00:34:38,540
Dus voor de eerste emmer, elke gehele getallen onder de 10 gaan in de eerste emmer.

398
00:34:38,540 --> 00:34:42,190
Hele getallen boven de 10 maar onder de 20 gaan in de tweede,

399
00:34:42,190 --> 00:34:44,179
en zo verder enzovoort.

400
00:34:44,179 --> 00:34:52,370
Voor mij is elke emmer die deze nummers.

401
00:34:52,370 --> 00:34:59,850
Maar, zeg ik zou slagen in 50, bijvoorbeeld.

402
00:34:59,850 --> 00:35:07,490
Het lijkt alsof de eerste drie bevatten een reeks van tien getallen.

403
00:35:07,490 --> 00:35:12,570
Maar ik wil toestaan ​​mijn hash-tabel te nemen in een soort van gehele getallen,

404
00:35:12,570 --> 00:35:19,860
dus dan zou ik om te filteren op alle nummers boven de 30 in het laatste segment.

405
00:35:19,860 --> 00:35:26,660
En zo dan zou dat resulteren in een soort onevenwichtige hash-tabel.

406
00:35:31,330 --> 00:35:35,640
Herhalen tot, een hash-tabel is slechts een array van emmers

407
00:35:35,640 --> 00:35:38,590
waar elke bak is een gelinkte lijst.

408
00:35:38,590 --> 00:35:43,730
En zo te bepalen waar elke waarde gaat die bak gaat het in,

409
00:35:43,730 --> 00:35:46,260
je gaat te willen wat heet een hash-functie

410
00:35:46,260 --> 00:35:55,010
dat neemt een waarde vervolgens zegt deze waarde correspondeert met een bepaalde bak.

411
00:35:55,010 --> 00:36:00,970
Dus boven in dit voorbeeld my hashfunctie heeft elke waarde.

412
00:36:00,970 --> 00:36:03,020
Gecontroleerd of het was minder dan 10.

413
00:36:03,020 --> 00:36:05,360
Zo ja, zou zet het in het eerste segment.

414
00:36:05,360 --> 00:36:08,910
Het controleert of het nu minder dan 20, zet het in de tweede als het waar is,

415
00:36:08,910 --> 00:36:12,880
controleert of het is minder dan 30, en dan zet het in de derde emmer,

416
00:36:12,880 --> 00:36:16,990
en dan al het andere valt net op de vierde emmer.

417
00:36:16,990 --> 00:36:20,110
Dus wanneer je een waarde hebben, je hash-functie

418
00:36:20,110 --> 00:36:25,420
plaatst die waarde in de juiste emmer.

419
00:36:25,420 --> 00:36:32,430
De hash-functie moet in principe om te weten hoeveel emmers je hebt.

420
00:36:32,430 --> 00:36:37,960
Uw hash table grootte, het aantal bakken die je hebt,

421
00:36:37,960 --> 00:36:41,190
dat gaat een vast nummer dat up is voor u, voor u beslist te zijn,

422
00:36:41,190 --> 00:36:43,590
maar het gaat om een ​​vast nummer zijn.

423
00:36:43,590 --> 00:36:51,840
Dus je hash-functie wordt een beroep op dat om te bepalen welke emmer elke toets gaat in

424
00:36:51,840 --> 00:36:54,450
zodanig dat het gelijk is verdeeld.

425
00:36:56,150 --> 00:37:03,820
Net als bij onze implementatie van gelinkte lijsten, nu elke node in de hash-tabel

426
00:37:03,820 --> 00:37:07,000
er werkelijk gaande is om een ​​type char hebben.

427
00:37:07,000 --> 00:37:14,340
Dus hebben we een char array woord en dan nog een pointer naar het volgende knooppunt,

428
00:37:14,340 --> 00:37:19,010
wat logisch is, omdat het gaat om een ​​gekoppelde lijst.

429
00:37:19,010 --> 00:37:24,350
Weet je nog dat we hadden gelinkte lijsten, heb ik een knoop * genaamd hoofd

430
00:37:24,350 --> 00:37:31,060
wees dat het eerste knooppunt in de gekoppelde lijst.

431
00:37:31,060 --> 00:37:34,020
Maar voor onze hash-tabel, want we hebben meerdere gekoppelde lijsten,

432
00:37:34,020 --> 00:37:37,520
wat we willen is dat we willen dat onze hash-tabel om te zijn zoals: "Wat is een emmer?"

433
00:37:37,520 --> 00:37:43,340
Een emmer is slechts een lijst van knooppunt pointers,

434
00:37:43,340 --> 00:37:50,620
Dus iedere element in de emmer daadwerkelijk onder verwijzing naar de bijbehorende verbonden lijst.

435
00:37:56,180 --> 00:38:01,520
Om terug te gaan naar dit schema, zie je dat de emmers zelf de pijlen,

436
00:38:01,520 --> 00:38:06,980
niet de werkelijke knooppunten.

437
00:38:11,680 --> 00:38:16,420
Een essentiële eigenschap van hash functies is dat ze deterministisch zijn.

438
00:38:16,420 --> 00:38:19,440
Dat betekent dat wanneer u hash de nummer 2,

439
00:38:19,440 --> 00:38:22,270
het moet altijd weer terug op dezelfde emmer.

440
00:38:22,270 --> 00:38:26,440
Elke waarde die gaat in de hash-functie, bij herhaling,

441
00:38:26,440 --> 00:38:29,690
moet krijgen dezelfde index.

442
00:38:29,690 --> 00:38:34,210
Dus je hash-functie geeft de index van de array

443
00:38:34,210 --> 00:38:38,530
indien deze waarde hoort.

444
00:38:38,530 --> 00:38:41,790
Zoals ik al zei, is het aantal emmers vast,

445
00:38:41,790 --> 00:38:49,630
en zo uw index dat je terug moet kleiner zijn dan het aantal emmers

446
00:38:49,630 --> 00:38:52,680
maar groter dan 0.

447
00:38:52,680 --> 00:39:00,780
De reden waarom we hash-functies in plaats van slechts een enkele gelinkte lijst

448
00:39:00,780 --> 00:39:09,290
of een array is dat we in staat om naar een bepaald gedeelte snelst

449
00:39:09,290 --> 00:39:11,720
Als we weten dat de eigenschap van een waarde -

450
00:39:11,720 --> 00:39:14,760
in plaats van te zoeken in het volledige woordenboek,

451
00:39:14,760 --> 00:39:18,320
kunnen om naar een bepaald deel daarvan.

452
00:39:19,880 --> 00:39:24,440
Uw hashfunctie moet rekening worden gehouden met een ideale,

453
00:39:24,440 --> 00:39:28,980
elke emmer ongeveer hetzelfde aantal sleutels.

454
00:39:28,980 --> 00:39:35,040
Aangezien de hashtabel een reeks gekoppelde lijsten

455
00:39:35,040 --> 00:39:38,480
dan de verbonden lijsten zelf zullen meerdere node.

456
00:39:38,480 --> 00:39:43,210
In het vorige voorbeeld, twee verschillende getallen, hoewel ze niet gelijk zijn,

457
00:39:43,210 --> 00:39:46,950
wanneer gehashed, zou terugkeren op dezelfde index.

458
00:39:46,950 --> 00:39:53,620
Dus als je te maken hebt met woorden, een woord als hashed

459
00:39:53,620 --> 00:39:57,450
zou dezelfde hash-waarde als een ander woord.

460
00:39:57,450 --> 00:40:04,140
Dat is wat wij noemen een botsing, wanneer we een knooppunt dat, wanneer hashed,

461
00:40:04,140 --> 00:40:09,610
de gekoppelde lijst op die emmer niet leeg is.

462
00:40:09,610 --> 00:40:14,180
De techniek die we noemen er lineaire sonderen,

463
00:40:14,180 --> 00:40:22,550
waar je in de gekoppelde lijst en vervolgens te zoeken waar u wilt dat knooppunt te voegen

464
00:40:22,550 --> 00:40:25,520
omdat je een botsing.

465
00:40:25,520 --> 00:40:28,070
Je kunt zien dat er misschien een trade-off hier te zijn, toch?

466
00:40:28,070 --> 00:40:33,760
Als je een heel klein hash-tabel, een zeer klein aantal emmers,

467
00:40:33,760 --> 00:40:36,380
dan zul je een hoop botsingen hebben.

468
00:40:36,380 --> 00:40:40,460
Maar dan als je een zeer grote hash-tabel,

469
00:40:40,460 --> 00:40:44,110
ben je waarschijnlijk gaat om de botsingen te minimaliseren,

470
00:40:44,110 --> 00:40:47,170
maar het gaat om een ​​zeer grote data structuur.

471
00:40:47,170 --> 00:40:49,310
Er zal trade-offs zijn met dat.

472
00:40:49,310 --> 00:40:51,310
Dus wanneer u uw PSET maken, proberen te spelen rond

473
00:40:51,310 --> 00:40:54,210
tussen misschien het maken van een kleinere hash-tabel

474
00:40:54,210 --> 00:41:02,100
maar dan weten dat het gaat om een ​​beetje langer duren om de verschillende elementen doorkruisen

475
00:41:02,100 --> 00:41:04,270
van die gelinkte lijsten.

476
00:41:04,270 --> 00:41:09,500
>> Wat belasting gaat doen is itereren over elk woord in het woordenboek.

477
00:41:09,500 --> 00:41:13,180
Het gaat in een verwijzing naar het woordenboek bestand.

478
00:41:13,180 --> 00:41:18,050
Dus je gaat om te profiteren van het bestand I / O functies die u onder de knie in pset4

479
00:41:18,050 --> 00:41:23,010
en itereren over elk woord in het woordenboek.

480
00:41:23,010 --> 00:41:26,620
U wilt elk woord in het woordenboek op een nieuw knooppunt te worden,

481
00:41:26,620 --> 00:41:32,730
en je gaat elk van die knooppunten te plaatsen in uw woordenboek datastructuur.

482
00:41:32,730 --> 00:41:36,560
Wanneer u een nieuw woord te krijgen, weet je dat het gaat om een ​​knooppunt te worden.

483
00:41:36,560 --> 00:41:46,590
U kunt dus direct gaan en malloc een knooppunt pointer voor elk nieuw woord dat je hebt.

484
00:41:46,590 --> 00:41:52,610
Hier Ik bel mijn knooppunt aanwijzer new_node en ik ben mallocing wat? De grootte van een node.

485
00:41:52,610 --> 00:41:59,190
Dan naar de werkelijke tekenreeks uit een bestand te lezen, omdat het woordenboek is eigenlijk opgeslagen

486
00:41:59,190 --> 00:42:03,340
met een woord en vervolgens een nieuwe lijn, wat we kunnen profiteren van

487
00:42:03,340 --> 00:42:06,520
is de functie fscanf,

488
00:42:06,520 --> 00:42:10,280
waarbij bestand is het woordenboek bestand dat we doorgegeven in,

489
00:42:10,280 --> 00:42:18,900
dus het scant het bestand op een string en plaatsen die string in het laatste argument.

490
00:42:18,900 --> 00:42:26,890
Misschien herinner je je terug naar een van de lezingen, toen we gingen over

491
00:42:26,890 --> 00:42:29,320
en de aard van gepelde de lagen weer op de CS50 bibliotheek,

492
00:42:29,320 --> 00:42:33,430
zagen we een implementatie van fscanf daar.

493
00:42:33,430 --> 00:42:37,700
Om terug te gaan naar fscanf, hebben we het bestand dat we het lezen van,

494
00:42:37,700 --> 00:42:42,570
We zijn op zoek naar een string in dat bestand, en dan gaan we het plaatsen van het in

495
00:42:42,570 --> 00:42:48,340
hier heb ik new_node-> woord, omdat new_node is een knooppunt pointer,

496
00:42:48,340 --> 00:42:50,380
niet een echte node.

497
00:42:50,380 --> 00:42:57,100
Dus dan zeg ik new_node, ik wil naar het knooppunt dat het is te wijzen op

498
00:42:57,100 --> 00:43:01,190
en wijs die waarde te woord.

499
00:43:01,190 --> 00:43:08,540
We willen vervolgens dat woord en in te voegen in de hash tabel.

500
00:43:08,540 --> 00:43:13,750
Realiseer je dat we new_node een knooppunt pointer

501
00:43:13,750 --> 00:43:18,230
want we gaan om te willen weten wat het adres van dat knooppunt is

502
00:43:18,230 --> 00:43:23,940
als we invoegen in omdat de structuur van de nodes van de struct,

503
00:43:23,940 --> 00:43:26,380
is dat ze een pointer naar een nieuwe node.

504
00:43:26,380 --> 00:43:30,820
Dus wat is dan het adres van dat knooppunt te gaan om te verwijzen naar?

505
00:43:30,820 --> 00:43:34,550
Dat adres zal worden new_node.

506
00:43:34,550 --> 00:43:42,140
Is dat zinvol, waarom maken we new_node een knooppunt * in tegenstelling tot een knooppunt?

507
00:43:43,700 --> 00:43:45,700
Oke.

508
00:43:45,700 --> 00:43:52,840
We hebben een woord. Die waarde is new_node-> woord.

509
00:43:52,840 --> 00:43:55,970
Dat bevat het woord uit het woordenboek die we willen invoeren.

510
00:43:55,970 --> 00:44:00,210
Dus wat we willen doen is dat we willen onze hash-functie een beroep doen op die string

511
00:44:00,210 --> 00:44:03,780
omdat onze hashfunctie neemt in een string en keert dan terug ons een geheel getal,

512
00:44:03,780 --> 00:44:12,090
waar dat getal is de index waar hash op die index vertegenwoordigt die emmer.

513
00:44:12,090 --> 00:44:18,260
We willen dat de index te nemen en ga dan naar die index van de hash-tabel

514
00:44:18,260 --> 00:44:26,960
en gebruik die gelinkte lijst om het knooppunt te voegen op new_node.

515
00:44:26,960 --> 00:44:31,950
Vergeet niet dat hoe je besluit je knooppunt invoegen,

516
00:44:31,950 --> 00:44:34,370
of het nu in het midden als je wilt om het te sorteren

517
00:44:34,370 --> 00:44:39,650
of aan het begin of aan het eind, maar zorg ervoor dat uw laatste knooppunt wijst altijd NULL te

518
00:44:39,650 --> 00:44:46,730
want dat is de enige manier waarop we weten waar het laatste element van onze gekoppelde lijst is.

519
00:44:50,790 --> 00:44:59,710
>> Als maat is een geheel getal dat het aantal woorden in een woordenboek is,

520
00:44:59,710 --> 00:45:03,060
dan een manier om dit te doen is dat wanneer formaat wordt genoemd

521
00:45:03,060 --> 00:45:05,840
we gaan door elk element in onze hash-tabel

522
00:45:05,840 --> 00:45:09,410
en dan doorlopen om de gelinkte lijst in de hash-tabel

523
00:45:09,410 --> 00:45:13,770
en berekent dan de lengte van dat, het verhogen van onze teller 1 voor 1.

524
00:45:13,770 --> 00:45:16,580
Maar elke keer die grootte wordt genoemd, dat gaat lang duren

525
00:45:16,580 --> 00:45:22,120
want we gaan naar lineair zijn indringende elke gelinkte lijst.

526
00:45:22,120 --> 00:45:30,530
In plaats daarvan gaat het om een ​​stuk makkelijker zijn als je bijhouden hoeveel woorden worden doorgegeven inch

527
00:45:30,530 --> 00:45:36,330
Dus dan kun je een teller in uw belasting-functie

528
00:45:36,330 --> 00:45:42,430
dat updates indien nodig, vervolgens tegen te gaan, als u het naar een globale variabele,

529
00:45:42,430 --> 00:45:44,930
kunnen worden geraadpleegd op grootte.

530
00:45:44,930 --> 00:45:51,450
Dus wat omvang kon gewoon doen is in een lijn, net terug van de waarde van de teller,

531
00:45:51,450 --> 00:45:55,500
de grootte van het woordenboek, die u reeds behandeld belasting.

532
00:45:55,500 --> 00:46:05,190
Dat is wat ik bedoelde toen ik zei dat als je belasting te implementeren in een nuttige manier,

533
00:46:05,190 --> 00:46:08,540
Vervolgens grootte gaat vrij gemakkelijk.

534
00:46:08,540 --> 00:46:11,350
>> Dus nu krijgen we te controleren.

535
00:46:11,350 --> 00:46:15,960
Nu we te maken hebben met woorden uit de input tekstbestand,

536
00:46:15,960 --> 00:46:19,910
en dus we gaan te controleren of al die ingangswoorden

537
00:46:19,910 --> 00:46:22,520
zijn eigenlijk in het woordenboek of niet.

538
00:46:22,520 --> 00:46:26,520
Net als bij Scramble, willen we zorgen voor hoofdlettergevoeligheid.

539
00:46:26,520 --> 00:46:32,110
U wilt er zeker van zijn dat alle woorden doorgegeven, ook al zijn ze gemengde geval is,

540
00:46:32,110 --> 00:46:37,840
als ze worden opgeroepen met string vergelijken, gelijkwaardig zijn.

541
00:46:37,840 --> 00:46:42,450
De woorden in het woordenboek tekstbestanden zijn eigenlijk allemaal kleine letters.

542
00:46:42,450 --> 00:46:49,280
Een ander ding is dat je kunt ervan uitgaan dat elk woord doorgegeven in, elke string,

543
00:46:49,280 --> 00:46:53,200
gaat worden, hetzij alfabetische of bevatten apostrof.

544
00:46:53,200 --> 00:46:58,010
Apostrofs zullen geldig woorden in ons woordenboek.

545
00:46:58,010 --> 00:47:06,470
Dus als je een woord met apostrof S hebben, dat is een echte legitieme woord in uw woordenboek

546
00:47:06,470 --> 00:47:11,650
dat gaat als een van de knooppunten in uw hash tabel.

547
00:47:13,470 --> 00:47:18,350
Controleer werkt met als het woord bestaat, dan moet wel in onze hash table.

548
00:47:18,350 --> 00:47:22,210
Als het woord in het woordenboek, dan alle woorden in het woordenboek zijn in de hash tabel,

549
00:47:22,210 --> 00:47:26,560
dus laten we eens kijken naar dit woord in de hash tabel.

550
00:47:26,560 --> 00:47:29,250
We weten dat omdat we onze hash-functie geïmplementeerd

551
00:47:29,250 --> 00:47:38,420
zodat elke unieke woord altijd gehashed op dezelfde waarde,

552
00:47:38,420 --> 00:47:43,340
dan weten we dat in plaats van te zoeken in onze hele hele hash-tabel,

553
00:47:43,340 --> 00:47:48,310
kunnen we eigenlijk vinden de gekoppelde lijst die dat woord moet behoren.

554
00:47:48,310 --> 00:47:51,850
Als het in het woordenboek, dan zou in die emmer.

555
00:47:51,850 --> 00:47:57,140
Wat we wel kunnen doen, als woord is de naam van onze string doorgegeven in,

556
00:47:57,140 --> 00:48:01,560
we kunnen gewoon hash dat woord en blik op de gekoppelde lijst

557
00:48:01,560 --> 00:48:06,410
op de waarde van de hash [hash (woord)].

558
00:48:06,410 --> 00:48:12,410
Van daar, wat we kunnen doen is dat we hebben een kleinere subset van knooppunten om te zoeken naar dit woord,

559
00:48:12,410 --> 00:48:16,770
en dus kunnen we doorkruisen de gelinkte lijst, met behulp van een voorbeeld uit eerder in de walkthrough,

560
00:48:16,770 --> 00:48:24,110
en dan bellen string vergelijker op het woord waar de cursor op,

561
00:48:24,110 --> 00:48:28,430
dat woord, en zien of deze te vergelijken.

562
00:48:30,280 --> 00:48:35,110
Afhankelijk van de manier waarop je je hash-functie te organiseren,

563
00:48:35,110 --> 00:48:39,260
als het gesorteerd, kunt u mogelijk om valse wat eerder terug te keren,

564
00:48:39,260 --> 00:48:43,440
maar als het ongesorteerd, dan moet je verder wilt gaan doorkruisen via uw gekoppelde lijst

565
00:48:43,440 --> 00:48:46,480
totdat u het laatste element van de lijst.

566
00:48:46,480 --> 00:48:53,320
En als je nog steeds niet gevonden het woord door de tijd dat je aan het einde van de gekoppelde lijst,

567
00:48:53,320 --> 00:48:56,890
dat betekent dat uw woord niet bestaat in het woordenboek,

568
00:48:56,890 --> 00:48:59,410
en zo dat woord is ongeldig,

569
00:48:59,410 --> 00:49:02,730
en controle moet return false.

570
00:49:02,730 --> 00:49:09,530
>> Nu komen we bij lossen, waar we willen alle knooppunten die we hebben malloc'd bevrijden,

571
00:49:09,530 --> 00:49:14,050
zo vrij alle knooppunten binnenkant van onze hash-tabel.

572
00:49:14,050 --> 00:49:20,270
We gaan willen itereren over alle van de gelinkte lijsten en vrij van alle knooppunten in dat.

573
00:49:20,270 --> 00:49:29,350
Als je kijkt boven in de walkthrough op het voorbeeld, waar we gratis een gelinkte lijst,

574
00:49:29,350 --> 00:49:35,140
dan zul je om dat proces te herhalen voor elk element in de hash tabel.

575
00:49:35,140 --> 00:49:37,780
En ik zal gaan over deze tegen het einde van de walkthrough,

576
00:49:37,780 --> 00:49:46,600
maar Valgrind is een hulpmiddel waar je kunt zien of je op de juiste wijze bevrijd

577
00:49:46,600 --> 00:49:53,600
elke knoop die u hebt malloc'd of iets anders dat u malloc'd, een andere wijzer.

578
00:49:55,140 --> 00:50:00,530
Dus dat is hash tables, waar we een eindig aantal emmers

579
00:50:00,530 --> 00:50:09,220
en een hash functie die een waarde toekennen en vervolgens deze waarde een bepaalde bak.

580
00:50:09,220 --> 00:50:13,340
>> Nu komen we bij pogingen.

581
00:50:13,340 --> 00:50:18,750
Probeert soort look als dit, en ik zal ook trekken uit een voorbeeld.

582
00:50:18,750 --> 00:50:25,630
In principe heb je een heel scala aan mogelijke letters,

583
00:50:25,630 --> 00:50:29,210
en dan als je de bouw van een woord,

584
00:50:29,210 --> 00:50:36,490
deze brief kan worden gekoppeld om een ​​woordenboek een breed scala aan mogelijkheden.

585
00:50:36,490 --> 00:50:40,840
Sommige woorden beginnen met C, maar ga dan verder met A,

586
00:50:40,840 --> 00:50:42,960
maar anderen voortzetten O bijvoorbeeld.

587
00:50:42,960 --> 00:50:51,090
Een trie is een manier van het visualiseren van alle mogelijke combinaties van die woorden.

588
00:50:51,090 --> 00:50:59,070
Een trie gaat om bij te houden van de opeenvolging van letters die woorden bestaan,

589
00:50:59,070 --> 00:51:08,280
aftakking indien nodig, wanneer een brief kan worden gevolgd door een veelvoud van letters,

590
00:51:08,280 --> 00:51:16,630
en aan het eind dan op elk punt of dat woord wel of niet geldig

591
00:51:16,630 --> 00:51:30,120
want als je spelling van het woord MAT, MA Ik denk niet dat een geldige woord, maar MAT is.

592
00:51:30,120 --> 00:51:37,820
En zo in uw trie, zou dat betekenen dat na MAT dat is eigenlijk een geldig woord.

593
00:51:41,790 --> 00:51:48,590
Elk knooppunt in onze trie daadwerkelijk zal een array van knooppunt pointers bevat,

594
00:51:48,590 --> 00:51:52,970
en we gaan specifiek hebben, 27 van die knoop pointers,

595
00:51:52,970 --> 00:52:00,550
een voor elke letter van het alfabet en de apostrof karakter.

596
00:52:00,550 --> 00:52:10,450
Elk element in dat array zelf zal wijzen naar een ander knooppunt.

597
00:52:10,450 --> 00:52:14,020
Dus als dat knooppunt is NULL, als er niets na dat,

598
00:52:14,020 --> 00:52:20,550
dan weten we dat er geen verdere letters in dat woord volgorde.

599
00:52:20,550 --> 00:52:26,950
Maar als dat knooppunt niet NULL is, dat betekent dat er meer letters in die brief volgorde.

600
00:52:26,950 --> 00:52:32,160
En dan verder, elke node geeft aan of het is de laatste letter van een woord is of niet.

601
00:52:38,110 --> 00:52:43,170
>> Laten we naar een voorbeeld van een trie.

602
00:52:50,500 --> 00:52:58,340
Eerst heb ik ruimte hebben voor 27 knooppunten in deze array.

603
00:52:58,340 --> 00:53:03,200
Als ik het woord BAR -

604
00:53:13,310 --> 00:53:15,370
Als ik het woord BAR en ik wil dat invoegen in,

605
00:53:15,370 --> 00:53:22,700
de eerste letter is B, dus als mijn trie leeg is,

606
00:53:22,700 --> 00:53:29,910
B is de tweede letter van het alfabet, dus ik ga ervoor kiezen om hier zet deze op deze index.

607
00:53:29,910 --> 00:53:33,450
Ik ga hier hebben B.

608
00:53:33,450 --> 00:53:42,400
B gaat een knooppunt dat wijst op een andere array van alle mogelijke tekens zijn

609
00:53:42,400 --> 00:53:45,870
die kunnen volgen na de letter B.

610
00:53:45,870 --> 00:53:57,610
In dit geval ben ik het omgaan met het woord BAR, dus A zal hier gaan.

611
00:54:02,000 --> 00:54:08,990
Na een, ik heb de letter R, dus dan A nu wijst op zijn eigen combinatie,

612
00:54:08,990 --> 00:54:15,120
en dan R zal hier zijn.

613
00:54:15,120 --> 00:54:22,470
BAR is een volledig woord, dus dan ga ik R-punt moeten naar een ander knooppunt

614
00:54:22,470 --> 00:54:33,990
die zegt dat dat woord geldig is.

615
00:54:36,010 --> 00:54:40,970
Dat knooppunt zal ook een reeks knooppunten,

616
00:54:40,970 --> 00:54:45,260
maar die kan NULL.

617
00:54:45,260 --> 00:54:49,080
Maar in principe kan het verder zo.

618
00:54:49,080 --> 00:54:54,250
Dat zal een beetje meer duidelijk toen we naar een ander voorbeeld,

619
00:54:54,250 --> 00:54:56,780
dus er gewoon geduld met mij.

620
00:54:56,780 --> 00:55:02,050
Nu hebben we BAR binnenkant van ons woordenboek.

621
00:55:02,050 --> 00:55:05,980
Nu zeggen dat we het woord BAZ.

622
00:55:05,980 --> 00:55:12,630
We beginnen met B, en we hebben al B als een van de letters dat is in ons woordenboek.

623
00:55:12,630 --> 00:55:15,170
Dat is gevolgd met A. We hebben een reeds.

624
00:55:15,170 --> 00:55:19,250
Maar in plaats daarvan hebben we Z volgende.

625
00:55:19,250 --> 00:55:25,490
Dus dan een element in ons aanbod zal zijn Z,

626
00:55:25,490 --> 00:55:30,810
En dus dat gaat om naar een andere geldige eindtoestand van het woord.

627
00:55:30,810 --> 00:55:36,930
We zien dus dat als we verder door B en dan A,

628
00:55:36,930 --> 00:55:43,480
Er zijn twee opties die in ons woordenboek voor woorden die beginnen met B en A.

629
00:55:49,650 --> 00:55:57,460
Stel dat we wilden het woord FOOBAR te voegen.

630
00:55:57,460 --> 00:56:05,620
Dan zouden we een vermelding bij F.

631
00:56:05,620 --> 00:56:11,320
F is een knooppunt dat wijst op een hele reeks.

632
00:56:11,320 --> 00:56:22,790
We zouden O, gaat u naar O, O koppelt vervolgens naar een hele lijst.

633
00:56:22,790 --> 00:56:35,340
We zouden B hebben en dan verder, zouden we A en vervolgens R.

634
00:56:35,340 --> 00:56:43,570
Dus dan FOOBAR doorkruist helemaal naar beneden totdat FOOBAR is een juiste woord.

635
00:56:43,570 --> 00:56:52,590
En dus dan zou dit een geldig woord.

636
00:56:52,590 --> 00:57:00,170
Nu zeggen dat onze volgende woord in het woordenboek is eigenlijk het woord FOO.

637
00:57:00,170 --> 00:57:03,530
Wij zouden zeggen F. Wat volgt F?

638
00:57:03,530 --> 00:57:06,190
Ik heb eigenlijk al een ruimte voor O, dus ik ga om verder te gaan.

639
00:57:06,190 --> 00:57:09,150
Ik heb geen behoefte om een ​​nieuwe te maken. Doorgaan.

640
00:57:09,150 --> 00:57:15,500
FOO is een geldig woord in dit woordenboek, dus dan ga ik om aan te geven

641
00:57:15,500 --> 00:57:21,660
dat geldig is.

642
00:57:21,660 --> 00:57:28,370
Als ik daar te stoppen mijn volgorde, dat zou juist zijn.

643
00:57:28,370 --> 00:57:33,050
Maar als we onze reeks van FOO naar B

644
00:57:33,050 --> 00:57:39,750
en net FOOB had, FOOB is geen woord, en dat is niet geïndiceerd als geldig is.

645
00:57:47,370 --> 00:57:57,600
In een trie, heb je elke node wordt aangegeven of het een geldig woord is of niet,

646
00:57:57,600 --> 00:58:05,840
en dan elke knoop heeft ook een scala van 27 knoop pointers

647
00:58:05,840 --> 00:58:09,520
die wijs knooppunten zelf.

648
00:58:09,520 --> 00:58:12,940
>> Hier is een manier van hoe je zou willen om dit te definiëren.

649
00:58:12,940 --> 00:58:17,260
Echter, net als in de hash tabel bijvoorbeeld, waar we een knooppunt * hoofd

650
00:58:17,260 --> 00:58:21,320
aan het begin van onze verbonden lijst geven, zijn we ook zullen willen

651
00:58:21,320 --> 00:58:29,150
enkele manier om te weten waar het begin van onze trie is.

652
00:58:29,150 --> 00:58:34,110
Sommige mensen noemen probeert bomen, en dat is waar wortel vandaan komt.

653
00:58:34,110 --> 00:58:36,910
Dus we willen dat de wortel van de boom om ervoor te zorgen dat we blijven geaard

654
00:58:36,910 --> 00:58:39,570
naar de plaats waar onze trie is.

655
00:58:42,910 --> 00:58:46,300
We hebben al soort van ging

656
00:58:46,300 --> 00:58:50,240
de manier waarop je zou kunnen denken over het plaatsen van elk woord in het woordenboek.

657
00:58:50,240 --> 00:58:54,540
In wezen, voor elk woord dat je gaat te willen doorlopen uw trie

658
00:58:54,540 --> 00:58:59,590
en wetende dat elk element in de kinderen - we noemden het kind in dit geval -

659
00:58:59,590 --> 00:59:04,290
komt overeen met een andere letter, je gaat te willen om die waarden te controleren

660
00:59:04,290 --> 00:59:08,320
op dat index die overeenkomt met de letter.

661
00:59:08,320 --> 00:59:11,260
Dus denk de hele weg terug naar Caesar en Vigenere,

662
00:59:11,260 --> 00:59:16,070
wetende dat elke brief kunt u soort kaart terug naar een alfabetische index,

663
00:59:16,070 --> 00:59:20,690
zeker A tot Z zal zijn vrij eenvoudig in kaart om een ​​alfabetische letter,

664
00:59:20,690 --> 00:59:25,200
maar helaas, apostrofs zijn ook een geaccepteerde karakter in woorden.

665
00:59:25,200 --> 00:59:31,650
Ik weet niet eens zeker wat de ASCII-waarde is,

666
00:59:31,650 --> 00:59:39,250
dus voor dat als je wilt om een ​​index te beslissen of u het wilt of de eerste te zijn vinden

667
00:59:39,250 --> 00:59:44,550
of de laatste, dan moet je een harde gecodeerde cheque die deel uitmaken van

668
00:59:44,550 --> 00:59:48,930
en deze in index 26, bijvoorbeeld.

669
00:59:48,930 --> 00:59:55,300
Zo word je dan het controleren van de waarde bij kinderen [i]

670
00:59:55,300 --> 00:59:58,400
waar [i] komt overeen met wat brief je toch bezig bent.

671
00:59:58,400 --> 01:00:04,110
Als dat NULL, dat betekent dat er op dit moment niet alle mogelijke letters

672
01:00:04,110 --> 01:00:08,150
als gevolg van dat eerdere volgorde, dus je gaat te willen malloc

673
01:00:08,150 --> 01:00:13,150
en maak een nieuw knooppunt en hebben dat kinderen [i] punt om het te

674
01:00:13,150 --> 01:00:17,890
zodat u - als we ingevoegd een brief in de rechthoek -

675
01:00:17,890 --> 01:00:23,680
het maken van kinderen van niet-NULL en punt in dat nieuwe knooppunt.

676
01:00:23,680 --> 01:00:28,340
Maar als dat niet NULL is, zoals in ons geval van FOO

677
01:00:28,340 --> 01:00:34,570
als we al FOOBAR hadden, blijven we,

678
01:00:34,570 --> 01:00:44,010
en we zijn nooit het maken van een nieuw knooppunt, maar liever gewoon instellen is_word om waar te

679
01:00:44,010 --> 01:00:47,790
aan het einde van dat woord.

680
01:00:50,060 --> 01:00:55,340
>> Zo dan als voorheen, want hier te maken hebt met iedere letter in een tijd,

681
01:00:55,340 --> 01:01:01,470
het gaat gemakkelijker voor je zijn voor de grootte, in plaats van te berekenen

682
01:01:01,470 --> 01:01:06,910
en ga door de hele boom en bereken hoeveel kinderen heb ik

683
01:01:06,910 --> 01:01:10,850
en aftakkingen, herinneren hoeveel zijn links en rechts

684
01:01:10,850 --> 01:01:12,850
en dat soort dingen, het gaat om een ​​stuk makkelijker voor je zijn

685
01:01:12,850 --> 01:01:16,220
als je gewoon bijhouden hoeveel woorden je toe te voegen in

686
01:01:16,220 --> 01:01:18,080
wanneer je te maken hebt met last.

687
01:01:18,080 --> 01:01:22,630
En toen op die manier omvang kan net terug van een globale variabele van grootte.

688
01:01:25,320 --> 01:01:28,530
>> Nu komen we bij controleren.

689
01:01:28,530 --> 01:01:33,920
Dezelfde normen als voorheen, waar we willen zorgen voor hoofdlettergevoeligheid.

690
01:01:33,920 --> 01:01:40,400
Als goed, nemen we aan dat de snaren alleen alfabetische tekens of de apostrof

691
01:01:40,400 --> 01:01:44,000
omdat de kinderen is een array van 27 lang,

692
01:01:44,000 --> 01:01:48,480
zodat alle letters van het alfabet plus de apostrof.

693
01:01:48,480 --> 01:01:53,800
Om in te checken wat je wilt doen is je wilt beginnen aan de wortel

694
01:01:53,800 --> 01:01:58,440
omdat de wortel zal wijzen aan een array die bestaat uit

695
01:01:58,440 --> 01:02:01,630
alle mogelijke start letters van een woord.

696
01:02:01,630 --> 01:02:03,680
Je gaat daar beginnen,

697
01:02:03,680 --> 01:02:11,590
en dan zul je om te controleren is deze waarde NULL of niet,

698
01:02:11,590 --> 01:02:16,490
want als de waarde NULL, dat betekent dat het woordenboek geen enkele waarden

699
01:02:16,490 --> 01:02:21,480
die bevatten die letter in die bepaalde volgorde.

700
01:02:21,480 --> 01:02:24,970
Als het NULL, dan betekent dat dat het woord wordt meteen verkeerd gespeld.

701
01:02:24,970 --> 01:02:27,110
Maar als het niet NULL is, dan kunt u blijven,

702
01:02:27,110 --> 01:02:34,090
zeggen dat de eerste letter is een mogelijke eerste letter in een woord,

703
01:02:34,090 --> 01:02:40,630
dus nu wil ik om te controleren of de tweede brief, die volgorde, is in mijn woordenboek.

704
01:02:40,630 --> 01:02:46,540
Dus je gaat naar de index van de kinderen van het eerste knooppunt

705
01:02:46,540 --> 01:02:50,720
en controleer of deze tweede brief bestaat.

706
01:02:50,720 --> 01:02:57,440
Dan herhaal je dat proces om te controleren of de sequentie geldig is of niet

707
01:02:57,440 --> 01:02:59,060
binnen uw trie.

708
01:02:59,060 --> 01:03:06,430
Wanneer de knoop kinderen op dat indexpunten op NULL,

709
01:03:06,430 --> 01:03:10,710
je weet dat die volgorde niet bestaat,

710
01:03:10,710 --> 01:03:16,230
maar dan als u het einde van het woord dat u hebt ingevoerd,

711
01:03:16,230 --> 01:03:20,070
dan wilt u nu controleren dat ik deze sequentie voltooid

712
01:03:20,070 --> 01:03:27,610
en vond het in mijn trie, is dat woord dan niet geldig?

713
01:03:27,610 --> 01:03:32,480
En dus dan wil je dat controleren, en dat is wanneer als je hebt gevonden die volgorde,

714
01:03:32,480 --> 01:03:35,120
dan wilt u controleren of dat woord geldig is of niet

715
01:03:35,120 --> 01:03:40,290
want herinner me terug in het vorige geval, dat trok ik waar we FOOB,

716
01:03:40,290 --> 01:03:48,410
dat was een geldige sequentie die we gevonden, maar geen daadwerkelijke geldig woord zelf.

717
01:03:50,570 --> 01:03:59,000
>> Ook voor lossen in de pogingen u alle van de knooppunten in uw trie lossen.

718
01:03:59,000 --> 01:04:04,790
Sorry. Net als bij de hash tabellen waar in lossen we bevrijd alle knooppunten,

719
01:04:04,790 --> 01:04:09,740
in de pogingen willen we ook vrij alle knooppunten.

720
01:04:09,740 --> 01:04:15,000
Eigenlijk Unload werkt makkelijkst van onder naar boven

721
01:04:15,000 --> 01:04:19,290
omdat deze zijn in wezen gelinkte lijsten.

722
01:04:19,290 --> 01:04:22,540
Dus we willen zorgen dat we vasthouden maken op om alle waarden

723
01:04:22,540 --> 01:04:25,700
en vrij allemaal expliciet.

724
01:04:25,700 --> 01:04:28,840
Wat je gaat te willen doen als je werkt met een trie

725
01:04:28,840 --> 01:04:35,640
is eerst naar beneden en de laagste vrije knooppunt

726
01:04:35,640 --> 01:04:39,190
en ga dan naar al die kinderen en dan vrij al die,

727
01:04:39,190 --> 01:04:43,050
gaan omhoog en dan vrij, enz.

728
01:04:43,050 --> 01:04:48,790
Zoiets als het omgaan met de onderste laag van de trie eerste

729
01:04:48,790 --> 01:04:51,940
en dan omhoog gaan top als je eenmaal hebt bevrijd alles.

730
01:04:51,940 --> 01:04:56,720
Dit is een goed voorbeeld van waar recursieve functie van pas kan komen.

731
01:04:56,720 --> 01:05:03,830
Als je eenmaal hebt bevrijd van de onderste laag van je trie,

732
01:05:03,830 --> 01:05:08,000
dan bel je uitladen op de rest van het,

733
01:05:08,000 --> 01:05:13,620
ervoor te zorgen dat u elke mini bevrijden -

734
01:05:13,620 --> 01:05:16,410
U kunt dergelijke visualiseren als mini pogingen.

735
01:05:23,300 --> 01:05:28,990
Dus je hier hebt je root.

736
01:05:30,840 --> 01:05:35,230
Ik ben gewoon te vereenvoudigen, zodat ik niet hoeft te 26 van hen te trekken.

737
01:05:37,250 --> 01:05:43,770
Dus je hebt deze, en dan zijn deze vertegenwoordigen sequenties van woorden

738
01:05:43,770 --> 01:05:54,620
waar al deze kleine cirkels zijn brieven die geldig zijn sequenties van letters.

739
01:06:03,040 --> 01:06:07,160
Laten we doorgaan net een beetje meer.

740
01:06:15,110 --> 01:06:25,750
Wat je gaat te willen doen, is vrij de bodem hier en dan vrij deze

741
01:06:25,750 --> 01:06:31,640
en dan vrij dit aan de onderkant voordat u bevrijden van de bovenste hier

742
01:06:31,640 --> 01:06:38,180
want als je gratis iets in het tweede niveau hier,

743
01:06:38,180 --> 01:06:47,230
dan je eigenlijk zou verliezen deze waarde hier.

744
01:06:47,230 --> 01:06:54,780
Dat is waarom het belangrijk is in te lossen voor een trie om ervoor te zorgen dat u de bodem eerst vrij te maken.

745
01:06:54,780 --> 01:06:59,480
Wat je zou willen is zeggen te doen voor elk knooppunt

746
01:06:59,480 --> 01:07:06,430
Ik wil alle kinderen uit te laden.

747
01:07:16,060 --> 01:07:22,140
>> Nu we gegaan lossen voor de hash-tabel werkwijze alsmede de trie methode,

748
01:07:22,140 --> 01:07:27,020
we gaan kijken naar Valgrind.

749
01:07:27,020 --> 01:07:29,640
Valgrind je met de volgende commando's.

750
01:07:29,640 --> 01:07:32,700
Je hebt valgrind-v.

751
01:07:32,700 --> 01:07:40,960
Je controleert alle lekken wanneer u speller gaven deze bepaalde tekst

752
01:07:40,960 --> 01:07:46,980
omdat speller moet nemen in een tekstbestand.

753
01:07:46,980 --> 01:07:52,330
Dus Valgrind loopt uw ​​programma, u vertellen hoeveel bytes u toegewezen,

754
01:07:52,330 --> 01:07:57,150
hoeveel bytes u bevrijd, en het zal u vertellen of u net genoeg bevrijd

755
01:07:57,150 --> 01:07:58,930
of dat je niet vrij genoeg,

756
01:07:58,930 --> 01:08:02,850
of soms kun je zelfs over-vrij, zoals gratis een knooppunt dat is al bevrijd

757
01:08:02,850 --> 01:08:05,140
en zo zal het u terug fouten.

758
01:08:05,140 --> 01:08:11,600
Als u gebruik maakt Valgrind, zal het u een aantal berichten

759
01:08:11,600 --> 01:08:15,970
aangeeft of u ofwel hebt minder dan genoeg bevrijd, net genoeg,

760
01:08:15,970 --> 01:08:19,609
of meer dan genoeg keer.

761
01:08:24,370 --> 01:08:30,410
>> Een deel van deze PSET, is het optioneel om uitdagen The Big Board.

762
01:08:30,410 --> 01:08:35,790
Maar als we te maken hebben met deze datastructuren

763
01:08:35,790 --> 01:08:40,689
het is wel leuk om te zien hoe snel en hoe efficiënt uw data structuren zou kunnen zijn.

764
01:08:40,689 --> 01:08:44,490
Heeft uw hash-functie resulteert in een veel botsingen?

765
01:08:44,490 --> 01:08:46,300
Of is uw data grootte echt groot?

766
01:08:46,300 --> 01:08:49,420
Kost het veel tijd om te doorkruisen?

767
01:08:49,420 --> 01:08:54,800
In het logboek van de speller, het systeem voert hoeveel tijd die u gebruikt om te laden,

768
01:08:54,800 --> 01:08:57,700
om te controleren, op maat uit te voeren, en te lossen,

769
01:08:57,700 --> 01:09:00,720
en dus die zijn geplaatst in The Big Board,

770
01:09:00,720 --> 01:09:03,600
waar kun je het tegen je klasgenoten

771
01:09:03,600 --> 01:09:11,350
en een aantal medewerkers om te zien wie heeft de snelste spellingcontrole.

772
01:09:11,350 --> 01:09:14,760
Een ding dat ik zou willen om op te merken over de hash tables

773
01:09:14,760 --> 01:09:20,470
is dat er een aantal vrij eenvoudig hash functies die we konden bedenken.

774
01:09:20,470 --> 01:09:27,240
Bijvoorbeeld, je hebt 26 emmers, en zo elke emmer

775
01:09:27,240 --> 01:09:30,200
overeenkomt met de eerste letter van een woord,

776
01:09:30,200 --> 01:09:35,229
maar dat gaat resulteren in een vrij onevenwichtige hash-tabel

777
01:09:35,229 --> 01:09:40,979
omdat er veel minder woorden die met X beginnen dan beginnen met M, bijvoorbeeld.

778
01:09:40,979 --> 01:09:47,890
Een manier om te gaan over speller is als u alle andere functionaliteit te krijgen naar beneden,

779
01:09:47,890 --> 01:09:53,240
dan gewoon gebruik maken van een eenvoudige hash-functie te kunnen om uw code die wordt uitgevoerd

780
01:09:53,240 --> 01:09:58,650
en ga dan terug en wijzig de grootte van uw hash tabel en de definitie.

781
01:09:58,650 --> 01:10:03,430
Er zijn heel wat middelen op het internet voor hash-functies,

782
01:10:03,430 --> 01:10:08,250
en dus voor deze PSET je mag hashfuncties onderzoek op het internet

783
01:10:08,250 --> 01:10:15,560
voor wat tips en inspiratie, zolang je ervoor zorgen om te verwijzen waar heb je het uit.

784
01:10:15,560 --> 01:10:22,060
Je bent van harte welkom om te kijken en te interpreteren wat hash-functie die u vindt op het internet.

785
01:10:22,060 --> 01:10:27,460
Terug naar dat, zou je in staat zijn om te zien of iemand gebruik gemaakt van een trie

786
01:10:27,460 --> 01:10:31,700
of de uitvoering ervan is sneller dan je hash-tabel of niet.

787
01:10:31,700 --> 01:10:35,290
U kunt indienen bij het grote bord meerdere keren.

788
01:10:35,290 --> 01:10:37,660
Het zal opnemen van uw meest recente item.

789
01:10:37,660 --> 01:10:44,300
Dus misschien heb je je hashing-functie en dan beseffen dat het eigenlijk een stuk sneller

790
01:10:44,300 --> 01:10:46,780
of een stuk langzamer dan voorheen.

791
01:10:46,780 --> 01:10:50,960
Dat is een beetje een leuke manier.

792
01:10:50,960 --> 01:10:57,190
Er is altijd 1 of 2 medewerkers die proberen om een ​​zo laag mogelijk woordenboek te maken,

793
01:10:57,190 --> 01:11:00,210
dus dat is altijd leuk om naar te kijken.

794
01:11:00,210 --> 01:11:07,630
>> Het gebruik van de PSET is dat je speller loopt met een optionele woordenboek

795
01:11:07,630 --> 01:11:12,840
en dan een verplichte tekstbestand.

796
01:11:12,840 --> 01:11:18,380
Standaard wanneer u speller met slechts een tekstbestand en niet specificeren een woordenboek,

797
01:11:18,380 --> 01:11:24,410
het gaat om het woordenboek tekstbestand, de grote men gebruik maken van

798
01:11:24,410 --> 01:11:27,920
in de cs50/pset5/dictionaries map.

799
01:11:27,920 --> 01:11:32,760
Die ene heeft meer dan 100.000 woorden.

800
01:11:32,760 --> 01:11:37,950
Ze hebben ook een kleine woordenboek dat aanzienlijk minder woorden heeft

801
01:11:37,950 --> 01:11:40,730
dat CS50 heeft voor u gemaakt.

802
01:11:40,730 --> 01:11:44,050
Echter, kunt u heel eenvoudig gewoon uw eigen woordenboek

803
01:11:44,050 --> 01:11:47,150
als je gewoon wilt om te werken in kleine voorbeelden -

804
01:11:47,150 --> 01:11:51,140
bijvoorbeeld, als u wilt gdb gebruiken en je weet de specifieke waarden

805
01:11:51,140 --> 01:11:53,560
dat u wilt dat uw hash-tabel in kaart te.

806
01:11:53,560 --> 01:12:00,430
Zo kunt u uw eigen tekst bestand gewoon alleen met BAR, BAZ, FOO, en FOOBAR,

807
01:12:00,430 --> 01:12:04,860
maken dat in een tekstbestand, gescheiden mensen elk met 1 regel,

808
01:12:04,860 --> 01:12:12,670
en maak uw eigen tekst bestand dat alleen letterlijk bevat misschien 1 of 2 woorden

809
01:12:12,670 --> 01:12:15,950
zodat u precies weet wat de output zou moeten zijn.

810
01:12:15,950 --> 01:12:21,870
Een deel van het monster tekstbestandjes die in The Big Board als je uitdaging loopt zal controleren

811
01:12:21,870 --> 01:12:25,580
zijn Oorlog en Vrede en een roman van Jane Austen of iets dergelijks.

812
01:12:25,580 --> 01:12:30,450
Dus als je begint, is het een stuk gemakkelijker om uw eigen tekst bestanden

813
01:12:30,450 --> 01:12:34,160
die bevatten slechts een paar woorden of misschien 10

814
01:12:34,160 --> 01:12:38,280
zodat u kunt voorspellen wat de uitkomst zou moeten zijn

815
01:12:38,280 --> 01:12:42,880
en controleer vervolgens het tegen dat, dus meer van een gecontroleerde voorbeeld.

816
01:12:42,880 --> 01:12:45,820
En dus, omdat we te maken hebben met het voorspellen van en tekenen dingen rond,

817
01:12:45,820 --> 01:12:48,690
nogmaals, ik wil u aanmoedigen om pen en papier te gebruiken

818
01:12:48,690 --> 01:12:50,700
omdat het echt gaat om u te helpen met deze -

819
01:12:50,700 --> 01:12:55,620
het tekenen van de pijlen, hoe de hash-tabel of hoe je eruit ziet trie,

820
01:12:55,620 --> 01:12:57,980
als je het vrijmaken van iets waar de pijlen gaan,

821
01:12:57,980 --> 01:13:01,730
je vasthouden aan genoeg, zie je alle links verdwijnen

822
01:13:01,730 --> 01:13:05,750
en vallen in de afgrond van gelekte geheugen.

823
01:13:05,750 --> 01:13:11,070
Dus alsjeblieft, probeer om dingen te tekenen, zelfs voordat je bij het schrijven van code beneden.

824
01:13:11,070 --> 01:13:14,520
Teken dingen uit, zodat u weet hoe de dingen gaan aan de slag

825
01:13:14,520 --> 01:13:22,750
want dan garandeer ik je daar tegenkomen minder pointer warboel.

826
01:13:24,270 --> 01:13:25,910
>> Oke.

827
01:13:25,910 --> 01:13:28,780
Ik wens u het allerbeste van geluk met deze PSET.

828
01:13:28,780 --> 01:13:31,980
Het is waarschijnlijk de moeilijkste.

829
01:13:31,980 --> 01:13:40,360
Dus probeer te vroeg beginnen, trekken dingen uit, trekken dingen uit, en veel geluk.

830
01:13:40,360 --> 01:13:42,980
Dit was Walkthrough 5.

831
01:13:45,160 --> 01:13:47,000
>> [CS50.TV]