1
00:00:00,000 --> 00:00:12,350
>> [За възпроизвеждане на музика]

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

3
00:00:13,050 --> 00:00:13,640
Аз съм Роб.

4
00:00:13,640 --> 00:00:16,210
И нека това решение навън.

5
00:00:16,210 --> 00:00:20,070
Така че тук ние ще се приложат
обща таблица.

6
00:00:20,070 --> 00:00:24,090
Виждаме, че структурата на възел на нашата
маса ще изглежда по този начин.

7
00:00:24,090 --> 00:00:28,710
Така че няма да има Чар дума
масив на площ ДЪЛЖИНА + 1.

8
00:00:28,710 --> 00:00:32,259
Да не забравяме и + 1, тъй като максималната
дума в речника е 45

9
00:00:32,259 --> 00:00:33,130
символа.

10
00:00:33,130 --> 00:00:37,070
И тогава ние ще трябва едно допълнително
характер за обратно наклонена черта нула.

11
00:00:37,070 --> 00:00:40,870
>> И тогава нашата Hashtable във всяка
кофа ще се съхранява

12
00:00:40,870 --> 00:00:42,320
свързан списък от възли.

13
00:00:42,320 --> 00:00:44,420
Ние не правим линейна сондиране тук.

14
00:00:44,420 --> 00:00:48,430
И така, за да се свърже към следващата
елемент в кофата, ние се нуждаем от

15
00:00:48,430 --> 00:00:50,390
структура възел * следващия.

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

17
00:00:51,110 --> 00:00:53,090
Така че това е, което възел изглежда.

18
00:00:53,090 --> 00:00:56,180
>> Сега тук е декларацията
на нашата Hashtable.

19
00:00:56,180 --> 00:00:59,640
Тя ще има 16 834 кофи.

20
00:00:59,640 --> 00:01:01,910
Но този номер няма значение.

21
00:01:01,910 --> 00:01:05,450
И накрая, ние ще имаме
глобална променлива размер изпробван звукът, който

22
00:01:05,450 --> 00:01:07,000
ще започнем като нула.

23
00:01:07,000 --> 00:01:10,760
И това се случва, за да следите как
много думи са в нашия речник.

24
00:01:10,760 --> 00:01:13,710
>> Така че нека да разгледаме най-натоварване.

25
00:01:13,710 --> 00:01:16,390
Забележете, че товара, то връща булев.

26
00:01:16,390 --> 00:01:20,530
Ще се върнете вярно, ако това беше успешно
заредена, и лъжа в противен случай.

27
00:01:20,530 --> 00:01:23,990
И това отнема Конст Чар * речник,
който е речника

28
00:01:23,990 --> 00:01:25,280
че искаме да се отвори.

29
00:01:25,280 --> 00:01:27,170
Така че това е първото нещо,
ние ще направим.

30
00:01:27,170 --> 00:01:29,500
>> Отиваме да Fopen на
речник за четене.

31
00:01:29,500 --> 00:01:31,680
И ние ще трябва да се направи
уверите, че тя успя.

32
00:01:31,680 --> 00:01:35,920
Така че, ако го връща NULL, тогава ние не направихме
успешно отворите речника.

33
00:01:35,920 --> 00:01:37,440
И ние трябва да се върне фалшиви.

34
00:01:37,440 --> 00:01:41,580
Но ако приемем, че го е направил успешно
отворен, след това ние искаме да прочетете

35
00:01:41,580 --> 00:01:42,400
речник.

36
00:01:42,400 --> 00:01:46,450
Така че продължавайте да примка, докато не се намери някои
причина да се измъкнат от този цикъл,

37
00:01:46,450 --> 00:01:47,570
, които ще видим.

38
00:01:47,570 --> 00:01:48,920
Така че продължавайте да примка.

39
00:01:48,920 --> 00:01:51,780
>> И сега ние ще
изчистване на един възел.

40
00:01:51,780 --> 00:01:54,020
И разбира се, ние трябва
да излъчи проверете отново.

41
00:01:54,020 --> 00:01:58,680
Така че, ако mallocing не успее, тогава
ние искаме да се разтоварят всеки възел, който ние

42
00:01:58,680 --> 00:02:02,590
случило с изчистване преди, затворете
речник и връщане фалшиви.

43
00:02:02,590 --> 00:02:06,830
Но пренебрегвайки факта, че, ако се приеме, че
успял, тогава искаме да използваме fscanf

44
00:02:06,830 --> 00:02:12,400
за да прочетете една-единствена дума от нашия
речника в нашия възел.

45
00:02:12,400 --> 00:02:17,940
Така че не забравяйте, че влизането> дума е Чар
Думата буфер с размер LENGHTH + 1

46
00:02:17,940 --> 00:02:20,300
че отиваме да съхранявате думата инча

47
00:02:20,300 --> 00:02:25,070
>> Така fscanf ще се върне един, толкова дълго,
, тъй като е в състояние да успешно

