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

2
00:00:09,700 --> 00:00:12,140
>> ZAMYLA CHAN: Låt oss göra
en stavningskontroll.

3
00:00:12,140 --> 00:00:16,900
Om du öppnar speller.c Du kommer att se
att de flesta av funktionerna för

4
00:00:16,900 --> 00:00:20,810
kontrollera en textfil mot en
ordlistan är redan gjord för dig.

5
00:00:20,810 --> 00:00:26,330
. / Speller, passerar i en ordbok text
fil och sedan en annan textfil,

6
00:00:26,330 --> 00:00:28,960
kommer att kontrollera att textfilen
mot ordboken.

7
00:00:28,960 --> 00:00:34,160
>> Nu kommer ordbok textfiler innehåller
giltiga ord, en per rad.

8
00:00:34,160 --> 00:00:37,910
Då speller.c ringer Load
på ordboken textfil.

9
00:00:37,910 --> 00:00:43,650
Det ringer en funktion som heter Kolla på
varje ord i den inmatade textfilen,

10
00:00:43,650 --> 00:00:46,460
skriva ut alla felstavade ord.

11
00:00:46,460 --> 00:00:50,030
>> Speller.c kommer även ringa storlek till
bestämma antalet ord i

12
00:00:50,030 --> 00:00:53,500
lexikon och ringa Unload
att frigöra minne.

13
00:00:53,500 --> 00:00:57,600
speller.c kommer också att hålla reda på hur
mycket tid används för att utföra dessa

14
00:00:57,600 --> 00:01:00,560
processer, men vi ska
kommer till det senare.

15
00:01:00,560 --> 00:01:02,440
>> Så vad behöver vi göra?

16
00:01:02,440 --> 00:01:05,110
Vi behöver fylla på dictionary.c.

17
00:01:05,110 --> 00:01:09,940
I dictionary.c har vi hjälpare
funktionen Load, som läser in

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

19
00:01:10,855 --> 00:01:15,490
Funktionen Check, som kontrollerar om
ett givet ord i ordboken.

20
00:01:15,490 --> 00:01:19,150
Funktionen storlek returnerar antalet
ord i ordboken.

21
00:01:19,150 --> 00:01:24,870
Och slutligen har vi Lasta, vilket
befriar ordlistan från minnet.

22
00:01:24,870 --> 00:01:27,070
>> Så först, låt oss ta itu Load.

23
00:01:27,070 --> 00:01:32,110
För varje ord i ordboken text
fil, kommer Load lagra dessa ord i

24
00:01:32,110 --> 00:01:34,860
ordboken datastruktur
som du väljer, antingen ett

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

26
00:01:36,750 --> 00:01:39,440
Jag går över både i
detta går igenom.

27
00:01:39,440 --> 00:01:43,150
>> Först ska vi prata om hashtabeller.

28
00:01:43,150 --> 00:01:47,050
Säg att du hade 10 biljardbollar och
du ville att lagra dem.

29
00:01:47,050 --> 00:01:50,420
Du kan sätta dem alla i en hink,
och när man behövde en viss

30
00:01:50,420 --> 00:01:54,010
numrerad boll, skulle du ta en
ut ur skopan vid en tidpunkt

31
00:01:54,010 --> 00:01:55,880
söker den bollen.

32
00:01:55,880 --> 00:01:59,370
Och med bara 10 bollar, bör du vara
kunna hitta din boll på ett rimligt

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

34
00:02:01,160 --> 00:02:03,180
>> Men tänk om du hade 20 bollar?

35
00:02:03,180 --> 00:02:05,480
Det kan ta lite längre tid nu.

36
00:02:05,480 --> 00:02:06,180
Vad sägs om 100?

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

38
00:02:07,880 --> 00:02:11,590
Nu skulle det vara mycket enklare om
du hade flera hinkar.

39
00:02:11,590 --> 00:02:15,890
Kanske en hink för bollar numrerade noll
till nio, en annan hink för

