1
00:00:00,000 --> 00:00:12,350
>> [MUSIC SPIEL]

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

3
00:00:13,050 --> 00:00:13,640
Ich bin Rob.

4
00:00:13,640 --> 00:00:16,210
Und lassen Sie uns diese Lösung aus.

5
00:00:16,210 --> 00:00:20,070
Also hier werden wir umsetzen
eine allgemeine Tabelle.

6
00:00:20,070 --> 00:00:24,090
Wir sehen, dass die Struktur der Knoten
Tabelle wird wie folgt aussehen.

7
00:00:24,090 --> 00:00:28,710
Also es geht um einen char Wort haben
Array der Größe LÄNGE + 1.

8
00:00:28,710 --> 00:00:32,259
Vergessen Sie nicht die + 1, da die maximale
Wort in dem Wörterbuch 45

9
00:00:32,259 --> 00:00:33,130
Zeichen.

10
00:00:33,130 --> 00:00:37,070
Und dann werden wir brauchen, eine zusätzliche
Zeichen für den umgekehrten Schrägstrich Null.

11
00:00:37,070 --> 00:00:40,870
>> Und dann unsere Hash-Tabelle in jeder
Eimer wird zu speichern, eine

12
00:00:40,870 --> 00:00:42,320
verkettete Liste von Knoten.

13
00:00:42,320 --> 00:00:44,420
Wir sind nicht hier, lineare Sondieren tun.

14
00:00:44,420 --> 00:00:48,430
Und so, um auf die nächste verlinken
Element in den Eimer, brauchen wir eine

15
00:00:48,430 --> 00:00:50,390
struct node * next.

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

17
00:00:51,110 --> 00:00:53,090
Also das ist, was ein Knoten aussieht.

18
00:00:53,090 --> 00:00:56,180
>> Nun, hier ist die Erklärung
der Hash-Tabelle.

19
00:00:56,180 --> 00:00:59,640
Es geht um 16.834 Schaufeln haben.

20
00:00:59,640 --> 00:01:01,910
Aber diese Zahl ist nicht wirklich wichtig.

21
00:01:01,910 --> 00:01:05,450
Und schließlich werden wir haben die
globale Variable Hash-Tabelle Größe, die

22
00:01:05,450 --> 00:01:07,000
wird zu starten als Null.

23
00:01:07,000 --> 00:01:10,760
Und es wird zu verfolgen, wie halten
viele Wörter sind im Wörterbuch.

24
00:01:10,760 --> 00:01:13,710
>> Werfen wir also einen Blick auf Last.

25
00:01:13,710 --> 00:01:16,390
Beachten Sie, dass Last, gibt sie eine bool.

26
00:01:16,390 --> 00:01:20,530
Sie kehren dann, wenn es erfolgreich war
geladen ist, und ansonsten false.

27
00:01:20,530 --> 00:01:23,990
Und es ein char * nimmt Wörterbuch,
welches das Wörterbuch

28
00:01:23,990 --> 00:01:25,280
dass wir wollen, sich zu öffnen.

29
00:01:25,280 --> 00:01:27,170
Also das ist das erste, was
wir tun werden.

30
00:01:27,170 --> 00:01:29,500
>> Wir werden die fopen
Wörterbuch zum Lesen.

31
00:01:29,500 --> 00:01:31,680
Und wir gehen zu müssen, um
sicher, dass es gelungen.

32
00:01:31,680 --> 00:01:35,920
Also, wenn es NULL zurückgegeben, dann haben wir nicht
erfolgreich das Wörterbuch zu öffnen.

33
00:01:35,920 --> 00:01:37,440
Und wir müssen return false.

34
00:01:37,440 --> 00:01:41,580
Aber unter der Annahme, dass es erfolgreich war
offen ist, dann lesen wollen wir die

35
00:01:41,580 --> 00:01:42,400
Wörterbuch.

36
00:01:42,400 --> 00:01:46,450
So halten Looping, bis wir einige
Grund, um aus dieser Schleife zu brechen,

37
00:01:46,450 --> 00:01:47,570
was wir sehen.

38
00:01:47,570 --> 00:01:48,920
So halten Looping.

39
00:01:48,920 --> 00:01:51,780
>> Und jetzt sind wir zu gehen
malloc eines einzelnen Knotens.

40
00:01:51,780 --> 00:01:54,020
Und natürlich brauchen wir
an der Luft noch einmal überprüfen.

41
00:01:54,020 --> 00:01:58,680
Also, wenn mallocing nicht gelingt, dann
wir einen beliebigen Knoten, die wir entladen möchten

42
00:01:58,680 --> 00:02:02,590
passiert malloc vor, schließen Sie die
Wörterbuch-und Rück falsch.

43
00:02:02,590 --> 00:02:06,830
Aber ignorieren, dass, vorausgesetzt, wir
gelang es, dann wollen wir nutzen fscanf

44
00:02:06,830 --> 00:02:12,400
ein einziges Wort aus lesen Sie unsere
Lexikon in unsere Knoten.

45
00:02:12,400 --> 00:02:17,940
Also denken Sie daran, dass der Eintritt> Wort ist der char
Wort Puffer der Größe LAENGE + 1

46
00:02:17,940 --> 00:02:20,300
dass wir gehen, um das Wort zu speichern in.

47
00:02:20,300 --> 00:02:25,070
>> So fscanf wird zu 1 zurück, so lange,
da es in der Lage, erfolgreich

