1
00:00:00,000 --> 00:00:09,700

2
00:00:09,700 --> 00:00:12,140
>> ZAMYLA Чан: Давайте зробимо
перевірка орфографії.

3
00:00:12,140 --> 00:00:16,900
Якщо ви відкриєте speller.c, то ви побачите,
що більшість функціональних можливостей для

4
00:00:16,900 --> 00:00:20,810
перевірки текстовий файл проти
словник вже зроблено для вас.

5
00:00:20,810 --> 00:00:26,330
. / Правописної, проходячи в словнику тексту
файл, а потім інший текстовий файл,

6
00:00:26,330 --> 00:00:28,960
перевірятиме, що текстовий файл
проти словнику.

7
00:00:28,960 --> 00:00:34,160
>> Тепер, словник текстові файли будуть містити
дійсні слова, по одному в рядку.

8
00:00:34,160 --> 00:00:37,910
Тоді speller.c подзвонить Load
на словника текстового файлу.

9
00:00:37,910 --> 00:00:43,650
Це подзвоню функція називається Перевірка на
кожне слово в введеної текстовий файл,

10
00:00:43,650 --> 00:00:46,460
друк всіх слів з помилками.

11
00:00:46,460 --> 00:00:50,030
>> Speller.c також викличе Розмір для
визначити кількість слів у

12
00:00:50,030 --> 00:00:53,500
словник і викликати вивантаження
щоб звільнити пам'ять.

13
00:00:53,500 --> 00:00:57,600
speller.c також відстежувати, як
скільки часу використовується для проведення з них

14
00:00:57,600 --> 00:01:00,560
процеси, але ми будемо
до цього пізніше.

15
00:01:00,560 --> 00:01:02,440
>> Так що ж ми повинні робити?

16
00:01:02,440 --> 00:01:05,110
Нам потрібно заповнити dictionary.c.

17
00:01:05,110 --> 00:01:09,940
У dictionary.c, у нас є помічник
Функція завантаження, яка завантажує

18
00:01:09,940 --> 00:01:10,855
словник.

19
00:01:10,855 --> 00:01:15,490
Функція Перевірити, який перевіряє, якщо
дане слово є в словнику.

20
00:01:15,490 --> 00:01:19,150
Функція Розмір повертає кількість
слів у словнику.

21
00:01:19,150 --> 00:01:24,870
І, нарешті, ми Вивантаження, які
звільняє словник з пам'яті.

22
00:01:24,870 --> 00:01:27,070
>> Отже, спочатку давайте візьмемося Load.

23
00:01:27,070 --> 00:01:32,110
Для кожного слова у словнику тексту
файл, навантаження буде зберігати ці слова в

24
00:01:32,110 --> 00:01:34,860
словник структура даних
за вашим вибором, або

25
00:01:34,860 --> 00:01:36,750
хеш-таблиці або синтаксичного дерева.

26
00:01:36,750 --> 00:01:39,440
Я піду за як в
це йти через.

27
00:01:39,440 --> 00:01:43,150
>> Спочатку, давайте поговоримо про хеш-таблиці.

28
00:01:43,150 --> 00:01:47,050
Скажімо, у вас було 10 більярдні кулі та
ви хотіли, щоб зберегти їх.

29
00:01:47,050 --> 00:01:50,420
Ви можете помістити їх усіх в відро,
і коли ви потребували специфічного

30
00:01:50,420 --> 00:01:54,010
пронумеровані м'яч, ви б взяти один
з відра в той час

31
00:01:54,010 --> 00:01:55,880
шукає, що м'яч.

32
00:01:55,880 --> 00:01:59,370
І тільки з 10 кульками, ви повинні бути
в змозі знайти свій м'яч в розумний

33
00:01:59,370 --> 00:02:01,160
кількість часу.

34
00:02:01,160 --> 00:02:03,180
>> Але що, якщо у вас було 20 м'ячів?

35
00:02:03,180 --> 00:02:05,480
Це може зайняти трохи більше часу тепер.

36
00:02:05,480 --> 00:02:06,180
А як щодо 100?

37
00:02:06,180 --> 00:02:07,880
1000?

38
00:02:07,880 --> 00:02:11,590
Тепер, було б набагато легше, якщо
у вас було кілька відер.

39
00:02:11,590 --> 00:02:15,890
Може бути, один ківш для куль номер нуль
до дев'яти, ще відро для

