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

2
00:00:09,700 --> 00:00:12,140
>> ZAMYLA CHAN: Lad os gøre
en stavekontrol.

3
00:00:12,140 --> 00:00:16,900
Hvis du åbner speller.c, så vil du se
at de fleste af funktionerne til

4
00:00:16,900 --> 00:00:20,810
kontrol af en tekstfil mod en
ordbog er allerede gjort for dig.

5
00:00:20,810 --> 00:00:26,330
. / Speller, der passerer i en ordbog tekst
fil og derefter en anden tekstfil,

6
00:00:26,330 --> 00:00:28,960
vil kontrollere, at tekstfil
mod ordbogen.

7
00:00:28,960 --> 00:00:34,160
>> Nu vil ordbog tekstfiler indeholder
gyldige ord, én pr linje.

8
00:00:34,160 --> 00:00:37,910
Så vil speller.c kalder Load
på ordbogen tekstfil.

9
00:00:37,910 --> 00:00:43,650
Det vil kalde en funktion kaldet Tjek på
hvert ord i den indtastet tekst-fil,

10
00:00:43,650 --> 00:00:46,460
udskrivning af alle forkert stavede ord.

11
00:00:46,460 --> 00:00:50,030
>> Speller.c vil også ringe størrelse til
bestemme antallet af ord i

12
00:00:50,030 --> 00:00:53,500
ordbog og kalder Unload
for at frigøre hukommelse.

13
00:00:53,500 --> 00:00:57,600
speller.c vil også holde styr på, hvor
meget tid der bruges til at udføre disse

14
00:00:57,600 --> 00:01:00,560
processer, men vi vil
komme til senere.

15
00:01:00,560 --> 00:01:02,440
>> Så hvad skal vi gøre?

16
00:01:02,440 --> 00:01:05,110
Vi er nødt til at udfylde dictionary.c.

17
00:01:05,110 --> 00:01:09,940
I dictionary.c har vi hjælper
funktion Belastning, der indlæser

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

19
00:01:10,855 --> 00:01:15,490
Funktionen Check, som tjekker, om
et givet ord findes i ordbogen.

20
00:01:15,490 --> 00:01:19,150
Funktionen Size returnerer antallet
af ord i ordbogen.

21
00:01:19,150 --> 00:01:24,870
Og endelig har vi losse, som
frigør ordbogen fra hukommelsen.

22
00:01:24,870 --> 00:01:27,070
>> Så det første, lad os tackle Load.

23
00:01:27,070 --> 00:01:32,110
For hvert ord i ordbogen tekst
fil, vil Load gemme disse ord i

24
00:01:32,110 --> 00:01:34,860
ordbogen datastruktur
efter eget valg, enten et

25
00:01:34,860 --> 00:01:36,750
hash tabel eller en trie.

26
00:01:36,750 --> 00:01:39,440
Jeg vil gå over i både
dette gå igennem.

27
00:01:39,440 --> 00:01:43,150
>> Først lad os tale om hash-tabeller.

28
00:01:43,150 --> 00:01:47,050
Sige, at du havde 10 billardkugler og
du ønskede at gemme dem.

29
00:01:47,050 --> 00:01:50,420
Du kan sætte dem alle i en spand,
og når du havde brug for en specifik

30
00:01:50,420 --> 00:01:54,010
nummererede kugle, ville du tage en
ud af spanden på et tidspunkt

31
00:01:54,010 --> 00:01:55,880
udkig efter at bolden.

32
00:01:55,880 --> 00:01:59,370
Og med kun 10 bolde, skal du være
i stand til at finde din bold i en rimelig

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

34
00:02:01,160 --> 00:02:03,180
>> Men hvad hvis du havde 20 bolde?

35
00:02:03,180 --> 00:02:05,480
Det kan tage lidt længere tid nu.

36
00:02:05,480 --> 00:02:06,180
Hvad med 100?

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

38
00:02:07,880 --> 00:02:11,590
Nu ville det være meget lettere, hvis
du havde flere spande.

39
00:02:11,590 --> 00:02:15,890
Måske en skovl til kugler nummereret nul
gennem ni anden spand for

