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

2
00:00:00,530 --> 00:00:03,070
>> SPEAKER 1: Да дадем
Този разтвор се пробвам.

3
00:00:03,070 --> 00:00:07,130
Така че нека да разгледаме какво ни
Struct възел ще изглежда така.

4
00:00:07,130 --> 00:00:11,040
Ето, ние виждаме, че ще има
Bool Word и възел звезда Struct

5
00:00:11,040 --> 00:00:12,990
Деца скоба азбука.

6
00:00:12,990 --> 00:00:18,720
Така че първото нещо, което може би се чудите,
защо е азбука хеш определя като 27?

7
00:00:18,720 --> 00:00:22,540
Е, не забравяйте, че ние ще трябва
да се борави с апостроф, така

8
00:00:22,540 --> 00:00:25,610
че ще бъде малко на специален
При цялата тази програма.

9
00:00:25,610 --> 00:00:28,780
>> Добре, сега, си спомням как един
Trie действително работи.

10
00:00:28,780 --> 00:00:33,420
Да кажем, че ние сме индексиране думата котки,
после от корена на нашата Trie,

11
00:00:33,420 --> 00:00:36,670
ние ще разгледаме в Детския
масив, и ние отиваме да погледнем в

12
00:00:36,670 --> 00:00:42,250
индекс, който отговаря на буквата
C. Така че би било индекс две.

13
00:00:42,250 --> 00:00:46,400
Така че, имайки предвид, че това ще ни даде
нов възел, и след това ще

14
00:00:46,400 --> 00:00:47,880
работа от този възел.

15
00:00:47,880 --> 00:00:51,830
>> Така че, имайки предвид, че възел, ние сме отново
ще разгледаме масива деца,

16
00:00:51,830 --> 00:00:56,170
и ние отиваме да погледнем индекса нула
да съответства на А в котка.

17
00:00:56,170 --> 00:01:01,240
Така че след това ние ще отидем до този възел,
и предвид това, че възел, отиваме

18
00:01:01,240 --> 00:01:05,170
да погледнете индекса, който съответства
Т. и да преминат към този възел,

19
00:01:05,170 --> 00:01:09,590
Най-накрая, ние сме напълно погледна
чрез нашата дума Cat, а сега Bool

20
00:01:09,590 --> 00:01:15,020
Word е трябвало да посочи дали
дадената дума всъщност е дума.

21
00:01:15,020 --> 00:01:17,530
>> Така че, защо имаме нужда от този специален случай?

22
00:01:17,530 --> 00:01:21,680
Е, какво ще стане ако катастрофа думата
е в нашия речник, но

23
00:01:21,680 --> 00:01:24,120
думата котката не е?

24
00:01:24,120 --> 00:01:29,030
Така че в търсенето, за да видите, ако думата е котката
в нашия речник, ние ще

25
00:01:29,030 --> 00:01:34,880
успешно гледам през индексите
C-A-T и да достигне един възел, но това е

26
00:01:34,880 --> 00:01:39,760
само заради катастрофа се случи с
създаде възли по пътя от C-A-T всички

27
00:01:39,760 --> 00:01:41,250
чак до края на думата.

28
00:01:41,250 --> 00:01:46,520
Така Bool Word се използва да посочи дали
това определено място, всъщност

29
00:01:46,520 --> 00:01:48,370
показва една дума.

30
00:01:48,370 --> 00:01:52,920
>> Добре, така че сега, че ние знаем какво е
Trie ще изглежда така, нека да разгледаме

31
00:01:52,920 --> 00:01:54,800
на функцията Load.

32
00:01:54,800 --> 00:01:58,670
Така Load ще се върне Bool
за това дали ние успешно или

33
00:01:58,670 --> 00:02:03,020
безуспешно се зарежда речник и
това ще бъде речника

34
00:02:03,020 --> 00:02:04,520
че искаме да се зареди.

35
00:02:04,520 --> 00:02:08,310
Така че първото нещо, което ще направим е отворен
нагоре, че речник за четене.

