1
00:00:00,000 --> 00:00:09,700

2
00:00:09,700 --> 00:00:12,140
>> ZAMYLA CHAN: Let's make
een spellingscontrole.

3
00:00:12,140 --> 00:00:16,900
Als je speller.c opent, dan zie je
dat de meeste functionaliteit

4
00:00:16,900 --> 00:00:20,810
het controleren van een tekst bestand tegen een
woordenboek is al voor u gemaakt.

5
00:00:20,810 --> 00:00:26,330
. / Speller, passeren in een woordenboek tekst
bestand en dan nog een tekstbestand,

6
00:00:26,330 --> 00:00:28,960
zal dat tekstbestand controleren
tegen het woordenboek.

7
00:00:28,960 --> 00:00:34,160
>> Nu zal woordenboek tekstbestanden bevatten
geldige woorden, een per regel.

8
00:00:34,160 --> 00:00:37,910
Dan zal speller.c Load bellen
op het woordenboek tekstbestand.

9
00:00:37,910 --> 00:00:43,650
Het zal noemen een functie genaamd Controle op
elk woord in de ingevoerde tekst bestand,

10
00:00:43,650 --> 00:00:46,460
het afdrukken van alle verkeerd gespelde woorden.

11
00:00:46,460 --> 00:00:50,030
>> Speller.c zal ook Grootte bellen om
bepalen het aantal woorden in

12
00:00:50,030 --> 00:00:53,500
woordenboek en bel Unload
om geheugen vrij te maken.

13
00:00:53,500 --> 00:00:57,600
speller.c zal ook bijhouden hoe houden
veel tijd wordt gebruikt voor het uitvoeren van deze

14
00:00:57,600 --> 00:01:00,560
processen, maar we zullen
krijgen om dat later.

15
00:01:00,560 --> 00:01:02,440
>> Dus wat moeten we doen?

16
00:01:02,440 --> 00:01:05,110
We moeten in dictionary.c te vullen.

17
00:01:05,110 --> 00:01:09,940
In dictionary.c, hebben we de helper
Load-functie, die de geladen

18
00:01:09,940 --> 00:01:10,855
woordenboek.

19
00:01:10,855 --> 00:01:15,490
De functie Controle, die controleert of
een bepaald woord in het woordenboek.

20
00:01:15,490 --> 00:01:19,150
De functie Size geeft het aantal
van woorden in het woordenboek.

21
00:01:19,150 --> 00:01:24,870
En tot slot, we hebben ontlasten, die
bevrijdt het woordenboek uit het geheugen.

22
00:01:24,870 --> 00:01:27,070
>> Dus laten we eerst eens aan te pakken Load.

23
00:01:27,070 --> 00:01:32,110
Voor elk woord in het woordenboek tekst
bestand, zal de belasting die woorden op te slaan in

24
00:01:32,110 --> 00:01:34,860
het woordenboek datastructuur
van uw keuze, ofwel een

25
00:01:34,860 --> 00:01:36,750
hash table of een Trie.

26
00:01:36,750 --> 00:01:39,440
Ik ga over zowel in
deze lopen door.

27
00:01:39,440 --> 00:01:43,150
>> Laten we het eerst hebben over hash tables.

28
00:01:43,150 --> 00:01:47,050
Zeggen dat je had 10 biljartballen en
je wilde ze op te slaan.

29
00:01:47,050 --> 00:01:50,420
Je zou ze allemaal in een emmer,
en als je een specifiek nodig

30
00:01:50,420 --> 00:01:54,010
genummerde bal, zou je een te nemen
uit de emmer op een moment

31
00:01:54,010 --> 00:01:55,880
op zoek naar die bal.

32
00:01:55,880 --> 00:01:59,370
En met slechts 10 ballen, moet u
in staat om je bal te vinden in een redelijke

33
00:01:59,370 --> 00:02:01,160
tijd.

34
00:02:01,160 --> 00:02:03,180
>> Maar wat als je 20 ballen gehad?

35
00:02:03,180 --> 00:02:05,480
Het is misschien een beetje langer nu nemen.

36
00:02:05,480 --> 00:02:06,180
Hoe zit het met 100?

37
00:02:06,180 --> 00:02:07,880
1000?

38
00:02:07,880 --> 00:02:11,590
Nu, zou het veel gemakkelijker zijn als
je had meerdere emmers.

39
00:02:11,590 --> 00:02:15,890
Misschien een emmer voor ballen genummerd nul
tot en met negen, een andere emmer voor