40
00:02:15,890 --> 00:02:18,800
куль, пронумерованих від 10 до
19, і так далі.

41
00:02:18,800 --> 00:02:22,330
>> Тепер, коли ви потребували шукати конкретних
м'яч, ви могли б автоматично

42
00:02:22,330 --> 00:02:26,320
перейти до однієї конкретної відро і
пошук через цей відро.

43
00:02:26,320 --> 00:02:29,840
І якщо кожен ківш має приблизно 10
кулі, то ви могли б легко знайти

44
00:02:29,840 --> 00:02:31,790
через нього.

45
00:02:31,790 --> 00:02:34,960
>> Тепер, так як ми маємо справу з
словники, одна ківш для

46
00:02:34,960 --> 00:02:41,970
всі слова в словнику буде
ймовірно, буде занадто мало відра.

47
00:02:41,970 --> 00:02:44,370
Так що давайте поглянемо на хеш-таблиці.

48
00:02:44,370 --> 00:02:46,940
>> Думайте про це як масив відра.

49
00:02:46,940 --> 00:02:50,370
І в цьому випадку, відра
наші зв'язані списки.

50
00:02:50,370 --> 00:02:54,770
І ми будемо поширювати на всі наші слова
серед цих кількох пов'язаних списків в

51
00:02:54,770 --> 00:02:58,940
організовано з використанням хеш-функції,
який покаже, які

52
00:02:58,940 --> 00:03:03,720
відро конкретний ключ, даний
Слово, належить.

53
00:03:03,720 --> 00:03:05,960
>> Давайте представити це схематично.

54
00:03:05,960 --> 00:03:11,320
Сині коробки тут містять значення і
червоні коробки вказують на інше значення

55
00:03:11,320 --> 00:03:12,280
Покажчик пара.

56
00:03:12,280 --> 00:03:14,800
Ми назвемо ці пари вузлів.

57
00:03:14,800 --> 00:03:18,260
Тепер кожен відро, як я вже сказав
раніше, є зв'язаний список.

58
00:03:18,260 --> 00:03:21,820
У зв'язаних списків, кожен вузол має значення,
а також покажчик на

59
00:03:21,820 --> 00:03:23,170
Наступне значення.

60
00:03:23,170 --> 00:03:26,150
>> Тепер справа зі зв'язаними списками,
це дуже важливо, що вам

61
00:03:26,150 --> 00:03:28,120
не втрачати посилання.

62
00:03:28,120 --> 00:03:32,250
І ще один факт, щоб пам'ятати, що
останній вузол, якщо він не вказує на

63
00:03:32,250 --> 00:03:35,120
інший вузол, вказує на нульовий.

64
00:03:35,120 --> 00:03:37,970
>> Так як же ми представляємо це в C?

65
00:03:37,970 --> 00:03:40,540
Ми визначаємо структуру тут.

66
00:03:40,540 --> 00:03:44,850
І цінність у цьому випадку
символ масив довжини.

67
00:03:44,850 --> 00:03:48,880
Довжина плюс 1, де довжина
Максимальна довжина будь-якого слова, плюс 1 для

68
00:03:48,880 --> 00:03:50,380
нульова термінатор.

69
00:03:50,380 --> 00:03:54,210
І тоді у нас є вказівник на
інший вузол називається Наступна.

70
00:03:54,210 --> 00:03:56,730
>> Так давайте зробимо невеликий зв'язаний список.

71
00:03:56,730 --> 00:04:00,390
По-перше, ви хочете, щоб Malloc свій вузол,
які створюють місця в оперативній пам'яті

72
00:04:00,390 --> 00:04:04,010
Розмір вашого типу вузла.

73
00:04:04,010 --> 00:04:06,100
І зробити ще один вузол,
знову mallocing.

74
00:04:06,100 --> 00:04:09,370

75
00:04:09,370 --> 00:04:14,340
>> Тепер, якщо ви хочете, щоб привласнити значення
слово, то ми могли б сказати node1 стрілку

76
00:04:14,340 --> 00:04:18,820
Слово одно "Привіт". Цей оператор стрілка
разименовивает покажчик і

77
00:04:18,820 --> 00:04:20,620
доступ змінні в структуру в.

78
00:04:20,620 --> 00:04:24,330
Таким чином, ми не повинні використовувати обидва
точка і зірка оператор.