48
00:02:25,070 --> 00:02:26,750
прочетете една дума от файла.

49
00:02:26,750 --> 00:02:30,460
Ако някоя грешка се случва, или ние
достигнат края на файла, да го

50
00:02:30,460 --> 00:02:31,950
няма да се върне един.

51
00:02:31,950 --> 00:02:35,180
В този случай тя не се връща 1,
ние сме най-накрая ще се измъкнат от

52
00:02:35,180 --> 00:02:37,280
тази линия, докато.

53
00:02:37,280 --> 00:02:42,770
Така ние виждаме, че след като имаме успешно
прочетете една дума в

54
00:02:42,770 --> 00:02:48,270
влизане> дума, след това отиваме в които
дума с помощта на нашата хеш функция.

55
00:02:48,270 --> 00:02:49,580
>> Нека да разгледаме най-
функцията за сегментиране.

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

57
00:02:52,430 --> 00:02:55,610
Така че наистина не се нуждаят
да се разбере това.

58
00:02:55,610 --> 00:02:59,460
И всъщност ние просто извади този хеш
функционира от интернет.

59
00:02:59,460 --> 00:03:04,010
Единственото нещо, което трябва да се признае, е
че това отнема Конст Чар * дума.

60
00:03:04,010 --> 00:03:08,960
Така че това е като низ като вход, и
връщане неподписан Int като продукция.

61
00:03:08,960 --> 00:03:12,360
Така че това е всичко, функция за сегментиране се, е, че
се в един вход и ви дава

62
00:03:12,360 --> 00:03:14,490
индекс в Hashtable.

63
00:03:14,490 --> 00:03:18,530
>> Забележете, че ние сме Модинг от NUM_BUCKETS,
така че стойността се връща

64
00:03:18,530 --> 00:03:21,730
всъщност е индекс в Hashtable
и не индекс на отвъдното

65
00:03:21,730 --> 00:03:24,320
границите на масива.

66
00:03:24,320 --> 00:03:28,060
Така че, предвид факта, че функция, отиваме
за сегментиране на думата, която четем

67
00:03:28,060 --> 00:03:29,390
речник.

68
00:03:29,390 --> 00:03:31,700
И тогава започваш да се използва
че хеш да вмъкнете

69
00:03:31,700 --> 00:03:33,750
влизане в Hashtable.

70
00:03:33,750 --> 00:03:38,520
>> Сега Hashtable хеш е токът
свързан списък в таблицата.

71
00:03:38,520 --> 00:03:41,410
И това е много възможно
че това е просто NULL.

72
00:03:41,410 --> 00:03:44,960
Искаме да вмъкнете влизането ни в
началото на този свързан списък.

73
00:03:44,960 --> 00:03:48,600
И така ние ще имаме ток
входна точка на това, което Hashtable

74
00:03:48,600 --> 00:03:50,380
В момента сочи към.

75
00:03:50,380 --> 00:03:53,310
И тогава ние ще се съхранява,
в Hashtable в

76
00:03:53,310 --> 00:03:55,350
хашиш, текущият запис.

77
00:03:55,350 --> 00:03:59,320
Така че тези две линии успешно вмъкват
влизането в началото на

78
00:03:59,320 --> 00:04:02,260
свързан списък в този форум
в Hashtable.

79
00:04:02,260 --> 00:04:04,900
>> След като сте готови с това, ние знаем,
че ние открихме друга дума в

80
00:04:04,900 --> 00:04:07,790
речник, и ние увеличаваме отново.

81
00:04:07,790 --> 00:04:13,960
Така че ние продължаваме да правим това, докато fscanf
най-накрая се върна нещо нон-1 в

82
00:04:13,960 --> 00:04:16,950
който момент се помни, че
ние трябва да се освободим влизане.

83
00:04:16,950 --> 00:04:19,459
Така че тук ние malloced запис.

84
00:04:19,459 --> 00:04:21,329
И ние се опитахме да се чете нещо
от речника.

85
00:04:21,329 --> 00:04:23,910
И ние не успешно чете
нещо от речника, в

86
00:04:23,910 --> 00:04:26,650
който случай ние трябва да се освободим от влизането
че ние никога не действително пуснати в

87
00:04:26,650 --> 00:04:29,140
Hashtable, и най-накрая счупи.

88
00:04:29,140 --> 00:04:32,750
>> След като избухне ние трябва да видим, добре,
не сме се измъкнат, защото има

89
00:04:32,750 --> 00:04:34,360
четеше грешка от файла?

90
00:04:34,360 --> 00:04:37,120
Или пък можем да избухне, защото ние
достигнала края на файла?

91
00:04:37,120 --> 00:04:39,480
Ако е налице грешка, тогава
ние искаме да се върне фалшиви.

92
00:04:39,480 --> 00:04:40,930
Защото натоварване не успее.

