1
00:00:00,000 --> 00:00:12,350
>> [Mūzikas atskaņošanai]

2
00:00:12,350 --> 00:00:13,050
>> ROB BOWDEN: Hi.

3
00:00:13,050 --> 00:00:13,640
Es esmu Rob.

4
00:00:13,640 --> 00:00:16,210
Un pieņemsim šo risinājumu out.

5
00:00:16,210 --> 00:00:20,070
Tāpēc šeit mēs ejam, lai īstenotu
vispārēja tabula.

6
00:00:20,070 --> 00:00:24,090
Mēs redzam, ka struktūrai mezgla mūsu
tabula gatavojas izskatās šādi.

7
00:00:24,090 --> 00:00:28,710
Tātad, tas notiek, lai būtu char vārds
masīva izmēru GARUMS + 1.

8
00:00:28,710 --> 00:00:32,259
Neaizmirstiet + 1, jo maksimālais
vārdu vārdnīcā ir 45

9
00:00:32,259 --> 00:00:33,130
rakstzīmes.

10
00:00:33,130 --> 00:00:37,070
Un tad mēs spēsim nepieciešams viens papildus
rakstzīme slīpsvītru nulles.

11
00:00:37,070 --> 00:00:40,870
>> Un tad mūsu Hashtable katrā
kauss ir gatavojas glabāt

12
00:00:40,870 --> 00:00:42,320
saistīts saraksts mezglu.

13
00:00:42,320 --> 00:00:44,420
Mēs nedarām lineāra zondēšana šeit.

14
00:00:44,420 --> 00:00:48,430
Un tāpēc, lai saite uz nākamā
elements spainī, mums ir nepieciešams

15
00:00:48,430 --> 00:00:50,390
struct mezglā * nākamo.

16
00:00:50,390 --> 00:00:51,110
OK.

17
00:00:51,110 --> 00:00:53,090
Tātad, tas ir tas, ko mezglā izskatās.

18
00:00:53,090 --> 00:00:56,180
>> Tagad šeit ir deklarācija
Mūsu Hashtable.

19
00:00:56,180 --> 00:00:59,640
Tas nāksies 16834 spaiņos.

20
00:00:59,640 --> 00:01:01,910
Bet šis numurs nav īsti jautājums.

21
00:01:01,910 --> 00:01:05,450
Un visbeidzot, mēs esam nāksies
globālo mainīgo Hashtable lielums, kas

22
00:01:05,450 --> 00:01:07,000
gatavojas sākt kā nulle.

23
00:01:07,000 --> 00:01:10,760
Un tas notiek, lai sekotu, kā
daudzi vārdi ir mūsu vārdnīcā.

24
00:01:10,760 --> 00:01:13,710
>> Tātad, pieņemsim to apskatīt slodzes.

25
00:01:13,710 --> 00:01:16,390
Ievērojiet, ka slodze, tā atgriež bool.

26
00:01:16,390 --> 00:01:20,530
Jūs atgrieztos taisnība, ja tas bija veiksmīgi
piekrauts, un viltus citādi.

27
00:01:20,530 --> 00:01:23,990
Un tas notiek const char * vārdnīcu,
kas ir vārdnīcā

28
00:01:23,990 --> 00:01:25,280
ka mēs vēlamies, lai atvērtu.

29
00:01:25,280 --> 00:01:27,170
Tā ka ir pirmā lieta,
mēs gatavojamies darīt.

30
00:01:27,170 --> 00:01:29,500
>> Mēs ejam, lai fopen
vārdnīca lasījumā.

31
00:01:29,500 --> 00:01:31,680
Un mēs esam nāksies veikt
pārliecināti, ka tas izdevās.

32
00:01:31,680 --> 00:01:35,920
Tātad, ja tas atgriezās nulle, tad mēs neesam
veiksmīgi atvērt vārdnīcu.

33
00:01:35,920 --> 00:01:37,440
Un mums ir nepieciešams, lai atgrieztos nepatiesa.

34
00:01:37,440 --> 00:01:41,580
Bet, pieņemot, ka tā veiksmīgi
atvērt, tad mēs vēlamies, lai izlasītu

35
00:01:41,580 --> 00:01:42,400
vārdnīca.

36
00:01:42,400 --> 00:01:46,450
Lai saglabātu looping kamēr mēs atrodam kādu
iemesls, lai izkļūt no šīs cilpas,

37
00:01:46,450 --> 00:01:47,570
ko mēs redzēsim.

38
00:01:47,570 --> 00:01:48,920
Lai saglabātu looping.

39
00:01:48,920 --> 00:01:51,780
>> Un tagad mēs esam gatavojas
malloc vienu mezglu.

40
00:01:51,780 --> 00:01:54,020
Un, protams, mums ir nepieciešams
gaisā pārbaudiet vēlreiz.

41
00:01:54,020 --> 00:01:58,680
Tātad, ja mallocing neizdevās, tad
Mēs vēlamies, lai izkrautu jebkuru mezglu, ko mēs

42
00:01:58,680 --> 00:02:02,590
notika ar malloc pirms slēgt
vārdnīcu un atgriezties viltus.

43
00:02:02,590 --> 00:02:06,830
Bet ignorējot, ka, pieņemot, ka mēs
izdevies, tad mēs vēlamies izmantot fscanf

44
00:02:06,830 --> 00:02:12,400
lasīt vienu vārdu no mūsu
vārdnīca mūsu mezglā.

45
00:02:12,400 --> 00:02:17,940
Tātad, atcerieties, ka ienākošo> vārds ir char
vārdu bufera izmēra garumiem + 1

46
00:02:17,940 --> 00:02:20,300
ka mēs ejam, lai saglabātu vārdu iekšā

