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

2
00:00:09,700 --> 00:00:12,140
>> ZAMYLA Chan: Csináljunk
a helyesírás-ellenőrző.

3
00:00:12,140 --> 00:00:16,900
Ha kinyitja speller.c, akkor látni fogod
hogy a legtöbb funkcionalitás

4
00:00:16,900 --> 00:00:20,810
ellenőrzése egy szöveges fájlt ellen
szótár már az Ön számára.

5
00:00:20,810 --> 00:00:26,330
. / Helyesírás, átadva a szótárban szövegben
fájlt, majd egy másik szöveges fájl,

6
00:00:26,330 --> 00:00:28,960
ellenőrzi, hogy a szöveges fájl
szemben a szótárban.

7
00:00:28,960 --> 00:00:34,160
>> Most, szótár szöveges fájlok tartalmazzák
érvényes szó, soronként egyet.

8
00:00:34,160 --> 00:00:37,910
Ezután speller.c hívja Load
A szótár szöveges fájl.

9
00:00:37,910 --> 00:00:43,650
Úgy hívom funkció nevű Ellenőrizze
minden szót a bevitt szöveges fájl,

10
00:00:43,650 --> 00:00:46,460
nyomtatás minden helytelenül írt szavakat.

11
00:00:46,460 --> 00:00:50,030
>> Speller.c is hívni Size
meghatározzák a szavak száma

12
00:00:50,030 --> 00:00:53,500
szótár és hívja Unload
felszabadítani memóriát.

13
00:00:53,500 --> 00:00:57,600
speller.c is nyomon követheti, hogy
sok időt használják, hogy végezzen ezen

14
00:00:57,600 --> 00:01:00,560
folyamatokat, de majd
eljutni, hogy később.

15
00:01:00,560 --> 00:01:02,440
>> Mit kell tennünk?

16
00:01:02,440 --> 00:01:05,110
Meg kell, hogy töltse ki dictionary.c.

17
00:01:05,110 --> 00:01:09,940
A dictionary.c, mi van a segítő
funkció betöltése, amely betölti a

18
00:01:09,940 --> 00:01:10,855
szótárban.

19
00:01:10,855 --> 00:01:15,490
A funkció Check, amely ellenőrzi, hogy
egy adott szó szerepel a szótárban.

20
00:01:15,490 --> 00:01:19,150
A függvény Size számát adja vissza
A szavak a szótárban.

21
00:01:19,150 --> 00:01:24,870
És végül, mi kirak, amely
megszabadítja a szótárban a memóriából.

22
00:01:24,870 --> 00:01:27,070
>> Tehát először, hadd kezelni betöltése.

23
00:01:27,070 --> 00:01:32,110
Minden szó a szótárban szövegben
fájl betöltése tárolja ezeket a szavakat

24
00:01:32,110 --> 00:01:34,860
A szótár adatstruktúra
az Ön által választott, vagy a

25
00:01:34,860 --> 00:01:36,750
hash tábla vagy trie.

26
00:01:36,750 --> 00:01:39,440
Megyek, mint mind a
ez a séta.

27
00:01:39,440 --> 00:01:43,150
>> Először is beszéljünk hash táblákat.

28
00:01:43,150 --> 00:01:47,050
Tegyük fel, hogy 10 biliárd golyó és
akarod tárolni őket.

29
00:01:47,050 --> 00:01:50,420
Lehet, hogy tedd őket egy vödör,
és ha szükség van egy bizonyos

30
00:01:50,420 --> 00:01:54,010
számozott golyó, azt hogy egy
ki a vödör egy időben

31
00:01:54,010 --> 00:01:55,880
keresi a labdát.

32
00:01:55,880 --> 00:01:59,370
És csak 10 golyó, ha kell
képes megtalálni a labdát ésszerű

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

34
00:02:01,160 --> 00:02:03,180
>> De mi van, ha már 20 golyót?

35
00:02:03,180 --> 00:02:05,480
Ez eltarthat egy kis ideig most.

36
00:02:05,480 --> 00:02:06,180
Mi a helyzet a 100?

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

38
00:02:07,880 --> 00:02:11,590
Nos, ez sokkal könnyebb, ha
hogy volt több vödör.

39
00:02:11,590 --> 00:02:15,890
Talán egy vödör labda számozott nulla
a kilenc, a másik vödör