36
00:02:08,310 --> 00:02:12,060
Ние трябва да сме сигурни, че не се провали,
така че ако речника не беше

37
00:02:12,060 --> 00:02:15,280
успешно отворен, той ще се върне
Не, в този случай ние ще

38
00:02:15,280 --> 00:02:16,340
върне False.

39
00:02:16,340 --> 00:02:21,290
Но ако приемем, че тя успешно
отвори, тогава ние действително могат да четат

40
00:02:21,290 --> 00:02:22,310
чрез речника.

41
00:02:22,310 --> 00:02:24,940
>> Така че първото нещо, което започваш да
искате да направите, е да имаме тази

42
00:02:24,940 --> 00:02:26,560
променлива корен глобален.

43
00:02:26,560 --> 00:02:30,250
Сега, корен ще бъде звезда възел.

44
00:02:30,250 --> 00:02:33,830
Тя е на върха на нашата Trie, че сме
ще бъде итерации чрез.

45
00:02:33,830 --> 00:02:38,200
Така че първото нещо, което ще искате да
направите, е заделена памет за нашия корен.

46
00:02:38,200 --> 00:02:42,040
>> Забележете, че ние сме с помощта на Calloc
функция, която е по същество същата

47
00:02:42,040 --> 00:02:45,560
тъй като функцията за изчистване, освен това е
гарантирано да се върне нещо, което е

48
00:02:45,560 --> 00:02:47,240
напълно на нула.

49
00:02:47,240 --> 00:02:51,350
Така че, ако ние използвахме изчистване, ние ще трябва да
мине през всички насоки в нашата

50
00:02:51,350 --> 00:02:54,220
възел и се уверете, че
всички те са нула.

51
00:02:54,220 --> 00:02:56,780
Така Calloc ще направи това за нас.

52
00:02:56,780 --> 00:03:00,390
>> Сега, точно като изчистване, ние трябва да се направи
уверите, че разпределението е всъщност

53
00:03:00,390 --> 00:03:01,580
успешно.

54
00:03:01,580 --> 00:03:04,060
Ако това се връща нула, тогава можем
Трябва да затворите нашия речник

55
00:03:04,060 --> 00:03:06,170
подаде и да се върне False.

56
00:03:06,170 --> 00:03:11,040
Така че, ако приемем, че разпределението е
успешно, ние ще използваме един възел

57
00:03:11,040 --> 00:03:14,340
звездни Cursor да превъртите
чрез нашия Trie.

58
00:03:14,340 --> 00:03:17,950
Така че нашият корен никога няма да се промени,
но ние ще използваме Cursor да

59
00:03:17,950 --> 00:03:20,770
действително отиде от възел до възел.

60
00:03:20,770 --> 00:03:25,000
>> Добре, така че в този за линия, ние сме
четене чрез файла на речника,

61
00:03:25,000 --> 00:03:26,965
и ние сме с помощта на fgetc.

62
00:03:26,965 --> 00:03:30,360
Така fgetc ще вземете една-единствена
символ от файла.

63
00:03:30,360 --> 00:03:33,430
Отиваме да продължи вземете
символи, докато ние не достигат

64
00:03:33,430 --> 00:03:37,540
края на файла, така че има
два случая, които трябва да се справя.

65
00:03:37,540 --> 00:03:41,640
Първият, ако характер не е
нов ред, за да сме сигурни дали това е нова

66
00:03:41,640 --> 00:03:44,480
линия, тогава ние сме на път да
се премине към нова дума.

67
00:03:44,480 --> 00:03:49,300
Но ако приемем, че не е на нов ред, а след това
тук, ние искаме да разбера

68
00:03:49,300 --> 00:03:52,440
индекс отиваме да индекс в
в масива деца, които

69
00:03:52,440 --> 00:03:53,890
разгледахме преди.

70
00:03:53,890 --> 00:03:57,950
>> Така че, както казах и преди, ние трябва да
специален случай апостроф.

71
00:03:57,950 --> 00:04:01,040
Забележете, ние сме с помощта на третичния оператор
тук, така че отиваме да се чете

