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

2
00:00:00,530 --> 00:00:03,070
>> Выступоўца 1: Давайце дамо
гэта рашэнне паспрабаваць.

3
00:00:03,070 --> 00:00:07,130
Такім чынам, давайце паглядзім, што наш
Структура, вузел будзе выглядаць.

4
00:00:07,130 --> 00:00:11,040
Тут мы бачым, што мы збіраемся мець
Bool Слова і 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
індэкс, які адпавядае літары
С. Так што было б індэкс два.

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
Слова мяркуецца паказаць, ці з'яўляецца
гэта дадзенае слова на самой справе слова.

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
паспяхова праглядаць індэксаў
З-А-Т і дасягнуць вузел, але гэта

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 Слова выкарыстоўваецца ці пазначаюць
гэта асаблівая размяшчэнне фактычна

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
Так нагрузкі збіраецца вяртаць 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
як функцыя Malloc, за выключэннем, што гэта
гарантавана вярнуць тое, што з'яўляецца

48
00:02:45,560 --> 00:02:47,240
цалкам абнуляецца.

49
00:02:47,240 --> 00:02:51,350
Так што, калі мы выкарыстоўвалі Malloc, мы павінны былі б
прайсці праз усе ўказальнікі ў нашай

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
>> Цяпер, гэтак жа, як Malloc, мы павінны зрабіць
упэўнены, што вылучэнне на самай справе

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
зоркі курсора для ітэрацыі
праз нашу Trie.

58
00:03:14,340 --> 00:03:17,950
Такім чынам, наш корань ніколі не збіраецца мяняць,
але мы збіраемся выкарыстоўваць курсор ў

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
алфавітны становішча з, так што калі
з літарай А, гэтая воля

78
00:04:27,470 --> 00:04:28,770
даць нам нулявы індэкс.

79
00:04:28,770 --> 00:04:32,180
Для лісты B, гэта дало б
нам індэкс 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
>> Мы хочам, каб усталяваць, што да Праўда, такім чынам, каб
паказвае, што гэты вузел паказвае

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
Яна вяртае Праўда, калі гэта слова, што гэта
перадаецца ў нашай 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
індэкс ў масіве дзяцей, што
адпавядае слова кранштэйна I.

130
00:07:29,280 --> 00:07:34,150
Так што гэта будзе выглядаць гэтак жа, як
Нагрузка, дзе, калі слова кранштэйны я з'яўляецца

131
00:07:34,150 --> 00:07:38,110
апостраф, то мы хочам выкарыстоўваць індэкс
алфавіт мінус 1, таму што мы вызначылі

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
слова кошка, але курсор слова
будзе Хлусня і няпраўда.

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
>> Дык давайце праверым Памер.

158
00:09:08,310 --> 00:09:11,410
Так Памер будзе даволі лёгка
так, памятаеце, у Load, мы

159
00:09:11,410 --> 00:09:15,480
павялічваючы памер слоўніка для
кожнае слова, што мы сутыкаемся з.

160
00:09:15,480 --> 00:09:20,820
Так Памер толькі збіраецца вярнуцца
памер слоўніка, і вось яно што.

161
00:09:20,820 --> 00:09:24,650
>> Добра, нарэшце, у нас ёсць Unload.

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
можа вызваліцца, таму разгрузіць OURSELF.

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
Таму, як толькі мы скончым вызваляючы
ўсё, вярнуцца Праўда.

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