40
00:02:15,890 --> 00:02:18,800
kugler nummereret 10 gennem
19, og så videre.

41
00:02:18,800 --> 00:02:22,330
>> Nu når du behov for at søge efter specifikke
bold, kunne du automatisk

42
00:02:22,330 --> 00:02:26,320
gå til en specifik spand og
søge gennem den spand.

43
00:02:26,320 --> 00:02:29,840
Og hvis hver spand har cirka 10
bolde, så kunne du nemt søge

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

45
00:02:31,790 --> 00:02:34,960
>> Nu da vi har at gøre med
ordbøger, en enkelt spand til

46
00:02:34,960 --> 00:02:41,970
alle de ord i ordbogen, vil
sandsynligvis være alt for få spande.

47
00:02:41,970 --> 00:02:44,370
Så lad os tage et kig på hash-tabeller.

48
00:02:44,370 --> 00:02:46,940
>> Tænk på det som en vifte af spande.

49
00:02:46,940 --> 00:02:50,370
Og i dette tilfælde, spande
er vores hægtede lister.

50
00:02:50,370 --> 00:02:54,770
Og vi vil distribuere alle vores ord
blandt disse mange hægtede lister i

51
00:02:54,770 --> 00:02:58,940
en organiseret måde ved hjælp af en hash-funktion,
som vil fortælle os, hvilke

52
00:02:58,940 --> 00:03:03,720
spand en given nøgle, en given
ord, tilhører.

53
00:03:03,720 --> 00:03:05,960
>> Lad os repræsentere denne skematisk.

54
00:03:05,960 --> 00:03:11,320
De blå bokse her indeholder værdier og
røde kasser peger på en anden værdi

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

56
00:03:12,280 --> 00:03:14,800
Vi kalder disse par noder.

57
00:03:14,800 --> 00:03:18,260
Nu, hver spand, som jeg sagde
tidligere, er en linket liste.

58
00:03:18,260 --> 00:03:21,820
I hægtede lister, hver node har en værdi,
samt en pointer til

59
00:03:21,820 --> 00:03:23,170
næste værdi.

60
00:03:23,170 --> 00:03:26,150
>> Nu beskæftiger sig med hægtede lister,
det er meget vigtigt, at du

61
00:03:26,150 --> 00:03:28,120
ikke mister nogen links.

62
00:03:28,120 --> 00:03:32,250
Og en anden kendsgerning at huske, er, at
sidste node, hvis den ikke peger på

63
00:03:32,250 --> 00:03:35,120
anden node, peger på nul.

64
00:03:35,120 --> 00:03:37,970
>> Så hvordan kan vi repræsentere denne i C?

65
00:03:37,970 --> 00:03:40,540
Vi definerer vores struct her.

66
00:03:40,540 --> 00:03:44,850
Og værdien i dette tilfælde er
en char array af længde.

67
00:03:44,850 --> 00:03:48,880
Længde plus 1, hvor længde er den
maksimale varighed af enhver ord, plus 1 for

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

69
00:03:50,380 --> 00:03:54,210
Og så har vi en pointer til
anden node kaldet Next.

70
00:03:54,210 --> 00:03:56,730
>> Så lad os gøre en lille linket liste.

71
00:03:56,730 --> 00:04:00,390
Først, vil du ønsker at allokere din node,
som skaber plads i hukommelsen

72
00:04:00,390 --> 00:04:04,010
størrelsen på din node type.

73
00:04:04,010 --> 00:04:06,100
Og gøre en anden node,
igen mallocing.

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

75
00:04:09,370 --> 00:04:14,340
>> Nu, hvis du ønsker at tildele en værdi til en
ord, så vi kan sige node1 pil

76
00:04:14,340 --> 00:04:18,820
ord er lig med "Hello". Denne pil operatør
dereferences markøren og

77
00:04:18,820 --> 00:04:20,620
adgang til struct'er variabler.

78
00:04:20,620 --> 00:04:24,330
Denne måde, behøver vi ikke at bruge både
prikken og stjernen operatør.

79
00:04:24,330 --> 00:04:30,100
>> Så jeg har node2 pil ord lig
"Verden". Og der er værdierne