93
00:04:40,930 --> 00:04:43,890
И в този процес искаме да разтоварим
всички думи, които четем в, и

94
00:04:43,890 --> 00:04:45,670
затворете файла речник.

95
00:04:45,670 --> 00:04:48,740
>> Ако приемем, че ние успяхме, тогава ние просто
Все още трябва да се затвори речника

96
00:04:48,740 --> 00:04:53,040
Файл, а най-накрая се върнете вярно, тъй като ние
успешно зареден речника.

97
00:04:53,040 --> 00:04:54,420
И това е за натоварване.

98
00:04:54,420 --> 00:04:59,020
Така че сега се провери, като се има зареден Hashtable,
ще изглежда по този начин.

99
00:04:59,020 --> 00:05:03,140
Така че проверете, тя връща булев, което е
ще посочи дали преминава

100
00:05:03,140 --> 00:05:07,530
в Чар * дума, дали преминава
в низ е в нашия речник.

101
00:05:07,530 --> 00:05:09,890
Така че, ако това е в речника,
ако това е в нашия Hashtable,

102
00:05:09,890 --> 00:05:11,170
ние ще се върне вярно.

103
00:05:11,170 --> 00:05:13,380
И ако не е, ще се върне фалшиви.

104
00:05:13,380 --> 00:05:17,740
>> Като се има предвид това, приет през дума, ние сме
ще сегментиране на думата.

105
00:05:17,740 --> 00:05:22,110
Сега важно нещо е да се признае,
че при натоварване ние знаехме, че всички

106
00:05:22,110 --> 00:05:23,820
думи Отиваме да бъде по-ниска случай.

107
00:05:23,820 --> 00:05:25,820
Но тук ние не сме толкова сигурни.

108
00:05:25,820 --> 00:05:29,510
Ако можем да погледнем в нашата хеш функция,
нашата хеш функция всъщност

109
00:05:29,510 --> 00:05:32,700
е по-нисък корпус всеки знак
на думата.

110
00:05:32,700 --> 00:05:37,940
Така че независимо от капитализацията на
дума, нашата хеш функция е завръщането

111
00:05:37,940 --> 00:05:42,270
на същия показател за каквото и да било на
капитализация е, тъй като той ще има

112
00:05:42,270 --> 00:05:45,280
върнато за съвсем малки букви
версия на думата.

113
00:05:45,280 --> 00:05:46,600
Добре.

114
00:05:46,600 --> 00:05:49,790
Това е нашият форум е в
HashTable за тази дума.

115
00:05:49,790 --> 00:05:52,940
>> Сега това за линия ще
обхождане на свързан списък

116
00:05:52,940 --> 00:05:55,000
, което бе в този индекс.

117
00:05:55,000 --> 00:05:59,610
Така че забележите ние сме инициализиране влизане
да сочи към този индекс.

118
00:05:59,610 --> 00:06:02,750
Отиваме да продължи
докато влизането! = NULL.

119
00:06:02,750 --> 00:06:07,770
И не забравяйте, че актуализирането на показалеца
в нашата свързан списък влизане = запис> следващия.

120
00:06:07,770 --> 00:06:14,400
Така че имаме сегашната ни входна точка към
следващия елемент в свързан списък.

121
00:06:14,400 --> 00:06:19,250
>> Така че за всяко влизане в свързан списък,
ние ще използваме strcasecmp.

122
00:06:19,250 --> 00:06:20,330
Това не е strcomp.

123
00:06:20,330 --> 00:06:23,780
Защото за пореден път, ние искаме да
правят неща случай безчувствено.

124
00:06:23,780 --> 00:06:27,870
Така че ние използваме strcasecmp да се сравни
дума, която се прекарва през този

125
00:06:27,870 --> 00:06:31,860
функция срещу думата
, която е в този пост.

126
00:06:31,860 --> 00:06:35,570
Ако това се връща на нула, това означава, че не е
един мач, в който случай ние искаме да

127
00:06:35,570 --> 00:06:36,630
връщане вярно.

128
00:06:36,630 --> 00:06:39,590
Ние успешно намери
дума в нашия Hashtable.

129
00:06:39,590 --> 00:06:43,040
>> Ако там не беше мач, а след това ние сме
Ще цикъл отново и погледнете в

130
00:06:43,040 --> 00:06:43,990
следващия запис.

131
00:06:43,990 --> 00:06:47,640
И ние ще продължим примка, докато има
са вписвания в тази свързан списък.

132
00:06:47,640 --> 00:06:50,160
Какво ще стане, ако се прекъсне
от това за цикъл?

133
00:06:50,160 --> 00:06:55,110
Това означава, че ние не се намери запис, който
съвпадащи тази дума, в който случай

134
00:06:55,110 --> 00:07:00,220
ние връщане фалшиви да покаже, че нашата
Hashtable не съдържа тази дума.

135
00:07:00,220 --> 00:07:02,540
И това е чек.

