1
00:00:00,000 --> 00:00:00,530

2
00:00:00,530 --> 00:00:03,070
>> Sprecher 1: Geben wir
diese Lösung versuchen.

3
00:00:03,070 --> 00:00:07,130
Werfen wir also einen Blick auf das, was unsere
Struct Knoten aussehen wird.

4
00:00:07,130 --> 00:00:11,040
Hier sehen wir, wir gehen zu müssen, ein
Bool Word und ein Struct Knoten Sterne

5
00:00:11,040 --> 00:00:12,990
Kinder klammern Alphabet.

6
00:00:12,990 --> 00:00:18,720
Also erste, was werden Sie vielleicht fragen,
warum ist Alphabet Hash als 27 definiert?

7
00:00:18,720 --> 00:00:22,540
Nun, denken Sie daran, dass wir gehen zu müssen,
werden, um die Handhabung des Apostroph, so

8
00:00:22,540 --> 00:00:25,610
das wird so etwas wie ein besonderes sein
Fall dieses Programms.

9
00:00:25,610 --> 00:00:28,780
>> OK, jetzt, daran erinnern, wie ein
Trie tatsächlich funktioniert.

10
00:00:28,780 --> 00:00:33,420
Lassen Sie uns sagen, dass wir die Indizierung der Wort Katzen,
dann aus der Wurzel unserer Trie,

11
00:00:33,420 --> 00:00:36,670
werden wir an die Kinder kümmern
Array und wir werden bei der Suche

12
00:00:36,670 --> 00:00:42,250
Index, die dem Buchstaben entspricht,
C. Damit würde Index zwei sein.

13
00:00:42,250 --> 00:00:46,400
Also da, dass wird uns
ein neuer Knoten, und dann werden wir

14
00:00:46,400 --> 00:00:47,880
arbeiten von diesem Knoten.

15
00:00:47,880 --> 00:00:51,830
>> Also gegeben, dass der Knoten wieder einmal sind wir
später in der Kinder-Array aus,

16
00:00:51,830 --> 00:00:56,170
und wir werden mit dem Index Null aussehen
auf die A in Katzen entsprechen.

17
00:00:56,170 --> 00:01:01,240
So dann werden wir zu diesem Knoten zu gehen,
und da Knoten, wir gehen

18
00:01:01,240 --> 00:01:05,170
an der Index, entspricht aussehen
T. und Bewegen auf diesem Knoten,

19
00:01:05,170 --> 00:01:09,590
schließlich haben wir komplett ausgesehen haben
durch unser Wort Katze, und jetzt Bool

20
00:01:09,590 --> 00:01:15,020
Wort soll zeigen, ob
Dieser gegebene Wort tatsächlich ein Wort.

21
00:01:15,020 --> 00:01:17,530
>> Warum also brauchen wir das Spezialfall?

22
00:01:17,530 --> 00:01:21,680
Nun, was ist, wenn das Wort Katastrophe
ist im Wörterbuch, aber

23
00:01:21,680 --> 00:01:24,120
das Wort Katze nicht?

24
00:01:24,120 --> 00:01:29,030
So in der Suche, um zu sehen, wenn das Wort Katze ist
im Wörterbuch, werden wir

25
00:01:29,030 --> 00:01:34,880
erfolgreich durch die Indizes suchen
C-A-T und einen Knoten zu erreichen, aber das ist

26
00:01:34,880 --> 00:01:39,760
nur, weil Katastrophe passiert
erstellen Knoten auf dem Weg von C-A-T alle

27
00:01:39,760 --> 00:01:41,250
die bis zum Ende des Wortes.

28
00:01:41,250 --> 00:01:46,520
So Bool Wort wird verwendet, ob deuten
diese besondere Lage tatsächlich

29
00:01:46,520 --> 00:01:48,370
zeigt, ein Wort.

30
00:01:48,370 --> 00:01:52,920
>> Na gut, so dass wir jetzt wissen, was für ein
Trie wird wie, schauen wir uns freuen

31
00:01:52,920 --> 00:01:54,800
auf der Load-Funktion.

32
00:01:54,800 --> 00:01:58,670
So laden wird eine Bool zurück
für, ob wir erfolgreich oder

33
00:01:58,670 --> 00:02:03,020
erfolglos geladen und Wörterbuch
das wird das Wörterbuch sein

34
00:02:03,020 --> 00:02:04,520
dass wir wollen, laden.

35
00:02:04,520 --> 00:02:08,310
Also erste, was wir tun werden, ist offen
bis diesem Wörterbuch zum Lesen.