40
00:02:15,890 --> 00:02:18,800
genummerd van 10 tot en met
19, enzovoort.

41
00:02:18,800 --> 00:02:22,330
>> Als u nu nodig om te zoeken naar specifieke
bal, kon je automatisch

42
00:02:22,330 --> 00:02:26,320
gaan naar een specifieke emmer en
zoeken door die emmer.

43
00:02:26,320 --> 00:02:29,840
En als elke emmer heeft ongeveer 10
ballen, dan kun je gemakkelijk zoeken

44
00:02:29,840 --> 00:02:31,790
doorheen.

45
00:02:31,790 --> 00:02:34,960
>> Nu, aangezien we te maken hebben met
woordenboeken, een enkele emmer voor

46
00:02:34,960 --> 00:02:41,970
alle woorden in het woordenboek zal
waarschijnlijk veel te weinig emmers.

47
00:02:41,970 --> 00:02:44,370
Dus laten we eens een kijkje nemen op hash tables.

48
00:02:44,370 --> 00:02:46,940
>> Zie het als een array van emmers.

49
00:02:46,940 --> 00:02:50,370
En in dit geval, de emmers
zijn onze gelinkte lijsten.

50
00:02:50,370 --> 00:02:54,770
En we zullen al onze woorden te verdelen
onder deze meerdere gekoppelde lijsten in

51
00:02:54,770 --> 00:02:58,940
een georganiseerde manier met behulp van een hash-functie,
die ons zal vertellen welke

52
00:02:58,940 --> 00:03:03,720
emmer een bepaalde sleutel, een gegeven
woord, behoort.

53
00:03:03,720 --> 00:03:05,960
>> Laten we vertegenwoordigen dit schematisch.

54
00:03:05,960 --> 00:03:11,320
De blauwe dozen hier bevatten waarden en
rode dozen wijzen op een andere waarde

55
00:03:11,320 --> 00:03:12,280
pointer paar.

56
00:03:12,280 --> 00:03:14,800
We zullen deze paren knopen noemen.

57
00:03:14,800 --> 00:03:18,260
Nu, elke emmer, zoals ik al zei
eerder, is een gelinkte lijst.

58
00:03:18,260 --> 00:03:21,820
In gekoppelde lijsten, elk knooppunt een waarde
alsmede een pointer naar de

59
00:03:21,820 --> 00:03:23,170
volgende waarde.

60
00:03:23,170 --> 00:03:26,150
>> Nu, het omgaan met gelinkte lijsten,
het is erg belangrijk dat u

61
00:03:26,150 --> 00:03:28,120
verliest geen koppelingen.

62
00:03:28,120 --> 00:03:32,250
En een ander feit om te onthouden is dat de
laatste knoop, als het niet wijzen op

63
00:03:32,250 --> 00:03:35,120
ander knooppunt, wijst op null.

64
00:03:35,120 --> 00:03:37,970
>> Dus hoe kunnen we deze vertegenwoordigen in C?

65
00:03:37,970 --> 00:03:40,540
We definiëren hier onze structuur.

66
00:03:40,540 --> 00:03:44,850
En de waarde is in dit geval
een char array met lengte.

67
00:03:44,850 --> 00:03:48,880
Lengte plus 1, waarbij de lengte
maximale lengte van een woord, plus 1 voor

68
00:03:48,880 --> 00:03:50,380
de null-terminator.

69
00:03:50,380 --> 00:03:54,210
En dan hebben we een pointer naar
ander knooppunt genaamd Next.

70
00:03:54,210 --> 00:03:56,730
>> Dus laten we een klein gelinkte lijst.

71
00:03:56,730 --> 00:04:00,390
Ten eerste, zult u wilt uw knooppunt malloc,
die ruimte in het geheugen van de

72
00:04:00,390 --> 00:04:04,010
grootte van uw knooppunt type.

73
00:04:04,010 --> 00:04:06,100
En maak een ander knooppunt,
weer mallocing.

74
00:04:06,100 --> 00:04:09,370

75
00:04:09,370 --> 00:04:14,340
>> Nu als je wilt om een ​​waarde toe te kennen aan een
woord, dan zouden we kunnen zeggen node1 pijl

76
00:04:14,340 --> 00:04:18,820
woord is gelijk aan "Hallo." Deze pijl operator
dereferences de aanwijzer en

77
00:04:18,820 --> 00:04:20,620
toegang tot variabelen van de struct's.