40
00:02:15,890 --> 00:02:18,800
bollar numrerade 10 till
19, och så vidare.

41
00:02:18,800 --> 00:02:22,330
>> Nu när du behövs för att leta efter specifika
boll, kan du automatiskt

42
00:02:22,330 --> 00:02:26,320
gå till en specifik hink och
söka igenom hinken.

43
00:02:26,320 --> 00:02:29,840
Och om varje hink har cirka 10
bollar, då kan du enkelt söka

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

45
00:02:31,790 --> 00:02:34,960
>> Nu, eftersom vi har att göra med
ordböcker, en enda hink för

46
00:02:34,960 --> 00:02:41,970
alla ord i ordlistan kommer
förmodligen vara alltför få hinkar.

47
00:02:41,970 --> 00:02:44,370
Så låt oss ta en titt på hashtabeller.

48
00:02:44,370 --> 00:02:46,940
>> Se det som en array av skopor.

49
00:02:46,940 --> 00:02:50,370
Och i detta fall skoporna
är våra länkade listor.

50
00:02:50,370 --> 00:02:54,770
Och vi kommer att dela ut alla våra ord
bland dessa flera länkade listor i

51
00:02:54,770 --> 00:02:58,940
ett organiserat sätt genom att använda en hash-funktion,
som kommer att tala om för oss vilka

52
00:02:58,940 --> 00:03:03,720
hink en viss nyckel, en viss
ord, tillhör.

53
00:03:03,720 --> 00:03:05,960
>> Låt oss föreställa denna schematiskt.

54
00:03:05,960 --> 00:03:11,320
De blå rutorna här innehåller värderingar och
röda lådor pekar på ett annat värde

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

56
00:03:12,280 --> 00:03:14,800
Vi kallar dessa par noder.

57
00:03:14,800 --> 00:03:18,260
Nu, varje hink, som sagt
tidigare, är en länkad lista.

58
00:03:18,260 --> 00:03:21,820
I länkade listor, har varje nod ett värde,
såväl som en pekare till

59
00:03:21,820 --> 00:03:23,170
nästa värde.

60
00:03:23,170 --> 00:03:26,150
>> Nu, som handlar om länkade listor,
det är mycket viktigt att du

61
00:03:26,150 --> 00:03:28,120
inte förlorar några länkar.

62
00:03:28,120 --> 00:03:32,250
Och ett annat faktum att komma ihåg är att det
sista noden, om den inte pekar på

63
00:03:32,250 --> 00:03:35,120
annan nod, pekar på null.

64
00:03:35,120 --> 00:03:37,970
>> Så hur ska vi företräder här i C?

65
00:03:37,970 --> 00:03:40,540
Vi definierar vår struct här.

66
00:03:40,540 --> 00:03:44,850
Och värdet i det här fallet är
en char array med längden.

67
00:03:44,850 --> 00:03:48,880
Längd plus ett, där längden är det
Längsta tid för ord, plus 1 för

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

69
00:03:50,380 --> 00:03:54,210
Och sedan har vi en pekare till
annan nod som kallas Next.

70
00:03:54,210 --> 00:03:56,730
>> Så låt oss göra en liten länkad lista.

71
00:03:56,730 --> 00:04:00,390
Först vill du malloc din nod,
vilket skapar utrymme i minnet för

72
00:04:00,390 --> 00:04:04,010
storleken på din nodtyp.

73
00:04:04,010 --> 00:04:06,100
Och gör en annan nod,
igen mallocing.

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

75
00:04:09,370 --> 00:04:14,340
>> Nu om du vill tilldela ett värde till en
ord, då vi kan säga node1 pil

76
00:04:14,340 --> 00:04:18,820
Ordet är lika med "Hej." Denna pil operatör
dereferences pekaren och

77
00:04:18,820 --> 00:04:20,620
accessar struct variabler.

78
00:04:20,620 --> 00:04:24,330
På så sätt behöver vi inte använda båda
pricken och stjärnan operatören.