40
00:02:15,890 --> 00:02:18,800
labdák számozott 10 és
19, és így tovább.

41
00:02:18,800 --> 00:02:22,330
>> Most, amikor kellett keresni bizonyos
labda, akkor automatikusan

42
00:02:22,330 --> 00:02:26,320
menj egy adott vödör és
keresni, hogy a vödör.

43
00:02:26,320 --> 00:02:29,840
És ha minden vödör körülbelül 10
golyó, akkor könnyen keres

44
00:02:29,840 --> 00:02:31,790
át rajta.

45
00:02:31,790 --> 00:02:34,960
>> Most, mivel van dolgunk
szótárak, egyetlen vödör

46
00:02:34,960 --> 00:02:41,970
az összes szó a szótár
valószínűleg túl kevés vödör.

47
00:02:41,970 --> 00:02:44,370
Szóval vessünk egy pillantást a hash táblák.

48
00:02:44,370 --> 00:02:46,940
>> Gondold azt, hogy egy sor vödör.

49
00:02:46,940 --> 00:02:50,370
És ebben az esetben, a kanalak
a mi kapcsolt listák.

50
00:02:50,370 --> 00:02:54,770
És mi terjeszteni minden szavaink
ezek közül több kapcsolt listák

51
00:02:54,770 --> 00:02:58,940
szervezett módon egy hash függvény,
, amely megmondja, hogy melyik

52
00:02:58,940 --> 00:03:03,720
vödör egy adott kulcsot, egy adott
szó, tartozik.

53
00:03:03,720 --> 00:03:05,960
>> Nézzük képviseli ezt sematikusan.

54
00:03:05,960 --> 00:03:11,320
A kék doboz Itt értékeket tartalmaz, és
piros doboz pont egy másik értéket

55
00:03:11,320 --> 00:03:12,280
mutató pár.

56
00:03:12,280 --> 00:03:14,800
Majd hívja ezeket pár csomópontok.

57
00:03:14,800 --> 00:03:18,260
Most minden vödör, mint mondtam
korábban, egy láncolt lista.

58
00:03:18,260 --> 00:03:21,820
A kapcsolt listák, minden csomópont értéke,
valamint a mutató a

59
00:03:21,820 --> 00:03:23,170
következő érték.

60
00:03:23,170 --> 00:03:26,150
>> Most foglalkozó kapcsolt listák,
ez nagyon fontos, hogy

61
00:03:26,150 --> 00:03:28,120
ne vesszenek el linkeket.

62
00:03:28,120 --> 00:03:32,250
És egy másik tény, hogy emlékezzen, hogy a
utolsó csomópont, ha nem mutat

63
00:03:32,250 --> 00:03:35,120
egy másik csomópont, rámutat arra, null.

64
00:03:35,120 --> 00:03:37,970
>> Szóval hogyan képviseljük ezt a C?

65
00:03:37,970 --> 00:03:40,540
Mi határozza meg a struct itt.

66
00:03:40,540 --> 00:03:44,850
És az érték ebben az esetben
egy char tömb hosszát.

67
00:03:44,850 --> 00:03:48,880
Hossz plusz 1, ahol a hossza
maximális hossza minden szó, plusz 1

68
00:03:48,880 --> 00:03:50,380
A null terminátor.

69
00:03:50,380 --> 00:03:54,210
És akkor van egy mutatót
másik csomópont az úgynevezett Next.

70
00:03:54,210 --> 00:03:56,730
>> Szóval egy kis láncolt lista.

71
00:03:56,730 --> 00:04:00,390
Először is, akkor szeretné malloc a csomópont,
melyek között helyet a memóriában a

72
00:04:00,390 --> 00:04:04,010
mérete a csomópont típusát.

73
00:04:04,010 --> 00:04:06,100
És hogy egy másik csomópont,
ismét mallocing.

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

75
00:04:09,370 --> 00:04:14,340
>> Most, ha azt szeretnénk, hogy egy értéket, hogy a
szó, akkor azt mondhatnánk Node1 nyíl

76
00:04:14,340 --> 00:04:18,820
szó egyenlő "Hello." Ez a nyíl operátor
dereferences a mutató és a

77
00:04:18,820 --> 00:04:20,620
hozzáfér a struct a változókat.

78
00:04:20,620 --> 00:04:24,330
Így nem kell használni a két
A pont és a csillag operátor.