47
00:02:20,300 --> 00:02:25,070
>> Tāpēc fscanf gatavojas atgriezties 1, ja vien
jo tas varēja veiksmīgi

48
00:02:25,070 --> 00:02:26,750
lasīt vārdu no lietas materiāliem.

49
00:02:26,750 --> 00:02:30,460
Ja nu kļūda notiek, vai mēs
beigs faila, tā

50
00:02:30,460 --> 00:02:31,950
vairs neatgriezīsies 1.

51
00:02:31,950 --> 00:02:35,180
Tādā gadījumā tas neatgriežas 1,
mēs beidzot gatavojas izkļūt no

52
00:02:35,180 --> 00:02:37,280
to, kamēr cilpa.

53
00:02:37,280 --> 00:02:42,770
Tātad mēs redzam, ka tad, kad mēs esam veiksmīgi
lasīt vārdu uz

54
00:02:42,770 --> 00:02:48,270
Ierakstu> vārds, tad mēs ejam, ka
vārdu, izmantojot mūsu hash funkciju.

55
00:02:48,270 --> 00:02:49,580
>> Pieņemsim to apskatīt
hash funkciju.

56
00:02:49,580 --> 00:02:52,430

57
00:02:52,430 --> 00:02:55,610
Tātad jums nav tiešām ir nepieciešams
saprast.

58
00:02:55,610 --> 00:02:59,460
Un faktiski mēs vienkārši velk šo hash
darboties no interneta.

59
00:02:59,460 --> 00:03:04,010
Vienīgais, kas jums ir nepieciešams atzīt,
ka tas aizņem const char * vārdu.

60
00:03:04,010 --> 00:03:08,960
Tātad, tas ir ņemot virkni kā ievade, un
atgriešanās neparakstītu int kā produkciju.

61
00:03:08,960 --> 00:03:12,360
Tātad tas viss hash funkciju, tas ir
uzņem ieejas un sniedz jums

62
00:03:12,360 --> 00:03:14,490
indeksu uz Hashtable.

63
00:03:14,490 --> 00:03:18,530
>> Ievērojiet, ka mēs esam moding ar NUM_BUCKETS,
lai atgrieztā vērtība

64
00:03:18,530 --> 00:03:21,730
patiesībā ir rādītājs uz Hashtable
un nav rādītājs pārsniedz

65
00:03:21,730 --> 00:03:24,320
robežas no masīva.

66
00:03:24,320 --> 00:03:28,060
Tāpēc, ka funkciju, mēs ejam
hash vārdu, ka mēs lasām

67
00:03:28,060 --> 00:03:29,390
vārdnīca.

68
00:03:29,390 --> 00:03:31,700
Un tad mēs ejam, lai izmantotu
ka hash ievietot

69
00:03:31,700 --> 00:03:33,750
iekļūšanu Hashtable.

70
00:03:33,750 --> 00:03:38,520
>> Tagad Hashtable hash ir pašreizējā
saistīts sarakstu tabulā.

71
00:03:38,520 --> 00:03:41,410
Un tas ir ļoti iespējams,
ka tas ir tikai NULL.

72
00:03:41,410 --> 00:03:44,960
Mēs vēlamies, lai ievietotu savu ienākšanu
sākumā šī saistīta saraksta.

73
00:03:44,960 --> 00:03:48,600
Un tā mēs ejam, lai ir mūsu pašreizējo
ieejas punkts, ko Hashtable

74
00:03:48,600 --> 00:03:50,380
Pašlaik norāda.

75
00:03:50,380 --> 00:03:53,310
Un tad mēs ejam uz veikalu,
in Hashtable pie

76
00:03:53,310 --> 00:03:55,350
hash, pašreizējais ieraksts.

77
00:03:55,350 --> 00:03:59,320
Tātad šīs divas līnijas veiksmīgi ievietot
ieraksts sākumā

78
00:03:59,320 --> 00:04:02,260
saistīts saraksts šajā indeksā
in Hashtable.

79
00:04:02,260 --> 00:04:04,900
>> Pēc tam, kad mēs esam darīts ar to, ka mēs zinām,
ka mēs atradām vēl vienu vārdu

80
00:04:04,900 --> 00:04:07,790
vārdnīcu, un mēs solis vēlreiz.

81
00:04:07,790 --> 00:04:13,960
Tāpēc mēs turpinām darām līdz fscanf
beidzot atgriezās kaut non-1 at

82
00:04:13,960 --> 00:04:16,950
Kurā brīdī jāatceras, ka
mums ir nepieciešams, lai atbrīvotu ierakstu.

83
00:04:16,950 --> 00:04:19,459
Tāpēc šeit mēs malloced ierakstu.

84
00:04:19,459 --> 00:04:21,329
Un mēs centāmies, lai lasītu kaut ko
no vārdnīcas.

85
00:04:21,329 --> 00:04:23,910
Un mēs neesam veiksmīgi nolasīt
kaut kas no vārdnīcas, kas

86
00:04:23,910 --> 00:04:26,650
tādā gadījumā mums ir nepieciešams, lai atbrīvotu ierakstu
ka mēs nekad faktiski laisti

87
00:04:26,650 --> 00:04:29,140
Hashtable, un beidzot pauze.

88
00:04:29,140 --> 00:04:32,750
>> Kad mēs izcelties mums ir nepieciešams, lai redzētu, labi,
mēs esam izcelties, jo tur

89
00:04:32,750 --> 00:04:34,360
bija kļūda lasot no lietas materiāliem?

90
00:04:34,360 --> 00:04:37,120
Vai mēs esam izcelties, jo mēs
sasnieguši faila?

91
00:04:37,120 --> 00:04:39,480
Ja tur bija kļūda, tad
mēs vēlamies atgriezties viltus.