48
00:02:25,070 --> 00:02:26,750
lesen Sie ein Wort aus der Datei.

49
00:02:26,750 --> 00:02:30,460
Wenn entweder ein Fehler passiert, oder wir
erreichen das Ende der Datei, es

50
00:02:30,460 --> 00:02:31,950
1 wird nicht zurückkehren.

51
00:02:31,950 --> 00:02:35,180
In diesem Fall ist es nicht wieder ein,
wir endlich zu durchbrechen

52
00:02:35,180 --> 00:02:37,280
Diese while-Schleife.

53
00:02:37,280 --> 00:02:42,770
So sehen wir, dass, wenn wir erfolgreich haben
lesen Sie ein Wort in

54
00:02:42,770 --> 00:02:48,270
entry> Wort, dann sind wir zu, dass geht
Wort über unser Hash-Funktion.

55
00:02:48,270 --> 00:02:49,580
>> Werfen wir einen Blick auf
die Hash-Funktion.

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

57
00:02:52,430 --> 00:02:55,610
So können Sie nicht wirklich brauchen
um das zu verstehen.

58
00:02:55,610 --> 00:02:59,460
Und eigentlich haben wir nur diesen Hash gezogen
Funktion aus dem Internet.

59
00:02:59,460 --> 00:03:04,010
Das einzige, was Sie brauchen, um zu erkennen, ist
dass das dauert ein char * Wort.

60
00:03:04,010 --> 00:03:08,960
So ist es sie einen String als Eingabe und
Rückgabe eines unsigned int als Ausgabe.

61
00:03:08,960 --> 00:03:12,360
Also das ist alles eine Hash-Funktion, ist es
nimmt in einem Eingang und gibt Ihnen ein

62
00:03:12,360 --> 00:03:14,490
Index in die Hash-Tabelle.

63
00:03:14,490 --> 00:03:18,530
>> Beachten Sie, dass wir durch num_buckets Moding,
so dass Wert zurückgegeben

64
00:03:18,530 --> 00:03:21,730
tatsächlich ist ein Index in die Hash-Tabelle
und nicht über die Index

65
00:03:21,730 --> 00:03:24,320
Grenzen des Arrays.

66
00:03:24,320 --> 00:03:28,060
Also da Funktion, wir gehen
das Wort, das wir lesen die Hash

67
00:03:28,060 --> 00:03:29,390
Wörterbuch.

68
00:03:29,390 --> 00:03:31,700
Und dann werden wir nutzen
dass die Hash einfügen

69
00:03:31,700 --> 00:03:33,750
Eintritt in die Hash-Tabelle.

70
00:03:33,750 --> 00:03:38,520
>> Jetzt Hash Hash-Tabelle ist der aktuelle
in der Tabelle verketteten Liste.

71
00:03:38,520 --> 00:03:41,410
Und es ist sehr gut möglich,
dass es nur NULL.

72
00:03:41,410 --> 00:03:44,960
Wir wollen unseren Eintrag bei der einfügen
Anfang dieses verketteten Liste.

73
00:03:44,960 --> 00:03:48,600
Und so werden wir unsere aktuellen haben
Einstiegspunkt, was der Hash-Tabelle

74
00:03:48,600 --> 00:03:50,380
derzeit zeigt.

75
00:03:50,380 --> 00:03:53,310
Und dann werden wir zu speichern,
in der Hash-Tabelle an die

76
00:03:53,310 --> 00:03:55,350
Hash, der aktuelle Eintrag.

77
00:03:55,350 --> 00:03:59,320
Also diese beiden Linien erfolgreich einfügen
der Eintrag am Anfang der

78
00:03:59,320 --> 00:04:02,260
verketteten Liste an diesem Index
in der Hash-Tabelle.

79
00:04:02,260 --> 00:04:04,900
>> Sobald wir damit fertig sind, wissen wir,
dass wir fanden ein anderes Wort in der

80
00:04:04,900 --> 00:04:07,790
Wörterbuch, und wir wieder zu erhöhen.

81
00:04:07,790 --> 00:04:13,960
So halten wir tun, bis fscanf
endlich wieder etwas Nicht-1 bei

82
00:04:13,960 --> 00:04:16,950
die Stelle daran erinnern, dass
wir brauchen, um Eintrag zu befreien.

83
00:04:16,950 --> 00:04:19,459
Also hier haben wir malloced einen Eintrag.

84
00:04:19,459 --> 00:04:21,329
Und wir haben versucht, etwas zu lesen
aus dem Wörterbuch.

85
00:04:21,329 --> 00:04:23,910
Und haben wir nicht erfolgreich gelesen
etwas aus dem Wörterbuch, in

86
00:04:23,910 --> 00:04:26,650
welcher Fall müssen wir den freien Eintritt
dass wir nie wirklich in die setzen

87
00:04:26,650 --> 00:04:29,140
Hash-Tabelle, und schließlich brechen.

88
00:04:29,140 --> 00:04:32,750
>> Sobald wir ausbrechen müssen wir sehen, na ja,
haben wir ausbrechen, weil es

89
00:04:32,750 --> 00:04:34,360
wurde ein Fehler beim Lesen aus der Datei?

90
00:04:34,360 --> 00:04:37,120
Oder haben wir brechen, weil wir
erreicht das Ende der Datei?