36
00:02:08,310 --> 00:02:12,060
Wir müssen sicherstellen, dass wir nicht scheitern,
Wenn das Wörterbuch nicht

37
00:02:12,060 --> 00:02:15,280
erfolgreich geöffnet wurde, wird es zurück
Nein, wobei in diesem Fall werden wir

38
00:02:15,280 --> 00:02:16,340
False zurück.

39
00:02:16,340 --> 00:02:21,290
Aber unter der Annahme, dass es erfolgreich
geöffnet, dann können wir tatsächlich lesen

40
00:02:21,290 --> 00:02:22,310
durch das Wörterbuch.

41
00:02:22,310 --> 00:02:24,940
>> Also erste, was wir zu gehen
tun möchte, ist, dass wir dies

42
00:02:24,940 --> 00:02:26,560
globale Variable Wurzel.

43
00:02:26,560 --> 00:02:30,250
Nun wird Wurzel wird ein Knoten Stern.

44
00:02:30,250 --> 00:02:33,830
Es ist die Spitze unserer Trie, dass wir
sein werden, durch Iteration.

45
00:02:33,830 --> 00:02:38,200
Also erste, was wir werden wollen
zu tun ist, reservieren Speicher für unsere Wurzel.

46
00:02:38,200 --> 00:02:42,040
>> Beachten Sie, dass wir mit der calloc
Funktion, die im Wesentlichen die gleiche ist

47
00:02:42,040 --> 00:02:45,560
als Malloc Funktion, außer es ist
garantiert etwas, das ist zurück

48
00:02:45,560 --> 00:02:47,240
komplett auf Null gesetzt.

49
00:02:47,240 --> 00:02:51,350
Also, wenn wir Malloc verwendet, würden wir brauchen,
gehen durch alle Zeiger in unserem

50
00:02:51,350 --> 00:02:54,220
Knoten und stellen Sie sicher, dass
sie sind alle null.

51
00:02:54,220 --> 00:02:56,780
So calloc wird das für uns tun.

52
00:02:56,780 --> 00:03:00,390
>> Jetzt, nur wie malloc, müssen wir sicherstellen,
sicher, dass die Zuteilung ist eigentlich

53
00:03:00,390 --> 00:03:01,580
erfolgreich.

54
00:03:01,580 --> 00:03:04,060
Wenn diese wieder null, dann werden wir
müssen unser Wörterbuch zu schließen

55
00:03:04,060 --> 00:03:06,170
Datei-und Rück False.

56
00:03:06,170 --> 00:03:11,040
So wurde unter der Annahme der Zuteilung
erfolgreich ist, werden wir einen Knoten verwenden

57
00:03:11,040 --> 00:03:14,340
Sterne-Cursor zu durchlaufen
durch unsere Trie.

58
00:03:14,340 --> 00:03:17,950
Also Root ist nie zu verändern,
aber wir werden Cursor zu bedienen

59
00:03:17,950 --> 00:03:20,770
tatsächlich gehen von Knoten zu Knoten.

60
00:03:20,770 --> 00:03:25,000
>> Na gut, so dass in diesem For-Schleife, wir sind
Lesen durch die Wörterbuchdatei,

61
00:03:25,000 --> 00:03:26,965
und wir bei fgetc verwenden.

62
00:03:26,965 --> 00:03:30,360
So fgetc wird zu schnappen Sie sich einen einzigen
Zeichen aus der Datei.

63
00:03:30,360 --> 00:03:33,430
Wir werden weiter greifen
Zeichen, während wir nicht erreichen, die

64
00:03:33,430 --> 00:03:37,540
am Ende der Datei, so gibt es
beiden Fällen müssen wir umgehen.

65
00:03:37,540 --> 00:03:41,640
Die erste, wenn das Zeichen kein
neue Linie, so dass wir wissen, ob es eine neue

66
00:03:41,640 --> 00:03:44,480
Linie, dann sind wir über den
dem Weg zu einem neuen Wort.

67
00:03:44,480 --> 00:03:49,300
Aber angenommen, es war nicht eine neue Zeile, dann
hier, um herauszufinden, wollen wir die

68
00:03:49,300 --> 00:03:52,440
Index wir gehen in den Index
in der Kinder-Array,

69
00:03:52,440 --> 00:03:53,890
schauten wir uns vor.

70
00:03:53,890 --> 00:03:57,950
>> Also wie ich schon sagte, müssen wir
Sonderfall der Apostroph.

71
00:03:57,950 --> 00:04:01,040
Beachten Sie, wir sind mit dem ternären Operator
hier, so werden wir lesen