78
00:04:20,620 --> 00:04:24,330
Op deze manier hoeven we niet te gebruiken beide
de stip en de ster operator.

79
00:04:24,330 --> 00:04:30,100
>> Dus dan heb ik clustnode2 pijl woord gelijk
"Wereld." En daar de waarden

80
00:04:30,100 --> 00:04:33,110
bevolkt in mijn knooppunten.

81
00:04:33,110 --> 00:04:38,780
Om de links te maken, zal ik pas in node1
pijl naast, de toegang die knoop ster,

82
00:04:38,780 --> 00:04:44,160
dat knooppunt wijzer, gelijk clustnode2,
wijzend node1 te clustnode2 twee.

83
00:04:44,160 --> 00:04:46,360
En daar hebben we een gelinkte lijst.

84
00:04:46,360 --> 00:04:51,480
>> Dus dat was slechts een gelinkte lijst, maar
een hash table is een hele reeks van

85
00:04:51,480 --> 00:04:52,520
gelinkte lijsten.

86
00:04:52,520 --> 00:04:55,920
Nou, zullen we dezelfde knoop hebben
structuur als voorheen.

87
00:04:55,920 --> 00:05:00,140
Maar als we wilden een echte hash table,
dan kunnen we gewoon een knooppunt aanwijzer

88
00:05:00,140 --> 00:05:01,330
serie hier.

89
00:05:01,330 --> 00:05:04,940
Bijvoorbeeld, maat 500.

90
00:05:04,940 --> 00:05:08,910
>> Nu mededeling, er gaat een handel zijn
off tussen de grootte van uw

91
00:05:08,910 --> 00:05:11,280
hash table en de grootte
van uw gelinkte lijsten.

92
00:05:11,280 --> 00:05:15,640
Als je een echt hoge aantal
emmers, verbeelden hoeven terug te draaien

93
00:05:15,640 --> 00:05:18,230
en weer in een lijn
vind je emmer.

94
00:05:18,230 --> 00:05:21,530
Maar je wilt ook niet een klein aantal
emmers, want dan zijn we terug naar

95
00:05:21,530 --> 00:05:26,850
het oorspronkelijke probleem van hoe het hebben
te veel ballen in onze emmer.

96
00:05:26,850 --> 00:05:30,480
>> OK, maar waar komt onze bal heen?

97
00:05:30,480 --> 00:05:33,150
Nou, moeten we eerst
een bal hebben, toch?

98
00:05:33,150 --> 00:05:39,130
Dus laten we malloc een knooppunt voor elke
nieuw woord dat we hebben.

99
00:05:39,130 --> 00:05:42,900
knooppunt * new_node gelijken
malloc (sizeof (node)).

100
00:05:42,900 --> 00:05:46,760
>> Nu we deze structuur, we
kan scannen in, met behulp van de functie

101
00:05:46,760 --> 00:05:51,850
fscanf, een string uit ons bestand, indien
dat is een woordenboek bestand, in

102
00:05:51,850 --> 00:05:55,780
new_node pijl woord, waar new_node
pijl woord is onze

103
00:05:55,780 --> 00:05:58,110
bestemming van dat woord.

104
00:05:58,110 --> 00:06:01,900
>> Vervolgens zullen we willen hash dat
woord met behulp van een hash-functie.

105
00:06:01,900 --> 00:06:05,860
Een hash-functie neemt een string
en geeft een index.

106
00:06:05,860 --> 00:06:09,760
In dit geval, de index moet
minder dan het aantal

107
00:06:09,760 --> 00:06:11,440
emmers die je hebt.

108
00:06:11,440 --> 00:06:14,600
>> Nu, hash functies, als je probeert
er een te vinden en creëren een van

109
00:06:14,600 --> 00:06:17,890
uw eigen, vergeet niet dat ze
moet deterministisch zijn.

110
00:06:17,890 --> 00:06:22,420
Dit betekent dat dezelfde waarde moet
toewijzen aan dezelfde emmer elke keer

111
00:06:22,420 --> 00:06:23,800
dat je hash het.

112
00:06:23,800 --> 00:06:25,300
>> Het is net zoiets als een bibliotheek.

113
00:06:25,300 --> 00:06:28,560
Wanneer u een boek, op basis van de te nemen
auteur, weet u welke plank het zou moeten

114
00:06:28,560 --> 00:06:31,890
gaan, of het nu plaatsnummer
een, twee of drie.