79
00:04:24,330 --> 00:04:30,100
>> Так то у мене є node2 стрілка слово одно
"Мир". І там, ці значення

80
00:04:30,100 --> 00:04:33,110
населений в моїх вузлів.

81
00:04:33,110 --> 00:04:38,780
Щоб посилання, я передам в node1
стрілку поруч, доступ до цієї вузла зірку,

82
00:04:38,780 --> 00:04:44,160
що покажчик вузол, дорівнює node2,
вказуючи node1 щоб node2 два.

83
00:04:44,160 --> 00:04:46,360
І там у нас є зв'язаний список.

84
00:04:46,360 --> 00:04:51,480
>> Так, щоб був тільки один зв'язаний список, але
хеш-таблицю цілий масив

85
00:04:51,480 --> 00:04:52,520
зв'язані списки.

86
00:04:52,520 --> 00:04:55,920
Ну, у нас буде той же вузол
структуру, що й раніше.

87
00:04:55,920 --> 00:05:00,140
Але якщо б ми хотіли фактичний хеш-таблицю,
тоді ми можемо просто зробити покажчик вузла

88
00:05:00,140 --> 00:05:01,330
Масив тут.

89
00:05:01,330 --> 00:05:04,940
Наприклад, розмір 500.

90
00:05:04,940 --> 00:05:08,910
>> Тепер зауважте, там збирається бути торгівля
від між розміром вашого

91
00:05:08,910 --> 00:05:11,280
хеш-таблиці і розмір
з ваших пов'язаних списків.

92
00:05:11,280 --> 00:05:15,640
Якщо у вас є дійсно велика кількість
відра, уявляючи того, щоб бігти назад

93
00:05:15,640 --> 00:05:18,230
і вперед в лінії
Тут ви знайдете відро.

94
00:05:18,230 --> 00:05:21,530
Але ви також не хочете невелика кількість
ковшів, бо тоді ми повернулися до

95
00:05:21,530 --> 00:05:26,850
вихідна завдання, як мають
занадто багато кулі в нашій відро.

96
00:05:26,850 --> 00:05:30,480
>> Добре, але де ж наш м'яч?

97
00:05:30,480 --> 00:05:33,150
Ну, ми в першу чергу необхідно
є м'яч, чи не так?

98
00:05:33,150 --> 00:05:39,130
Так що давайте Malloc вузол для кожен
нове слово, що у нас є.

99
00:05:39,130 --> 00:05:42,900
вузол * new_node одно
Танос (SizeOf (вузол)).

100
00:05:42,900 --> 00:05:46,760
>> Тепер, коли у нас є ця структура, ми
може сканувати в, використовуючи функцію

101
00:05:46,760 --> 00:05:51,850
fscanf, рядок з нашого файлу, якщо
що це файл словник, в

102
00:05:51,850 --> 00:05:55,780
new_node стрілка слово, де new_node
стрілка слово є нашим

103
00:05:55,780 --> 00:05:58,110
призначення цього слова.

104
00:05:58,110 --> 00:06:01,900
>> Далі ми хочемо, щоб прояснити, що
Слово використанням хеш-функції.

105
00:06:01,900 --> 00:06:05,860
Хеш-функція приймає рядок
і повертає індекс.

106
00:06:05,860 --> 00:06:09,760
У цьому випадку індекс повинен
бути менше, ніж кількість

107
00:06:09,760 --> 00:06:11,440
відра, що у вас є.

108
00:06:11,440 --> 00:06:14,600
>> Тепер, хеш-функції, коли ви намагаєтеся
щоб знайти той, і створити один з

109
00:06:14,600 --> 00:06:17,890
самостійно, пам'ятайте, що вони
повинні бути детермінованим.

110
00:06:17,890 --> 00:06:22,420
Це означає, що те ж саме значення має
карта до того ж кожен раз, коли ківш

111
00:06:22,420 --> 00:06:23,800
що ви хеш його.

112
00:06:23,800 --> 00:06:25,300
>> Це ніби як бібліотеки.

113
00:06:25,300 --> 00:06:28,560
Коли ви берете книгу, засновану на
автор, ви знаєте, які полки треба

114
00:06:28,560 --> 00:06:31,890
продовжуватися, будь число полку
один, два, або три.