91
00:04:37,120 --> 00:04:39,480
Wenn es ein Fehler ist, dann
wir wollen return false.

92
00:04:39,480 --> 00:04:40,930
Weil Last nicht gelungen.

93
00:04:40,930 --> 00:04:43,890
Und in dem Prozess, den wir entladen möchten
alle Worte, die wir lesen in und

94
00:04:43,890 --> 00:04:45,670
schließen Sie die Wörterbuchdatei.

95
00:04:45,670 --> 00:04:48,740
>> Angenommen, wir haben, gelingt es uns nur
noch brauchen, um das Wörterbuch zu schließen

96
00:04:48,740 --> 00:04:53,040
Datei, und endlich wieder wahr, da wir
erfolgreich geladen das Wörterbuch.

97
00:04:53,040 --> 00:04:54,420
Und das ist es für die Last.

98
00:04:54,420 --> 00:04:59,020
So, jetzt zu prüfen, da eine geladene Hash-Tabelle,
wird wie folgt aussehen.

99
00:04:59,020 --> 00:05:03,140
So überprüfen Sie, es gibt einen bool, das ist,
gehen, um anzuzeigen, ob das übergebene

100
00:05:03,140 --> 00:05:07,530
char * in Wort, ob das übergebene
in String im Wörterbuch.

101
00:05:07,530 --> 00:05:09,890
So dass, wenn es in dem Wörterbuch ist,
wenn es in unserer Hash-Tabelle,

102
00:05:09,890 --> 00:05:11,170
wir true zurück.

103
00:05:11,170 --> 00:05:13,380
Und wenn es nicht, werden wir false zurück.

104
00:05:13,380 --> 00:05:17,740
>> Angesichts dieser in Wort übergeben, wir sind
gehen, um das Wort Hash.

105
00:05:17,740 --> 00:05:22,110
Jetzt eine wichtige Sache zu erkennen ist
dass in Last wir wussten, dass alle der

106
00:05:22,110 --> 00:05:23,820
Worten, wir werden klein geschrieben werden.

107
00:05:23,820 --> 00:05:25,820
Aber hier sind wir nicht so sicher.

108
00:05:25,820 --> 00:05:29,510
Wenn wir einen Blick auf unsere Hash-Funktion,
unsere Hash-Funktion tatsächlich

109
00:05:29,510 --> 00:05:32,700
untere Gehäuse ist jedes Zeichen
des Wortes.

110
00:05:32,700 --> 00:05:37,940
Also unabhängig von der Aktivierung von
Wort, ist unser Hash-Funktion der Rück

111
00:05:37,940 --> 00:05:42,270
der gleiche Index für was auch immer der
Kapitalisierung ist, wie es sein würde,

112
00:05:42,270 --> 00:05:45,280
für eine komplett in Kleinbuchstaben zurück
Version des Wortes.

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

114
00:05:46,600 --> 00:05:49,790
Das ist unser Index ist in der
Hash-Tabelle für dieses Wort.

115
00:05:49,790 --> 00:05:52,940
>> Nun ist diese for-Schleife wird zu
laufen der verketteten Liste

116
00:05:52,940 --> 00:05:55,000
das war an diesem Index.

117
00:05:55,000 --> 00:05:59,610
So bemerken wir Initialisierung Eintrag
zu diesem Index zu verweisen.

118
00:05:59,610 --> 00:06:02,750
Wir werden weiterhin
während Eintrag! = NULL.

119
00:06:02,750 --> 00:06:07,770
Und denken Sie daran, dass die Aktualisierung der Zeiger
in unserem verketteten Liste entry = Eintrag> weiter.

120
00:06:07,770 --> 00:06:14,400
So haben unsere aktuellen Einstiegspunkt
das nächste Element in der verketteten Liste.

121
00:06:14,400 --> 00:06:19,250
>> So dass für jeden Eintrag in der verketteten Liste,
wir werden strcasecmp verwenden.

122
00:06:19,250 --> 00:06:20,330
Es ist nicht StrComp.

123
00:06:20,330 --> 00:06:23,780
Weil wieder einmal, wir wollen
Dinge tun, ohne Berücksichtigung der Groß-/Kleinschreibung.

124
00:06:23,780 --> 00:06:27,870
So verwenden wir zum Vergleich die strcasecmp
Wort, das durch diese übergeben wurde

125
00:06:27,870 --> 00:06:31,860
Funktion gegen das Wort
das ist in diesem Eintrag.

126
00:06:31,860 --> 00:06:35,570
Wenn er Null zurückkehrt, bedeutet, dass es
ein Spiel, in welchem ​​Fall wir wollen

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

128
00:06:36,630 --> 00:06:39,590
Wir fanden die erfolgreich
Wort in unserer Hash-Tabelle.

129
00:06:39,590 --> 00:06:43,040
>> Wenn es nicht ein Spiel, dann sind wir
werde Schleife wieder und sehen Sie sich die

130
00:06:43,040 --> 00:06:43,990
nächsten Eintrag.

131
00:06:43,990 --> 00:06:47,640
Und wir werden Looping, während es weiterhin
Einträge in dieser verketteten Liste.

132
00:06:47,640 --> 00:06:50,160
Was passiert, wenn wir brechen
aus dieser for-Schleife?

133
00:06:50,160 --> 00:06:55,110
Das heißt, wir haben einen Eintrag nicht zu finden, die
abgestimmt dieses Wort, in welchem ​​Fall