80
00:04:30,100 --> 00:04:33,110
befolket i mine noder.

81
00:04:33,110 --> 00:04:38,780
For at gøre links, vil jeg gå i node1
arrow næste, adgang til denne node stjerne,

82
00:04:38,780 --> 00:04:44,160
at node pointer, lig node2,
peger node1 at node2 to.

83
00:04:44,160 --> 00:04:46,360
Og der har vi en linket liste.

84
00:04:46,360 --> 00:04:51,480
>> Så det var bare en linkede liste, men
en hash tabel er en hel vifte af

85
00:04:51,480 --> 00:04:52,520
hægtede lister.

86
00:04:52,520 --> 00:04:55,920
Nå, vi har den samme knude
struktur som før.

87
00:04:55,920 --> 00:05:00,140
Men hvis vi ønskede en egentlig hash tabel,
så kan vi bare lave en knude pointer

88
00:05:00,140 --> 00:05:01,330
matrix her.

89
00:05:01,330 --> 00:05:04,940
For eksempel størrelse 500.

90
00:05:04,940 --> 00:05:08,910
>> Nu varsel, er der vil være en handel
off mellem størrelsen af ​​din

91
00:05:08,910 --> 00:05:11,280
hash tabel og størrelsen
af dine linkede lister.

92
00:05:11,280 --> 00:05:15,640
Hvis du har en virkelig højt antal
spande, forestiller at skulle køre tilbage

93
00:05:15,640 --> 00:05:18,230
og tilbage i en linie,
find din spand.

94
00:05:18,230 --> 00:05:21,530
Men du ønsker heller ikke et lille antal
spande, fordi så er vi tilbage til

95
00:05:21,530 --> 00:05:26,850
det oprindelige problem, hvordan har
alt for mange bolde i vores spand.

96
00:05:26,850 --> 00:05:30,480
>> OK, men hvor er vores bold hen?

97
00:05:30,480 --> 00:05:33,150
Nå, vi først nødt til at
har en bold, right?

98
00:05:33,150 --> 00:05:39,130
Så lad os malloc en knude for hver
nye ord, som vi har.

99
00:05:39,130 --> 00:05:42,900
node * new_node ligemænd
malloc (sizeof (node)).

100
00:05:42,900 --> 00:05:46,760
>> Nu, hvor vi har denne struktur, vi
kan scanne i, ved hjælp af funktionen

101
00:05:46,760 --> 00:05:51,850
fscanf, en snor fra vores fil, hvis
det er en ordbog fil, i

102
00:05:51,850 --> 00:05:55,780
new_node pil ord, hvor new_node
pil ord er vores

103
00:05:55,780 --> 00:05:58,110
destination af dette ord.

104
00:05:58,110 --> 00:06:01,900
>> Dernæst vil vi ønsker at hash, der
ordet ved hjælp af en hash-funktion.

105
00:06:01,900 --> 00:06:05,860
En hash-funktion tager en streng
og returnerer et indeks.

106
00:06:05,860 --> 00:06:09,760
I dette tilfælde indekset skal
være mindre end antallet af

107
00:06:09,760 --> 00:06:11,440
spande, som du har.

108
00:06:11,440 --> 00:06:14,600
>> Nu hashfunktioner, når du forsøger
at finde en og skabe et af

109
00:06:14,600 --> 00:06:17,890
din egen, så husk, at de
være deterministisk.

110
00:06:17,890 --> 00:06:22,420
Det betyder, at den samme værdi skal
til det samme spand hver gang

111
00:06:22,420 --> 00:06:23,800
at du hash det.

112
00:06:23,800 --> 00:06:25,300
>> Det er lidt ligesom et bibliotek.

113
00:06:25,300 --> 00:06:28,560
Når du tager en bog, baseret på den
forfatter, du ved, hvilken hylde det skal

114
00:06:28,560 --> 00:06:31,890
gå på, om det er hylde nummer
en, to eller tre.

115
00:06:31,890 --> 00:06:36,280
Og at bogen vil altid tilhøre på
enten hylde en, to eller tre.

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

117
00:06:39,460 --> 00:06:43,810
>> Så hvis new_node pil ord har
ord fra din ordbog, så