115
00:06:31,890 --> 00:06:36,280
En dat boek zal altijd thuis op
ofwel plank een, twee, of drie.

116
00:06:36,280 --> 00:06:39,460

117
00:06:39,460 --> 00:06:43,810
>> Dus, als new_node pijl woord heeft de
Het woord van uw woordenboek, dan

118
00:06:43,810 --> 00:06:47,770
hashing new_node pijl woord zal
geven ons de index van de

119
00:06:47,770 --> 00:06:49,370
emmer van de hash table.

120
00:06:49,370 --> 00:06:54,040
En dan zullen we voegen dat in die
specifieke gelinkte lijst wordt aangegeven door de

121
00:06:54,040 --> 00:06:56,060
waarde van onze hash-functie terug te keren.

122
00:06:56,060 --> 00:06:59,070
>> Laten we eens kijken naar een voorbeeld van
inbrengen van een knooppunt in de

123
00:06:59,070 --> 00:07:01,750
het begin van een gelinkte lijst.

124
00:07:01,750 --> 00:07:06,930
Als hoofd is een knooppunt aanwijzer die aangeeft
het begin van een gekoppelde

125
00:07:06,930 --> 00:07:12,420
lijst en new_node geeft de nieuwe
knooppunt dat u wilt in te gaan, maar

126
00:07:12,420 --> 00:07:17,340
toewijzen van kop tot new_node zou verliezen
de link naar de rest van de lijst.

127
00:07:17,340 --> 00:07:19,330
Zodat we niet willen doen.

128
00:07:19,330 --> 00:07:22,160
>> Integendeel, we willen ervoor zorgen dat
dat we vasthouden aan elke

129
00:07:22,160 --> 00:07:23,550
enkele knoop in ons programma.

130
00:07:23,550 --> 00:07:29,560
Dus loopt new_node pijl naast gelijken
hoofd en vervolgens hoofd gelijk new_node

131
00:07:29,560 --> 00:07:34,470
zullen alle van de te behouden
koppelingen en verliest geen.

132
00:07:34,470 --> 00:07:39,330
>> Maar wat als u wilt dat uw lijst te zijn
gesorteerd, omdat het hebben van een gesorteerde gekoppeld

133
00:07:39,330 --> 00:07:42,910
lijst is misschien makkelijker voor
zoek het later?

134
00:07:42,910 --> 00:07:46,020
Nou, voor dat, moet u weten
hoe gelinkte lijsten doorkruisen.

135
00:07:46,020 --> 00:07:51,210
>> Om een ​​gekoppelde lijst doorkruisen, laten we
een knooppunt pointer, een knooppunt *, om als

136
00:07:51,210 --> 00:07:54,120
uw cursor, die aangeeft welke
knooppunt je toch bezig bent, te beginnen

137
00:07:54,120 --> 00:07:55,460
in het eerste element.

138
00:07:55,460 --> 00:08:01,070
Looping tot cursor nul is, kunnen we
voeren bepaalde processen en vervolgens

139
00:08:01,070 --> 00:08:04,330
vooraf de cursor wanneer we het nodig
gebruik cursor pijl waarde.

140
00:08:04,330 --> 00:08:08,820
>> Vergeet niet, dit is hetzelfde als
zeggende ster cursor, dereferentie

141
00:08:08,820 --> 00:08:13,480
cursor, vervolgens met behulp van de
operator punt waarde.

142
00:08:13,480 --> 00:08:19,000
Dus bijwerken van de cursor door het toewijzen
de cursor naar cursor pijl naast.

143
00:08:19,000 --> 00:08:24,960
>> Zeggen u hebt vastgesteld dat D wordt in
tussen C en E. De knoop voegen,

144
00:08:24,960 --> 00:08:30,030
hebben de new_node D wijzen op de
knooppunt E, dat is cursor naast.

145
00:08:30,030 --> 00:08:36,409
En dan C, de cursor, kan wijs
D. Op die manier behoudt u een lijst.

146
00:08:36,409 --> 00:08:41,080
Wees voorzichtig niet om uw links te verliezen door
het verplaatsen van de cursor naast D

147
00:08:41,080 --> 00:08:43,929
meteen.

148
00:08:43,929 --> 00:08:44,620
>> Oke.

149
00:08:44,620 --> 00:08:48,920
Dus dat is hoe je nodes zouden kunnen opnemen,
plaats ze in, belasting woorden in die

150
00:08:48,920 --> 00:08:51,600
knooppunten, en plaats ze
in uw hash table.