79
00:04:24,330 --> 00:04:30,100
>> Így aztán van node2 nyíl szó értéke
"A világ." És ott, az értékek

80
00:04:30,100 --> 00:04:33,110
lakott az én csomópontok.

81
00:04:33,110 --> 00:04:38,780
Ahhoz, hogy a linkeket, majd át a Node1
mutató nyilat, hozzáférés a csomópont csillag,

82
00:04:38,780 --> 00:04:44,160
hogy a csomópont mutató, egyenlő node2,
rámutatva Node1 a node2 kettő.

83
00:04:44,160 --> 00:04:46,360
És ott van egy láncolt lista.

84
00:04:46,360 --> 00:04:51,480
>> Szóval ez csak egy láncolt lista, de
a hash tábla egy egész sor

85
00:04:51,480 --> 00:04:52,520
kapcsolt listák.

86
00:04:52,520 --> 00:04:55,920
Nos, akkor ugyanaz a csomópont
szerkezet, mint korábban.

87
00:04:55,920 --> 00:05:00,140
De ha volna egy valódi hash tábla,
akkor csak egy csomópontot mutató

88
00:05:00,140 --> 00:05:01,330
array itt.

89
00:05:01,330 --> 00:05:04,940
Például, méret 500.

90
00:05:04,940 --> 00:05:08,910
>> Figyeljük, ott lesz a kereskedelmi
le a méretét, a

91
00:05:08,910 --> 00:05:11,280
hash tábla és a méret
a kapcsolt listák.

92
00:05:11,280 --> 00:05:15,640
Ha van egy nagyon nagy számú
vödrök, elképzeli, hogy fuss vissza

93
00:05:15,640 --> 00:05:18,230
-oda, hogy egy sorban
megtalálja a vödör.

94
00:05:18,230 --> 00:05:21,530
De akkor is, nem akar egy kis számú
vödrök, mert akkor vagyunk vissza

95
00:05:21,530 --> 00:05:26,850
Az eredeti probléma az, hogy miután
Túl sok golyókat a vödör.

96
00:05:26,850 --> 00:05:30,480
>> OK, de hol a labda megy?

97
00:05:30,480 --> 00:05:33,150
Nos, először meg kell
van a labda, nem igaz?

98
00:05:33,150 --> 00:05:39,130
Szóval malloc csomópont minden
új szó, hogy mi van.

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

100
00:05:42,900 --> 00:05:46,760
>> Most, hogy ezt a struktúrát, akkor
képes beolvasni, a funkció

101
00:05:46,760 --> 00:05:51,850
fscanf egy stringet a fájlt, ha
ez a szótár fájlt, a

102
00:05:51,850 --> 00:05:55,780
new_node nyíl szó, ahol new_node
nyíl szó a mi

103
00:05:55,780 --> 00:05:58,110
rendeltetési ezt a szót.

104
00:05:58,110 --> 00:06:01,900
>> Ezután, akkor szeretnénk kódot, ami
szót a hash függvényt.

105
00:06:01,900 --> 00:06:05,860
A hash függvény a karakterlánc
, és visszatér az index.

106
00:06:05,860 --> 00:06:09,760
Ebben az esetben, az index kell
lehet kevesebb, mint ahány

107
00:06:09,760 --> 00:06:11,440
vödör, hogy van.

108
00:06:11,440 --> 00:06:14,600
>> Most, hash függvények, amikor akarsz
megtalálni az egyik, és hozzon létre egy

109
00:06:14,600 --> 00:06:17,890
saját, ne feledje, hogy
kell determinisztikus.

110
00:06:17,890 --> 00:06:22,420
Ez azt jelenti, hogy ugyanazt az értéket kell
ugyanarra az vödör minden alkalommal

111
00:06:22,420 --> 00:06:23,800
hogy hash azt.

112
00:06:23,800 --> 00:06:25,300
>> Ez olyan, mint egy könyvtár.

113
00:06:25,300 --> 00:06:28,560
Ha veszel egy könyvet, amely a
szerző, tudja, melyik polcon kellene

114
00:06:28,560 --> 00:06:31,890
megy, legyen szó akár polc számot
egy, kettő, vagy három.

115
00:06:31,890 --> 00:06:36,280
És ez a könyv mindig tartozik a
polc vagy egy, két, vagy három.

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