79
00:04:24,330 --> 00:04:30,100
>> Så då har jag node2 pil ord lika
"Värld." Och där, är värdena

80
00:04:30,100 --> 00:04:33,110
befolkat i mina noder.

81
00:04:33,110 --> 00:04:38,780
För att göra länkarna, jag ska passera i node1
arrow nästa, komma åt den noden stjärna,

82
00:04:38,780 --> 00:04:44,160
den noden pekare, lika node2,
pekar node1 att node2 två.

83
00:04:44,160 --> 00:04:46,360
Där har vi en länkad lista.

84
00:04:46,360 --> 00:04:51,480
>> Så det var bara en länkad lista, men
en hash-tabell är en hel rad av

85
00:04:51,480 --> 00:04:52,520
länkade listor.

86
00:04:52,520 --> 00:04:55,920
Tja, vi har samma nod
strukturera som tidigare.

87
00:04:55,920 --> 00:05:00,140
Men om vi ville ha en verklig hash-tabell,
då kan vi bara göra en nod pekare

88
00:05:00,140 --> 00:05:01,330
array här.

89
00:05:01,330 --> 00:05:04,940
Till exempel, storlek 500.

90
00:05:04,940 --> 00:05:08,910
>> Nu varsel, det kommer att bli en handels
off mellan storleken på din

91
00:05:08,910 --> 00:05:11,280
hashtabell och storleken
av länkade listor.

92
00:05:11,280 --> 00:05:15,640
Om du har ett riktigt stort antal
hinkar, inbillar behöva springa tillbaka

93
00:05:15,640 --> 00:05:18,230
och tillbaka i en linje till
hitta din hink.

94
00:05:18,230 --> 00:05:21,530
Men du vill inte heller ett litet antal
av skopor, för då är vi tillbaka till

95
00:05:21,530 --> 00:05:26,850
det ursprungliga problemet med hur har
för många bollar i vår hink.

96
00:05:26,850 --> 00:05:30,480
>> OK, men vart tar vår boll går?

97
00:05:30,480 --> 00:05:33,150
Tja, måste vi först
har en boll, eller hur?

98
00:05:33,150 --> 00:05:39,130
Så låt oss malloc en nod för varje
nya ord som vi har.

99
00:05:39,130 --> 00:05:42,900
node * new_node jämlikar
malloc (sizeof (nod)).

100
00:05:42,900 --> 00:05:46,760
>> Nu när vi har denna struktur, vi
kan skanna in, med hjälp av funktionen

101
00:05:46,760 --> 00:05:51,850
fscanf, en sträng från vår fil, om
det är en ordbok fil, i

102
00:05:51,850 --> 00:05:55,780
new_node pilen ord, där new_node
pil ord är vår

103
00:05:55,780 --> 00:05:58,110
destinationen för det ordet.

104
00:05:58,110 --> 00:06:01,900
>> Därefter ska vi vill hash som
ordet med en hash-funktion.

105
00:06:01,900 --> 00:06:05,860
En hashfunktion tar en sträng
och returnerar ett index.

106
00:06:05,860 --> 00:06:09,760
I detta fall har de index till
vara mindre än antalet

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

108
00:06:11,440 --> 00:06:14,600
>> Nu, hashfunktioner, när du försöker
att hitta en och skapa en av

109
00:06:14,600 --> 00:06:17,890
egen hand, kom ihåg att de
måste vara deterministisk.

110
00:06:17,890 --> 00:06:22,420
Det betyder att samma värde måste
mappas till samma hink varje gång

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

112
00:06:23,800 --> 00:06:25,300
>> Det är ungefär som ett bibliotek.

113
00:06:25,300 --> 00:06:28,560
När man tar en bok, baserat på den
författare, vet du vilken hylla den ska

114
00:06:28,560 --> 00:06:31,890
gå på, oavsett om det är hyllnummer
en, två, eller tre.