92
00:04:39,480 --> 00:04:40,930
Jo slodze neizdevās.

93
00:04:40,930 --> 00:04:43,890
Un šajā procesā mēs vēlamies, lai izkrautu
visi vārdi, ka mēs lasām, un

94
00:04:43,890 --> 00:04:45,670
aizveriet vārdnīcas faila.

95
00:04:45,670 --> 00:04:48,740
>> Pieņemot, ka mums izdosies, tad mēs vienkārši
joprojām ir nepieciešams, lai aizvērtu vārdnīcu

96
00:04:48,740 --> 00:04:53,040
failu, un visbeidzot atgriezties taisnība, jo mēs
veiksmīgi ielādēta vārdnīca.

97
00:04:53,040 --> 00:04:54,420
Un tas ir tas, lai slodze.

98
00:04:54,420 --> 00:04:59,020
Tāpēc tagad pārbaudiet, ņemot piekrauts Hashtable,
gatavojas izskatās šādi.

99
00:04:59,020 --> 00:05:03,140
Lai pārbaudītu, tas atgriež bool, kas ir
gatavojas, lai norādītu, vai pagājis

100
00:05:03,140 --> 00:05:07,530
in char * vārdu, vai pagājis
virknē ir mūsu vārdnīcā.

101
00:05:07,530 --> 00:05:09,890
Tātad, ja tas ir norādīts vārdnīcā,
ja tas ir mūsu Hashtable,

102
00:05:09,890 --> 00:05:11,170
mēs atgriezīsimies taisnība.

103
00:05:11,170 --> 00:05:13,380
Un, ja tā nav, mēs atgriezīsimies nepatiesa.

104
00:05:13,380 --> 00:05:17,740
>> Ņemot vērā šo pieņemts vārdu, mēs esam
gatavojas hash vārdu.

105
00:05:17,740 --> 00:05:22,110
Tagad svarīga lieta atzīt,
ka slodze mēs zinājām, ka visi

106
00:05:22,110 --> 00:05:23,820
vārdus mēs gribam būt mazie burti.

107
00:05:23,820 --> 00:05:25,820
Bet šeit mēs esam tik pārliecināts.

108
00:05:25,820 --> 00:05:29,510
Ja mēs to apskatīt mūsu hash funkciju,
mūsu hash funkcija faktiski

109
00:05:29,510 --> 00:05:32,700
ir mazāks korpuss katra rakstzīme
vārda.

110
00:05:32,700 --> 00:05:37,940
Tāpēc neatkarīgi no kapitalizācijas
Vārds, mūsu hash funkcija ir atgriešanās

111
00:05:37,940 --> 00:05:42,270
pats indekss neatkarīgi
kapitalizācija, jo tas būtu

112
00:05:42,270 --> 00:05:45,280
atpakaļ uz pavisam mazie burti
versija vārda.

113
00:05:45,280 --> 00:05:46,600
Alright.

114
00:05:46,600 --> 00:05:49,790
Tas ir mūsu indekss ir spēkā
Hashtable par šo vārdu.

115
00:05:49,790 --> 00:05:52,940
>> Tagad šis cilpa gatavojas
atkārtot pa saistīts saraksts

116
00:05:52,940 --> 00:05:55,000
tas bija šajā indeksā.

117
00:05:55,000 --> 00:05:59,610
Tāpēc paziņojums mums ir inicializēta ierakstu
, lai norādītu uz minētā indeksa.

118
00:05:59,610 --> 00:06:02,750
Mēs ejam, lai turpinātu
bet ieraksts! = NULL.

119
00:06:02,750 --> 00:06:07,770
Un atcerieties, ka rādītāju atjaunināšana
mūsu saistīts saraksts ieraksts = ieraksts> nākamo.

120
00:06:07,770 --> 00:06:14,400
Tā ir mūsu pašreizējais piekļuves vietu
Nākamais punkts saistītajā sarakstā.

121
00:06:14,400 --> 00:06:19,250
>> Tātad uz katru ierakstu saistītajā sarakstā,
mēs ejam, lai izmantotu strcasecmp.

122
00:06:19,250 --> 00:06:20,330
Tas nav strcomp.

123
00:06:20,330 --> 00:06:23,780
Jo atkal, mēs vēlamies
darīt lietas gadījumā insensitively.

124
00:06:23,780 --> 00:06:27,870
Tāpēc mēs izmantojam strcasecmp, lai salīdzinātu
vārdu, kas tika pieņemts, izmantojot šo

125
00:06:27,870 --> 00:06:31,860
funkcija pret vārdu
, kas ir šā ieraksta.

126
00:06:31,860 --> 00:06:35,570
Ja tā atgriež nulli, tas nozīmē, ka tur bija
spēles, un tādā gadījumā mēs vēlamies

127
00:06:35,570 --> 00:06:36,630
atgriezties true.

128
00:06:36,630 --> 00:06:39,590
Mēs veiksmīgi atraduši
vārdu mūsu Hashtable.

129
00:06:39,590 --> 00:06:43,040
>> Ja nebija spēle, tad mēs esam
dodas uz cilpu atkal un apskatīt

130
00:06:43,040 --> 00:06:43,990
Nākamais ieraksts.

131
00:06:43,990 --> 00:06:47,640
Un mēs turpināsim looping, bet tur
Ir ieraksti šajā saistīta sarakstā.

132
00:06:47,640 --> 00:06:50,160
Kas notiek, ja mēs pārkāpjam
no šīs cilpa?

133
00:06:50,160 --> 00:06:55,110
Tas nozīmē, ka mēs neesam atrast ierakstu, kas
saskaņota šo vārdu, tādā gadījumā

134
00:06:55,110 --> 00:07:00,220
mēs atgriežamies viltus, lai norādītu, ka mūsu
Hashtable neietvēra šo vārdu.