72
00:04:01,040 --> 00:04:05,500
това сякаш характера четем в е
апостроф, след това отиваме да

73
00:04:05,500 --> 00:04:11,740
определен индекс, равен на азбука минус
1, който ще бъде индекс 26.

74
00:04:11,740 --> 00:04:15,190
Иначе, ако не беше апостроф,
След това отиваме да зададете индекс

75
00:04:15,190 --> 00:04:17,820
равна на с минус.

76
00:04:17,820 --> 00:04:23,090
Така че не забравяйте обратно от предишна т. комплекти,
в минус ще ни даде на

77
00:04:23,090 --> 00:04:27,470
азбучен ред на С, така че ако
C е буквата А, това ще

78
00:04:27,470 --> 00:04:28,770
ни даде индекс нула.

79
00:04:28,770 --> 00:04:32,180
За буквата Б, тя ще даде
ни индекс 1, и така нататък.

80
00:04:32,180 --> 00:04:37,070
>> Така че това ни дава индекса в
Деца масив, който ние искаме.

81
00:04:37,070 --> 00:04:42,540
Сега, ако този показател в момента е нула в
масива деца, това означава, че

82
00:04:42,540 --> 00:04:47,470
възел в момента не съществува от
този път, така че ние трябва да се разпредели

83
00:04:47,470 --> 00:04:49,220
възел за този път.

84
00:04:49,220 --> 00:04:50,610
Това е, което правим тук.

85
00:04:50,610 --> 00:04:54,650
Така че ние отиваме да, отново, използвайте Calloc
функция, така че ние нямаме

86
00:04:54,650 --> 00:05:00,130
до нула, за всички указатели, както и ние,
отново, трябва да се провери, че Calloc

87
00:05:00,130 --> 00:05:01,300
не се провали.

88
00:05:01,300 --> 00:05:04,760
Ако Calloc се провали, тогава ние трябва
да се разтоварят всичко, затворете ни

89
00:05:04,760 --> 00:05:06,880
речник, и да се върне False.

90
00:05:06,880 --> 00:05:14,110
>> Така че, ако се приеме, че той не се провали, след това
това ще създаде ново дете за нас,

91
00:05:14,110 --> 00:05:16,000
и след това ние ще отидем на това дете.

92
00:05:16,000 --> 00:05:19,030
Нашата курсора ще обхождане
свежда до това дете.

93
00:05:19,030 --> 00:05:23,390
Сега, ако това не е нула, за да започнем с това,
след курсора може просто да превъртите

94
00:05:23,390 --> 00:05:26,650
свежда до това дете, без всъщност да
се налага да заделят нищо.

95
00:05:26,650 --> 00:05:30,790
Това е случаят, когато за първи път се е случило
да се разпредели дума котката, и

96
00:05:30,790 --> 00:05:34,390
това означава, че когато отидем да се разпределят
катастрофа, ние не трябва да се създаде

97
00:05:34,390 --> 00:05:35,720
възли за C-A-T отново.

98
00:05:35,720 --> 00:05:37,620
Те вече съществува.

99
00:05:37,620 --> 00:05:40,140
>> ОК, така че какво е това друго?

100
00:05:40,140 --> 00:05:44,600
Това е състояние, при което е в
наклонена черта н, където С е на нов ред.

101
00:05:44,600 --> 00:05:47,780
Това означава, че ние имаме успешно
завършен дума.

102
00:05:47,780 --> 00:05:51,020
Сега, това, което искаме да правим, когато
успешно завършено дума?

103
00:05:51,020 --> 00:05:55,250
Ние ще използваме тази дума поле
във вътрешността на нашата Struct възел.

104
00:05:55,250 --> 00:06:00,570
>> Ние искаме да се създаде, че да True, така че
показва, че този възел показва

105
00:06:00,570 --> 00:06:03,320
Успешното дума действително дума.

106
00:06:03,320 --> 00:06:05,050
Сега, задайте, че за да е истина.

107
00:06:05,050 --> 00:06:09,210
Искаме да изчисти нашия курсора до точка
в началото на TRIE отново.

