1
00:00:00,000 --> 00:00:12,350
>> [Музика грає]

2
00:00:12,350 --> 00:00:13,050
>> ROB BOWDEN: Привет.

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
>> А потім наш хеш в кожному
відро збирається зберігати

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
ОК.

17
00:00:51,110 --> 00:00:53,090
Так ось що вузол виглядає.

18
00:00:53,090 --> 00:00:56,180
>> Тепер ось декларація
нашої хеш-таблиці.

19
00:00:56,180 --> 00:00:59,640
Це матиме 16834 відер.

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
>> Ми збираємося відкрити потік,
словник для читання.

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
>> І тепер ми збираємося
Malloc один вузол.

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 збирається повертати 1, до тих пір,
, Як це було в змозі успішно

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
не поверне 1.

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
індекс у хеш-таблиці.

63
00:03:14,490 --> 00:03:18,530
>> Зверніть увагу, що ми Moding по NUM_BUCKETS,
так що значення, повернене

64
00:03:18,530 --> 00:03:21,730
насправді є індексом в хеш-таблиці
і не індексує за

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
вступ до хеш-таблиці.

70
00:03:33,750 --> 00:03:38,520
>> Тепер хеш хеш поточний
пов'язано список в таблиці.

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
І таким чином ми будемо мати нашу ток
Точка входу до того, що хеш-таблиця

74
00:03:48,600 --> 00:03:50,380
В даний час вказує.

75
00:03:50,380 --> 00:03:53,310
А потім ми збираємося зберігати,
в хеш-таблиці на

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
Зв'язаний список за цим індексом
в хеш-таблиці.

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
хеш, і, нарешті, зламати.

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
Так що тепер перевірити, враховуючи завантажений хеш,
буде виглядати наступним чином.

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
Так що, якщо він знаходиться в словнику,
якщо він знаходиться в нашій хеш-таблиці,

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
Ми успішно знайшли
Слово в нашій хеш-таблиці.

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
ми повернутися помилковим, щоб вказати, що наш
хеш не містять це слово.

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
змінний розмір хеш.

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
І для кожного зв'язаного списку в нашому
хеш, ми збираємося циклу по

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
Ми зробимо це для всіх пов'язаний
Списки в хеш-таблиці.

160
00:08:15,620 --> 00:08:19,460
І як тільки ми закінчимо з цим, ми
повністю розвантажили хеш-таблицю, і

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
>> Тепер згадайте, як синтаксичного дерева
насправді працює.

174
00:08:54,710 --> 00:08:59,380
Скажімо ми індексації слово
"Кішки". Тоді з кореня синтаксичного дерева,

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
збирається успішно переглядати
індекси С-А-Т в області вузла.

190
00:09:59,970 --> 00:10:04,290
Але це тільки тому, що катастрофа
відбулося створити вузли на шляху

191
00:10:04,290 --> 00:10:07,190
від С-А-Т, аж до
кінець слова.

192
00:10:07,190 --> 00:10:12,020
Так BOOL слово використовується, щоб вказати,
це особливе розташування

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
Так що тепер ми знаємо, що це синтаксичного дерева є
буде виглядати, давайте подивимося на

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
Це вершина нашого синтаксичного дерева, що ми
буде ітерації.

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
курсор для перебору нашого синтаксичного дерева.

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
Так що пам'ятайте порівнянні з раніше р-наборів,
с - а даватиме нам

245
00:12:49,030 --> 00:12:53,410
алфавітний позиція С. Так що якщо
З буква А, це буде

246
00:12:53,410 --> 00:12:54,700
дати нам нульовий індекс.

247
00:12:54,700 --> 00:12:58,120
Для письма B, це дасть
нам індекс 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
Ми хочемо, щоб скинути нашу курсор до точки
на початку синтаксичного дерева знову.

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
побудови нових вузлів в нашій синтаксичного дерева і
для кожного слова в словнику, до

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
успішно завантажений словник
в нашій синтаксичного дерева.

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
Це повертає істину, якщо це слово, що це
передається в нашій синтаксичного дерева.

291
00:15:29,680 --> 00:15:32,110
Це повертає брехня в іншому випадку.

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

293
00:15:36,050 --> 00:15:40,190
>> Ми бачимо тут, що, як і раніше,
ми збираємося використовувати курсор для перебору

294
00:15:40,190 --> 00:15:41,970
через нашу синтаксичного дерева.

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
>> Решту ми збираємося використовувати два нижніх слово
Кронштейн І. Так що пам'ятайте, що слово може

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
більше не може продовжувати ітерації
вниз нашого синтаксичного дерева.

310
00:16:34,990 --> 00:16:38,870
Якщо це так, то це слово не може
можливо, буде в нашому синтаксичного дерева.

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
Це буде працювати рекурсивно
вивантажити весь синтаксичного дерева.

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
>> [Музика грає]