134
00:06:55,110 --> 00:07:00,220
wir false zurück, um anzuzeigen, dass unsere
Hash-Tabelle nicht dieses Wort enthalten.

135
00:07:00,220 --> 00:07:02,540
Und das ist ein Scheck.

136
00:07:02,540 --> 00:07:04,790
>> Werfen wir also einen Blick auf Größe.

137
00:07:04,790 --> 00:07:06,970
Jetzt Größe sein wird, ziemlich einfach.

138
00:07:06,970 --> 00:07:11,080
Da erinnere mich, in Last, für jedes Wort
wir fanden, wir erhöht, eine globale

139
00:07:11,080 --> 00:07:12,880
variable Größe Hash-Tabelle.

140
00:07:12,880 --> 00:07:16,480
Also die Größe Funktion wird nur gehen
zu globalen Variablen zurück.

141
00:07:16,480 --> 00:07:18,150
Und das ist es.

142
00:07:18,150 --> 00:07:22,300
>> Nun endlich, wir müssen entladen, die
Wörterbuch einmal alles fertig ist.

143
00:07:22,300 --> 00:07:25,340
Also, wie sollen wir das tun?

144
00:07:25,340 --> 00:07:30,440
Genau hier sind wir Schleifen über
Alle Eimer unserem Tisch.

145
00:07:30,440 --> 00:07:33,240
So gibt es num_buckets Eimer.

146
00:07:33,240 --> 00:07:37,410
Und für jede verknüpfte Liste in unserem
Hash-Tabelle, sind wir eine Schleife über gehen

147
00:07:37,410 --> 00:07:41,070
die Gesamtheit der verbundenen Liste,
jedes Element zu befreien.

148
00:07:41,070 --> 00:07:42,900
>> Jetzt müssen wir vorsichtig sein.

149
00:07:42,900 --> 00:07:47,910
So, hier haben wir eine temporäre Variable
das ist das Speichern der Zeiger auf den nächsten

150
00:07:47,910 --> 00:07:49,730
Element in der verketteten Liste.

151
00:07:49,730 --> 00:07:52,140
Und dann sind wir frei gehen
das aktuelle Element.

152
00:07:52,140 --> 00:07:55,990
Wir müssen sicher sein, wir tun dies, weil wir
können nicht nur kostenlos das aktuelle Element

153
00:07:55,990 --> 00:07:59,180
und dann versuchen, die nächste Zeiger zuzugreifen,
da, sobald wir davon befreit,

154
00:07:59,180 --> 00:08:00,870
der Speicher wird ungültig.

155
00:08:00,870 --> 00:08:04,990
>> Also müssen wir einen Zeiger auf herum zu halten
das nächste Element, dann werden wir frei kann der

156
00:08:04,990 --> 00:08:08,360
aktuelle Element, und dann werden wir aktualisieren können
unsere aktuelle Element zu Punkt

157
00:08:08,360 --> 00:08:09,550
das nächste Element.

158
00:08:09,550 --> 00:08:12,800
Wir werden während Schleife gibt es Elemente
in dieser verketteten Liste.

159
00:08:12,800 --> 00:08:15,620
Wir werden das für alle verknüpft tun
Listen in der Hash-Tabelle.

160
00:08:15,620 --> 00:08:19,460
Und wenn wir damit fertig sind, haben wir
die Hash-Tabelle vollständig entladen und

161
00:08:19,460 --> 00:08:20,190
wir fertig sind.

162
00:08:20,190 --> 00:08:23,200
So ist es unmöglich, Entladen
immer false zurück.

163
00:08:23,200 --> 00:08:26,470
Und wenn wir fertig sind, werden wir
nur true zurück.

164
00:08:26,470 --> 00:08:29,000
>> Geben wir diese Lösung versuchen.

165
00:08:29,000 --> 00:08:33,070
Werfen wir also einen Blick auf das, was unsere
struct Knoten aussehen wird.

166
00:08:33,070 --> 00:08:36,220
Hier sehen wir, wir werden einen bool haben
Wort und eine struct node * Kinder

167
00:08:36,220 --> 00:08:37,470
Halterung Alphabet.

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

169
00:08:38,929 --> 00:08:42,020
Das erste, was Sie sein könnten
frage mich, warum ist ALPHABET

170
00:08:42,020 --> 00:08:44,660
ed als 27 definiert?

171
00:08:44,660 --> 00:08:47,900
Nun, denken Sie daran, dass wir gehen zu müssen,
werden, um die Handhabung des Apostroph.

172
00:08:47,900 --> 00:08:51,910
Also, das wird so etwas wie ein sein
Sonderfall dieses Programms.

173
00:08:51,910 --> 00:08:54,710
>> Jetzt erinnere, wie ein Trie
tatsächlich funktioniert.

174
00:08:54,710 --> 00:08:59,380
Lassen Sie uns sagen, dass wir das Wort der Indizierung
"Katzen." Dann von der Wurzel des Trie

175
00:08:59,380 --> 00:09:02,610
werden wir an die Kinder kümmern
Array und wir werden bei der Suche

176
00:09:02,610 --> 00:09:08,090
Index, die dem Buchstaben entspricht,
C. So, die indiziert 2 wird.

177
00:09:08,090 --> 00:09:11,530
Also da, das wird
geben uns einen neuen Knoten.

178
00:09:11,530 --> 00:09:13,820
Und dann werden wir von diesem Knoten zu arbeiten.