135
00:07:00,220 --> 00:07:02,540
Un tas ir pārbaude.

136
00:07:02,540 --> 00:07:04,790
>> Tātad, pieņemsim to apskatīt lieluma.

137
00:07:04,790 --> 00:07:06,970
Tagad lielums būs diezgan vienkārši.

138
00:07:06,970 --> 00:07:11,080
Jo atceros, slodzes, katram vārdam
mēs noskaidrojām, mēs palielina globālās

139
00:07:11,080 --> 00:07:12,880
mainīgais Hashtable izmērs.

140
00:07:12,880 --> 00:07:16,480
Tā lielums funkcija ir tikai gatavojas
atgriezties globālo mainīgo.

141
00:07:16,480 --> 00:07:18,150
Un tas arī viss.

142
00:07:18,150 --> 00:07:22,300
>> Beidzot, mums ir nepieciešams, lai izkrautu
vārdnīca, kad viss ir izdarīts.

143
00:07:22,300 --> 00:07:25,340
Tātad, kā mēs gatavojamies darīt?

144
00:07:25,340 --> 00:07:30,440
Tieši šeit mēs esam looping vairāk
visi spaiņi mūsu galda.

145
00:07:30,440 --> 00:07:33,240
Tāpēc ir NUM_BUCKETS kausi.

146
00:07:33,240 --> 00:07:37,410
Un katram, kas saistīta saraksta mūsu
Hashtable, mēs ejam, lai cilpa vairāk

147
00:07:37,410 --> 00:07:41,070
veselums saistītā saraksta
atbrīvojot katru elementu.

148
00:07:41,070 --> 00:07:42,900
>> Tagad mums ir jābūt uzmanīgiem.

149
00:07:42,900 --> 00:07:47,910
Tātad, šeit mums ir pagaidu mainīgo
kas ir uzglabāšanas rādītāju uz nākamā

150
00:07:47,910 --> 00:07:49,730
elements saistītajā sarakstā.

151
00:07:49,730 --> 00:07:52,140
Un tad mēs ejam uz brīvu
pašreizējais elements.

152
00:07:52,140 --> 00:07:55,990
Mums ir nepieciešams, lai pārliecinātos, mēs to darām, jo ​​mēs
var ne tikai brīvi Pašlaik skatītās elements

153
00:07:55,990 --> 00:07:59,180
un tad mēģināt piekļūtu nākamajai rādītāju,
jo, kad mēs esam atbrīvojušies to,

154
00:07:59,180 --> 00:08:00,870
atmiņa ir nederīgs.

155
00:08:00,870 --> 00:08:04,990
>> Tāpēc mums ir nepieciešams, lai saglabātu apmēram rādītāju uz
nākamais elements, tad mēs varam brīvi

156
00:08:04,990 --> 00:08:08,360
strāvas elements, un pēc tam, mēs var atjaunināt
Mūsu pašreizējais elements, lai norādītu

157
00:08:08,360 --> 00:08:09,550
nākamais elements.

158
00:08:09,550 --> 00:08:12,800
Mēs cilpas, bet tur ir elementi
Šajā saistīts sarakstā.

159
00:08:12,800 --> 00:08:15,620
Mēs darīsim, ka visi ir saistīti
sarakstus Hashtable.

160
00:08:15,620 --> 00:08:19,460
Un, kad mēs esam darīts ar to, ka mēs esam
pilnībā izkrauta Hashtable, un

161
00:08:19,460 --> 00:08:20,190
mēs esam darījuši.

162
00:08:20,190 --> 00:08:23,200
Tātad, tas ir neiespējami, lai izkrautu
kādreiz atgriezties viltus.

163
00:08:23,200 --> 00:08:26,470
Un, kad mēs esam darīts, mēs
vienkārši atgriezties true.

164
00:08:26,470 --> 00:08:29,000
>> Pieņemsim sniegt šo risinājumu izmēģināt.

165
00:08:29,000 --> 00:08:33,070
Tātad, pieņemsim apskatīt to, kas mūsu
struktūrai mezgls izskatīsies.

166
00:08:33,070 --> 00:08:36,220
Šeit mēs redzam, mēs ejam, lai būtu bool
vārdu un struct mezglā * bērni

167
00:08:36,220 --> 00:08:37,470
kronšteins alfabētu.

168
00:08:37,470 --> 00:08:38,929

169
00:08:38,929 --> 00:08:42,020
Tātad pirmā lieta, jūs varētu būt
jautājums, kāpēc ir ALFABĒTS

170
00:08:42,020 --> 00:08:44,660
ed definēta kā 27?

171
00:08:44,660 --> 00:08:47,900
Nu, atcerieties, ka mēs ejam uz nepieciešamību
kas apstrādes apostrofu.

172
00:08:47,900 --> 00:08:51,910
Tā, ka būs nedaudz
Īpašs gadījums visā šajā programmā.

173
00:08:51,910 --> 00:08:54,710
>> Tagad atceros, kā trie
faktiski darbojas.

174
00:08:54,710 --> 00:08:59,380
Pieņemsim, ka mēs indeksāciju vārdu
"kaķi". Tad no saknes Trie,

175
00:08:59,380 --> 00:09:02,610
mēs ejam apskatīt bērniem
masīvs, un mēs ejam apskatīt

176
00:09:02,610 --> 00:09:08,090
indekss, kas atbilst vēstules
C. Tāpēc, ka tiks indeksētas 2.

177
00:09:08,090 --> 00:09:11,530
Tātad, ņemot vērā, ka tas būs
dod mums jaunu mezglu.

178
00:09:11,530 --> 00:09:13,820
Un tad mēs strādājam no šī mezgla.