136
00:07:02,540 --> 00:07:04,790
>> Така че нека да разгледаме най-размер.

137
00:07:04,790 --> 00:07:06,970
Сега размер ще е доста проста.

138
00:07:06,970 --> 00:07:11,080
Откакто се помни в натоварване, за всяка дума
ние открихме, ние увеличава в световен

139
00:07:11,080 --> 00:07:12,880
променлив размер Hashtable.

140
00:07:12,880 --> 00:07:16,480
Така функцията размер е просто ще
да се върне глобална променлива.

141
00:07:16,480 --> 00:07:18,150
И това е всичко.

142
00:07:18,150 --> 00:07:22,300
>> Сега най-накрая, ние трябва да се разтоварим
речник След като всичко е готово.

143
00:07:22,300 --> 00:07:25,340
Така че как ще го направиш?

144
00:07:25,340 --> 00:07:30,440
Точно тук ние използваме цикъл
всички кофи на нашата трапеза.

145
00:07:30,440 --> 00:07:33,240
Така че има NUM_BUCKETS кофи.

146
00:07:33,240 --> 00:07:37,410
И за всеки свързан списък в нашата
Hashtable, отиваме да отскача над

147
00:07:37,410 --> 00:07:41,070
целостта на свързан списък,
освобождавайки всеки елемент.

148
00:07:41,070 --> 00:07:42,900
>> Сега ние трябва да бъдем внимателни.

149
00:07:42,900 --> 00:07:47,910
Така че тук имаме временна променлива
това е съхранение на показалеца към следващата

150
00:07:47,910 --> 00:07:49,730
елемент в свързан списък.

151
00:07:49,730 --> 00:07:52,140
И след това отиваме на свободно
текущия елемент.

152
00:07:52,140 --> 00:07:55,990
Ние трябва да бъдем сигурни, че правим това, тъй като ние
Не може просто да освободи текущия елемент

153
00:07:55,990 --> 00:07:59,180
и след това се опитайте да влезете в следващия показалеца,
тъй като веднъж сме го освободи,

154
00:07:59,180 --> 00:08:00,870
паметта става невалиден.

155
00:08:00,870 --> 00:08:04,990
>> Така че ние трябва да се запази около указател към
следващия елемент, тогава можем да се освободи

156
00:08:04,990 --> 00:08:08,360
текущия елемент, а след това можем да се актуализира
сегашната ни елемент да сочи към

157
00:08:08,360 --> 00:08:09,550
на следващия елемент.

158
00:08:09,550 --> 00:08:12,800
Ще контур докато има елементи
в този свързан списък.

159
00:08:12,800 --> 00:08:15,620
Ние ще направим това за всички свързани
списъци в Hashtable.

160
00:08:15,620 --> 00:08:19,460
И след като сме готови с това, ние сме
напълно разтоварени на Hashtable, и

161
00:08:19,460 --> 00:08:20,190
сме готови.

162
00:08:20,190 --> 00:08:23,200
Така че това е невъзможно за разтоварване
някога да се върне фалшиви.

163
00:08:23,200 --> 00:08:26,470
И когато сме готови, ние
просто връщане вярно.

164
00:08:26,470 --> 00:08:29,000
>> Нека дадем това решение опитам.

165
00:08:29,000 --> 00:08:33,070
Така че нека да разгледаме какво ни
структура възел ще изглежда така.

166
00:08:33,070 --> 00:08:36,220
Тук виждаме, че ще има булев
дума и структура възел * деца

167
00:08:36,220 --> 00:08:37,470
скоба азбука.

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

169
00:08:38,929 --> 00:08:42,020
Така че първото нещо, което може да бъде
чудех, защо е ПИСМЕНОСТ

170
00:08:42,020 --> 00:08:44,660
Ед определя като 27?

171
00:08:44,660 --> 00:08:47,900
Е, не забравяйте, че ние ще трябва
да се борави с апостроф.

172
00:08:47,900 --> 00:08:51,910
Така че това ще бъде до известна степен на
специален случай в цялата тази програма.

173
00:08:51,910 --> 00:08:54,710
>> Сега си спомням как един Trie
действително работи.

174
00:08:54,710 --> 00:08:59,380
Да кажем, че ние сме индексиране думата
"котки." Тогава от корена на Trie,

175
00:08:59,380 --> 00:09:02,610
ние ще разгледаме децата
масив, и ние отиваме да погледнем в

176
00:09:02,610 --> 00:09:08,090
индекс, който отговаря на буквата
С така, че да бъдат индексирани 2.

177
00:09:08,090 --> 00:09:11,530
Така че, имайки предвид, че тази воля
ни даде нов възел.

178
00:09:11,530 --> 00:09:13,820
И тогава ние ще работим от този възел.

179
00:09:13,820 --> 00:09:17,770
>> Така че, имайки предвид, че възел, ние сме отново
Ще погледнем към децата масива.