179
00:09:13,820 --> 00:09:17,770
>> Also gegeben, dass der Knoten wieder einmal sind wir
später in der Kinder-Array zu suchen.

180
00:09:17,770 --> 00:09:22,110
Und wir werden bei Index Null aussehen
auf die A in Katzen entsprechen.

181
00:09:22,110 --> 00:09:27,170
So dann werden wir zu diesem Knoten zu gehen,
und da Knoten werden wir

182
00:09:27,170 --> 00:09:31,090
am Ende sehen, es ist eine, entspricht
T. und Bewegen auf diesem Knoten,

183
00:09:31,090 --> 00:09:35,530
schließlich haben wir komplett ausgesehen haben
durch unser Wort "Katze". Und jetzt bool

184
00:09:35,530 --> 00:09:40,960
Wort soll zeigen, ob
Dieser gegebene Wort tatsächlich ein Wort.

185
00:09:40,960 --> 00:09:43,470
>> Warum also brauchen wir das Spezialfall?

186
00:09:43,470 --> 00:09:47,700
Nun, was das Wort "Katastrophe"
ist im Wörterbuch, aber die

187
00:09:47,700 --> 00:09:50,150
Wort "Katze" ist es nicht?

188
00:09:50,150 --> 00:09:54,580
So und zu schauen, ob das Wort "Katze"
wird im Wörterbuch, wir sind

189
00:09:54,580 --> 00:09:59,970
gehen, um erfolgreich durch zu schauen
die Indizes C-A-T in der Region Knoten.

190
00:09:59,970 --> 00:10:04,290
Aber das ist nur, weil Katastrophe
passiert, um Knoten auf dem Weg zu schaffen

191
00:10:04,290 --> 00:10:07,190
von C-A-T, bis hin zu
das Ende des Wortes.

192
00:10:07,190 --> 00:10:12,020
So bool Wort wird verwendet, um anzugeben, ob
diese besondere Lage

193
00:10:12,020 --> 00:10:14,310
tatsächlich zeigt ein Wort.

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

195
00:10:15,140 --> 00:10:19,310
So, jetzt wissen wir, was es ist Trie
aussehen würde, schauen wir uns die

196
00:10:19,310 --> 00:10:20,730
Laden-Funktion.

197
00:10:20,730 --> 00:10:24,610
Also Last wird einen bool zurück
für, ob wir erfolgreich oder

198
00:10:24,610 --> 00:10:26,720
erfolglos geladen das Wörterbuch.

199
00:10:26,720 --> 00:10:30,460
Und das wird das Wörterbuch sein
dass wir wollen, laden.

200
00:10:30,460 --> 00:10:33,930
>> Also erste, was wir zu tun, ist offen
bis diesem Wörterbuch zum Lesen.

201
00:10:33,930 --> 00:10:36,160
Und wir müssen dafür sorgen,
wir nicht scheitern.

202
00:10:36,160 --> 00:10:39,580
Also, wenn das Wörterbuch nicht
erfolgreich geöffnet wurde, wird es zurück

203
00:10:39,580 --> 00:10:42,400
null, wobei in diesem Fall sind wir
werde return false.

204
00:10:42,400 --> 00:10:47,230
Aber unter der Annahme, dass es erfolgreich
geöffnet, dann können wir tatsächlich lesen

205
00:10:47,230 --> 00:10:48,220
durch das Wörterbuch.

206
00:10:48,220 --> 00:10:50,880
>> Also erste, was wir zu gehen
tun möchte, ist, dass wir dies

207
00:10:50,880 --> 00:10:52,500
globale Variable Wurzel.

208
00:10:52,500 --> 00:10:56,190
Jetzt Wurzel wird ein Knoten sein *.

209
00:10:56,190 --> 00:10:59,760
Es ist die Spitze unserer Trie, dass wir
sein werden, durch Iteration.

210
00:10:59,760 --> 00:11:02,660
So ist die erste Sache, die wir gehen
zu wollen, ist vergeben

211
00:11:02,660 --> 00:11:04,140
Speicher für Root.

212
00:11:04,140 --> 00:11:07,980
Beachten Sie, dass wir mit der calloc
Funktion, die im Wesentlichen die gleiche ist

213
00:11:07,980 --> 00:11:11,500
wie die malloc-Funktion, außer es ist
garantiert etwas, das ist zurück

214
00:11:11,500 --> 00:11:13,180
komplett auf Null gesetzt.

215
00:11:13,180 --> 00:11:17,290
Also, wenn wir malloc verwendet, würden wir brauchen,
gehen durch alle Zeiger in unserem

216
00:11:17,290 --> 00:11:20,160
Knoten, und stellen Sie sicher, dass
sie sind alle null.

217
00:11:20,160 --> 00:11:22,710
So calloc wird das für uns tun.

218
00:11:22,710 --> 00:11:26,330
>> Jetzt nur wie malloc, müssen wir sicherstellen,
sicher, dass die Zuteilung war eigentlich

219
00:11:26,330 --> 00:11:27,520
erfolgreich.

220
00:11:27,520 --> 00:11:29,990
Wenn diese wieder null, dann werden wir
müssen schließen oder Wörterbuch

221
00:11:29,990 --> 00:11:32,100
Datei-und Rück falsch.