115
00:06:31,890 --> 00:06:36,280
І ця книга завжди буде належати на
або полки один, два, або три.

116
00:06:36,280 --> 00:06:39,460

117
00:06:39,460 --> 00:06:43,810
>> Так що, якщо new_node стрілка слово має
слово зі словника, то

118
00:06:43,810 --> 00:06:47,770
хешування new_node стрілка слово буде
дати нам індекс

119
00:06:47,770 --> 00:06:49,370
відро хеш-таблиці.

120
00:06:49,370 --> 00:06:54,040
А потім ми вставимо це в тому, що
конкретних зв'язаний список позначається

121
00:06:54,040 --> 00:06:56,060
повернутися цінність нашої хеш-функції.

122
00:06:56,060 --> 00:06:59,070
>> Давайте подивимося на прикладі
вставка вузла в

123
00:06:59,070 --> 00:07:01,750
початок пов'язаного списку.

124
00:07:01,750 --> 00:07:06,930
Якщо керівник є покажчиком вузол, який вказує
початок пов'язані

125
00:07:06,930 --> 00:07:12,420
Список та new_node вказує новий
вузол, який ви хочете увійти, просто

126
00:07:12,420 --> 00:07:17,340
присвоєння голову new_node втратить
посилання на решті частини списку.

127
00:07:17,340 --> 00:07:19,330
Таким чином, ми не хочемо, щоб це зробити.

128
00:07:19,330 --> 00:07:22,160
>> Швидше, ми хочемо переконатися, що
що ми тримаємося за кожен

129
00:07:22,160 --> 00:07:23,550
один вузол в нашій програмі.

130
00:07:23,550 --> 00:07:29,560
Так працює new_node стрілку поруч рівності
голова і тодішній глава одно new_node

131
00:07:29,560 --> 00:07:34,470
збереже всі
Посилання і не втратите ні.

132
00:07:34,470 --> 00:07:39,330
>> Але що, якщо ви хочете, щоб ваш список, який буде
упорядковано, тому що, упорядковано пов'язані

133
00:07:39,330 --> 00:07:42,910
Список може бути простіше для
пошук його в подальшому?

134
00:07:42,910 --> 00:07:46,020
Ну, для цього вам потрібно знати
як пройти пов'язаних списків.

135
00:07:46,020 --> 00:07:51,210
>> Для переміщення зв'язаний список, давайте
покажчик вузол, вузол *, в якості

136
00:07:51,210 --> 00:07:54,120
курсор, який вказує, які
вузлу ви на, починаючи

137
00:07:54,120 --> 00:07:55,460
з першого елемента.

138
00:07:55,460 --> 00:08:01,070
НЕ Looping до курсору порожній, ми можемо
здійснювати певні процеси, а потім

139
00:08:01,070 --> 00:08:04,330
переміщення курсору, коли нам потрібно
використовуючи значення стрілкою курсору.

140
00:08:04,330 --> 00:08:08,820
>> Пам'ятайте, що це те ж саме,
кажучи зірка курсор, разименованія

141
00:08:08,820 --> 00:08:13,480
курсор, потім за допомогою
точка значення оператора.

142
00:08:13,480 --> 00:08:19,000
Так оновленні курсор буде, призначивши
курсор стрілка курсору поруч.

143
00:08:19,000 --> 00:08:24,960
>> Припустимо, ви визначили, що D стає в
між С і Е. Щоб вставити вузол,

144
00:08:24,960 --> 00:08:30,030
є D точку new_node до
вузол E, який є поруч курсор.

145
00:08:30,030 --> 00:08:36,409
А потім C, курсор, може вказувати
до D. Таким чином, ви підтримувати список.

146
00:08:36,409 --> 00:08:41,080
Будьте обережні, щоб не втратити свої посилання на
переміщаючи стрілку курсора поруч з D

147
00:08:41,080 --> 00:08:43,929
відразу ж.

148
00:08:43,929 --> 00:08:44,620
>> Добре.

149
00:08:44,620 --> 00:08:48,920
Так от, як ви могли б вставити вузли,
завантажити їх в, навантаження слова в тих

150
00:08:48,920 --> 00:08:51,600
вузли, і вставити їх
в ваш хеш-таблиці.

151
00:08:51,600 --> 00:08:53,580
Так що тепер давайте подивимося на спроб.