72
00:04:01,040 --> 00:04:05,500
dies, als ob der Charakter, den wir in las, war
ein Apostroph, dann werden wir

73
00:04:05,500 --> 00:04:11,740
gesetzt Index gleich Alphabet minus
1, die der Index 26 sein.

74
00:04:11,740 --> 00:04:15,190
Else, wenn es nicht ein Apostroph,
dann werden wir, um den Index gesetzt

75
00:04:15,190 --> 00:04:17,820
gleich c minus ein.

76
00:04:17,820 --> 00:04:23,090
Also denken Sie daran aus früheren p Sätze zurück,
c abzüglich einer wird uns das zu geben

77
00:04:23,090 --> 00:04:27,470
alphabetisch Position c, so dass, wenn
c ist der Buchstabe A, dieser Wille

78
00:04:27,470 --> 00:04:28,770
geben uns Index Null.

79
00:04:28,770 --> 00:04:32,180
Denn der Buchstabe B, es geben würde,
uns der Index ein, und so weiter.

80
00:04:32,180 --> 00:04:37,070
>> So gibt uns den Index in die
Kinder Array, das wir wollen.

81
00:04:37,070 --> 00:04:42,540
Nun, wenn dieser Index ist derzeit null in
die Kinder-Array, das bedeutet, dass

82
00:04:42,540 --> 00:04:47,470
ein Knoten nicht aktuell vom existieren
dieser Weg, so müssen wir vergeben ein

83
00:04:47,470 --> 00:04:49,220
Knoten für diesen Pfad.

84
00:04:49,220 --> 00:04:50,610
Das ist, was wir hier tun.

85
00:04:50,610 --> 00:04:54,650
So werden wir, wieder, verwenden Sie die calloc
Funktion, so dass wir nicht

86
00:04:54,650 --> 00:05:00,130
auf Null aus alle Zeiger, und wir,
wieder, müssen diese calloc überprüfen

87
00:05:00,130 --> 00:05:01,300
nicht scheitern.

88
00:05:01,300 --> 00:05:04,760
Wenn calloc hat scheitern, dann müssen wir
um alles zu entladen, schließen unsere

89
00:05:04,760 --> 00:05:06,880
Wörterbuch und False.

90
00:05:06,880 --> 00:05:14,110
>> Also unter der Annahme, dass es nicht scheitern, dann
dies wird ein neues Kind für uns zu schaffen,

91
00:05:14,110 --> 00:05:16,000
und dann werden wir diesem Kind zu gehen.

92
00:05:16,000 --> 00:05:19,030
Unsere Cursor laufen
auf das Kind.

93
00:05:19,030 --> 00:05:23,390
Nun, wenn dies nicht null zu beginnen,
dann wird der Cursor gerade durchlaufen kann

94
00:05:23,390 --> 00:05:26,650
auf das Kind, ohne tatsächlich
dass Sie etwas zuzuweisen.

95
00:05:26,650 --> 00:05:30,790
Dies ist der Fall, wenn wir zuerst passiert
um das Wort Katze zuzuordnen, und

96
00:05:30,790 --> 00:05:34,390
das bedeutet, dass, wenn wir zu vergeben
Katastrophe, brauchen wir nicht zu schaffen

97
00:05:34,390 --> 00:05:35,720
Knoten für C-A-T wieder.

98
00:05:35,720 --> 00:05:37,620
Sie existieren bereits.

99
00:05:37,620 --> 00:05:40,140
>> OK, also was ist das sonst?

100
00:05:40,140 --> 00:05:44,600
Dies ist der Zustand, in der c
Backslash-n, wobei c war eine neue Zeile.

101
00:05:44,600 --> 00:05:47,780
Das heißt, wir haben erfolgreich
abgeschlossen Wort.

102
00:05:47,780 --> 00:05:51,020
Nun, was wir tun wollen, wenn wir
erfolgreich ein Wort abgeschlossen?

103
00:05:51,020 --> 00:05:55,250
Wir werden dieses Wort Feld verwenden
Innere unserer Struct-Knoten.

104
00:05:55,250 --> 00:06:00,570
>> Wir wollen, dass auf True gesetzt, so dass
bedeutet, dass der Knoten zeigt eine

105
00:06:00,570 --> 00:06:03,320
erfolgreich ein Wort eigentliche Wort.

106
00:06:03,320 --> 00:06:05,050
Nun eingestellt, dass auf True.

107
00:06:05,050 --> 00:06:09,210
Wir wollen unsere Cursor auf Punkt zurückgesetzt
zu Beginn des Trie wieder.