151
00:08:51,600 --> 00:08:53,580
Dus laten we nu eens kijken naar pogingen.

152
00:08:53,580 --> 00:08:58,540
>> In een Trie, zal elk knooppunt een bevatten
reeks knooppunt pointers, een voor elke

153
00:08:58,540 --> 00:09:02,260
letter in het alfabet
plus een apostrof.

154
00:09:02,260 --> 00:09:06,150
En elk element in de array
zal wijzen naar een ander knooppunt.

155
00:09:06,150 --> 00:09:10,130
Als dat knooppunt nul is, dan is dat brief
is niet van plan om de volgende letter van zijn

156
00:09:10,130 --> 00:09:15,690
een woord in een reeks, omdat elke
woord geeft aan of het is de laatste

157
00:09:15,690 --> 00:09:18,160
karakter van een woord of niet.

158
00:09:18,160 --> 00:09:19,750
>> Laten we eens kijken naar een diagram.

159
00:09:19,750 --> 00:09:22,260
Hopelijk zal
een beetje duidelijker.

160
00:09:22,260 --> 00:09:27,210
In dit diagram zien we dat alleen
bepaalde letters en bepaalde substrings

161
00:09:27,210 --> 00:09:28,190
worden vermeld uit.

162
00:09:28,190 --> 00:09:32,500
Zo kunt u bepaalde paden te volgen, en
al die paden zal u leiden tot

163
00:09:32,500 --> 00:09:34,020
verschillende woorden.

164
00:09:34,020 --> 00:09:37,630
>> Dus hoe kunnen we deze vertegenwoordigen in C?

165
00:09:37,630 --> 00:09:41,910
Nou, elke knoop nu zal hebben
een Booleaanse waarde die aangeeft of

166
00:09:41,910 --> 00:09:46,580
dat knooppunt eind
een bepaald woord of niet.

167
00:09:46,580 --> 00:09:50,690
En dan zal het ook hebben een scala aan
knooppunt pointers genaamd kinderen, en

168
00:09:50,690 --> 00:09:53,440
er zullen zijn 27 van hen.

169
00:09:53,440 --> 00:09:56,510
En vergeet niet, je zult ook willen
bijhouden van uw eerste knooppunt.

170
00:09:56,510 --> 00:09:59,830
We gaan die wortel noemen.

171
00:09:59,830 --> 00:10:01,690
>> Dat is de structuur van een trie.

172
00:10:01,690 --> 00:10:05,630
Hoe gaan we deze vertegenwoordigen
als een woordenboek?

173
00:10:05,630 --> 00:10:09,890
Nou, om woorden te laden in, voor elke
woord uit het woordenboek, je gaat te willen

174
00:10:09,890 --> 00:10:11,960
te doorlopen de Trie.

175
00:10:11,960 --> 00:10:16,170
En elk element in de kinderen
komt overeen met een andere letter.

176
00:10:16,170 --> 00:10:21,660
>> Dus het controleren van de waarde bij kinderen
index i, waarbij i de

177
00:10:21,660 --> 00:10:24,840
specifieke index van de brief die
je probeert in te voegen.

178
00:10:24,840 --> 00:10:28,980
Nou, als het null, dan zult u wilt
malloc een nieuw knooppunt en kinderen

179
00:10:28,980 --> 00:10:31,110
ik wijzen op dat knooppunt.

180
00:10:31,110 --> 00:10:35,630
>> Als het niet null, dan betekent dat dat
dat bepaalde tak van dat gegeven

181
00:10:35,630 --> 00:10:37,350
substring, al bestaat.

182
00:10:37,350 --> 00:10:40,160
Dus dan zul je gewoon naar die
nieuwe knooppunt en doorgaan.

183
00:10:40,160 --> 00:10:43,220
Als je aan het eind van het woord dat
je probeert te laden in de

184
00:10:43,220 --> 00:10:48,120
woordenboek, dan kunt u instellen dat
huidige knooppunt dat je op true.

185
00:10:48,120 --> 00:10:51,550
>> Dus laten we eens kijken naar een voorbeeld van het plaatsen van
het woord "vos" in onze

186
00:10:51,550 --> 00:10:53,070
woordenboek.

187
00:10:53,070 --> 00:10:56,110
Doen alsof we beginnen met
een leeg woordenboek.

188
00:10:56,110 --> 00:11:01,610
De eerste brief, F, zal worden gevestigd
bij kinderen index vijf van de wortels