118
00:06:43,810 --> 00:06:47,770
hashing new_node pil Word
give os indekset for

119
00:06:47,770 --> 00:06:49,370
spand af hash tabellen.

120
00:06:49,370 --> 00:06:54,040
Og så vil vi indsætte det i det
specifik linkede liste angives af

121
00:06:54,040 --> 00:06:56,060
returnere værdien af ​​vores hash funktion.

122
00:06:56,060 --> 00:06:59,070
>> Lad os se på et eksempel på
indsætning af en knude i

123
00:06:59,070 --> 00:07:01,750
begyndelsen af ​​en linket liste.

124
00:07:01,750 --> 00:07:06,930
Hvis hovedet er et knudepunkt pointer, der angiver
begyndelsen af ​​en sammenkædet

125
00:07:06,930 --> 00:07:12,420
listen, og new_node angiver den nye
node, du ønsker at komme ind, blot

126
00:07:12,420 --> 00:07:17,340
tildele hoved til new_node ville miste
linket til resten af ​​listen.

127
00:07:17,340 --> 00:07:19,330
Så vi ønsker ikke at gøre dette.

128
00:07:19,330 --> 00:07:22,160
>> Snarere, vi ønsker at sikre,
at vi holder fast i hver

129
00:07:22,160 --> 00:07:23,550
enkelt node i vores program.

130
00:07:23,550 --> 00:07:29,560
Så kører new_node pil ud ligemænd
hoved og derefter hoved lig new_node

131
00:07:29,560 --> 00:07:34,470
bevarer alle de
links og ikke miste nogen.

132
00:07:34,470 --> 00:07:39,330
>> Men hvad nu hvis du vil have din liste til at være
sorteres, fordi at have en ordnet forbundet

133
00:07:39,330 --> 00:07:42,910
Listen kan være lettere for
søge det senere?

134
00:07:42,910 --> 00:07:46,020
Tja, for det, du behøver at vide
hvordan at krydse hægtede lister.

135
00:07:46,020 --> 00:07:51,210
>> At krydse en sammenkædet liste, lad os få
en knude Pointeren, et knudepunkt * at virke som

136
00:07:51,210 --> 00:07:54,120
markøren, angiver, hvilke
node du er på, startende

137
00:07:54,120 --> 00:07:55,460
på det første element.

138
00:07:55,460 --> 00:08:01,070
Looping indtil markøren er nul, kan vi
foretage visse processer og derefter

139
00:08:01,070 --> 00:08:04,330
flytte markøren, når vi har brug for
hjælp markørpil værdi.

140
00:08:04,330 --> 00:08:08,820
>> Husk, det er det samme som
siger stjerne cursor, dereferere

141
00:08:08,820 --> 00:08:13,480
markøren, og derefter ved hjælp af
dot operatør værdi.

142
00:08:13,480 --> 00:08:19,000
Så opdatere markøren ved at tildele
markøren til markørpil næste.

143
00:08:19,000 --> 00:08:24,960
>> Sig du bestemme, at D bliver i
mellem C og E. Hvis du vil indsætte noden,

144
00:08:24,960 --> 00:08:30,030
har new_node D peger på
node E, som er markøren ud.

145
00:08:30,030 --> 00:08:36,409
Og så C, markøren, kan derefter pege
til D. Denne måde, du vedligeholde en liste.

146
00:08:36,409 --> 00:08:41,080
Vær forsigtig med ikke at miste dine links ved
flytte markøren pilen ved siden af ​​D

147
00:08:41,080 --> 00:08:43,929
højre væk.

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

149
00:08:44,620 --> 00:08:48,920
Så det er, hvordan du kan indsætte noder,
indlæse dem i, load ord i dem

150
00:08:48,920 --> 00:08:51,600
knudepunkter, og indsætte dem
ind i din hash tabellen.

151
00:08:51,600 --> 00:08:53,580
Så lad os nu se på forsøg.

152
00:08:53,580 --> 00:08:58,540
>> I en trie vil hver node indeholde en
matrix node pegepinde, en for hver

153
00:08:58,540 --> 00:09:02,260
bogstav i alfabetet
plus en apostrof.