117
00:06:39,460 --> 00:06:43,810
>> Tehát, ha new_node nyíl szónak a
szót a szótárban, akkor

118
00:06:43,810 --> 00:06:47,770
hashing new_node nyíl Word
nekünk az index a

119
00:06:47,770 --> 00:06:49,370
vödör a hash tábla.

120
00:06:49,370 --> 00:06:54,040
És akkor majd be, hogy az ebbe a
speciális láncolt lista jelzi,

121
00:06:54,040 --> 00:06:56,060
vissza értéket a hash függvény.

122
00:06:56,060 --> 00:06:59,070
>> Nézzünk egy példát
behelyezése csomópont a

123
00:06:59,070 --> 00:07:01,750
elején egy láncolt lista.

124
00:07:01,750 --> 00:07:06,930
Ha a feje egy csomópont mutató, amely jelzi
az elején egy kapcsolt

125
00:07:06,930 --> 00:07:12,420
listára, new_node jelzi az új
csomópont, amely meg szeretné adni a csak

126
00:07:12,420 --> 00:07:17,340
hozzárendelése fej new_node veszít
a kapcsolatot a többi a listán.

127
00:07:17,340 --> 00:07:19,330
Tehát nem akarom ezt csinálni.

128
00:07:19,330 --> 00:07:22,160
>> Inkább azt szeretnénk, hogy győződjön meg arról,
hogy ragaszkodnak a minden

129
00:07:22,160 --> 00:07:23,550
single node a programunkban.

130
00:07:23,550 --> 00:07:29,560
Így fut new_node nyílra egyenlő
fejét, majd fej egyenlő new_node

131
00:07:29,560 --> 00:07:34,470
megőrzi az összes
kapcsolatokat, és nem vesztett.

132
00:07:34,470 --> 00:07:39,330
>> De mi van, ha azt szeretné, hogy dől, hogy
sorrendje, mert miután a sorrendje kötött

133
00:07:39,330 --> 00:07:42,910
lista talán könnyebb
keres, hogy a későbbiekben?

134
00:07:42,910 --> 00:07:46,020
Nos, az, hogy akkor kell tudni
hogyan áthalad láncolt listák.

135
00:07:46,020 --> 00:07:51,210
>> Áthalad a láncolt lista, vessünk
egy csomópont mutató, egy csomópont *, hogy jár

136
00:07:51,210 --> 00:07:54,120
a kurzort, hogy mely
csomópont te vagy, kezdve

137
00:07:54,120 --> 00:07:55,460
az első elem.

138
00:07:55,460 --> 00:08:01,070
Hurok amíg kurzor null, tudjuk
magatartás bizonyos folyamatokat, majd a

139
00:08:01,070 --> 00:08:04,330
előre a kurzor, amikor szükségünk
a kurzor nyíl értéket.

140
00:08:04,330 --> 00:08:08,820
>> Ne feledje, hogy ez ugyanaz, mint a
mondván csillag kurzor, dereferencing

141
00:08:08,820 --> 00:08:13,480
kurzorral, majd a
dot operátor értéke.

142
00:08:13,480 --> 00:08:19,000
Így frissíti a kurzor hozzárendelésével
a kurzort a kurzor nyílra.

143
00:08:19,000 --> 00:08:24,960
>> Mondja el, hogy határozza meg, hogy a D válik a
a C és E behelyezéséhez a csomópont,

144
00:08:24,960 --> 00:08:30,030
van new_node D pont a
node E, amely a kurzor mellett.

145
00:08:30,030 --> 00:08:36,409
És akkor a C, a kurzor, aztán pont
D. Így, ha fenntartja a listát.

146
00:08:36,409 --> 00:08:41,080
Ügyeljen arra, hogy ne veszítse el a linkeket
mozog a kurzor nyílra D

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

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

149
00:08:44,620 --> 00:08:48,920
Szóval így lehet beszúrni csomópontok,
töltse be őket, terhelés szavak ezek

150
00:08:48,920 --> 00:08:51,600
csomópontok, és helyezze őket
be a hash tábla.

151
00:08:51,600 --> 00:08:53,580
Most nézzük meg próbál.

152
00:08:53,580 --> 00:08:58,540
>> A trie minden csomópont tartalmaz
tömb csomópont mutatók, egy minden

153
00:08:58,540 --> 00:09:02,260
betű az ábécé
plusz egy aposztróf.