222
00:11:32,100 --> 00:11:36,835
So wurde unter der Annahme, dass die Zuweisung
erfolgreich ist, werden wir einen Knoten verwenden *

223
00:11:36,835 --> 00:11:40,270
Cursor durch unsere Trie laufen.

224
00:11:40,270 --> 00:11:43,890
Also unsere Wurzeln nie ändern,
aber wir werden, um den Cursor zu bedienen

225
00:11:43,890 --> 00:11:47,875
tatsächlich gehen von Knoten zu Knoten.

226
00:11:47,875 --> 00:11:50,940
>> So in dieser for-Schleife wir lesen
durch die Wörterbuchdatei.

227
00:11:50,940 --> 00:11:53,670
Und wir sind mit fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc wird zu schnappen Sie sich einen einzigen
Zeichen aus der Datei.

229
00:11:56,290 --> 00:11:59,370
Wir werden weiter greifen
Zeichen, während wir nicht erreichen, die

230
00:11:59,370 --> 00:12:01,570
Ende der Datei.

231
00:12:01,570 --> 00:12:03,480
>> Es gibt zwei Fälle müssen wir umgehen.

232
00:12:03,480 --> 00:12:06,610
Der erste, wenn die Zeichen
war nicht eine neue Zeile.

233
00:12:06,610 --> 00:12:10,450
So wissen wir, ob es eine neue Linie, dann
wir sind dabei auf dem Weg zu einem neuen Wort.

234
00:12:10,450 --> 00:12:15,240
Aber angenommen, es war nicht eine neue Zeile, dann
hier, um herauszufinden, wollen wir die

235
00:12:15,240 --> 00:12:18,380
Index wir gehen in den Index
in der Kinder-Array,

236
00:12:18,380 --> 00:12:19,810
schauten wir uns vor.

237
00:12:19,810 --> 00:12:23,880
>> Also, wie ich schon sagte, müssen wir
Sonderfall der Apostroph.

238
00:12:23,880 --> 00:12:26,220
Beachten Sie, wir sind mit den ternären
Betreiber hier.

239
00:12:26,220 --> 00:12:29,580
So werden wir dies als, wenn lesen
der Charakter, den wir in las, war ein

240
00:12:29,580 --> 00:12:35,330
Apostroph, dann werden wir gesetzt
index = "Alphabet" -1, was wird

241
00:12:35,330 --> 00:12:37,680
sein, der Index 26.

242
00:12:37,680 --> 00:12:41,130
>> Else, wenn es nicht ein Apostroph, gibt
wir gehen, um den Index gesetzt

243
00:12:41,130 --> 00:12:43,760
= c - a.

244
00:12:43,760 --> 00:12:49,030
Also denken Sie daran aus zuvor p-Sätzen zurück,
c - a wird uns das zu geben

245
00:12:49,030 --> 00:12:53,410
alphabetische Position von C. Also, wenn
C ist der Buchstabe A, das wird

246
00:12:53,410 --> 00:12:54,700
geben uns Index Null.

247
00:12:54,700 --> 00:12:58,120
Denn der Buchstabe B, wird es geben
uns der Index ein, und so weiter.

248
00:12:58,120 --> 00:13:03,010
>> So gibt uns den Index in die
Kinder Array, das wir wollen.

249
00:13:03,010 --> 00:13:08,890
Nun, wenn dieser Index ist derzeit null in
Kinder, bedeutet das, dass ein Knoten

250
00:13:08,890 --> 00:13:11,830
noch nicht vorhanden ist
aus diesem Pfad.

251
00:13:11,830 --> 00:13:15,160
Also müssen wir vergeben
ein Knoten für diesen Pfad.

252
00:13:15,160 --> 00:13:16,550
Das ist, was wir hier tun.

253
00:13:16,550 --> 00:13:20,690
>> So werden wir wieder das calloc
Funktion, so dass wir nicht haben, um

254
00:13:20,690 --> 00:13:22,880
Null aus, alle Zeiger.

255
00:13:22,880 --> 00:13:27,240
Und wir müssen wieder zu überprüfen,
dass calloc nicht scheitern.

256
00:13:27,240 --> 00:13:30,700
Wenn calloc hat scheitern, dann müssen wir
um alles zu entladen, schließen unsere

257
00:13:30,700 --> 00:13:32,820
Wörterbuch und false zurück.

258
00:13:32,820 --> 00:13:40,050
Also unter der Annahme, dass es nicht scheitern, dann
dies wird ein neues Kind für uns zu schaffen.

259
00:13:40,050 --> 00:13:41,930
Und dann werden wir diesem Kind zu gehen.

260
00:13:41,930 --> 00:13:44,960
Unsere Cursor laufen
auf das Kind.

261
00:13:44,960 --> 00:13:49,330
>> Nun, wenn dies nicht mit null zu beginnen,
dann wird der Cursor gerade durchlaufen kann

262
00:13:49,330 --> 00:13:52,590
auf das Kind, ohne tatsächlich
dass Sie etwas zuzuweisen.

263
00:13:52,590 --> 00:13:56,730
Dies ist der Fall, wenn wir zuerst passiert
zuteilen, das Wort "Katze". Und

264
00:13:56,730 --> 00:14:00,330
das bedeutet, dass, wenn wir zu vergeben
"Katastrophe", die wir nicht brauchen, um zu erstellen

265
00:14:00,330 --> 00:14:01,680
Knoten für C-A-T wieder.