154
00:09:02,260 --> 00:09:06,150
Og hvert element i arrayet
vil pege på en anden node.

155
00:09:06,150 --> 00:09:10,130
Hvis denne node er nul, så dette bogstav
kommer ikke til at være det næste bogstav i

156
00:09:10,130 --> 00:09:15,690
et ord i en rækkefølge, fordi hver
ord angiver, om det er den sidste

157
00:09:15,690 --> 00:09:18,160
karakter af et ord eller ej.

158
00:09:18,160 --> 00:09:19,750
>> Lad os se på et diagram.

159
00:09:19,750 --> 00:09:22,260
Forhåbentlig vil tingene
være lidt tydeligere.

160
00:09:22,260 --> 00:09:27,210
I dette diagram, ser vi, at kun
visse bogstaver og visse delstrenge

161
00:09:27,210 --> 00:09:28,190
er ved at blive opført ud.

162
00:09:28,190 --> 00:09:32,500
Så du kan følge visse stier, og
alle disse stier vil føre dig til

163
00:09:32,500 --> 00:09:34,020
forskellige ord.

164
00:09:34,020 --> 00:09:37,630
>> Så hvordan kan vi repræsentere denne i C?

165
00:09:37,630 --> 00:09:41,910
Nå, hver node nu kommer til at have
en boolesk værdi, der angiver, om

166
00:09:41,910 --> 00:09:46,580
dette knudepunkt er slutningen af
et givet ord eller ej.

167
00:09:46,580 --> 00:09:50,690
Og så vil det også have en bred vifte af
node pointers kaldet børn, og

168
00:09:50,690 --> 00:09:53,440
Der kommer til at være 27 af dem.

169
00:09:53,440 --> 00:09:56,510
Og husk, vil du også ønsker at
holde styr på din første node.

170
00:09:56,510 --> 00:09:59,830
Vi kommer til at kalde det rod.

171
00:09:59,830 --> 00:10:01,690
>> Så det er strukturen af ​​en trie.

172
00:10:01,690 --> 00:10:05,630
Hvordan kan vi repræsentere denne
som en ordbog?

173
00:10:05,630 --> 00:10:09,890
Nå, for at indlæse ord, for hver
ordbog ord, du vil ønsker

174
00:10:09,890 --> 00:10:11,960
at gentage gennem trie.

175
00:10:11,960 --> 00:10:16,170
Og hvert element i børnenes
svarer til et andet bogstav.

176
00:10:16,170 --> 00:10:21,660
>> Så kontrollere værdien på børn
indeks i, hvor jeg repræsenterer

177
00:10:21,660 --> 00:10:24,840
specifik indeks af brevet, at
du forsøger at indsætte.

178
00:10:24,840 --> 00:10:28,980
Tja, hvis det er nul, så vil du ønsker at
malloc en ny node og få børn

179
00:10:28,980 --> 00:10:31,110
Jeg peger på denne node.

180
00:10:31,110 --> 00:10:35,630
>> Hvis det ikke er null, så det betyder, at
at i betragtning gren, der givet

181
00:10:35,630 --> 00:10:37,350
substring, findes allerede.

182
00:10:37,350 --> 00:10:40,160
Så vil du bare flytte til det
ny node og fortsætte.

183
00:10:40,160 --> 00:10:43,220
Hvis du er i slutningen af ​​det ord,
du forsøger at indlæse i

184
00:10:43,220 --> 00:10:48,120
ordbog, så du kan indstille, at
aktuelle node, at du er på sand.

185
00:10:48,120 --> 00:10:51,550
>> Så lad os se på et eksempel på at indsætte
ordet "ræv" i vores

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

187
00:10:53,070 --> 00:10:56,110
Lad som om vi starter med
en tom ordbog.

188
00:10:56,110 --> 00:11:01,610
Det første bogstav, F, vil blive placeret
børn indeks fem af rødderne

189
00:11:01,610 --> 00:11:03,700
børn array.

190
00:11:03,700 --> 00:11:05,430
Så vi indsætter det i.