115
00:06:31,890 --> 00:06:36,280
Och att boken kommer alltid att tillhöra den
antingen hylla en, två, eller tre.

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

117
00:06:39,460 --> 00:06:43,810
>> Så, har om new_node pil ord den
ord från din ordlista, sedan

118
00:06:43,810 --> 00:06:47,770
hashing new_node pil ord kommer
ge oss index för

119
00:06:47,770 --> 00:06:49,370
hink med hash-tabellen.

120
00:06:49,370 --> 00:06:54,040
Och sedan ska vi sätta in det i det
specifika länkad lista som anges av

121
00:06:54,040 --> 00:06:56,060
returnera värdet på vår hashfunktion.

122
00:06:56,060 --> 00:06:59,070
>> Låt oss titta på ett exempel på
sätta in en nod i

123
00:06:59,070 --> 00:07:01,750
början av en länkad lista.

124
00:07:01,750 --> 00:07:06,930
Om huvudet är en nod pekare som indikerar
I början av en länkad

125
00:07:06,930 --> 00:07:12,420
listan, och new_node indikerar den nya
nod som du vill skriva in, precis

126
00:07:12,420 --> 00:07:17,340
tilldela huvud till new_node skulle förlora
länken till resten av listan.

127
00:07:17,340 --> 00:07:19,330
Så vi vill inte göra det här.

128
00:07:19,330 --> 00:07:22,160
>> I stället vill vi se till att
att vi håller på att varje

129
00:07:22,160 --> 00:07:23,550
enda nod i vårt program.

130
00:07:23,550 --> 00:07:29,560
Så kör new_node pilen jämlikar
huvud och sedan huvudet lika new_node

131
00:07:29,560 --> 00:07:34,470
kommer att bevara alla av
länkar och inte förlora något.

132
00:07:34,470 --> 00:07:39,330
>> Men om du vill att listan ska vara
sorteras, eftersom att ha en sorterad länkad

133
00:07:39,330 --> 00:07:42,910
Listan kan vara lättare för
söka den senare?

134
00:07:42,910 --> 00:07:46,020
Jo, för det måste du veta
hur man korsa länkade listor.

135
00:07:46,020 --> 00:07:51,210
>> För att gå igenom en länkad lista, låt oss ha
en nod pekare, en nod *, för att fungera som

136
00:07:51,210 --> 00:07:54,120
markören, som anger vilka
nod du är på, börjar

137
00:07:54,120 --> 00:07:55,460
vid det första elementet.

138
00:07:55,460 --> 00:08:01,070
Looping tills markören är noll, kan vi
genomföra vissa processer och sedan

139
00:08:01,070 --> 00:08:04,330
föra markören när vi behöver
med hjälp av markörpilen värde.

140
00:08:04,330 --> 00:08:08,820
>> Kom ihåg, det här är samma sak som
säger stjärnan markör, dereferencing

141
00:08:08,820 --> 00:08:13,480
markören, sedan använda
punktopera värde.

142
00:08:13,480 --> 00:08:19,000
Så uppdatera markören genom att tilldela
markören till markörpilen bredvid.

143
00:08:19,000 --> 00:08:24,960
>> Säg att du bestämmer att D blir i
mellan C och E. För att infoga noden,

144
00:08:24,960 --> 00:08:30,030
har new_node D punkten till
nod E, som är markör bredvid.

145
00:08:30,030 --> 00:08:36,409
Och sedan C, markören, kan peka
till D. På så sätt hålla dig en lista.

146
00:08:36,409 --> 00:08:41,080
Var noga med att inte förlora dina länkar med
flytta markören pilen bredvid D

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

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

149
00:08:44,620 --> 00:08:48,920
Så det är hur du kan infoga noder,
ladda dem, last ord till dem

150
00:08:48,920 --> 00:08:51,600
noder, och sätt in dem
in i din hash-tabell.

151
00:08:51,600 --> 00:08:53,580
Så nu ska vi titta på försök.