108
00:06:09,210 --> 00:06:13,510
И най-накрая, нарастване нашия речник
размер, тъй като ние открихме друга дума.

109
00:06:13,510 --> 00:06:16,450
>> Добре, така че ние ще продължим да правим
че, четейки по характер от

110
00:06:16,450 --> 00:06:21,960
характер, изграждане на нови възли в
нашата Trie и за всяка дума в

111
00:06:21,960 --> 00:06:26,810
речник, докато най-накрая достигне в
се равнява на EOF, като в този случай, ние се прекъсне

112
00:06:26,810 --> 00:06:28,100
от файла.

113
00:06:28,100 --> 00:06:31,110
Сега, има два случая, при
които бихме могли да са хит EOF.

114
00:06:31,110 --> 00:06:35,680
Първият е, ако е имало грешка
четене от файла, така че ако е имало

115
00:06:35,680 --> 00:06:39,280
грешка, ние трябва да направим характерния
разтоварят всичко, затворете файла,

116
00:06:39,280 --> 00:06:40,520
върне False.

117
00:06:40,520 --> 00:06:43,870
Ако приемем, че не е грешка, че
просто означава, че ние всъщност се удари в края на

118
00:06:43,870 --> 00:06:47,820
файла, като в този случай, ние затворете
подаде и да се върнете вярно, тъй като ние

119
00:06:47,820 --> 00:06:51,010
успешно зареден речника
в нашата Trie.

120
00:06:51,010 --> 00:06:54,240
>> Добре, сега нека
проверите Проверка.

121
00:06:54,240 --> 00:06:58,780
С поглед към Проверка на функцията, ще видим,
Тази проверка ще се върне Bool.

122
00:06:58,780 --> 00:07:03,740
Тя връща True, ако тази дума, че това е
да се прехвърлят в наш Trie.

123
00:07:03,740 --> 00:07:06,170
Тя връща False друго.

124
00:07:06,170 --> 00:07:10,110
>> Така че как ще се определи дали
тази дума е в нашата Trie?

125
00:07:10,110 --> 00:07:14,270
Виждаме, че тук, точно както и преди,
отиваме да използвате курсора, за да превъртате

126
00:07:14,270 --> 00:07:16,010
чрез нашия Trie.

127
00:07:16,010 --> 00:07:20,650
Сега, тук, ние отиваме да превъртите
над цялата ни дума.

128
00:07:20,650 --> 00:07:24,680
Така итерации върху думата ние сме
преминал, отиваме да се определи

129
00:07:24,680 --> 00:07:29,280
индекс в масива деца, които
съответства на дума скоба аз.

130
00:07:29,280 --> 00:07:34,150
Така че това ще изглежда точно като
Load, където, ако думата скоба и е

131
00:07:34,150 --> 00:07:38,110
апостроф, тогава искаме да използваме индекса
азбука минус един, защото ние определихме

132
00:07:38,110 --> 00:07:41,160
това е мястото, където отиваме
да съхранява апострофи.

133
00:07:41,160 --> 00:07:44,440
>> Иначе ние ще използваме tolower
Думата скоба аз.

134
00:07:44,440 --> 00:07:48,270
Така че не забравяйте, че думата може да има произволна
капитализация, и така ние

135
00:07:48,270 --> 00:07:51,590
искате да се уверите, че ние използваме
с малки букви версия на нещата.

136
00:07:51,590 --> 00:07:55,300
И след това се изважда от тази с малки букви
а да, още веднъж, дай ни

137
00:07:55,300 --> 00:07:57,940
азбучен ред
от този характер.

138
00:07:57,940 --> 00:08:01,740
Така че това ще бъде нашият форум
в масива деца.

139
00:08:01,740 --> 00:08:06,480
>> И сега, ако този индекс в Детския
масив е нула, това означава, че ние

140
00:08:06,480 --> 00:08:09,050
вече не може да продължи итерации
надолу нашия Trie.

141
00:08:09,050 --> 00:08:13,320
Ако това е така, тази дума не може да
евентуално да бъде в нашия Trie, тъй като, ако го