191
00:11:05,430 --> 00:11:14,610
>> Bogstavet O vil derefter være i børn
indeks 15, efter at F. Og så X

192
00:11:14,610 --> 00:11:20,180
vil være endnu lavere end det, der forgrener
off af O børn.

193
00:11:20,180 --> 00:11:24,120
Og så fordi X er det sidste bogstav
af ordet "ræv", så jeg har tænkt mig at

194
00:11:24,120 --> 00:11:27,210
farve, at grøn for at angive,
Det er slutningen af ​​ordet.

195
00:11:27,210 --> 00:11:32,880
I C, ville det være indstilling er
Word Boolean værdien sandt.

196
00:11:32,880 --> 00:11:36,780
>> Hvad nu hvis det næste ord, at du er
lastning i er ordet "foo"?

197
00:11:36,780 --> 00:11:41,490
Nå, behøver du ikke at allokere mere
plads til F eller O, fordi

198
00:11:41,490 --> 00:11:42,990
de findes allerede.

199
00:11:42,990 --> 00:11:45,910
Men den sidste O i foo?

200
00:11:45,910 --> 00:11:47,320
At man, er du nødt til malloc.

201
00:11:47,320 --> 00:11:52,390
Lav en ny knude til at sætte
Is Word Boolean til sand.

202
00:11:52,390 --> 00:11:57,340
>> Så lad os nu indsætte "hund". Dog vil
starte med indeks tre af rødderne

203
00:11:57,340 --> 00:12:00,520
børn, fordi D har ikke
blevet oprettet endnu.

204
00:12:00,520 --> 00:12:04,990
Og vi vil følge en lignende proces som
før, skaber understreng hund,

205
00:12:04,990 --> 00:12:10,400
hvor er G er farvet grøn, fordi
det er slutningen af ​​et ord.

206
00:12:10,400 --> 00:12:13,160
>> Hvad nu, hvis vi ønsker at indsætte "gøre"?

207
00:12:13,160 --> 00:12:17,150
Nå, dette er en delstreng af hund, så
vi behøver ikke at malloc længere.

208
00:12:17,150 --> 00:12:20,800
Men vi har brug for at angive, hvor vi har
nået slutningen af ​​det ord.

209
00:12:20,800 --> 00:12:24,020
Så O vil blive farvet grøn.

210
00:12:24,020 --> 00:12:27,810
Fortsat denne proces for hver enkelt
ord i din ordbog, du har

211
00:12:27,810 --> 00:12:32,120
indlæst dem i ind i enten din
hash tabel eller din trie.

212
00:12:32,120 --> 00:12:37,530
>> speller.c vil passere i snore for
dictionary.c at kontrollere dem.

213
00:12:37,530 --> 00:12:41,140
Nu Kontrollér funktionen har til at operere
under tilfælde ufølsomhed.

214
00:12:41,140 --> 00:12:45,980
Det betyder, at store bogstaver og
små bogstaver og en blanding af begge

215
00:12:45,980 --> 00:12:50,670
bør alle svare til sand, hvis nogen
kombination, der er i

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

217
00:12:51,880 --> 00:12:55,580
Du kan også antage, at strenge er
kun kommer til at indeholde alfabetisk

218
00:12:55,580 --> 00:12:58,200
tegn eller apostrof.

219
00:12:58,200 --> 00:13:02,490
>> Så lad os se på, hvordan du kan kontrollere
med en hash tabel struktur.

220
00:13:02,490 --> 00:13:07,330
Tja, hvis ordet findes, så er det
kan findes i hash tabellen.

221
00:13:07,330 --> 00:13:12,240
Så kan du prøve at finde,
ord i den pågældende spand.

222
00:13:12,240 --> 00:13:14,480
>> Så der spand ville dette ord være i?

223
00:13:14,480 --> 00:13:20,060
Nå, ville du få nummeret, at indekset
af spanden, ved hashing det ord

224
00:13:20,060 --> 00:13:23,690
og derefter søge i den linkede liste,
gennemkører gennem hele

225
00:13:23,690 --> 00:13:28,060
linkede liste, ved hjælp af String
Sammenlign funktion.