189
00:11:01,610 --> 00:11:03,700
kinderen array.

190
00:11:03,700 --> 00:11:05,430
Zodat voegen we binnen

191
00:11:05,430 --> 00:11:14,610
>> De letter O wordt dan bij kinderen
index 15, na dat F. En dan X

192
00:11:14,610 --> 00:11:20,180
zal zelfs daaronder vertakking
off van de kinderen van de O's.

193
00:11:20,180 --> 00:11:24,120
En dan, omdat X is de laatste letter
van het woord "vos", dan ga ik

194
00:11:24,120 --> 00:11:27,210
kleur groen wanneer
het is het einde van het woord.

195
00:11:27,210 --> 00:11:32,880
In C, zou dat zijn instelling de Is
Woord Boolean om de waarde true.

196
00:11:32,880 --> 00:11:36,780
>> Nu, wat als het volgende woord dat je
laden in het woord "foo"?

197
00:11:36,780 --> 00:11:41,490
Nou, je hoeft niet meer hoeft te malloc
ruimte voor F of voor O, omdat

198
00:11:41,490 --> 00:11:42,990
deze bestaan.

199
00:11:42,990 --> 00:11:45,910
Maar de laatste O in foo?

200
00:11:45,910 --> 00:11:47,320
Die ene, dan moet je malloc.

201
00:11:47,320 --> 00:11:52,390
Maak een nieuw knooppunt voor dat, het instellen
Is het Woord Boolean true.

202
00:11:52,390 --> 00:11:57,340
>> Dus laten we nu invoegen "hond." Hond zal
beginnen met index drie wortels

203
00:11:57,340 --> 00:12:00,520
kinderen, want D heeft niet
nog niet gemaakt.

204
00:12:00,520 --> 00:12:04,990
En we zullen een soortgelijk proces als volgt
voor, het creëren van de substring hond,

205
00:12:04,990 --> 00:12:10,400
Waar is de G is groen gekleurd, omdat
dit is het einde van een woord.

206
00:12:10,400 --> 00:12:13,160
>> Nu, wat als we willen invoegen "doen"?

207
00:12:13,160 --> 00:12:17,150
Nou, dit is een substring van de hond, dus
we hoeven niet meer te malloc.

208
00:12:17,150 --> 00:12:20,800
Maar we moeten wel aangeven waar we hebben
aan het einde van dat woord.

209
00:12:20,800 --> 00:12:24,020
Dus de O zal groen gekleurd.

210
00:12:24,020 --> 00:12:27,810
Voortzetting van dat proces voor elke
woord in uw woordenboek, je hebt

211
00:12:27,810 --> 00:12:32,120
geladen ze in in ofwel uw
hash table of uw trie.

212
00:12:32,120 --> 00:12:37,530
>> speller.c passeert in strings voor
dictionary.c om ze te controleren.

213
00:12:37,530 --> 00:12:41,140
Nu, de Check-functie moet opereren
onder geval ongevoeligheid.

214
00:12:41,140 --> 00:12:45,980
Dat betekent dat hoofdletters en
kleine letters en een mix van beide

215
00:12:45,980 --> 00:12:50,670
moeten alle gelijk om waar eventueel
combinatie daarvan is in de

216
00:12:50,670 --> 00:12:51,880
woordenboek.

217
00:12:51,880 --> 00:12:55,580
U kunt ook aannemen dat strings
alleen maar alfabetisch te bevatten

218
00:12:55,580 --> 00:12:58,200
tekens of apostrof.

219
00:12:58,200 --> 00:13:02,490
>> Dus laten we eens kijken hoe je zou controleren
met een hash table structuur.

220
00:13:02,490 --> 00:13:07,330
Nou, als het woord bestaat, dan is het
kan worden gevonden in de hash tabel.

221
00:13:07,330 --> 00:13:12,240
Dus dan kun je proberen te vinden dat
woord in de desbetreffende bak.

222
00:13:12,240 --> 00:13:14,480
>> Dus welke emmer zou dat woord in?

223
00:13:14,480 --> 00:13:20,060
Nou, je zou het nummer, die index te krijgen
van de bak, door hashing dat woord

224
00:13:20,060 --> 00:13:23,690
en dan zoeken in die gelinkte lijst,
doorkruist door de gehele

225
00:13:23,690 --> 00:13:28,060
gelinkte lijst, met behulp van de String
Vergelijk functie.