152
00:08:53,580 --> 00:08:58,540
>> I en trie, kommer varje nod innehåller ett
matris av noder pekare, en för varje

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

154
00:09:02,260 --> 00:09:06,150
Och varje element i arrayen
kommer att peka på en annan nod.

155
00:09:06,150 --> 00:09:10,130
Om denna nod är noll, då skrivelsen
kommer inte att bli nästa bokstav i

156
00:09:10,130 --> 00:09:15,690
varje ord i en sekvens, eftersom varje
ord visar om det är det sista

157
00:09:15,690 --> 00:09:18,160
karaktären av ett ord eller inte.

158
00:09:18,160 --> 00:09:19,750
>> Låt oss titta på ett diagram.

159
00:09:19,750 --> 00:09:22,260
Förhoppningsvis kommer
vara lite tydligare.

160
00:09:22,260 --> 00:09:27,210
I det här diagrammet ser vi att endast
vissa bokstäver och vissa delsträngar

161
00:09:27,210 --> 00:09:28,190
håller listade ut.

162
00:09:28,190 --> 00:09:32,500
Så du kan följa vissa vägar, och
alla dessa stigar leder dig till

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

164
00:09:34,020 --> 00:09:37,630
>> Så hur ska vi företräder här i C?

165
00:09:37,630 --> 00:09:41,910
Tja, varje nod nu kommer att ha
ett booleskt värde som anger om

166
00:09:41,910 --> 00:09:46,580
den noden är i slutet av
ett givet ord eller inte.

167
00:09:46,580 --> 00:09:50,690
Och då kommer också ha en rad
nod pekare kallas barn och

168
00:09:50,690 --> 00:09:53,440
det kommer att bli 27 av dem.

169
00:09:53,440 --> 00:09:56,510
Och kom ihåg, du kommer också vill
hålla koll på din första noden.

170
00:09:56,510 --> 00:09:59,830
Vi kommer att kalla det rot.

171
00:09:59,830 --> 00:10:01,690
>> Så det är strukturen i en trie.

172
00:10:01,690 --> 00:10:05,630
Hur vi representerar här
som ett lexikon?

173
00:10:05,630 --> 00:10:09,890
Jo, för att ladda ord, för varje
ord i ordlistan, du kommer att vilja

174
00:10:09,890 --> 00:10:11,960
att iterera igenom trie.

175
00:10:11,960 --> 00:10:16,170
Och varje element i barnens
motsvarar en annan bokstav.

176
00:10:16,170 --> 00:10:21,660
>> Så kontrollera värdet på barn
index i, där jag representerar

177
00:10:21,660 --> 00:10:24,840
specifika index för brev som
du försöker sätta in.

178
00:10:24,840 --> 00:10:28,980
Tja, om det är noll, då du kommer att vilja
malloc en ny nod och har barn

179
00:10:28,980 --> 00:10:31,110
Jag pekar på den noden.

180
00:10:31,110 --> 00:10:35,630
>> Om det inte är noll, då det innebär att
som viss gren, att med tanke

181
00:10:35,630 --> 00:10:37,350
delsträng, finns redan.

182
00:10:37,350 --> 00:10:40,160
Så då kommer du bara flytta till det
ny nod och fortsätta.

183
00:10:40,160 --> 00:10:43,220
Om du är i slutet av ordet som
du försöker läsa in i

184
00:10:43,220 --> 00:10:48,120
ordbok, då kan du ställa in att
nuvarande nod som du är på till true.

185
00:10:48,120 --> 00:10:51,550
>> Så låt oss titta på ett exempel på att sätta in
ordet "räven" i vår

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

187
00:10:53,070 --> 00:10:56,110
Låtsas vi börjar med
en tom ordboken.

188
00:10:56,110 --> 00:11:01,610
Den första bokstaven, F, kommer att ligga
i barn index fem av rötterna

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

190
00:11:03,700 --> 00:11:05,430
Så vi sätter den i.