226
00:13:28,060 --> 00:13:31,940
>> Hvis enden af ​​den sammenkædede liste
nået, hvilket betyder, at markøren

227
00:13:31,940 --> 00:13:36,030
når nul, så ordet ikke
findes i ordbogen.

228
00:13:36,030 --> 00:13:39,090
Det vil ikke være i en anden spand.

229
00:13:39,090 --> 00:13:43,020
Så her kan du se, hvordan der måske
være et trade-off mellem at have enten

230
00:13:43,020 --> 00:13:46,280
sorteret hægtede lister eller usorterede dem.

231
00:13:46,280 --> 00:13:51,180
Enten vil tage mere tid under
indlæse eller mere tid under kontrol.

232
00:13:51,180 --> 00:13:53,560
>> Hvordan kan du tjekke
en trie struktur?

233
00:13:53,560 --> 00:13:56,370
Vi kommer til at rejse nedad
i trie.

234
00:13:56,370 --> 00:14:00,390
For hvert bogstav i indtastet ord
at vi tjekker, vil vi gå til at

235
00:14:00,390 --> 00:14:03,280
tilsvarende element i børnene.

236
00:14:03,280 --> 00:14:07,770
>> Hvis dette element er nul, så det betyder,
at der ikke er delstrenge

237
00:14:07,770 --> 00:14:11,110
indeholder vores input ord, så
ordet er stavet forkert.

238
00:14:11,110 --> 00:14:15,140
Hvis det ikke er nul, kan vi flytte til
næste bogstav i ordet, at vi er

239
00:14:15,140 --> 00:14:18,850
kontrol og fortsætte denne proces
indtil vi når til slutningen

240
00:14:18,850 --> 00:14:20,350
af input-ord.

241
00:14:20,350 --> 00:14:23,330
Og så kan vi kontrollere
IF er Word er sandt.

242
00:14:23,330 --> 00:14:24,610
Hvis det er, så stor.

243
00:14:24,610 --> 00:14:25,590
Ordet er korrekt.

244
00:14:25,590 --> 00:14:30,890
Men hvis ikke, selvom det substring
findes i trie ordet er

245
00:14:30,890 --> 00:14:32,250
stavet forkert.

246
00:14:32,250 --> 00:14:36,590
>> Når funktionen Størrelse kaldes, størrelse
skal returnere antallet af ord,

247
00:14:36,590 --> 00:14:39,110
er i din given ordbog
datastruktur.

248
00:14:39,110 --> 00:14:42,780
Så hvis du bruger en hash tabel, du
kan enten gå gennem hver enkelt

249
00:14:42,780 --> 00:14:45,860
forbundet liste i hvert enkelt
spand tælle antallet

250
00:14:45,860 --> 00:14:47,130
ord er der.

251
00:14:47,130 --> 00:14:49,940
Hvis du bruger en trie, kan du
gå igennem alle ikke null

252
00:14:49,940 --> 00:14:52,030
sti i din trie.

253
00:14:52,030 --> 00:14:56,420
Eller mens du lægger ordbogen
i, måske kan du holde styr på, hvordan

254
00:14:56,420 --> 00:14:58,760
mange ord du lægger i.

255
00:14:58,760 --> 00:15:03,180
>> Når speller.c færdig kontrollere
tekstfil mod ordbogen, så

256
00:15:03,180 --> 00:15:08,010
det er gjort, og så det kalder Unload, hvor
dit job er at frigøre noget

257
00:15:08,010 --> 00:15:09,500
at du har malloced.

258
00:15:09,500 --> 00:15:14,420
Så hvis du bruger en hash tabel, så du
skal være særlig omhyggelig med at undgå

259
00:15:14,420 --> 00:15:18,830
memory leaks ved ikke at frigøre noget
tidligt og holde på hver

260
00:15:18,830 --> 00:15:20,780
enkelt link, før du gratis.

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

262
00:15:24,680 --> 00:15:30,100
>> Så for hvert element i hash tabellen
og for hver node i den linkede liste,

263
00:15:30,100 --> 00:15:32,370
du ønsker at frigøre denne node.

264
00:15:32,370 --> 00:15:34,970
Hvordan kan du gå om at frigøre
en sammenkædet liste?