179
00:09:13,820 --> 00:09:17,770
>> Tāpēc, ka mezglā, mēs atkal esam
skatīsies uz bērnu masīvs.

180
00:09:17,770 --> 00:09:22,110
Un mēs ejam apskatīt indeksu nulles
lai tā atbilstu A kaķu.

181
00:09:22,110 --> 00:09:27,170
Tātad, tad mēs ejam, lai dotos uz šo mezglu,
un ņemot vērā, ka mezgla mēs ejam

182
00:09:27,170 --> 00:09:31,090
apskatīt beigās tas ir atbilst
ar T. un pārvietojas uz šo mezglu,

183
00:09:31,090 --> 00:09:35,530
Visbeidzot, mēs esam pilnīgi izskatījās
caur mūsu vārdu "kaķis". Un tagad bool

184
00:09:35,530 --> 00:09:40,960
Vārds ir paredzēts, lai norādītu, vai
tas dots vārds ir faktiski vārdu.

185
00:09:40,960 --> 00:09:43,470
>> Tātad, kāpēc mums ir nepieciešams, ka īpaša gadījumā?

186
00:09:43,470 --> 00:09:47,700
Nu ko par vārdu "katastrofa"
ir mūsu vārdnīcā, bet

187
00:09:47,700 --> 00:09:50,150
vārdu "kaķis" ir ne?

188
00:09:50,150 --> 00:09:54,580
Tik un vēlas redzēt, ja vārds "kaķis"
ir mūsu vārdnīcā, mēs esam

189
00:09:54,580 --> 00:09:59,970
būs veiksmīgi izskatīt
indeksi C-T reģionā mezglā.

190
00:09:59,970 --> 00:10:04,290
Bet tas ir tikai tāpēc, ka katastrofa
noticis, lai radītu mezglu ceļā

191
00:10:04,290 --> 00:10:07,190
no C-A-T, visu veidu
vārda beigām.

192
00:10:07,190 --> 00:10:12,020
Tāpēc bool vārds tiek izmantots, lai norādītu, vai
šo konkrēto atrašanās vietu

193
00:10:12,020 --> 00:10:14,310
faktiski norāda vārdu.

194
00:10:14,310 --> 00:10:15,140
>> Labi.

195
00:10:15,140 --> 00:10:19,310
Tāpēc tagad, ka mēs zinām, kas tas trie ir
gatavojas izskatās, aplūkosim

196
00:10:19,310 --> 00:10:20,730
slodze funkciju.

197
00:10:20,730 --> 00:10:24,610
Tāpēc slodze gatavojas atgriezties bool
par to, vai mēs veiksmīgi vai

198
00:10:24,610 --> 00:10:26,720
nesekmīgi ielādes vārdnīca.

199
00:10:26,720 --> 00:10:30,460
Un tas būs vārdnīca
ka mēs gribam, lai slodze.

200
00:10:30,460 --> 00:10:33,930
>> Tātad pirmā lieta, ko mēs darīt, ir atvērts
līdz šim vārdnīcā lasījumā.

201
00:10:33,930 --> 00:10:36,160
Un mums ir jāpārliecinās,
mēs neesam neizdoties.

202
00:10:36,160 --> 00:10:39,580
Tātad, ja vārdnīcā nav
veiksmīgi atvērts, tas atgriezīsies

203
00:10:39,580 --> 00:10:42,400
null, tādā gadījumā mēs esam
gatavojas atgriezties viltus.

204
00:10:42,400 --> 00:10:47,230
Bet, pieņemot, ka tā veiksmīgi
atvērts, tad mēs faktiski var izlasīt

205
00:10:47,230 --> 00:10:48,220
izmantojot vārdnīcu.

206
00:10:48,220 --> 00:10:50,880
>> Tātad pirmā lieta, ko mēs gatavojamies
vēlaties darīt, ir, mums ir šis

207
00:10:50,880 --> 00:10:52,500
globālo mainīgo saknes.

208
00:10:52,500 --> 00:10:56,190
Tagad sakne būs mezglā *.

209
00:10:56,190 --> 00:10:59,760
Tā ir top mūsu Trie, ka mēs esam
būs atkārtojot cauri.

210
00:10:59,760 --> 00:11:02,660
Tātad pirmā lieta, ka mēs ejam
vēlaties darīt, ir piešķirt

211
00:11:02,660 --> 00:11:04,140
atmiņā mūsu saknes.

212
00:11:04,140 --> 00:11:07,980
Ievērojiet, ka mēs esam, izmantojot calloc
funkcija, kas būtībā ir tas pats

213
00:11:07,980 --> 00:11:11,500
jo malloc funkciju, izņemot tā
garantēta, lai atgrieztos kaut ko, kas ir

214
00:11:11,500 --> 00:11:13,180
pilnīgi nulli out.

215
00:11:13,180 --> 00:11:17,290
Tātad, ja mēs izmantojām malloc, mums būtu nepieciešams, lai
iet cauri visiem norādes mūsu

216
00:11:17,290 --> 00:11:20,160
mezglā, un pārliecinieties, ka
viņi visi null.

217
00:11:20,160 --> 00:11:22,710
Tāpēc calloc būs darīt, ka mums.

218
00:11:22,710 --> 00:11:26,330
>> Tagad, tāpat kā malloc, mums ir nepieciešams veikt
pārliecināts, ka piešķīrums bija faktiski

219
00:11:26,330 --> 00:11:27,520
veiksmīga.

220
00:11:27,520 --> 00:11:29,990
Ja tas atgriezās null, tad mēs
nepieciešams slēgt vai vārdnīca

221
00:11:29,990 --> 00:11:32,100
failu un atgriezties viltus.

222
00:11:32,100 --> 00:11:36,835
Tātad, pieņemot, ka sadalei ir
veiksmīga, mēs ejam, lai izmantotu mezglu *