154
00:09:02,260 --> 00:09:06,150
És minden egyes elem a tömbben
fog mutatni egy másik csomópont.

155
00:09:06,150 --> 00:09:10,130
Ha ez a csomópont null, akkor a levél
nem lesz, hogy a következő levél

156
00:09:10,130 --> 00:09:15,690
bármilyen szót egymás után, mert minden
szó jelzi, hogy ez az utolsó

157
00:09:15,690 --> 00:09:18,160
karakter egy szó, vagy sem.

158
00:09:18,160 --> 00:09:19,750
>> Nézzük meg a diagram.

159
00:09:19,750 --> 00:09:22,260
Remélhetőleg a dolgok
egy kicsit világosabb.

160
00:09:22,260 --> 00:09:27,210
Ezen az ábrán azt látjuk, hogy csak a
Egyes betűk és bizonyos stringek

161
00:09:27,210 --> 00:09:28,190
kerülnek felsorolt ​​ki.

162
00:09:28,190 --> 00:09:32,500
Így a bizonyos utak és
az összes ilyen út fog vezetni, hogy

163
00:09:32,500 --> 00:09:34,020
más szavakkal.

164
00:09:34,020 --> 00:09:37,630
>> Szóval hogyan képviseljük ezt a C?

165
00:09:37,630 --> 00:09:41,910
Nos, minden csomópont most már megy, hogy
egy logikai érték azt jelzi, hogy

166
00:09:41,910 --> 00:09:46,580
csomópont, hogy a vége a
egy adott szó vagy sem.

167
00:09:46,580 --> 00:09:50,690
És akkor lesz is egy sor
node mutatók nevű gyermekeket, és

168
00:09:50,690 --> 00:09:53,440
ott lesznek a 27-et.

169
00:09:53,440 --> 00:09:56,510
És ne feledd, akkor is szeretnénk
nyomon követheti az első csomópont.

170
00:09:56,510 --> 00:09:59,830
Fogjuk hívni, hogy a gyökér.

171
00:09:59,830 --> 00:10:01,690
>> Szóval ez a szerkezet egy trie.

172
00:10:01,690 --> 00:10:05,630
Hogyan képviselik ezt
a szótárban?

173
00:10:05,630 --> 00:10:09,890
Nos, betölteni szavak, minden
szótári szót, fogsz akar

174
00:10:09,890 --> 00:10:11,960
hogy halad végig a trie.

175
00:10:11,960 --> 00:10:16,170
És minden egyes eleme a gyerekek
felel meg egy másik levelet.

176
00:10:16,170 --> 00:10:21,660
>> Így ellenőrzi az értéket gyerekek
i indexet, ahol i a

177
00:10:21,660 --> 00:10:24,840
specifikus indexet a levélnek,
akarsz beilleszteni.

178
00:10:24,840 --> 00:10:28,980
Nos, ha ez nulla, akkor szeretné majd
malloc egy új csomópont, és a gyermekek

179
00:10:28,980 --> 00:10:31,110
Én pont a csomópont.

180
00:10:31,110 --> 00:10:35,630
>> Ha ez nem nulla, akkor ez azt jelenti, hogy az
hogy az adott ágazatban, hogy az adott

181
00:10:35,630 --> 00:10:37,350
substring, már létezik.

182
00:10:37,350 --> 00:10:40,160
Tehát akkor csak költözni, hogy
új csomópont és tovább.

183
00:10:40,160 --> 00:10:43,220
Ha a végén a szó, hogy
próbál betölteni a

184
00:10:43,220 --> 00:10:48,120
szótárt, akkor beállíthatja, hogy a
jelenlegi csomópont, hogy te vagy az igazi.

185
00:10:48,120 --> 00:10:51,550
>> Tehát nézzük meg egy példát beillesztése
a "róka" a mi

186
00:10:51,550 --> 00:10:53,070
szótárban.

187
00:10:53,070 --> 00:10:56,110
Tegyen úgy, mintha kezdjük
egy üres szótárban.

188
00:10:56,110 --> 00:11:01,610
Az első betű, N, lesz található
gyermekeknél indexe öt a gyökerek

189
00:11:01,610 --> 00:11:03,700
gyerekek tömb.

190
00:11:03,700 --> 00:11:05,430
Tehát be, hogy be

191
00:11:05,430 --> 00:11:14,610
>> Az O betű ezután a gyermekek
index 15, azt követően, hogy F. És akkor X