152
00:08:53,580 --> 00:08:58,540
>> У вигляді дерева, кожен вузол буде містити
масив вузлів покажчиків, по одному на кожен

153
00:08:58,540 --> 00:09:02,260
буква в алфавіті
плюс апостроф.

154
00:09:02,260 --> 00:09:06,150
І кожен елемент масиву
буде вказувати на інший вузол.

155
00:09:06,150 --> 00:09:10,130
Якщо це вузол є нульовим, то, що лист
не буде слідів літера з

156
00:09:10,130 --> 00:09:15,690
будь-яке слово в послідовності, тому що кожен
слово вказує, чи є це останній

157
00:09:15,690 --> 00:09:18,160
символ слова чи ні.

158
00:09:18,160 --> 00:09:19,750
>> Давайте подивимося на діаграму.

159
00:09:19,750 --> 00:09:22,260
Ми сподіваємося, речі
бути трохи ясніше.

160
00:09:22,260 --> 00:09:27,210
На цій діаграмі ми бачимо, що тільки
деякі букви і деякі підрядка

161
00:09:27,210 --> 00:09:28,190
в даний час перераховані поза.

162
00:09:28,190 --> 00:09:32,500
Таким чином, ви можете слідувати певним шляху, і
всі ці шляхи приведуть вас до

163
00:09:32,500 --> 00:09:34,020
різні слова.

164
00:09:34,020 --> 00:09:37,630
>> Так як же ми представляємо це в C?

165
00:09:37,630 --> 00:09:41,910
Ну, кожен вузол тепер матиме
Логічне значення, яке вказує

166
00:09:41,910 --> 00:09:46,580
що вузол є кінцем
дане слово чи ні.

167
00:09:46,580 --> 00:09:50,690
А потім також будете мати масив
вузол покажчиків звані діти, і

168
00:09:50,690 --> 00:09:53,440
там будуть 27 з них.

169
00:09:53,440 --> 00:09:56,510
І пам'ятайте, ви також хочете, щоб
стежити за своїм першим вузлом.

170
00:09:56,510 --> 00:09:59,830
Ми збираємося викликати цей корінь.

171
00:09:59,830 --> 00:10:01,690
>> Так от структура вигляді дерева.

172
00:10:01,690 --> 00:10:05,630
Як ми представляємо цей
в якості словника?

173
00:10:05,630 --> 00:10:09,890
Ну, для завантаження слова в, для кожного
словник слово, ви будете хотіти,

174
00:10:09,890 --> 00:10:11,960
для перебору синтаксичного дерева.

175
00:10:11,960 --> 00:10:16,170
І кожен елемент в дітях
відповідає різному письма.

176
00:10:16,170 --> 00:10:21,660
>> Так перевірки значення у дітей
Індекс г, де я представляє

177
00:10:21,660 --> 00:10:24,840
питомий показник листа, який
Ви намагаєтеся вставити.

178
00:10:24,840 --> 00:10:28,980
Ну, якщо це нуль, то ви хочете, щоб
Malloc новий вузол і мати дітей

179
00:10:28,980 --> 00:10:31,110
Я вказую на цьому вузлі.

180
00:10:31,110 --> 00:10:35,630
>> Якщо це не нуль, то це означає, що
що дана галузь, що, враховуючи

181
00:10:35,630 --> 00:10:37,350
подстрока, вже існує.

182
00:10:37,350 --> 00:10:40,160
Так то ви будете просто рухатися до того, що
Новий вузол і продовжити.

183
00:10:40,160 --> 00:10:43,220
Якщо ви в кінці слова, що
Ви намагаєтеся завантажити в

184
00:10:43,220 --> 00:10:48,120
словник, то ви можете встановити, що
поточний вузол, що ви перебуваєте на до істини.

185
00:10:48,120 --> 00:10:51,550
>> Отже, давайте поглянемо на приклад вставки
слово «лисиця» в нашу

186
00:10:51,550 --> 00:10:53,070
словник.

187
00:10:53,070 --> 00:10:56,110
Уявіть, що ми починаємо з
порожній словник.

188
00:10:56,110 --> 00:11:01,610
Перша буква, Ж, розташовуватиметься
в дитячому індексу п'ять з коріння

189
00:11:01,610 --> 00:11:03,700
діти масив.

190
00:11:03,700 --> 00:11:05,430
Таким чином, ми вставити, що дюйма