223
00:11:36,835 --> 00:11:40,270
kursoru atkārtot, izmantojot mūsu Trie.

224
00:11:40,270 --> 00:11:43,890
Tāpēc mūsu saknes nekad mainīsies,
bet mēs esam gatavojas izmantot kursoru

225
00:11:43,890 --> 00:11:47,875
tiešām iet no mezgla uz mezglu.

226
00:11:47,875 --> 00:11:50,940
>> Tātad šis cilpa mēs lasām
ar vārdnīcas faila.

227
00:11:50,940 --> 00:11:53,670
Un mēs esam izmantojot fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc gatavojas sagrābt vienotu
rakstzīmi no lietas materiāliem.

229
00:11:56,290 --> 00:11:59,370
Mēs turpināsim satveršanas
rakstzīmes, kamēr mēs nenonāk

230
00:11:59,370 --> 00:12:01,570
faila beigas.

231
00:12:01,570 --> 00:12:03,480
>> Ir divi gadījumi, mums ir nepieciešams rīkoties.

232
00:12:03,480 --> 00:12:06,610
Pirmais, ja raksturs
nebija jauna līnija.

233
00:12:06,610 --> 00:12:10,450
Tātad mēs zinām, ja tas bija jaunu līniju, tad
mēs esam par to, lai pārietu uz jaunu vārdu.

234
00:12:10,450 --> 00:12:15,240
Bet pieņemot, ka tas nebija jaunu līniju, tad
šeit mēs gribam, lai noskaidrotu

235
00:12:15,240 --> 00:12:18,380
indekss mēs ejam indeksēt
ar bērnu masīvā, ka

236
00:12:18,380 --> 00:12:19,810
mēs paskatījās agrāk.

237
00:12:19,810 --> 00:12:23,880
>> Tātad, kā es teicu iepriekš, mums ir nepieciešams
Īpašs gadījums Apostrofs.

238
00:12:23,880 --> 00:12:26,220
Ievērojiet, mēs izmantot trīskāršo
operators šeit.

239
00:12:26,220 --> 00:12:29,580
Tāpēc mēs esam gatavojas lasīt to kā, ja
rakstura lasām bija

240
00:12:29,580 --> 00:12:35,330
Apostrofs, tad mēs ejam, lai uzstādītu
indekss = "ALFABĒTS" -1, kas būs

241
00:12:35,330 --> 00:12:37,680
būt indekss 26.

242
00:12:37,680 --> 00:12:41,130
>> Cits, ja tas nav Apostrofs, tur
Mēs ejam, lai uzstādītu indeksu

243
00:12:41,130 --> 00:12:43,760
vienāds ar c -.

244
00:12:43,760 --> 00:12:49,030
Līdz ar to atcerēties atpakaļ ar iepriekš p komplektu,
c - gatavojas sniegt mums

245
00:12:49,030 --> 00:12:53,410
alfabēta pozīcija C. Tātad, ja
C ir burts, tas

246
00:12:53,410 --> 00:12:54,700
dod mums indekss nulle.

247
00:12:54,700 --> 00:12:58,120
Par vēstules B, tas dos
mums indekss 1, un tā tālāk.

248
00:12:58,120 --> 00:13:03,010
>> Tāpēc tas dod mums indekss spēkā
bērni, masīvs, ko mēs gribam.

249
00:13:03,010 --> 00:13:08,890
Tagad, ja šis rādītājs pašlaik Null
bērni, tas nozīmē, ka mezgls

250
00:13:08,890 --> 00:13:11,830
Pašlaik nav
no šī ceļa.

251
00:13:11,830 --> 00:13:15,160
Tāpēc mums ir nepieciešams piešķirt
mezglu, lai šajā ceļā.

252
00:13:15,160 --> 00:13:16,550
Tas ir tas, ko mēs darīsim šeit.

253
00:13:16,550 --> 00:13:20,690
>> Tāpēc mēs esam gatavojas atkal izmantot calloc
funkcija, tāpēc, ka mums nav

254
00:13:20,690 --> 00:13:22,880
nulle visas norādes.

255
00:13:22,880 --> 00:13:27,240
Un mums atkal nepieciešams, lai pārbaudītu
ka calloc nav neizdoties.

256
00:13:27,240 --> 00:13:30,700
Ja calloc tomēr neizdodas, tad mums
izkraut viss, aizvērt

257
00:13:30,700 --> 00:13:32,820
vārdnīcu, un atgriezties viltus.

258
00:13:32,820 --> 00:13:40,050
Tātad, pieņemot, ka tas nav neizdoties, tad
Tas radīs jaunu bērnu mums.

259
00:13:40,050 --> 00:13:41,930
Un tad mēs dosimies uz šo bērnu.

260
00:13:41,930 --> 00:13:44,960
Mūsu kursors atkārtot
uz leju, lai šo bērnu.

261
00:13:44,960 --> 00:13:49,330
>> Tagad, ja tas nav null, lai sāktu ar,
tad kursors var tikai atkārtot

262
00:13:49,330 --> 00:13:52,590
uz leju, lai šo bērnu, bet faktiski
kam piešķirt neko.

263
00:13:52,590 --> 00:13:56,730
Šis ir gadījums, kad mēs pirmo reizi notika
piešķirt vārdu "kaķis". Un

264
00:13:56,730 --> 00:14:00,330
tas nozīmē, ka tad, kad mēs ejam, lai sadalītu
"Katastrofa", mums nav nepieciešams, lai izveidotu

265
00:14:00,330 --> 00:14:01,680
mezglu C-A-T vēlreiz.

266
00:14:01,680 --> 00:14:04,830
Viņi jau pastāv.