142
00:08:13,320 --> 00:08:18,000
са, това би означавало, че ще има
път до тази дума, и бихте

143
00:08:18,000 --> 00:08:19,350
никога не се сблъскате нищожна.

144
00:08:19,350 --> 00:08:21,910
Така че се натъкват на нула, ние се върне False.

145
00:08:21,910 --> 00:08:23,810
Думата не е в речника.

146
00:08:23,810 --> 00:08:28,200
Ако не беше нула, след това отиваме да
продължи итерации, така че ще

147
00:08:28,200 --> 00:08:33,150
да актуализираме нашата курсора да посочи, че
специално възел в този индекс.

148
00:08:33,150 --> 00:08:36,659
>> Така че ние продължаваме да правим, че през
цялата дума.

149
00:08:36,659 --> 00:08:40,630
Ако приемем, че ние никога не удари нула, това означава,
ние бяхме в състояние да пробият през целия

150
00:08:40,630 --> 00:08:44,840
свят и да намерят възел в нашия Trie,
но ние не сме съвсем свършила още.

151
00:08:44,840 --> 00:08:46,350
Ние не искаме просто да се върне True.

152
00:08:46,350 --> 00:08:51,400
Ние искаме да се върне курсора грешка дума
тъй като, не забравяйте отново, ако котка не е

153
00:08:51,400 --> 00:08:55,140
в нашия речник и е катастрофа,
тогава ние успешно ще получите чрез

154
00:08:55,140 --> 00:08:59,810
думата котката, но думата курсора
ще бъде False и не е вярно.

155
00:08:59,810 --> 00:09:04,990
Така че ние се върнете курсора дума за обозначаване
дали този възел всъщност е дума,

156
00:09:04,990 --> 00:09:06,530
и че това е за проверка.

157
00:09:06,530 --> 00:09:08,310
>> Така че нека да се провери Size.

158
00:09:08,310 --> 00:09:11,410
Така Size ще бъде доста лесно
тъй като, не забравяйте, в Load, ние сме

159
00:09:11,410 --> 00:09:15,480
увеличаване размера на речник за
всяка дума, която се сблъскваме.

160
00:09:15,480 --> 00:09:20,820
Така Size е просто ще се върне
речник размер, и това е всичко.

161
00:09:20,820 --> 00:09:24,650
>> Добре, така че накрая, имаме разтоварване.

162
00:09:24,650 --> 00:09:29,050
Така разтоварване, отиваме да се използва
рекурсивна функция действително да направим всичко

163
00:09:29,050 --> 00:09:33,390
на работата за нас, така че нашата функция
ще се нарича за разтоварване.

164
00:09:33,390 --> 00:09:35,830
Какво е за разтоварване смяташ да правиш?

165
00:09:35,830 --> 00:09:40,640
Виждаме тук, че за разтоварване ще се
обхождане на всички деца в

166
00:09:40,640 --> 00:09:45,810
този възел, и ако детето
възел не е нула, а след това ние ще

167
00:09:45,810 --> 00:09:47,760
разтоварят дете възел.

168
00:09:47,760 --> 00:09:52,070
>> Така че това ще рекурсивно
разтоварят всички наши деца.

169
00:09:52,070 --> 00:09:55,140
След като ние сме сигурни, че всички наши деца
са били разтоварени, тогава ние

170
00:09:55,140 --> 00:09:58,830
да се освободим, така разтоварят бъдем себе си.

171
00:09:58,830 --> 00:10:04,550
Така че това рекурсивно ще разтоварим
Цялата Trie, а след това веднъж, че е

172
00:10:04,550 --> 00:10:06,910
направено, ние можем просто да се върне True.

173
00:10:06,910 --> 00:10:09,770
Разтоварете не може да се провали, ние сме
просто освобождава неща.

174
00:10:09,770 --> 00:10:12,985
Така че след като сме готови освобождавайки
всичко, върнете True.

175
00:10:12,985 --> 00:10:14,380
И това е всичко.

176
00:10:14,380 --> 00:10:16,792
Моето име е Роб, и това
е [недоловим].

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