191
00:11:05,430 --> 00:11:14,610
>> Буква О тоді буде у дітей
індекс 15, після цього F. А потім X

192
00:11:14,610 --> 00:11:20,180
буде ще нижче, що, розгалуження
від дітей Виходів.

193
00:11:20,180 --> 00:11:24,120
А потім, бо X є остання буква
слова "лиса", то я збираюся

194
00:11:24,120 --> 00:11:27,210
колір, що зелений, показуючи, що
це кінець слова.

195
00:11:27,210 --> 00:11:32,880
У C, які будуть налаштування ІС
Слово Boolean зі значенням істинною.

196
00:11:32,880 --> 00:11:36,780
>> А що, якщо наступне слово, що ти
вантаження в це слово "Foo"?

197
00:11:36,780 --> 00:11:41,490
Ну, вам не потрібно, щоб Malloc більше
простір для F або O, тому

198
00:11:41,490 --> 00:11:42,990
тих, хто вже існує.

199
00:11:42,990 --> 00:11:45,910
Але останній висновок в Foo?

200
00:11:45,910 --> 00:11:47,320
Це один, вам доведеться Танос.

201
00:11:47,320 --> 00:11:52,390
Створіть новий вузол для того, установка
це Слово Логічне до істини.

202
00:11:52,390 --> 00:11:57,340
>> А тепер давайте вставити "собаку". Собака буде
почати з індексом три коренів

203
00:11:57,340 --> 00:12:00,520
діти, тому що D не
створена.

204
00:12:00,520 --> 00:12:04,990
І ми будемо слідувати аналогічний процес, як
перш, створюючи підрядок собаку,

205
00:12:04,990 --> 00:12:10,400
де ж G пофарбована в зелений колір, тому що
це кінець слова.

206
00:12:10,400 --> 00:12:13,160
>> Тепер, що якщо ми хочемо, щоб вставити "робити"?

207
00:12:13,160 --> 00:12:17,150
Ну, це підрядок собаки, тому
ми не повинні Malloc більше.

208
00:12:17,150 --> 00:12:20,800
Але ми повинні вказати, де ми
підійшов до кінця цього слова.

209
00:12:20,800 --> 00:12:24,020
Так O буде забарвлений в зелений колір.

210
00:12:24,020 --> 00:12:27,810
Продовжуючи цей процес для кожного окремого
слово в словнику, ви,

211
00:12:27,810 --> 00:12:32,120
завантажив їх у в Або Ваш
хеш-таблиці або ваш синтаксичного дерева.

212
00:12:32,120 --> 00:12:37,530
>> speller.c пройде в рядках для
dictionary.c, щоб перевірити їх.

213
00:12:37,530 --> 00:12:41,140
Тепер Перевірити функція повинна працювати
під нечутливості до регістру.

214
00:12:41,140 --> 00:12:45,980
Це означає, що великі літери і
малі літери і поєднання того й іншого

215
00:12:45,980 --> 00:12:50,670
всі повинні прирівняти до вірно, якщо будь-яка
Поєднання тобто в

216
00:12:50,670 --> 00:12:51,880
словник.

217
00:12:51,880 --> 00:12:55,580
Можна також припустити, що рядки
тільки збирається містити алфавітний

218
00:12:55,580 --> 00:12:58,200
символів або апострофа.

219
00:12:58,200 --> 00:13:02,490
>> Отже, давайте поглянемо на те, як ви можете перевірити
зі структурою хеш-таблиці.

220
00:13:02,490 --> 00:13:07,330
Ну, якщо слово існує, то він
можна знайти в хеш-таблиці.

221
00:13:07,330 --> 00:13:12,240
Тоді ви можете спробувати знайти, що
слово у відповідному відрі.

222
00:13:12,240 --> 00:13:14,480
>> Отже, які відро б, що слово бути в?

223
00:13:14,480 --> 00:13:20,060
Ну, ви отримаєте номер, що індекс
ковша, шляхом хеширования це слово

224
00:13:20,060 --> 00:13:23,690
а потім шукати в цьому пов'язаному списку,
обході через весь

225
00:13:23,690 --> 00:13:28,060
зв'язаний список, використовуючи рядок
Функція порівняння.

226
00:13:28,060 --> 00:13:31,940
>> Якщо кінець зв'язаного списку є
досягли, а це означає, що курсор