191
00:11:05,430 --> 00:11:14,610
>> Bokstaven O kommer då att vara i barn
index 15, därefter F. Och sedan X

192
00:11:14,610 --> 00:11:20,180
kommer att bli ännu lägre än den som, förgrening
bort av O: s barn.

193
00:11:20,180 --> 00:11:24,120
Och då eftersom X är den sista bokstaven
av ordet "räv", då kommer jag att

194
00:11:24,120 --> 00:11:27,210
färg som grönt för att indikera att
det är i slutet av ordet.

195
00:11:27,210 --> 00:11:32,880
I C, skulle det vara att ställa in Is
Word Boolean till värdet true.

196
00:11:32,880 --> 00:11:36,780
>> Nu tänk om nästa ord som du är
fyller på är ordet "foo"?

197
00:11:36,780 --> 00:11:41,490
Tja, behöver du inte att malloc mer
utrymme för F eller O, eftersom

198
00:11:41,490 --> 00:11:42,990
de som redan finns.

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

200
00:11:45,910 --> 00:11:47,320
Att man, måste du malloc.

201
00:11:47,320 --> 00:11:52,390
Gör en ny nod för att ställa
Is Word Boolean till true.

202
00:11:52,390 --> 00:11:57,340
>> Så nu ska vi sätta "hund." Dog kommer
börja med index tre av rötterna

203
00:11:57,340 --> 00:12:00,520
barn, eftersom D har inte
skapats ännu.

204
00:12:00,520 --> 00:12:04,990
Och vi kommer att följa en liknande process som
tidigare, skapar träng hund,

205
00:12:04,990 --> 00:12:10,400
var är G är grön eftersom
det är i slutet av ett ord.

206
00:12:10,400 --> 00:12:13,160
>> Nu, tänk om vi vill infoga "göra"?

207
00:12:13,160 --> 00:12:17,150
Nåväl, detta är en delsträng av hund, så
Vi behöver inte malloc längre.

208
00:12:17,150 --> 00:12:20,800
Men vi behöver för att ange var vi har
nått slutet av det ordet.

209
00:12:20,800 --> 00:12:24,020
Så O kommer att färgas grönt.

210
00:12:24,020 --> 00:12:27,810
Att fortsätta denna process för varje enskild
ord i din ordlista, du har

211
00:12:27,810 --> 00:12:32,120
lastade dem i antingen din
hash bord eller din trie.

212
00:12:32,120 --> 00:12:37,530
>> speller.c kommer att passera i strängar för
dictionary.c att kontrollera dem.

213
00:12:37,530 --> 00:12:41,140
Nu har Kontrollera funktionen att driva
under ärende okänslighet.

214
00:12:41,140 --> 00:12:45,980
Det betyder att versaler och
gemener och en blandning av båda

215
00:12:45,980 --> 00:12:50,670
bör alla motsvara sant om någon
kombination av det är i

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

217
00:12:51,880 --> 00:12:55,580
Du kan också anta att strängar är
endast kommer att innehålla alfabetisk

218
00:12:55,580 --> 00:12:58,200
tecken eller apostrofer.

219
00:12:58,200 --> 00:13:02,490
>> Så låt oss titta på hur du kan kontrollera
med en hashtabell struktur.

220
00:13:02,490 --> 00:13:07,330
Tja, om ordet existerar, då det
kan hittas i hash-tabellen.

221
00:13:07,330 --> 00:13:12,240
Så då kan du försöka hitta det
ord i den relevanta hink.

222
00:13:12,240 --> 00:13:14,480
>> Så vilken hink skulle det ordet vara i?

223
00:13:14,480 --> 00:13:20,060
Tja, skulle du få numret att index
av skopan, genom hashing det ordet

224
00:13:20,060 --> 00:13:23,690
och sedan söka i den länkade listan,
korsar genom hela

225
00:13:23,690 --> 00:13:28,060
länkad lista, med hjälp av String
Jämför funktion.