180
00:09:17,770 --> 00:09:22,110
И ние отиваме да погледнем индекса нула
да съответства на А в котка.

181
00:09:22,110 --> 00:09:27,170
Така че след това ние ще отидем до този възел,
и предвид това, че възел отиваме

182
00:09:27,170 --> 00:09:31,090
да погледнем в крайна сметка това е А съответства
Т. и да преминат към този възел,

183
00:09:31,090 --> 00:09:35,530
Най-накрая, ние сме напълно погледна
чрез нашата дума "котка." И сега булев

184
00:09:35,530 --> 00:09:40,960
дума е предназначена да посочи дали
дадената дума всъщност е дума.

185
00:09:40,960 --> 00:09:43,470
>> Така че, защо имаме нужда от този специален случай?

186
00:09:43,470 --> 00:09:47,700
Ами какво да кажем за думата "катастрофа"
е в нашия речник, но

187
00:09:47,700 --> 00:09:50,150
Думата "котка" не е?

188
00:09:50,150 --> 00:09:54,580
Затова и гледам да се види дали думата "котка"
е в нашия речник, ние сме

189
00:09:54,580 --> 00:09:59,970
Ще успешно гледам през
индексите C-A-T в района на възел.

190
00:09:59,970 --> 00:10:04,290
Но това е само заради катастрофа
се случи, за да създадете възли по пътя

191
00:10:04,290 --> 00:10:07,190
от C-A-T, чак до
на края на думата.

192
00:10:07,190 --> 00:10:12,020
Така булев дума се използва, за да посочи дали
това определено място,

193
00:10:12,020 --> 00:10:14,310
всъщност означава думата.

194
00:10:14,310 --> 00:10:15,140
>> Добре.

195
00:10:15,140 --> 00:10:19,310
Така че сега, че ние знаем какво е Trie
ще изглежда така, нека да разгледаме най-

196
00:10:19,310 --> 00:10:20,730
зареди функция.

197
00:10:20,730 --> 00:10:24,610
Така че натоварването ще се върне булев
за това дали ние успешно или

198
00:10:24,610 --> 00:10:26,720
безуспешно се зарежда речника.

199
00:10:26,720 --> 00:10:30,460
И това ще бъде в речника
че искаме да се зареди.

200
00:10:30,460 --> 00:10:33,930
>> Така че първото нещо, което искаме да направим, е отворен
нагоре, че речник за четене.

201
00:10:33,930 --> 00:10:36,160
И ние трябва да се уверете, че
ние не се провали.

202
00:10:36,160 --> 00:10:39,580
Така че, ако речника не беше
успешно отворен, той ще се върне

203
00:10:39,580 --> 00:10:42,400
нула, в който случай ние сме
ще се върне фалшиви.

204
00:10:42,400 --> 00:10:47,230
Но ако приемем, че тя успешно
отвори, тогава ние действително могат да четат

205
00:10:47,230 --> 00:10:48,220
чрез речника.

206
00:10:48,220 --> 00:10:50,880
>> Така че първото нещо, което започваш да
искате да направите, е да имаме тази

207
00:10:50,880 --> 00:10:52,500
променлива корен глобален.

208
00:10:52,500 --> 00:10:56,190
Сега корен ще бъде възел *.

209
00:10:56,190 --> 00:10:59,760
Тя е на върха на нашата Trie, че сме
ще бъде итерации чрез.

210
00:10:59,760 --> 00:11:02,660
Така че първото нещо, което ние ще
да искате да направите, е да се разпределят

211
00:11:02,660 --> 00:11:04,140
памет за нашия корен.

212
00:11:04,140 --> 00:11:07,980
Забележете, че ние сме с помощта на calloc
функция, която е по същество същата

213
00:11:07,980 --> 00:11:11,500
като функцията за изчистване, освен това е
гарантирано да се върне нещо, което е

214
00:11:11,500 --> 00:11:13,180
напълно на нула.

215
00:11:13,180 --> 00:11:17,290
Така че, ако ние използвахме изчистване, ние ще трябва да
мине през всички насоки в нашата

216
00:11:17,290 --> 00:11:20,160
възел, и се уверете, че
всички те са нула.

217
00:11:20,160 --> 00:11:22,710
Така calloc ще направи това за нас.

218
00:11:22,710 --> 00:11:26,330
>> Сега просто като изчистване, ние трябва да се направи
уверите, че разпределението е всъщност

219
00:11:26,330 --> 00:11:27,520
успешно.

220
00:11:27,520 --> 00:11:29,990
Ако това се връща нула, тогава можем
Трябва да затворите или речник

221
00:11:29,990 --> 00:11:32,100
подаде и връщане фалшиви.

222
00:11:32,100 --> 00:11:36,835
Така че, ако се приеме, че разпределянето е
успешно, ние ще използваме един възел *