226
00:13:28,060 --> 00:13:31,940
>> Als het uiteinde van de gekoppelde lijst
bereikt, wat betekent dat uw cursor

227
00:13:31,940 --> 00:13:36,030
bereikt null, dan is het woord niet
te vinden in het woordenboek.

228
00:13:36,030 --> 00:13:39,090
Het zal niet in een andere bak.

229
00:13:39,090 --> 00:13:43,020
Dus hier, zou je zien hoe er misschien
is een trade-off tussen het hebben van een van beide

230
00:13:43,020 --> 00:13:46,280
gesorteerd gelinkte lijsten of ongesorteerde degenen.

231
00:13:46,280 --> 00:13:51,180
Ofwel zal meer tijd in beslag nemen tijdens
laden of meer tijd bij het inchecken.

232
00:13:51,180 --> 00:13:53,560
>> Hoe zou u incheckt
een trie-structuur?

233
00:13:53,560 --> 00:13:56,370
We gaan naar beneden te reizen
in trie.

234
00:13:56,370 --> 00:14:00,390
Voor elke letter in het ingevoerde woord
dat we het controleren, gaan we naar dat

235
00:14:00,390 --> 00:14:03,280
overeenkomstige element in de kinderen.

236
00:14:03,280 --> 00:14:07,770
>> Als dat element nul is, dan is dat middelen
dat er geen substrings

237
00:14:07,770 --> 00:14:11,110
met onze inbreng woord, dus
het woord verkeerd is gespeld.

238
00:14:11,110 --> 00:14:15,140
Als het niet null is, kunnen we overgaan tot de
volgende letter van het woord dat we

239
00:14:15,140 --> 00:14:18,850
controleren en blijven dit proces
totdat we het einde bereiken

240
00:14:18,850 --> 00:14:20,350
van de ingang woord.

241
00:14:20,350 --> 00:14:23,330
En dan kunnen we controleren
Als Is Woord waar is.

242
00:14:23,330 --> 00:14:24,610
Zo ja, dan groot.

243
00:14:24,610 --> 00:14:25,590
Het woord klopt.

244
00:14:25,590 --> 00:14:30,890
Maar zo niet, ook al is dat substring
bestaat in de trie, het woord is

245
00:14:30,890 --> 00:14:32,250
verkeerd gespeld.

246
00:14:32,250 --> 00:14:36,590
>> Wanneer de functie Grootte wordt genoemd, de grootte
moet het aantal woorden terug die

247
00:14:36,590 --> 00:14:39,110
zijn in uw gegeven woordenboek
gegevensstructuur.

248
00:14:39,110 --> 00:14:42,780
Dus als u een hash table, u
kan ofwel gaan door elke

249
00:14:42,780 --> 00:14:45,860
gelinkte lijst in elk
emmer tellen van het aantal

250
00:14:45,860 --> 00:14:47,130
woorden zijn er.

251
00:14:47,130 --> 00:14:49,940
Als u gebruik maakt van een Trie, kunt u
gaan door elke niet-null

252
00:14:49,940 --> 00:14:52,030
pad in uw trie.

253
00:14:52,030 --> 00:14:56,420
Of terwijl je het laden van het woordenboek
in, misschien kun je bijhouden hoe

254
00:14:56,420 --> 00:14:58,760
veel woorden je laden inch

255
00:14:58,760 --> 00:15:03,180
>> Zodra speller.c eindigt het controleren van de
tekstbestand tegen het woordenboek, dan

256
00:15:03,180 --> 00:15:08,010
het is gedaan en dus het roept Unload, waar
uw taak is om iets te bevrijden

257
00:15:08,010 --> 00:15:09,500
dat u malloced.

258
00:15:09,500 --> 00:15:14,420
Dus als je een hash tabel gebruiken, dan moet je
moeten extra voorzichtig om te voorkomen dat zijn

259
00:15:14,420 --> 00:15:18,830
geheugenlekken door niets te bevrijden
voortijdig en het bedrijf op elke

260
00:15:18,830 --> 00:15:20,780
single link voordat u gratis.

261
00:15:20,780 --> 00:15:24,680

262
00:15:24,680 --> 00:15:30,100
>> Dus voor elk element in de hash-tabel
en voor elke knooppunt in de gekoppelde lijst

263
00:15:30,100 --> 00:15:32,370
wil je bevrijden dat knooppunt.

264
00:15:32,370 --> 00:15:34,970
Hoe ga je over het vrijmaken
een gekoppelde lijst?