108
00:06:09,210 --> 00:06:13,510
Und schließlich erhöhen Wörterbuch
Größe, da wir festgestellt, ein anderes Wort.

109
00:06:13,510 --> 00:06:16,450
>> Na gut, also werden wir auch weiterhin tun
dass Lesen im Zeichen von

110
00:06:16,450 --> 00:06:21,960
Charakter, den Bau neuer Knoten in
unsere Trie und für jedes Wort in der

111
00:06:21,960 --> 00:06:26,810
Wörterbuch, zu erreichen, bis wir endlich c
EOF gleich, in welchem ​​Fall, wir brechen

112
00:06:26,810 --> 00:06:28,100
aus der Datei.

113
00:06:28,100 --> 00:06:31,110
Nun gibt es zwei Fälle unter
die wir vielleicht EOF getroffen haben.

114
00:06:31,110 --> 00:06:35,680
Die erste ist, wenn es einen Fehler
Lesen aus der Datei, so dass, wenn es

115
00:06:35,680 --> 00:06:39,280
ein Fehler, den typischen tun müssen, wir
Entladen alles, schließen Sie die Datei,

116
00:06:39,280 --> 00:06:40,520
False zurück.

117
00:06:40,520 --> 00:06:43,870
Angenommen, es war kein Fehler, dass
bedeutet nur, dass wir tatsächlich das Ende der

118
00:06:43,870 --> 00:06:47,820
die Datei, in diesem Fall schließen wir die
Datei-und True zurück, da wir

119
00:06:47,820 --> 00:06:51,010
das Wörterbuch erfolgreich geladen
in unsere Trie.

120
00:06:51,010 --> 00:06:54,240
>> Alle rechts, so jetzt wollen wir
Besuche Check.

121
00:06:54,240 --> 00:06:58,780
Mit Blick auf die Funktion prüfen, sehen wir
Überprüfen Sie, dass wird eine Bool zurück.

122
00:06:58,780 --> 00:07:03,740
Es gibt True zurück, wenn dieses Wort, dass es
übergeben ist in unserem Trie.

123
00:07:03,740 --> 00:07:06,170
Es gibt ansonsten False.

124
00:07:06,170 --> 00:07:10,110
>> Also, wie sollen wir ermitteln, ob
Dieses Wort ist in unserer Trie?

125
00:07:10,110 --> 00:07:14,270
Wir sehen hier, dass, genau wie zuvor,
wir gehen, um den Cursor zu verwenden, um laufen

126
00:07:14,270 --> 00:07:16,010
durch unsere Trie.

127
00:07:16,010 --> 00:07:20,650
Nun, hier, wir werden durchlaufen
über unsere gesamte Wort.

128
00:07:20,650 --> 00:07:24,680
So Iteration über dem Wort sind wir
übergeben, werden wir zur Bestimmung der

129
00:07:24,680 --> 00:07:29,280
Index in der Kinder-Array,
entspricht Wort Halterung i.

130
00:07:29,280 --> 00:07:34,150
Also, das wird genau so aussehen
Laden, wo, wenn Wort Halterung i ist eine

131
00:07:34,150 --> 00:07:38,110
Apostroph, dann auf Index verwenden, wollen wir
Alphabet minus 1, weil wir festgestellt,

132
00:07:38,110 --> 00:07:41,160
das ist, wohin wir gehen
Apostrophe speichern.

133
00:07:41,160 --> 00:07:44,440
>> Else, wir werden tolower verwenden
Wort Halterung i.

134
00:07:44,440 --> 00:07:48,270
Also denken Sie daran, dieses Wort kann beliebige
Kapitalisierung, und so haben wir

135
00:07:48,270 --> 00:07:51,590
wollen sicherstellen, dass wir mit
einen Kleinbuchstaben Version der Dinge.

136
00:07:51,590 --> 00:07:55,300
Und dann von diesem Klein subtrahieren
ein, um noch einmal, geben uns die

137
00:07:55,300 --> 00:07:57,940
alphabetisch Position
von diesem Charakter.

138
00:07:57,940 --> 00:08:01,740
Also, das wird zu unserem Index sein
in der Kinder-Arrays.

139
00:08:01,740 --> 00:08:06,480
>> Und nun, wenn dieser Index in die Kinder
Array null ist, bedeutet, dass wir

140
00:08:06,480 --> 00:08:09,050
kann nicht mehr weiter Laufen
hinunter unsere Trie.

141
00:08:09,050 --> 00:08:13,320
Wenn das der Fall ist, kann nicht dieses Wort
möglicherweise in unserem Trie sein, denn wenn es