223
00:11:36,835 --> 00:11:40,270
курсора, за да превъртате чрез нашия Trie.

224
00:11:40,270 --> 00:11:43,890
Така че нашите корени никога няма да се промени,
но ние ще използваме курсора

225
00:11:43,890 --> 00:11:47,875
действително отиде от възел до възел.

226
00:11:47,875 --> 00:11:50,940
>> Така че в тази линия за четем
чрез файла речник.

227
00:11:50,940 --> 00:11:53,670
И ние използваме fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc ще вземете една-единствена
символ от файла.

229
00:11:56,290 --> 00:11:59,370
Отиваме да продължи вземете
символи, докато ние не достигат

230
00:11:59,370 --> 00:12:01,570
край на файла.

231
00:12:01,570 --> 00:12:03,480
>> Има два случая, които трябва да се справя.

232
00:12:03,480 --> 00:12:06,610
Първият, ако характер
не е на нов ред.

233
00:12:06,610 --> 00:12:10,450
Така че ние знаем, ако това е нов ред, а след това
ние сме на път да се премине към нова дума.

234
00:12:10,450 --> 00:12:15,240
Но ако приемем, че не е на нов ред, а след това
Тук искаме да разбера

235
00:12:15,240 --> 00:12:18,380
индекс отиваме да индекс в
в масива, че децата

236
00:12:18,380 --> 00:12:19,810
разгледахме преди.

237
00:12:19,810 --> 00:12:23,880
>> Така че, както казах и преди, ние трябва да
специален случай апостроф.

238
00:12:23,880 --> 00:12:26,220
Забележете, ние сме с помощта на трикомпонентни
оператор тук.

239
00:12:26,220 --> 00:12:29,580
Така че ние ще чете това като, ако
характера четем в е

240
00:12:29,580 --> 00:12:35,330
апостроф, след това отиваме да настроите
индекс = "азбука" -1, което ще

241
00:12:35,330 --> 00:12:37,680
е индекс 26.

242
00:12:37,680 --> 00:12:41,130
>> Иначе, ако не беше апостроф, има
отиваме да зададете индекс

243
00:12:41,130 --> 00:12:43,760
равна на с - един.

244
00:12:43,760 --> 00:12:49,030
Така че не забравяйте преди това обратно от р-комплекти,
C - един ще ни даде на

245
00:12:49,030 --> 00:12:53,410
азбучен ред от C. Така че, ако
C е буквата А, това ще

246
00:12:53,410 --> 00:12:54,700
ни даде индекс нула.

247
00:12:54,700 --> 00:12:58,120
За буквата Б, тя ще даде
ни индекс 1, и така нататък.

248
00:12:58,120 --> 00:13:03,010
>> Така че това ни дава индекса в
деца масив, който ние искаме.

249
00:13:03,010 --> 00:13:08,890
Сега, ако този показател в момента е нула в
децата, това означава, че една възлова точка

250
00:13:08,890 --> 00:13:11,830
понастоящем не съществува
от този път.

251
00:13:11,830 --> 00:13:15,160
Така че ние трябва да се разпределят
възел за този път.

252
00:13:15,160 --> 00:13:16,550
Това е, което ние ще направим тук.

253
00:13:16,550 --> 00:13:20,690
>> Така че ние отиваме отново да използвате calloc
функция, така че ние не трябва да се

254
00:13:20,690 --> 00:13:22,880
нула, за всички указатели.

255
00:13:22,880 --> 00:13:27,240
И ние отново трябва да се провери
че calloc не пропусна.

256
00:13:27,240 --> 00:13:30,700
Ако calloc се провали, тогава ние трябва
да се разтоварят всичко, затворете ни

257
00:13:30,700 --> 00:13:32,820
речник, и връщане фалшиви.

258
00:13:32,820 --> 00:13:40,050
Така че, ако се приеме, че той не се провали, след това
това ще създаде ново дете за нас.

259
00:13:40,050 --> 00:13:41,930
И тогава ние ще отидем на това дете.

260
00:13:41,930 --> 00:13:44,960
Нашата курсора ще обхождане
свежда до това дете.

261
00:13:44,960 --> 00:13:49,330
>> Сега, ако това не е нула, за да започнем с това,
след курсора може просто да превъртите

262
00:13:49,330 --> 00:13:52,590
свежда до това дете, без всъщност да
се налага да заделят нищо.

263
00:13:52,590 --> 00:13:56,730
Това е случаят, когато за първи път се е случило
разпредели на думата "котка". И

264
00:13:56,730 --> 00:14:00,330
това означава, че когато отидем да се разпределят
"Катастрофа", ние не трябва да се създаде

265
00:14:00,330 --> 00:14:01,680
възли за C-A-T отново.

266
00:14:01,680 --> 00:14:04,830
Те вече съществува.

267
00:14:04,830 --> 00:14:06,080
>> Какво е това друго?