267
00:14:04,830 --> 00:14:06,080
>> Kas ir šis cits?

268
00:14:06,080 --> 00:14:10,480
Tas ir stāvoklis, kurā c ir
slīpsvītru n, kur c ir jauna līnija.

269
00:14:10,480 --> 00:14:13,710
Tas nozīmē, ka ir veiksmīgi
pabeidzis vārdu.

270
00:14:13,710 --> 00:14:16,860
Tagad tas, ko mēs vēlamies darīt, kad mēs
sekmīgi pabeigta vārdu?

271
00:14:16,860 --> 00:14:21,100
Mēs ejam, lai izmantotu šo vārdu lauku
iekšpusē mūsu struct mezglā.

272
00:14:21,100 --> 00:14:23,390
Mēs gribam, lai noteiktu, kas ir taisnība.

273
00:14:23,390 --> 00:14:27,150
Tā, kas norāda, ka šis mezgls
norāda veiksmīgs

274
00:14:27,150 --> 00:14:29,250
vārdu, faktisko vārdu.

275
00:14:29,250 --> 00:14:30,940
>> Tagad ir noteikts, ka, lai taisnība.

276
00:14:30,940 --> 00:14:35,150
Mēs vēlamies, lai atjaunotu savu kursoru uz punktu
līdz sākumā Trie atkal.

277
00:14:35,150 --> 00:14:40,160
Un visbeidzot, solis mūsu vārdnīca
izmērs, jo mēs atradām citu darbu.

278
00:14:40,160 --> 00:14:43,230
Tātad, mēs ejam, lai saglabātu darot, ka,
lasījumā raksturu, raksturs,

279
00:14:43,230 --> 00:14:49,150
būvējot jaunas mezglu mūsu Trie un
par katru vārdu vārdnīcā, līdz

280
00:14:49,150 --> 00:14:54,020
mēs beidzot sasniedz C! = EOF, kurā
gadījumā mēs izkļūt no faila.

281
00:14:54,020 --> 00:14:57,050
>> Tagad ir divas lietas, ko
kas mēs varētu būt hit EOF.

282
00:14:57,050 --> 00:15:00,980
Pirmais ir, ja tur bija kļūda
lasot no lietas materiāliem.

283
00:15:00,980 --> 00:15:03,470
Tātad, ja tur bija kļūda, mēs
jādara tipisks.

284
00:15:03,470 --> 00:15:06,460
Izkraut viss, close
failu, atgriezties viltus.

285
00:15:06,460 --> 00:15:09,810
Pieņemot, ka tur nebija kļūda, ka
tikai nozīmē, ka mēs faktiski hit beigām

286
00:15:09,810 --> 00:15:13,750
failu, un tādā gadījumā, mēs cieši
failu un atgriezties taisnība, jo mēs

287
00:15:13,750 --> 00:15:17,330
veiksmīgi ielādēta vārdnīca
mūsu Trie.

288
00:15:17,330 --> 00:15:20,170
>> Tāpēc tagad pieņemsim izbraukšana pārbaudi.

289
00:15:20,170 --> 00:15:25,156
Raugoties uz pārbaudes funkciju, mēs redzam,
ka pārbaude ir gatavojas atgriezties bool.

290
00:15:25,156 --> 00:15:29,680
Tā atgriež true, ja šis vārds, ka tas ir
tiek pieņemts, tur ir mūsu Trie.

291
00:15:29,680 --> 00:15:32,110
Tā atgriež false citādi.

292
00:15:32,110 --> 00:15:36,050
Tātad, kā jūs noteikt, vai
šis vārds ir mūsu Trie?

293
00:15:36,050 --> 00:15:40,190
>> Mēs redzam šeit, ka, tāpat kā iepriekš,
mēs gatavojamies izmantot kursoru atkārtot

294
00:15:40,190 --> 00:15:41,970
caur mūsu Trie.

295
00:15:41,970 --> 00:15:46,600
Tagad šeit mēs gatavojamies atkārtot
pār mūsu visu vārdu.

296
00:15:46,600 --> 00:15:50,620
Tātad, atkārtojot visā vārdu mēs pagātnē,
Mēs ejam, lai noteiktu

297
00:15:50,620 --> 00:15:56,400
indeksu uz bērnu masīvu, kas
atbilst vārdu stiprinājuma I. Tātad šis

298
00:15:56,400 --> 00:15:59,670
gatavojas izskatās tieši tāpat kā
slodze, kur, ja vārds [i]

299
00:15:59,670 --> 00:16:03,310
ir Apostrofs, tad mēs gribam
izmantot indeksa "Alfabēts" - 1.

300
00:16:03,310 --> 00:16:05,350
Jo tika konstatēts, ka tas
ir vieta, kur mēs ejam, lai saglabātu

301
00:16:05,350 --> 00:16:07,100
apostrofi.

302
00:16:07,100 --> 00:16:11,780
>> Vēl mēs spēsim izmantot divas zemāku vārdu
kronšteins I. Līdz ar to atcerēties, ka vārds var

303
00:16:11,780 --> 00:16:13,920
ir patvaļīgu kapitalizāciju.

304
00:16:13,920 --> 00:16:17,540
Un tāpēc mēs vēlamies, lai pārliecinātos, ka mēs esam
izmantojot mazo burtu versiju lietām.

305
00:16:17,540 --> 00:16:21,920
Un tad atņemt no tā "", lai pēc tam, kad
atkal dod mums alfabētiskā

306
00:16:21,920 --> 00:16:23,880
nostāja šajā raksturs.

307
00:16:23,880 --> 00:16:27,680
Tā, ka būs mūsu indeksu
uz bērnu masīvs.

308
00:16:27,680 --> 00:16:32,420
>> Un tagad, ja tas indekss par bērniem
masīvs ir nulle, tas nozīmē, ka mēs