142
00:08:13,320 --> 00:08:18,000
wurden, das würde bedeuten, es wäre ein
Pfad auf dieses Wort, und Sie würden

143
00:08:18,000 --> 00:08:19,350
nie begegnen null.

144
00:08:19,350 --> 00:08:21,910
So stoßen null kehren wir Falsch.

145
00:08:21,910 --> 00:08:23,810
Das Wort ist nicht im Wörterbuch.

146
00:08:23,810 --> 00:08:28,200
Wenn es nicht null wäre, dann werden wir
weiter Iteration, also werden wir

147
00:08:28,200 --> 00:08:33,150
unsere Cursor zu aktualisieren, um zu zeigen, dass
bestimmten Knoten an diesem Index.

148
00:08:33,150 --> 00:08:36,659
>> Also wir halten, dass in
das gesamte Wort.

149
00:08:36,659 --> 00:08:40,630
Unter der Annahme, die wir nie getroffen null, das heißt
Wir waren in der Lage, über den gesamten zu erhalten

150
00:08:40,630 --> 00:08:44,840
Welt und finden Sie einen Knoten in unserem Trie,
aber wir sind noch nicht ganz fertig.

151
00:08:44,840 --> 00:08:46,350
Wir wollen nicht nur True zurück.

152
00:08:46,350 --> 00:08:51,400
Wir wollen den Cursor Fehlerwort zurück
da, daran erinnern, wieder, wenn Katze nicht

153
00:08:51,400 --> 00:08:55,140
im Wörterbuch und Katastrophe,
dann werden wir erfolgreich durchkommen

154
00:08:55,140 --> 00:08:59,810
das Wort Katze, aber Cursor Wort
False und nicht wahr sein.

155
00:08:59,810 --> 00:09:04,990
Also haben wir Cursor Wort zurück, um anzuzeigen,
ob dieser Knoten tatsächlich ein Wort,

156
00:09:04,990 --> 00:09:06,530
und das ist es für den Check.

157
00:09:06,530 --> 00:09:08,310
>> Also lassen Sie uns prüfen, Größe.

158
00:09:08,310 --> 00:09:11,410
Also Größe sein wird, recht einfach
da, daran erinnern, in Laden, wir sind

159
00:09:11,410 --> 00:09:15,480
Erhöhen Wörterbuch Größe für
jedes Wort, denen wir begegnen.

160
00:09:15,480 --> 00:09:20,820
Also Größe ist gerade dabei, zurückzukehren
Wörterbuch Größe, und das ist es.

161
00:09:20,820 --> 00:09:24,650
>> Alle Rechte, so endlich, haben wir Entladen.

162
00:09:24,650 --> 00:09:29,050
So entlasten, werden wir für eine
rekursive Funktion, um tatsächlich alle tun

163
00:09:29,050 --> 00:09:33,390
der Arbeit für uns, so dass unsere Funktion
wird aufgerufen Unloader werden.

164
00:09:33,390 --> 00:09:35,830
Was Unloader tun?

165
00:09:35,830 --> 00:09:40,640
Wir sehen hier, dass Entlader wird sich
laufen alle Kinder bei

166
00:09:40,640 --> 00:09:45,810
Dieses spezielle Knoten, und wenn das Kind
Knoten nicht null ist, dann werden wir

167
00:09:45,810 --> 00:09:47,760
Entladen der untergeordneten Knoten.

168
00:09:47,760 --> 00:09:52,070
>> Also das wird rekursiv
entladen alle unsere Kinder.

169
00:09:52,070 --> 00:09:55,140
Sobald wir sicher sind, dass alle unsere Kinder
entladen haben, dann werden wir

170
00:09:55,140 --> 00:09:58,830
kann uns befreien, uns selbst so zu entladen.

171
00:09:58,830 --> 00:10:04,550
So wird dies rekursiv Entladen der
gesamten Trie, und dann noch einmal, das ist

172
00:10:04,550 --> 00:10:06,910
erledigt ist, können wir nur True zurück.

173
00:10:06,910 --> 00:10:09,770
Entladen kann nicht umhin, wir sind
nur Dinge zu befreien.

174
00:10:09,770 --> 00:10:12,985
Also, wenn wir fertig sind befreit
alles, True zurück.

175
00:10:12,985 --> 00:10:14,380
Und das ist es.

176
00:10:14,380 --> 00:10:16,792
Mein Name ist Rob, und dies
war [unverständlich].

177
00:10:16,792 --> 00:10:21,888