227
00:13:31,940 --> 00:13:36,030
досягає нульової, то слова не
можна знайти в словнику.

228
00:13:36,030 --> 00:13:39,090
Це не буде в будь-якому іншому відрі.

229
00:13:39,090 --> 00:13:43,020
Так от, ви можете побачити, як там могли б
бути компроміс між наявністю або

230
00:13:43,020 --> 00:13:46,280
Починаючи пов'язані списки або непідібране ті.

231
00:13:46,280 --> 00:13:51,180
Або займе більше часу, протягом
завантажити або більше разів під час перевірки.

232
00:13:51,180 --> 00:13:53,560
>> Як ви могли б перевірити в
синтаксичного дерева структура?

233
00:13:53,560 --> 00:13:56,370
Ми збираємося подорожувати вниз
в синтаксичного дерева.

234
00:13:56,370 --> 00:14:00,390
Для кожної букви в введеного слова
що ми перевіряємо, ми підемо в тому, що

235
00:14:00,390 --> 00:14:03,280
Відповідний елемент у дітей.

236
00:14:03,280 --> 00:14:07,770
>> Якщо цей елемент є порожнім, то це означає,
що немає підрядка

237
00:14:07,770 --> 00:14:11,110
містить нашу вхідне слово, так
слово написано з помилками.

238
00:14:11,110 --> 00:14:15,140
Якщо це не нуль, ми можемо перейти до
наступна буква слова, що ми знаходимося

239
00:14:15,140 --> 00:14:18,850
перевірки і продовжувати цей процес
поки ми не досягнемо кінця

240
00:14:18,850 --> 00:14:20,350
з вхідного слова.

241
00:14:20,350 --> 00:14:23,330
І тоді ми можемо перевірити
Якщо Слово істинне.

242
00:14:23,330 --> 00:14:24,610
Якщо це так, то це здорово.

243
00:14:24,610 --> 00:14:25,590
Слово це правильно.

244
00:14:25,590 --> 00:14:30,890
Але якщо ні, незважаючи на те, що подстрока
існує в синтаксичного дерева, це слово

245
00:14:30,890 --> 00:14:32,250
неправильно.

246
00:14:32,250 --> 00:14:36,590
>> Коли функція Розмір називається, розмір
повинен повернути кількість слів, які

247
00:14:36,590 --> 00:14:39,110
у вашому даного словника
Структура даних.

248
00:14:39,110 --> 00:14:42,780
Так що якщо ви використовуєте хеш-таблицю, ви
може або пройти кожен

249
00:14:42,780 --> 00:14:45,860
Зв'язаний список в кожен
відро підрахунку кількості

250
00:14:45,860 --> 00:14:47,130
слів там.

251
00:14:47,130 --> 00:14:49,940
Якщо ви використовуєте синтаксичного дерева, ви можете
пройти через кожного не нуль

252
00:14:49,940 --> 00:14:52,030
Шлях у вашому синтаксичного дерева.

253
00:14:52,030 --> 00:14:56,420
Або в той час як ви завантажуєте словник
в, може бути, ви можете відстежувати, як

254
00:14:56,420 --> 00:14:58,760
багато слів ви завантажуєте дюйма

255
00:14:58,760 --> 00:15:03,180
>> Після speller.c закінчується перевірка
текстовий файл проти словника, то

256
00:15:03,180 --> 00:15:08,010
це робиться і так вона називає вивантажити, де
ваша робота полягає в звільненні нічого

257
00:15:08,010 --> 00:15:09,500
що ви malloced.

258
00:15:09,500 --> 00:15:14,420
Так що якщо ви використовуєте хеш-таблицю, то ви
повинні бути особливо обережні, щоб уникнути

259
00:15:14,420 --> 00:15:18,830
витоку пам'яті по які звільняючи нічого
передчасно і тримаючись кожен

260
00:15:18,830 --> 00:15:20,780
одна ланка, перш ніж безкоштовно.

261
00:15:20,780 --> 00:15:24,680

262
00:15:24,680 --> 00:15:30,100
>> Таким чином, для кожного елемента в хеш-таблиці
і для кожного вузла в зв'язаний список,

263
00:15:30,100 --> 00:15:32,370
ви хочете, щоб звільнити цей вузол.

264
00:15:32,370 --> 00:15:34,970
Як ви про звільнення
зв'язаний список?