226
00:13:28,060 --> 00:13:31,940
>> Om slutet av den länkade listan är
nåtts, vilket innebär att markören

227
00:13:31,940 --> 00:13:36,030
når noll, då ordet inte
hittas i ordboken.

228
00:13:36,030 --> 00:13:39,090
Det kommer inte vara i någon annan skopa.

229
00:13:39,090 --> 00:13:43,020
Så här kan du se hur det kanske
vara en avvägning mellan att ha antingen

230
00:13:43,020 --> 00:13:46,280
sorterade länkade listor eller osorterade sådana.

231
00:13:46,280 --> 00:13:51,180
Antingen kommer att ta mer tid under
ladda eller mer tid under kontroll.

232
00:13:51,180 --> 00:13:53,560
>> Hur kan du checka in
en trie struktur?

233
00:13:53,560 --> 00:13:56,370
Vi kommer att resa nedåt
i trie.

234
00:13:56,370 --> 00:14:00,390
För varje bokstav i den inmatade ordet
att vi kollar, vi ska gå till den

235
00:14:00,390 --> 00:14:03,280
motsvarande element i barnen.

236
00:14:03,280 --> 00:14:07,770
>> Om detta element är noll, då det betyder
att det inte finns några understrängar

237
00:14:07,770 --> 00:14:11,110
innehåller vår ingång ord, så
ordet är felstavat.

238
00:14:11,110 --> 00:14:15,140
Om det inte är noll, kan vi gå till
nästa bokstav i ordet som vi är

239
00:14:15,140 --> 00:14:18,850
kontroll och fortsätta denna process
tills vi når slutet

240
00:14:18,850 --> 00:14:20,350
av ingångsordet.

241
00:14:20,350 --> 00:14:23,330
Och då kan vi kolla
Om Is Ord är sant.

242
00:14:23,330 --> 00:14:24,610
Om det är, då stor.

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

244
00:14:25,590 --> 00:14:30,890
Men om inte, även om det träng
finns i trie, är ordet

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

246
00:14:32,250 --> 00:14:36,590
>> När funktionen Storlek heter, storlek
ska returnera antalet ord som

247
00:14:36,590 --> 00:14:39,110
är i din tanke dictionary
datastruktur.

248
00:14:39,110 --> 00:14:42,780
Så om du använder en hashtabell, du
kan antingen gå igenom varenda

249
00:14:42,780 --> 00:14:45,860
länkad lista i varje enskild
hink räkna antalet

250
00:14:45,860 --> 00:14:47,130
ord finns där.

251
00:14:47,130 --> 00:14:49,940
Om du använder en trie kan du
gå igenom varje icke null

252
00:14:49,940 --> 00:14:52,030
sökvägen i din trie.

253
00:14:52,030 --> 00:14:56,420
Eller medan du laddar ordlistan
in, kanske du kan hålla reda på hur

254
00:14:56,420 --> 00:14:58,760
många ord du läser in i.

255
00:14:58,760 --> 00:15:03,180
>> När speller.c avslutar kontroll av
textfil mot ordlistan, då

256
00:15:03,180 --> 00:15:08,010
det är gjort och så kallar Unload, där
ditt jobb är att frigöra något

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

258
00:15:09,500 --> 00:15:14,420
Så om du använder en hashtabell, då du
måste vara särskilt noga med att undvika

259
00:15:14,420 --> 00:15:18,830
minnesläckor genom att inte frigöra något
tidigt och hålla på varje

260
00:15:18,830 --> 00:15:20,780
enda länk innan du fri.

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

262
00:15:24,680 --> 00:15:30,100
>> Så för varje element i hash-tabellen
och för varje nod i den länkade listan,

263
00:15:30,100 --> 00:15:32,370
du vill frigöra den noden.

264
00:15:32,370 --> 00:15:34,970
Hur gör man om att frigöra
en länkad lista?