268
00:14:06,080 --> 00:14:10,480
Това е състояние, при което е в
наклонена черта н, където С е на нов ред.

269
00:14:10,480 --> 00:14:13,710
Това означава, че ние имаме успешно
завършен дума.

270
00:14:13,710 --> 00:14:16,860
Сега това, което искаме да правим, когато
успешно завършено дума?

271
00:14:16,860 --> 00:14:21,100
Ние ще използваме тази дума поле
във вътрешността на нашата структура възел.

272
00:14:21,100 --> 00:14:23,390
Искаме да настроите, че за да е истина.

273
00:14:23,390 --> 00:14:27,150
Така че показва, че този възел
показва успешното

274
00:14:27,150 --> 00:14:29,250
дума, действително дума.

275
00:14:29,250 --> 00:14:30,940
>> Сега настроите, че за да е истина.

276
00:14:30,940 --> 00:14:35,150
Искаме да изчисти нашия курсора до точка
в началото на TRIE отново.

277
00:14:35,150 --> 00:14:40,160
И най-накрая, нарастване нашия речник
размер, тъй като ние открихме друга работа.

278
00:14:40,160 --> 00:14:43,230
Така че ние ще продължим да правим това,
четене в знак по знак,

279
00:14:43,230 --> 00:14:49,150
изграждане на нови възли в нашата Trie и
за всяка дума в речника, докато

280
00:14:49,150 --> 00:14:54,020
ние най-накрая достигне C! = EOF, в които
случай ние се измъкнат от файла.

281
00:14:54,020 --> 00:14:57,050
>> Сега има два случая, при
които бихме могли да са хит EOF.

282
00:14:57,050 --> 00:15:00,980
Първият е, ако е имало грешка
четене от файла.

283
00:15:00,980 --> 00:15:03,470
Така че, ако е имало грешка, ние
трябва да направите характерния.

284
00:15:03,470 --> 00:15:06,460
Разтоварете всичко, в близост
файла, връщане фалшиви.

285
00:15:06,460 --> 00:15:09,810
Ако приемем, че не е грешка, че
просто означава, че ние всъщност се удари в края на

286
00:15:09,810 --> 00:15:13,750
файла, като в този случай, ние затворете
подаде и да се върнете вярно, тъй като ние

287
00:15:13,750 --> 00:15:17,330
успешно зареден речник
в нашата Trie.

288
00:15:17,330 --> 00:15:20,170
>> Така че сега нека проверим проверка.

289
00:15:20,170 --> 00:15:25,156
С поглед към функцията за проверка, ние виждаме,
че проверка ще се върне булев.

290
00:15:25,156 --> 00:15:29,680
Тя връща истина, ако тази дума, че това е
да се прехвърлят в наш Trie.

291
00:15:29,680 --> 00:15:32,110
Тя връща лъжа в противен случай.

292
00:15:32,110 --> 00:15:36,050
Така че как се определя дали
тази дума е в нашата Trie?

293
00:15:36,050 --> 00:15:40,190
>> Виждаме, че тук, точно както и преди,
отиваме да използвате курсора, за да превъртате

294
00:15:40,190 --> 00:15:41,970
чрез нашия Trie.

295
00:15:41,970 --> 00:15:46,600
Сега тук отиваме да превъртите
над цялата ни дума.

296
00:15:46,600 --> 00:15:50,620
Така итерации върху думата ние сме минали,
ние отиваме да се определи

297
00:15:50,620 --> 00:15:56,400
индекс в масива на децата, които
съответства на дума скоба I. Така че това

298
00:15:56,400 --> 00:15:59,670
ще изглежда точно като
натоварване, където, ако думата [в]

299
00:15:59,670 --> 00:16:03,310
е апостроф, а след това ние искаме
използването на индексите "азбука" - 1.

300
00:16:03,310 --> 00:16:05,350
Тъй като установихме, че това
е мястото, където отиваме да съхранявате

301
00:16:05,350 --> 00:16:07,100
апострофи.

302
00:16:07,100 --> 00:16:11,780
>> Иначе ние ще използваме два ниска дума
скоба I. Така че не забравяйте, че думата може да

303
00:16:11,780 --> 00:16:13,920
имат произволна капитализация.

304
00:16:13,920 --> 00:16:17,540
И така, ние искаме да сме сигурни, че сме
с помощта на малки букви версия на нещата.

305
00:16:17,540 --> 00:16:21,920
И след това се изважда от тази "а" до веднъж
отново ни даде Буквеното

306
00:16:21,920 --> 00:16:23,880
позиция на този характер.

307
00:16:23,880 --> 00:16:27,680
Така че това ще бъде нашият форум
в деца масива.

308
00:16:27,680 --> 00:16:32,420
>> И сега, ако този индекс в децата
масив е нула, това означава, че ние

309
00:16:32,420 --> 00:16:34,990
вече не може да продължи итерации
надолу нашия Trie.