265
00:15:34,970 --> 00:15:38,570
Uw knooppunt pointer cursor naar het instellen
de kop, aan het begin van de

266
00:15:38,570 --> 00:15:43,100
gelinkte lijst, dan terwijl je cursor
is niet nul, kunt u een tijdelijke set

267
00:15:43,100 --> 00:15:45,610
knooppunt pointer naar de cursor.

268
00:15:45,610 --> 00:15:48,370
Vooruit dan de cursor.

269
00:15:48,370 --> 00:15:52,950
En dan kun je bevrijden dat tijdelijke
waarde, terwijl nog steeds vast aan

270
00:15:52,950 --> 00:15:55,650
alles achteraf.

271
00:15:55,650 --> 00:15:57,800
>> Wat als u een trie?

272
00:15:57,800 --> 00:16:00,410
Dan is de beste manier om dit te doen
te lossen vanaf het

273
00:16:00,410 --> 00:16:02,290
beneden naar boven.

274
00:16:02,290 --> 00:16:06,920
Door het reizen de laagst mogelijke
knooppunt, kunt u alle pointers bevrijden

275
00:16:06,920 --> 00:16:11,430
dat kinderen en dan backtrack
omhoog vrijmaken alle elementen in alle

276
00:16:11,430 --> 00:16:15,610
van de kinderen doeken, tot
u raakt uw top root node.

277
00:16:15,610 --> 00:16:18,920
Hier is waar Recursion
zal van pas komen.

278
00:16:18,920 --> 00:16:22,780
>> Om ervoor te zorgen dat je waarschijnlijk al bevrijd
alles wat je hebt malloced,

279
00:16:22,780 --> 00:16:24,400
u kunt Valgrind gebruiken.

280
00:16:24,400 --> 00:16:28,640
Hardlopen Valgrind zal uw programma uit te voeren
tellen hoeveel bytes van het geheugen

281
00:16:28,640 --> 00:16:32,440
u gebruikt en ervoor te zorgen dat je hebt
bevrijd ze allemaal, je vertellen

282
00:16:32,440 --> 00:16:34,530
waar je zou kunnen hebben
vergeten om gratis.

283
00:16:34,530 --> 00:16:38,390
Zo lopen dat en zodra Valgrind vertelt u
en geeft u het doorgaan, dan

284
00:16:38,390 --> 00:16:41,160
u klaar bent met uitladen.

285
00:16:41,160 --> 00:16:44,420
>> Nu, een paar tips voordat je gaat
uit en beginnen met de uitvoering van uw

286
00:16:44,420 --> 00:16:46,260
woordenboek.

287
00:16:46,260 --> 00:16:49,650
Ik zou aanraden te gaan in een kleinere
woordenboek als je probeert om te testen

288
00:16:49,650 --> 00:16:52,620
dingen uit en debuggen met het BBP.

289
00:16:52,620 --> 00:16:58,550
Het gebruik van speller is. / Speller, een
optioneel woordenboek, en dan een tekst.

290
00:16:58,550 --> 00:17:01,550
>> Standaard laadt in
het grote woordenboek.

291
00:17:01,550 --> 00:17:06,670
Dus je zou willen gaan in de kleine
woordenboek, of misschien zelfs uw

292
00:17:06,670 --> 00:17:11,819
eigen, het aanpassen van uw woordenboek
en uw tekstbestand.

293
00:17:11,819 --> 00:17:15,950
>> En dan eindelijk, Ik zou ook
een pen en papier te nemen en te tekenen

294
00:17:15,950 --> 00:17:20,490
dingen uit voor, tijdens en na
je hebt al je code geschreven.

295
00:17:20,490 --> 00:17:24,170
Maar zorg ervoor dat je hebt
die aanwijzingen precies goed.

296
00:17:24,170 --> 00:17:26,480
>> Ik wens u veel succes.

297
00:17:26,480 --> 00:17:29,690
En als je eenmaal klaar bent, als je wilt
aan het grote bord en uitdaging

298
00:17:29,690 --> 00:17:34,390
zien hoe snel je programma wordt vergeleken met
je klasgenoten ', dan nodigen ik

299
00:17:34,390 --> 00:17:35,960
u te controleren dat uit.

300
00:17:35,960 --> 00:17:39,220
>> Met dat u klaar bent met
de speller Pset.

301
00:17:39,220 --> 00:17:41,800
Mijn naam is Zamyla, en dit is CS50.

302
00:17:41,800 --> 00:17:49,504