265
00:15:34,970 --> 00:15:38,570
Ställa din nod pekaren markören till
huvudet, till början av den

266
00:15:38,570 --> 00:15:43,100
länkad lista, sedan när markören
inte är noll, kan du ställa in en tillfällig

267
00:15:43,100 --> 00:15:45,610
nod pekare till din markör.

268
00:15:45,610 --> 00:15:48,370
Avancera sedan markören.

269
00:15:48,370 --> 00:15:52,950
Och då kan du gratis att tillfälligt
värde samtidigt som du håller på att

270
00:15:52,950 --> 00:15:55,650
allt efteråt.

271
00:15:55,650 --> 00:15:57,800
>> Vad händer om du använder en trie?

272
00:15:57,800 --> 00:16:00,410
Då det bästa sättet att göra detta
är att lossa från den mycket

273
00:16:00,410 --> 00:16:02,290
botten till toppen.

274
00:16:02,290 --> 00:16:06,920
Genom att resa till lägsta möjliga
nod, kan du befria alla pekare i

275
00:16:06,920 --> 00:16:11,430
att barn och sedan backa
uppåt, vilket frigör alla element i alla

276
00:16:11,430 --> 00:16:15,610
av barnens arrayer, tills
du träffar dina bästa rotnoden.

277
00:16:15,610 --> 00:16:18,920
Här är där rekursion
kommer väl till hands.

278
00:16:18,920 --> 00:16:22,780
>> För att vara säker på att du förmodligen har befriat
allt som du har malloced,

279
00:16:22,780 --> 00:16:24,400
du kan använda Valgrind.

280
00:16:24,400 --> 00:16:28,640
Köra Valgrind kommer att köra ditt program
räkna hur många byte minne

281
00:16:28,640 --> 00:16:32,440
du använder och se till att du har
befriade dem alla, berättar

282
00:16:32,440 --> 00:16:34,530
där du kan ha
glömt att gratis.

283
00:16:34,530 --> 00:16:38,390
Så kör det och när Valgrind berättar
och ger klartecken, då

284
00:16:38,390 --> 00:16:41,160
du är klar lasta.

285
00:16:41,160 --> 00:16:44,420
>> Nu, ett par tips innan du går
av och börja genomföra din

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

287
00:16:46,260 --> 00:16:49,650
Jag skulle rekommendera att gå i en mindre
ordlistan när du försöker testa

288
00:16:49,650 --> 00:16:52,620
saker och felsökning med BNP.

289
00:16:52,620 --> 00:16:58,550
Användningen av speller visas. / Speller, en
valfri ordbok, och sedan en text.

290
00:16:58,550 --> 00:17:01,550
>> Som standard läser det i
tjockt ordboken.

291
00:17:01,550 --> 00:17:06,670
Så du kanske vill gå i den lilla
ordbok, eller kanske till och med göra din

292
00:17:06,670 --> 00:17:11,819
egna, skräddarsy din ordlista
och din textfil.

293
00:17:11,819 --> 00:17:15,950
>> Och slutligen, jag skulle också rekommendera
att ta en penna och papper och rita

294
00:17:15,950 --> 00:17:20,490
saker före, under, och efter
du har skrivit all din kod.

295
00:17:20,490 --> 00:17:24,170
Se bara till att du har
dessa pekare precis rätt.

296
00:17:24,170 --> 00:17:26,480
>> Jag önskar er lycka till.

297
00:17:26,480 --> 00:17:29,690
Och när du är klar, om du vill
att utmana den stora styrelsen och

298
00:17:29,690 --> 00:17:34,390
se hur snabbt ditt program jämförs med
dina klasskamrater ", så uppmuntrar jag

299
00:17:34,390 --> 00:17:35,960
dig att kolla som.

300
00:17:35,960 --> 00:17:39,220
>> Med det har du klar
det stavnings Pset.

301
00:17:39,220 --> 00:17:41,800
Mitt namn är Zamyla, och detta är CS50.

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