265
00:15:34,970 --> 00:15:38,570
Установка вашого вузла покажчика курсора
голова, до початку

266
00:15:38,570 --> 00:15:43,100
зв'язаний список, то в той час як курсор
не є нульовим, ви можете встановити тимчасовий

267
00:15:43,100 --> 00:15:45,610
вузол покажчик на курсор.

268
00:15:45,610 --> 00:15:48,370
Тоді переміщення курсору.

269
00:15:48,370 --> 00:15:52,950
І тоді ви можете завантажити, що тимчасове
значення в той же час тримаючись за

270
00:15:52,950 --> 00:15:55,650
все потім.

271
00:15:55,650 --> 00:15:57,800
>> Що робити, якщо ви використовуєте синтаксичного дерева?

272
00:15:57,800 --> 00:16:00,410
Тоді найкращий спосіб зробити це
це вивантажити з дуже

273
00:16:00,410 --> 00:16:02,290
знизу вгору.

274
00:16:02,290 --> 00:16:06,920
Подорожуючи за найнижчою можливою
вузол, ви можете завантажити всі покажчики в

275
00:16:06,920 --> 00:16:11,430
що діти, а потім повернутися
вгору, звільняючи всі елементи у всіх

276
00:16:11,430 --> 00:16:15,610
не з дітей масивів, поки
ви потрапляєте верхню кореневої вузол.

277
00:16:15,610 --> 00:16:18,920
Ось де Рекурсія
знадобиться.

278
00:16:18,920 --> 00:16:22,780
>> Щоб переконатися, що ви, мабуть, звільнені
все, що ви malloced,

279
00:16:22,780 --> 00:16:24,400
Ви можете використовувати Valgrind.

280
00:16:24,400 --> 00:16:28,640
Запуск Valgrind буде запустити програму
вважаючи, скільки байт пам'яті

281
00:16:28,640 --> 00:16:32,440
ви використовуєте і переконавшись, що у Вас є
звільнив їх усіх, кажу вам,

282
00:16:32,440 --> 00:16:34,530
де ви, можливо,
забули безкоштовно.

283
00:16:34,530 --> 00:16:38,390
Так біжіть, і як тільки Valgrind говорить вам
і дає вам йти вперед, то

284
00:16:38,390 --> 00:16:41,160
Ви закінчили вивантаження.

285
00:16:41,160 --> 00:16:44,420
>> Тепер кілька порад, перш ніж ви йдете
від і почати реалізацію вашого

286
00:16:44,420 --> 00:16:46,260
словник.

287
00:16:46,260 --> 00:16:49,650
Я б рекомендував пройти в меншому
словник, коли ви намагаєтеся, щоб перевірити

288
00:16:49,650 --> 00:16:52,620
речі і налагодження за ВВП.

289
00:16:52,620 --> 00:16:58,550
Використання правопису є. / Правописної,
опціонально словник, а потім текст.

290
00:16:58,550 --> 00:17:01,550
>> За замовчуванням, він завантажує в
великий словник.

291
00:17:01,550 --> 00:17:06,670
Таким чином, ви, можливо, захочете пройти в малому
словник, або, можливо, навіть зробити свій

292
00:17:06,670 --> 00:17:11,819
самостійно, налаштувавши словник
і текстовий файл.

293
00:17:11,819 --> 00:17:15,950
>> І, нарешті, я також рекомендував би
взяти ручку і папір і малювати

294
00:17:15,950 --> 00:17:20,490
речі до, під час, і після
ви написали весь код.

295
00:17:20,490 --> 00:17:24,170
Просто переконайтеся, що у вас є
ці покажчики в самий раз.

296
00:17:24,170 --> 00:17:26,480
>> Я бажаю вам успіху.

297
00:17:26,480 --> 00:17:29,690
І як тільки ви закінчили, якщо ви хочете
щоб кинути виклик велику раду і

298
00:17:29,690 --> 00:17:34,390
бачити, як швидко ваша програма в порівнянні з
, То я закликаю своїх однокласників

299
00:17:34,390 --> 00:17:35,960
Ви перевірити це.

300
00:17:35,960 --> 00:17:39,220
>> При тому, що ви закінчили
орфографії PSet.

301
00:17:39,220 --> 00:17:41,800
Мене звуть Zamyla, і це CS50.

302
00:17:41,800 --> 00:17:49,504