265
00:15:34,970 --> 00:15:38,570
Indstilling af din node pointer markøren til
hovedet, til begyndelsen af ​​den

266
00:15:38,570 --> 00:15:43,100
linkede liste, så mens markøren
ikke er nul, kan du indstille en midlertidig

267
00:15:43,100 --> 00:15:45,610
node pointer til din markør.

268
00:15:45,610 --> 00:15:48,370
Derefter rykke markøren.

269
00:15:48,370 --> 00:15:52,950
Og så kan du frigøre det midlertidige
værdi, mens du stadig holder på

270
00:15:52,950 --> 00:15:55,650
alt bagefter.

271
00:15:55,650 --> 00:15:57,800
>> Hvad hvis du bruger en trie?

272
00:15:57,800 --> 00:16:00,410
Så den bedste måde at gøre dette
er at losse fra den meget

273
00:16:00,410 --> 00:16:02,290
bunden til toppen.

274
00:16:02,290 --> 00:16:06,920
Ved at rejse til den lavest mulige
node, kan du frigøre alle pejlemærker i

275
00:16:06,920 --> 00:16:11,430
at børn og derefter bakke
opad, hvilket frigør alle elementer i alle

276
00:16:11,430 --> 00:16:15,610
børnenes arrays, indtil
du rammer din top rodnoden.

277
00:16:15,610 --> 00:16:18,920
Her er hvor Rekursion
vil komme i handy.

278
00:16:18,920 --> 00:16:22,780
>> For at sikre at du har sikkert befriet
alt det, du har malloced,

279
00:16:22,780 --> 00:16:24,400
kan du bruge Valgrind.

280
00:16:24,400 --> 00:16:28,640
Løb Valgrind vil køre dit program
tælle, hvor mange bytes af hukommelse

281
00:16:28,640 --> 00:16:32,440
du bruger, og at sikre, at du har
befriede dem alle, fortæller dig

282
00:16:32,440 --> 00:16:34,530
hvor du måske har
glemt at fri.

283
00:16:34,530 --> 00:16:38,390
Så kører det, og når Valgrind fortæller dig
og giver dig gå videre, så

284
00:16:38,390 --> 00:16:41,160
du er færdig med unload.

285
00:16:41,160 --> 00:16:44,420
>> Nu, et par tips, før du går
slukket og begynde at gennemføre din

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

287
00:16:46,260 --> 00:16:49,650
Jeg vil anbefale at passere i et mindre
ordbogen, når du forsøger at teste

288
00:16:49,650 --> 00:16:52,620
ting ud og debugging med BNP.

289
00:16:52,620 --> 00:16:58,550
Brugen af ​​Speller. / Speller, en
valgfri ordbog og derefter en tekst.

290
00:16:58,550 --> 00:17:01,550
>> Som standard, indlæser i
den store ordbog.

291
00:17:01,550 --> 00:17:06,670
Så du måske ønsker at videregive i den lille
ordbog, eller måske endda gøre din

292
00:17:06,670 --> 00:17:11,819
egne, tilpasse din ordbog
og din tekstfil.

293
00:17:11,819 --> 00:17:15,950
>> Og så endelig, jeg vil også anbefale
at tage en pen og papir og tegne

294
00:17:15,950 --> 00:17:20,490
ting ud før, under og efter
du har skrevet alle dine kode.

295
00:17:20,490 --> 00:17:24,170
Bare sørg for, at du har fået
disse pejlemærker lige højre.

296
00:17:24,170 --> 00:17:26,480
>> Jeg ønsker dig held og lykke.

297
00:17:26,480 --> 00:17:29,690
Og når du er færdig, hvis du gerne vil
at udfordre den store bestyrelse og

298
00:17:29,690 --> 00:17:34,390
se, hvor hurtigt dit program er i forhold til
dine klassekammerater ', så opfordrer jeg

299
00:17:34,390 --> 00:17:35,960
dig til at tjekke det ud.

300
00:17:35,960 --> 00:17:39,220
>> Med det, har du færdig
speller PSET.

301
00:17:39,220 --> 00:17:41,800
Mit navn er Zamyla, og det er CS50.

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