266
00:14:01,680 --> 00:14:04,830
Sie existieren bereits.

267
00:14:04,830 --> 00:14:06,080
>> Was ist das sonst?

268
00:14:06,080 --> 00:14:10,480
Dies ist der Zustand, in der c
Backslash-n, wobei c war eine neue Zeile.

269
00:14:10,480 --> 00:14:13,710
Das heißt, wir haben erfolgreich
abgeschlossen Wort.

270
00:14:13,710 --> 00:14:16,860
Nun, was wir tun wollen, wenn wir
erfolgreich ein Wort abgeschlossen?

271
00:14:16,860 --> 00:14:21,100
Wir werden dieses Wort Feld verwenden
Innere unserer Struktur-Knoten.

272
00:14:21,100 --> 00:14:23,390
Wir wollen, dass auf true setzen.

273
00:14:23,390 --> 00:14:27,150
Damit anzeigt, daß dieser Knoten
deutet auf eine erfolgreiche

274
00:14:27,150 --> 00:14:29,250
Wort, eine tatsächliche Wort.

275
00:14:29,250 --> 00:14:30,940
>> Nun setzen, dass auf true.

276
00:14:30,940 --> 00:14:35,150
Wir wollen unsere Cursor auf Punkt zurückgesetzt
zu Beginn des Trie wieder.

277
00:14:35,150 --> 00:14:40,160
Und schließlich erhöhen Wörterbuch
Größe, da wir fanden eine andere Arbeit.

278
00:14:40,160 --> 00:14:43,230
So werden wir weiterhin tun, dass,
Lesen im Zeichen für Zeichen,

279
00:14:43,230 --> 00:14:49,150
Bau neuer Knoten in unserem Trie und
für jedes Wort in dem Wörterbuch, bis

280
00:14:49,150 --> 00:14:54,020
erreichen wir schließlich C! = EOF, in der
Fall brechen wir aus der Datei.

281
00:14:54,020 --> 00:14:57,050
>> Jetzt gibt es zwei Fälle unter
die wir vielleicht EOF getroffen haben.

282
00:14:57,050 --> 00:15:00,980
Die erste ist, wenn es einen Fehler
Lesen aus der Datei.

283
00:15:00,980 --> 00:15:03,470
Also, wenn es einen Fehler, wir
müssen die typische tun.

284
00:15:03,470 --> 00:15:06,460
Entladen Sie alles, in der Nähe
die Datei, return false.

285
00:15:06,460 --> 00:15:09,810
Angenommen, es war kein Fehler, dass
bedeutet nur, dass wir tatsächlich das Ende der

286
00:15:09,810 --> 00:15:13,750
die Datei, in diesem Fall schließen wir die
Datei-und Rück wahr, da wir

287
00:15:13,750 --> 00:15:17,330
erfolgreich geladen Wörterbuch
in unsere Trie.

288
00:15:17,330 --> 00:15:20,170
>> So, jetzt bitte zuerst Prüfung lassen.

289
00:15:20,170 --> 00:15:25,156
Mit Blick auf die Check-Funktion, sehen wir
, dass der Check wird eine bool zurück.

290
00:15:25,156 --> 00:15:29,680
Es liefert true, wenn dieses Wort, dass es
übergeben ist in unserem Trie.

291
00:15:29,680 --> 00:15:32,110
Es gibt ansonsten false.

292
00:15:32,110 --> 00:15:36,050
Also, wie Sie ermitteln, ob
Dieses Wort ist in unserer Trie?

293
00:15:36,050 --> 00:15:40,190
>> Wir sehen hier, dass, genau wie zuvor,
wir gehen, um den Cursor zu verwenden, um laufen

294
00:15:40,190 --> 00:15:41,970
durch unsere Trie.

295
00:15:41,970 --> 00:15:46,600
Nun, hier werden wir durchlaufen
über unsere gesamte Wort.

296
00:15:46,600 --> 00:15:50,620
So Iteration über dem Wort sind wir Vergangenheit,
wir werden zur Bestimmung der

297
00:15:50,620 --> 00:15:56,400
Index in der Kinder-Array,
entspricht Wort Klammer I. Also das

298
00:15:56,400 --> 00:15:59,670
wird genau so aussehen
Last, wo, wenn Wort [i]

299
00:15:59,670 --> 00:16:03,310
ist ein Apostroph, dann möchten wir
Index "ALPHABET" verwenden - 1.

300
00:16:03,310 --> 00:16:05,350
Da wir festgestellt, dass die
ist, wohin wir gehen, um zu speichern

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

302
00:16:07,100 --> 00:16:11,780
>> Else, wir werden zwei untere Wort verwenden
Halterung I. Also denken Sie daran, dieses Wort kann

303
00:16:11,780 --> 00:16:13,920
willkürliche Kapitalisierung.

304
00:16:13,920 --> 00:16:17,540
Und so stellen Sie sicher, dass wir wollen, wir
mit einem Kleinbuchstaben Version der Dinge.

305
00:16:17,540 --> 00:16:21,920
Und dann aus, dass 'a', einmal subtrahieren
geben uns wieder die alphabetische

306
00:16:21,920 --> 00:16:23,880
Position dieses Charakters.

307
00:16:23,880 --> 00:16:27,680
Also, das wird zu unserem Index sein
in der Kinder-Arrays.

308
00:16:27,680 --> 00:16:32,420
>> Und jetzt, wenn dieser Index in die Kinder
Array null ist, bedeutet, dass wir