192
00:11:14,610 --> 00:11:20,180
lesz még elmarad, elágazás
ki az O gyermekei.

193
00:11:20,180 --> 00:11:24,120
És akkor azért, mert az X az utolsó betű
A szó "róka", akkor megyek

194
00:11:24,120 --> 00:11:27,210
hogy a zöld szín jelzi, hogy
ez a végén a szó.

195
00:11:27,210 --> 00:11:32,880
A C-ben, hogy a beállítás lenne az Is
A Word Boolean értékre igaz.

196
00:11:32,880 --> 00:11:36,780
>> Most mi van, ha a következő szó, hogy te
Betöltés a "valami"?

197
00:11:36,780 --> 00:11:41,490
Nos, akkor nem kell malloc többé
hely a F vagy O, mert

198
00:11:41,490 --> 00:11:42,990
a már léteznek.

199
00:11:42,990 --> 00:11:45,910
De az utolsó O foo?

200
00:11:45,910 --> 00:11:47,320
Az az egy, akkor meg kell malloc.

201
00:11:47,320 --> 00:11:52,390
Készíts egy új csomópont számára, hogy a beállítás
A szájról logikai igaz.

202
00:11:52,390 --> 00:11:57,340
>> Tehát most menjünk be "kutya". Kutya
indexe három kezdeni a gyökerek

203
00:11:57,340 --> 00:12:00,520
gyermekek, mert D nem
hozták létre, mégis.

204
00:12:00,520 --> 00:12:04,990
És mi követik hasonló folyamat
előtt, ami a substring kutya,

205
00:12:04,990 --> 00:12:10,400
hol van a G zöld színű, mivel
ez a végén egy szót sem.

206
00:12:10,400 --> 00:12:13,160
>> Nos, mi van, ha azt akarjuk, hogy be "csinálni"?

207
00:12:13,160 --> 00:12:17,150
Nos, ez egy substring kutya, így a
nem kell malloc többé.

208
00:12:17,150 --> 00:12:20,800
De el kell, hogy jelezze, hol voltunk
végére ért a szót.

209
00:12:20,800 --> 00:12:24,020
Így az O lesz zöld színű.

210
00:12:24,020 --> 00:12:27,810
Folytatva ezt a folyamatot minden egyes
szó a szótárban, akkor már

211
00:12:27,810 --> 00:12:32,120
betöltött őket be akár a
hash tábla, vagy a trie.

212
00:12:32,120 --> 00:12:37,530
>> speller.c fog múlni a húrok
dictionary.c, hogy ellenőrizze őket.

213
00:12:37,530 --> 00:12:41,140
Most, a Check funkció működik
alatt érzékenységet.

214
00:12:41,140 --> 00:12:45,980
Ez azt jelenti, hogy a nagybetűk és a
kisbetűk és a kettő keveréke

215
00:12:45,980 --> 00:12:50,670
kell minden egyenértékű a igaz, ha minden
kombinációja, ami a

216
00:12:50,670 --> 00:12:51,880
szótárban.

217
00:12:51,880 --> 00:12:55,580
Azt is feltételezik, hogy a húrok
csak akkor fog tartalmaznia ábécé

218
00:12:55,580 --> 00:12:58,200
karakterek vagy aposztrófok.

219
00:12:58,200 --> 00:13:02,490
>> Tehát nézzük meg, hogyan lehet ellenőrizni
egy hash tábla szerkezetét.

220
00:13:02,490 --> 00:13:07,330
Nos, ha a szó létezik, akkor
megtalálható a hash táblában.

221
00:13:07,330 --> 00:13:12,240
Szóval, akkor próbálja meg, hogy
szó a megfelelő kukába.

222
00:13:12,240 --> 00:13:14,480
>> Tehát melyik vödör lenne szó legyen?

223
00:13:14,480 --> 00:13:20,060
Nos, azt a számot, hogy az index
a kanál, a Wget szó

224
00:13:20,060 --> 00:13:23,690
, majd a keresés az, hogy láncolt lista,
áthaladó az egész

225
00:13:23,690 --> 00:13:28,060
láncolt lista, a karakterlánc
Hasonlítsa össze a funkciót.

226
00:13:28,060 --> 00:13:31,940
>> Ha a végén a kapcsolódó lista
érte el, ami azt jelenti, hogy a kurzor