310
00:16:34,990 --> 00:16:38,870
Ако това е така, тази дума не може да
евентуално да бъде в нашия Trie.

311
00:16:38,870 --> 00:16:42,340
Тъй като, ако се каже, че би
означава, че ще има път

312
00:16:42,340 --> 00:16:43,510
определени за тази дума.

313
00:16:43,510 --> 00:16:45,290
И никога не би срещнало нищожна.

314
00:16:45,290 --> 00:16:47,850
Така че се натъкват на нула, ние връщане фалшиви.

315
00:16:47,850 --> 00:16:49,840
Думата не е в речника.

316
00:16:49,840 --> 00:16:53,660
Ако не беше нула, след това ние сме
ще продължи итерации.

317
00:16:53,660 --> 00:16:57,220
>> Така че ние отиваме там курсора
да посочи, че специално

318
00:16:57,220 --> 00:16:59,760
възел в този индекс.

319
00:16:59,760 --> 00:17:03,150
Ние продължаваме да правим, че през
цялата дума, ако приемем,

320
00:17:03,150 --> 00:17:03,950
ние никога не удари нула.

321
00:17:03,950 --> 00:17:07,220
Това означава, че ние бяхме в състояние да се измъкне сам
цялата дума и находката

322
00:17:07,220 --> 00:17:08,920
възел в нашия опит.

323
00:17:08,920 --> 00:17:10,770
Но ние не сме съвсем свършила още.

324
00:17:10,770 --> 00:17:12,290
>> Ние не искаме просто да се върне вярно.

325
00:17:12,290 --> 00:17:14,770
Ние искаме да се върне на курсора> дума.

326
00:17:14,770 --> 00:17:18,980
Тъй като си спомня отново, е "котка" не е
в нашия речник, и "катастрофа"

327
00:17:18,980 --> 00:17:22,935
е, тогава ние ще можем успешно да
чрез думата "кат." Но курсора

328
00:17:22,935 --> 00:17:25,760
Думата ще бъде фалшива и не е вярно.

329
00:17:25,760 --> 00:17:30,930
Така че ние се върнете курсора дума за обозначаване
дали този възел всъщност е дума.

330
00:17:30,930 --> 00:17:32,470
И това е за проверка.

331
00:17:32,470 --> 00:17:34,250
>> Така че нека да се провери размера.

332
00:17:34,250 --> 00:17:37,350
Така размер ще бъде доста лесно
тъй като, не забравяйте, в натоварване, ние сме

333
00:17:37,350 --> 00:17:41,430
увеличаване размера на речник за
всяка дума, която се сблъскваме.

334
00:17:41,430 --> 00:17:45,350
Така размер е просто ще
върнете речник размер.

335
00:17:45,350 --> 00:17:47,390
И това е всичко.

336
00:17:47,390 --> 00:17:50,590
>> Така че най-накрая сме се разтоварят.

337
00:17:50,590 --> 00:17:55,100
Така се разтоварят, отиваме да се използва
рекурсивна функция действително да направим всичко

338
00:17:55,100 --> 00:17:56,530
на работата за нас.

339
00:17:56,530 --> 00:17:59,340
Така че нашата функция ще
бъде повикан за разтоварване.

340
00:17:59,340 --> 00:18:01,650
Какво е за разтоварване смяташ да правиш?

341
00:18:01,650 --> 00:18:06,580
Виждаме тук, че за разтоварване ще се
обхождане на всички деца в

342
00:18:06,580 --> 00:18:08,410
този конкретен възел.

343
00:18:08,410 --> 00:18:11,750
И ако детето възел не е
нула, след това отиваме да

344
00:18:11,750 --> 00:18:13,730
разтоварят дете възел.

345
00:18:13,730 --> 00:18:18,010
>> Така че това е, че рекурсивно разтоварят
всички от нашите деца.

346
00:18:18,010 --> 00:18:21,080
След като ние сме сигурни, че всички наши деца
са били разтоварени, тогава ние

347
00:18:21,080 --> 00:18:25,210
да се освободим, така
разтоварят себе си.

348
00:18:25,210 --> 00:18:29,460
Това ще работи рекурсивно
разтоварят целия TRIE.

349
00:18:29,460 --> 00:18:32,850
И тогава, след като това е направено,
ние може просто да се върне вярно.

350
00:18:32,850 --> 00:18:34,210
Разтоварете не може да се провали.

351
00:18:34,210 --> 00:18:35,710
Ние просто се освобождава неща.

352
00:18:35,710 --> 00:18:38,870
Така че след като сме готови освобождавайки
всичко, върнете вярно.

353
00:18:38,870 --> 00:18:40,320
И това е всичко.

354
00:18:40,320 --> 00:18:41,080
Моето име е Роб.

355
00:18:41,080 --> 00:18:42,426
И това е правопис.

356
00:18:42,426 --> 00:18:47,830
>> [За възпроизвеждане на музика]