309
00:16:32,420 --> 00:16:34,990
vairs nevar turpināt, atkārtojot
leju mūsu Trie.

310
00:16:34,990 --> 00:16:38,870
Ja tas ir gadījumā, šis vārds nevar
iespējams, varētu būt mūsu Trie.

311
00:16:38,870 --> 00:16:42,340
Jo, ja tas tā būtu, tas būtu
nozīmē, ka varētu būt ceļš

312
00:16:42,340 --> 00:16:43,510
uz leju, lai šo vārdu.

313
00:16:43,510 --> 00:16:45,290
Un jūs nekad sastapties null.

314
00:16:45,290 --> 00:16:47,850
Tātad sastopas Null, mēs atgriežamies nepatiesa.

315
00:16:47,850 --> 00:16:49,840
Vārda nav vārdnīcā.

316
00:16:49,840 --> 00:16:53,660
Ja tas nav null, tad mēs esam
turpinās atkārtojot.

317
00:16:53,660 --> 00:16:57,220
>> Tātad, mēs ejam ārā tur kursoru
norādīt to, ka īpaši

318
00:16:57,220 --> 00:16:59,760
mezglā šajā indeksā.

319
00:16:59,760 --> 00:17:03,150
Mēs turpinām darām visu
visu vārdu, pieņemot

320
00:17:03,150 --> 00:17:03,950
mēs nekad hit null.

321
00:17:03,950 --> 00:17:07,220
Tas nozīmē, ka mēs varējām dabūt cauri
visu vārdu un atrast

322
00:17:07,220 --> 00:17:08,920
mezglu mūsu mēģināt.

323
00:17:08,920 --> 00:17:10,770
Bet mēs esam ne gluži izdarīts vēl.

324
00:17:10,770 --> 00:17:12,290
>> Mēs nevēlamies, lai tikai atgrieztos taisnība.

325
00:17:12,290 --> 00:17:14,770
Mēs vēlamies, lai atgrieztos kursora> vārdu.

326
00:17:14,770 --> 00:17:18,980
Jo atceros atkal ir "kaķis" nav
mūsu vārdnīcā, un "katastrofa"

327
00:17:18,980 --> 00:17:22,935
ir, tad mēs veiksmīgi mēs saņemam
ar vārdu "kaķis". Bet kursors

328
00:17:22,935 --> 00:17:25,760
vārds būs nepatiess un nav taisnība.

329
00:17:25,760 --> 00:17:30,930
Tāpēc mēs atgriežamies kursora vārdu, lai norādītu
vai šis mezgls ir patiesībā vārds.

330
00:17:30,930 --> 00:17:32,470
Un tas ir tas, lai pārbaudi.

331
00:17:32,470 --> 00:17:34,250
>> Tāpēc pieņemsim izbraukšana izmēru.

332
00:17:34,250 --> 00:17:37,350
Tā lielums būs diezgan viegli
jo atceros, slodzes, mēs esam

333
00:17:37,350 --> 00:17:41,430
palielināšanai vārdnīca izmēru
katrs vārds, ko mēs saskaramies.

334
00:17:41,430 --> 00:17:45,350
Tā lielums ir tikai gatavojas
atgriezties vārdnīca izmēru.

335
00:17:45,350 --> 00:17:47,390
Un tas arī viss.

336
00:17:47,390 --> 00:17:50,590
>> Tātad visbeidzot mēs esam izkraut.

337
00:17:50,590 --> 00:17:55,100
Tātad izkraut, mēs ejam, lai izmantotu
rekursīvas funkcijas, lai faktiski darīt visu

338
00:17:55,100 --> 00:17:56,530
darbu mums.

339
00:17:56,530 --> 00:17:59,340
Tāpēc mūsu uzdevums būs
saukt par unloader.

340
00:17:59,340 --> 00:18:01,650
Kas ir izlādēšanas gatavojas darīt?

341
00:18:01,650 --> 00:18:06,580
Mēs redzam šeit, ka izlādēšanas gatavojas
atkārtot pār visiem bērniem

342
00:18:06,580 --> 00:18:08,410
Tas īpaši mezglā.

343
00:18:08,410 --> 00:18:11,750
Un, ja bērns mezgls nav
null, tad mēs ejam uz

344
00:18:11,750 --> 00:18:13,730
izkraut bērnu mezglu.

345
00:18:13,730 --> 00:18:18,010
>> Tāpēc tas ir jums rekursīvi izkrauj
visiem mūsu bērniem.

346
00:18:18,010 --> 00:18:21,080
Pēc tam, kad mēs esam pārliecināti, ka visi mūsu bērni
ir izkrautas, tad mēs

347
00:18:21,080 --> 00:18:25,210
var atbrīvot sevi, tāpēc
izkraut sevi.

348
00:18:25,210 --> 00:18:29,460
Tas darbosies rekursīvi
izkraut visu Trie.

349
00:18:29,460 --> 00:18:32,850
Un tad, kad tas ir izdarīts,
mēs varam vienkārši atgriezties taisnība.

350
00:18:32,850 --> 00:18:34,210
Izkraut nevar neizdoties.

351
00:18:34,210 --> 00:18:35,710
Mēs esam tikai atbrīvojot lietas.

352
00:18:35,710 --> 00:18:38,870
Tātad, kad mēs esam darījuši atbrīvojot
viss, atgriezties true.

353
00:18:38,870 --> 00:18:40,320
Un tas arī viss.

354
00:18:40,320 --> 00:18:41,080
Mans vārds ir Rob.

355
00:18:41,080 --> 00:18:42,426
Un tas bija Pareizrakstības.

356
00:18:42,426 --> 00:18:47,830
>> [Mūzikas atskaņošanai]