227
00:13:31,940 --> 00:13:36,030
eléri null, akkor a szó nem
megtalálható a szótárban.

228
00:13:36,030 --> 00:13:39,090
Nem lesz más vödör.

229
00:13:39,090 --> 00:13:43,020
Tehát itt, akkor lehet látni, hogy ott lehet
egy kompromisszumot, amelyek rendelkeznek

230
00:13:43,020 --> 00:13:46,280
sorrendje kapcsolt listák vagy válogatás nélkül is.

231
00:13:46,280 --> 00:13:51,180
Vagy több időre lesz szükség idején
betölteni vagy több idő alatt ellenőrzés.

232
00:13:51,180 --> 00:13:53,560
>> Hogy lehet, hogy ellenőrizze a
a trie szerkezet?

233
00:13:53,560 --> 00:13:56,370
Fogunk utazni lefelé
A trie.

234
00:13:56,370 --> 00:14:00,390
Minden egyes levél a bevitt szó
hogy mi ellenőrzés, akkor megy, hogy

235
00:14:00,390 --> 00:14:03,280
megfelelő elem a gyerekek.

236
00:14:03,280 --> 00:14:07,770
>> Ha ez az elem nulla, az azt jelenti,
hogy nincsenek részkarakterláncok

237
00:14:07,770 --> 00:14:11,110
amely a bemeneti szó, így a
a szó el van írva.

238
00:14:11,110 --> 00:14:15,140
Ha ez nem nulla, akkor menjen a
következő betű, a szó, hogy mi vagyunk

239
00:14:15,140 --> 00:14:18,850
ellenőrzése és továbbra is ezt a folyamatot
amíg el nem érjük a végét

240
00:14:18,850 --> 00:14:20,350
a bemeneti szó.

241
00:14:20,350 --> 00:14:23,330
És akkor tudjuk ellenőrizni
ha szájról igaz.

242
00:14:23,330 --> 00:14:24,610
Ha igen, akkor jó.

243
00:14:24,610 --> 00:14:25,590
A szó helyes.

244
00:14:25,590 --> 00:14:30,890
De ha nem, annak ellenére, hogy a substring
létezik a trie, a szó

245
00:14:30,890 --> 00:14:32,250
hibásan.

246
00:14:32,250 --> 00:14:36,590
>> A funkció Méret neve, mérete
vissza kell adnia a szavak száma, amely

247
00:14:36,590 --> 00:14:39,110
vannak a adott szótárban
adatstruktúra.

248
00:14:39,110 --> 00:14:42,780
Tehát, ha egy hash tábla, akkor
sem megy keresztül minden egyes

249
00:14:42,780 --> 00:14:45,860
láncolt lista minden egyes
vödör számítva a szám

250
00:14:45,860 --> 00:14:47,130
szavak vannak.

251
00:14:47,130 --> 00:14:49,940
Ha használ trie, akkor
megy keresztül minden nem null

252
00:14:49,940 --> 00:14:52,030
utat az trie.

253
00:14:52,030 --> 00:14:56,420
Vagy amíg töltöd a szótárban
ben, talán te is nyomon követheti, hogyan

254
00:14:56,420 --> 00:14:58,760
sok szót töltöd be

255
00:14:58,760 --> 00:15:03,180
>> Ha speller.c befejezi ellenőrzése
szöveges fájlt szemben a szótárban, akkor

256
00:15:03,180 --> 00:15:08,010
ez történt, és ezért kéri, kirak, ahol
a feladata, hogy szabad semmit

257
00:15:08,010 --> 00:15:09,500
hogy már malloced.

258
00:15:09,500 --> 00:15:14,420
Tehát, ha egy hash táblát, akkor
kell, hogy legyen különösen óvatos, hogy ne

259
00:15:14,420 --> 00:15:18,830
memóriavesztés, hogy nem szabaddá semmit
idő előtt és kapaszkodott minden

260
00:15:18,830 --> 00:15:20,780
Single Link előtt ingyenes.

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

262
00:15:24,680 --> 00:15:30,100
>> Így minden eleme a hash tábla
és minden csomópont a láncolt lista,

263
00:15:30,100 --> 00:15:32,370
akkor szeretnénk felszabadítani a csomópont.

264
00:15:32,370 --> 00:15:34,970
Hogy megy a szabaddá
A láncolt lista?