309
00:16:32,420 --> 00:16:34,990
kann nicht mehr weiter Laufen
hinunter unsere Trie.

310
00:16:34,990 --> 00:16:38,870
Wenn das der Fall ist, kann nicht dieses Wort
möglicherweise in unserem Trie sein.

311
00:16:38,870 --> 00:16:42,340
Da wäre es, würde das
meine, es wäre ein Weg sein

312
00:16:42,340 --> 00:16:43,510
bis zu diesem Wort.

313
00:16:43,510 --> 00:16:45,290
Und Sie würden nie begegnen null.

314
00:16:45,290 --> 00:16:47,850
So stoßen null kehren wir falsch.

315
00:16:47,850 --> 00:16:49,840
Das Wort ist nicht im Wörterbuch.

316
00:16:49,840 --> 00:16:53,660
Wenn es nicht null waren, dann sind wir
werde Laufen fortsetzen.

317
00:16:53,660 --> 00:16:57,220
>> Also werden wir dort Cursor
bis zu diesem bestimmten Punkt

318
00:16:57,220 --> 00:16:59,760
Knoten an diesem Index.

319
00:16:59,760 --> 00:17:03,150
Wir halten, dass in
das gesamte Wort, vorausgesetzt,

320
00:17:03,150 --> 00:17:03,950
wir nie getroffen null.

321
00:17:03,950 --> 00:17:07,220
Das heißt, wir waren in der Lage, um durchzukommen
das gesamte Wort und finden

322
00:17:07,220 --> 00:17:08,920
ein Knoten in unserem Versuch.

323
00:17:08,920 --> 00:17:10,770
Aber wir sind noch nicht ganz fertig.

324
00:17:10,770 --> 00:17:12,290
>> Wir wollen nicht nur true zurück.

325
00:17:12,290 --> 00:17:14,770
Wir wollen Cursor> Wort zurück.

326
00:17:14,770 --> 00:17:18,980
Da wieder erinnern, ist "cat" nicht
im Wörterbuch, und "Katastrophe"

327
00:17:18,980 --> 00:17:22,935
wird, dann werden wir erfolgreich wir
durch das Wort "Katze". Aber Cursor

328
00:17:22,935 --> 00:17:25,760
Wort falsch und nicht wahr sein.

329
00:17:25,760 --> 00:17:30,930
Also haben wir Cursor Wort zurück, um anzuzeigen,
ob dieser Knoten tatsächlich ein Wort.

330
00:17:30,930 --> 00:17:32,470
Und das ist es für den Check.

331
00:17:32,470 --> 00:17:34,250
>> Also lassen Sie uns prüfen, Größe.

332
00:17:34,250 --> 00:17:37,350
So Größe sein wird, recht einfach
da, daran erinnern, in der Last, wir sind

333
00:17:37,350 --> 00:17:41,430
Erhöhen Wörterbuch Größe für
jedes Wort, denen wir begegnen.

334
00:17:41,430 --> 00:17:45,350
Also Größe ist gerade dabei,
Rückkehr Wörterbuch Größe.

335
00:17:45,350 --> 00:17:47,390
Und das ist es.

336
00:17:47,390 --> 00:17:50,590
>> So haben wir schließlich entladen.

337
00:17:50,590 --> 00:17:55,100
So entladen, werden wir für eine
rekursive Funktion, um tatsächlich alle tun

338
00:17:55,100 --> 00:17:56,530
der Arbeit für uns.

339
00:17:56,530 --> 00:17:59,340
Also unsere Funktion wird sich
auf Entlader bezeichnet werden.

340
00:17:59,340 --> 00:18:01,650
Was Entlader tun?

341
00:18:01,650 --> 00:18:06,580
Wir sehen hier, dass Entlader wird sich
laufen alle Kinder bei

342
00:18:06,580 --> 00:18:08,410
Diese bestimmten Knoten.

343
00:18:08,410 --> 00:18:11,750
Und wenn der Kindknoten nicht
null ist, dann werden wir

344
00:18:11,750 --> 00:18:13,730
Entladen der untergeordneten Knoten.

345
00:18:13,730 --> 00:18:18,010
>> Das ist also rekursiv Sie entladen
alle unsere Kinder.

346
00:18:18,010 --> 00:18:21,080
Sobald wir sicher sind, dass alle unsere Kinder
entladen haben, dann werden wir

347
00:18:21,080 --> 00:18:25,210
kann uns befreien, so
entladen uns.

348
00:18:25,210 --> 00:18:29,460
Dies wird rekursiv arbeiten
Entladen des gesamten Trie.

349
00:18:29,460 --> 00:18:32,850
Und dann, wenn das erledigt ist,
wir können einfach true zurück.

350
00:18:32,850 --> 00:18:34,210
Entladen kann nicht scheitern.

351
00:18:34,210 --> 00:18:35,710
Wir stehen noch Dinge zu befreien.

352
00:18:35,710 --> 00:18:38,870
Also, wenn wir fertig sind befreit
alles, true zurückgeben.

353
00:18:38,870 --> 00:18:40,320
Und das ist es.

354
00:18:40,320 --> 00:18:41,080
Mein Name ist Rob.

355
00:18:41,080 --> 00:18:42,426
Und das war Speller.

356
00:18:42,426 --> 00:18:47,830
>> [MUSIC SPIEL]