265
00:15:34,970 --> 00:15:38,570
Beállítása csomópont egérmutatót a
a fejet, hogy az elején a

266
00:15:38,570 --> 00:15:43,100
láncolt lista, majd miközben a kurzor
nem null, akkor meg egy átmeneti

267
00:15:43,100 --> 00:15:45,610
node mutató a kurzort.

268
00:15:45,610 --> 00:15:48,370
Ezután előre a kurzort.

269
00:15:48,370 --> 00:15:52,950
És akkor szabad, hogy az ideiglenes
érték miközben folyamatosan tovább

270
00:15:52,950 --> 00:15:55,650
Mindent utána.

271
00:15:55,650 --> 00:15:57,800
>> Mi van, ha egy trie?

272
00:15:57,800 --> 00:16:00,410
Akkor a legjobb módja annak, hogy ezt
hogy kirak a nagyon

273
00:16:00,410 --> 00:16:02,290
lentről felfelé.

274
00:16:02,290 --> 00:16:06,920
Az utazás a lehető legalacsonyabb
csomópont, akkor szabad az összes mutatókat

275
00:16:06,920 --> 00:16:11,430
hogy a gyerekek majd visszalép
felfelé, felszabadítja az összes elemet minden

276
00:16:11,430 --> 00:16:15,610
a gyerekek tömbök, amíg
bejön a felső gyökér csomópont.

277
00:16:15,610 --> 00:16:18,920
Itt, ahol rekurzió
jól jöhet.

278
00:16:18,920 --> 00:16:22,780
>> Annak érdekében, hogy már valószínűleg felszabadult
Mindent, amit malloced,

279
00:16:22,780 --> 00:16:24,400
használhatja Valgrind.

280
00:16:24,400 --> 00:16:28,640
Running Valgrind fog futni a programot
számítva hány bájt memóriával

281
00:16:28,640 --> 00:16:32,440
amit használ, és ügyelve arra, hogy már
kiszabadította őket, mondom

282
00:16:32,440 --> 00:16:34,530
ahol lehet, hogy
elfelejtett ingyenes.

283
00:16:34,530 --> 00:16:38,390
Úgy fussatok, hogy az, és ha Valgrind megmondja
és adja meg a zöld utat, akkor

284
00:16:38,390 --> 00:16:41,160
befejezte a memóriából.

285
00:16:41,160 --> 00:16:44,420
>> Most, néhány tipp, mielőtt elmész
off és start végrehajtásának a

286
00:16:44,420 --> 00:16:46,260
szótárban.

287
00:16:46,260 --> 00:16:49,650
Én azt javasolnám, hogy adja át egy kisebb
szótár, ha akarsz tesztelni

288
00:16:49,650 --> 00:16:52,620
a dolgokat, és a hibakeresés a GDP.

289
00:16:52,620 --> 00:16:58,550
A használata helyesírás is. / Helyesírás, egy
opcionális szótár, majd a szöveget.

290
00:16:58,550 --> 00:17:01,550
>> Alapértelmezésben betölti a
nagy szótár.

291
00:17:01,550 --> 00:17:06,670
Tehát érdemes átadni a kis
szótár, vagy akár, hogy a

292
00:17:06,670 --> 00:17:11,819
saját, testre szótár
és a szöveges fájl.

293
00:17:11,819 --> 00:17:15,950
>> És végül, én is ajánlom
hogy egy tollat ​​és papírt, és felhívni

294
00:17:15,950 --> 00:17:20,490
dolgokat előtt, alatt és után
írtál az összes kódot.

295
00:17:20,490 --> 00:17:24,170
Csak győződjön meg arról, hogy van
ezek a mutatók csak jobb.

296
00:17:24,170 --> 00:17:26,480
>> Kívánok sok szerencsét.

297
00:17:26,480 --> 00:17:29,690
És ha egyszer már elkészült, ha szeretné
kihívást jelent a nagy táblára, és

298
00:17:29,690 --> 00:17:34,390
milyen gyors a program, mint a
az osztálytársaival ", akkor azt javasoljuk,

299
00:17:34,390 --> 00:17:35,960
, hogy ellenőrizze, hogy ki.

300
00:17:35,960 --> 00:17:39,220
>> Ezzel befejezte
A helyesírás Pset.

301
00:17:39,220 --> 00:17:41,800
A nevem Zamyla, és ez CS50.

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