>> Выступающий 1: Давайте дадим это решение попробовать.
Итак, давайте посмотрим, что наш Структура, узел будет выглядеть.
Здесь мы видим, что мы собираемся иметь Bool Слово и Struct узел звезды
Дети скобки алфавит.
Так первое, что вы можете быть удивлены,, почему алфавит хэш определяется как 27?
Ну, помните, что мы собираемся нужно быть обработки апостроф, так
что будет своего рода специальный место всюду этой программы.
>> Хорошо, теперь, вспомните, как Trie на самом деле работает.
Скажем мы индексации слова кошек, затем от корня нашего Trie,
мы будем смотреть на детей Массив, и мы будем смотреть на
индекс, который соответствует букве С. Так что было бы индекс два.
Поэтому, учитывая, что, что даст нам новый узел, а затем мы будем
работать с этим узлом.
>> Поэтому, учитывая, что узел, мы в очередной раз будем смотреть на массиве детей,
и мы будем смотреть на нулевой индекс чтобы соответствовать А в кот.
Итак, мы собираемся пойти на этот узел, и учитывая, что узел, мы собираемся
смотреть на индекс, который соответствует Т. и перейти к этому узлу,
наконец, мы полностью посмотрел через нашу слова Cat, а теперь Bool
Слово предполагается указать, является ли это данное слово на самом деле слово.
>> Так почему же мы должны, что частный случай?
Ну, что, если слово катастрофа находится в нашем словаре, но
слово кошка не является?
Таким образом, в смотрел, если слово кошка в нашем словаре, мы собираемся
успешно просматривать индексов С-А-Т и достичь узел, но это
только потому, что катастрофа произошла в создать узлы на пути из C-A-T все
вплоть до конца слова.
Так Bool Слово используется указывают ли это особое расположение фактически
указывает на слово.
>> Ладно, так что теперь, когда мы знаем, что Trie собирается выглядеть, давайте посмотрим
в функции Load.
Так нагрузки собирается возвращать Bool для того мы успешно или
безуспешно загружалась словарь и это будет словарь
что мы хотим загрузить.
Так первое, что мы собираемся сделать, это открыть до этого словаря для чтения.
Мы должны убедиться, что мы не преминул, поэтому, если словарь не был
успешно открыт, то он вернет Нет, в каком случае мы собираемся
вернуться False.
Но если предположить, что он успешно открыл, то мы можем на самом деле читать
через словаре.
>> Так первое, что мы собираемся хочу сделать, это у нас есть это
глобальная переменная корень.
Теперь, корень будет узел звезда.
Это вершина нашей Trie, что мы будет итерации.
Так первое, что мы собираемся хотите сделать, это выделить память для нашего корня.
>> Обратите внимание, что мы используем Calloc Функция, которая в основном то же самое
как функция Malloc, за исключением, что это гарантированно вернуть то, что является
полностью обнуляется.
Так что, если мы использовали Malloc, мы должны были бы пройти через все указатели в нашей
узел и убедитесь, что они все нуль.
Так Calloc сделает это за нас.
>> Теперь, так же, как Malloc, мы должны сделать уверен, что выделение на самом деле
успешным.
Если это возвращается нуль, то нужно закрыть наш словарь
файл и вернуть False.
Так предполагая распределение было успешно, мы собираемся использовать узел
звезды курсора для итерации через нашу Trie.
Таким образом, наш корень никогда не собирается менять, но мы собираемся использовать курсор в
на самом деле идти от узла к узлу.
>> Ладно, так что в этом для цикла, мы читать через файл словаря,
и мы используем в fgetc.
Так fgetc собирается захватить один персонаж из файла.
Мы собираемся продолжить захват символов в то время как мы не доходят
конец файла, так что есть два случая, которые мы должны справиться.
Первый, если персонаж не был Новая линия, поэтому мы знаем, если это был новый
линия, то мы собираемся перейти к новым словом.
Но если предположить, что это не было новой линии, то здесь, мы хотим выяснить,
Индекс мы собираемся индекса в в массиве детей, что
мы смотрели на перед.
>> Так как я уже говорил, мы должны Особый случай апостроф.
Обратите внимание, что мы с трехзначным оператором здесь, так что мы собираемся читать
это как если персонаж мы читаем, был апостроф, то мы собираемся
установить индекс, равный алфавита минус 1, который будет индекс 26.
В противном случае, если это не было апостроф, затем мы собираемся установить индекс
равна с минус.
Так что помните назад от предыдущих наборов р, с минус собирается дать нам
алфавитный положение с, так что если с буквой А, эта воля
дать нам нулевой индекс.
Для письма B, это дало бы нам индекс 1, и так далее.
>> Так что это дает нам индекс в Дети массив, который мы хотим.
Теперь, если этот показатель в настоящее время нулевой в массив Дети, что означает, что
узел настоящее время не существует от что путь, так что мы должны выделить
узел для этого пути.
Это то, что мы делаем здесь.
Таким образом, мы собираемся, опять же, использовать Calloc Функция, чтобы мы не должны
обнулить все указатели, и мы, опять же, нужно проверить, что Calloc
не провалился.
Если Calloc ничего не получится, то мы должны выгрузить все, закрываем
словарь, и вернуть False.
>> Так предполагая, что он не преминул, то это создаст нового ребенка для нас,
а затем мы пойдем в этого ребенка.
Наша курсор итерации до этого ребенка.
Теперь, если это не было пустой для начала, то курсор можно просто перебрать
до этого ребенка, фактически не того, чтобы выделить ничего.
Это тот случай, когда мы впервые произошло выделить слово кошку, и
это означает, что, когда мы идем выделить катастрофа, нам не нужно создавать
узлы для C-A-T снова.
Они уже существуют.
>> Итак, что же это за остальное?
Это состояние, при котором кондиционер был косая черта п, где кондиционер был новая линия.
Это означает, что мы успешно завершила слово.
Теперь, что мы хотим сделать, когда мы успешно завершила слово?
Мы собираемся использовать это поле слово внутри нашего Struct узла.
>> Мы хотим, чтобы установить, что к Правда, таким образом, чтобы указывает, что этот узел указывает
успешным слово актуальной слово.
Теперь установите, что Истина.
Мы хотим, чтобы сбросить нашу курсор к точке в начале Trie снова.
И, наконец, увеличить наш словарь Размер так как мы нашли еще одно слово.
>> Ладно, так что мы собираемся продолжать делать что, читая характер по
характер, построения новых узлов в наша Trie и для каждого слова в
словарь, пока мы наконец не достигнет гр равно EOF, в этом случае, мы нарушаем
из файла.
Теперь, есть два случая под которые мы могли бы попасть EOF.
Первый, если произошла ошибка чтение из файла, так что если не было
об ошибке, мы должны сделать типичный выгрузить все, закройте файл,
вернуться False.
Предполагая, что не было ошибок, которые просто означает, что мы на самом деле попал в конце
файл, в каком случае, мы закрываем файл и вернуться Правда, так как мы
успешно загружен словарь в нашей Trie.
>> Ладно, так что теперь давайте Выезд Заезд.
Глядя на проверки функции, мы видим, что Проверить собирается возвращать Bool.
Она возвращает Правда, если это слово, что это передается в нашей Trie.
Она возвращает значение False в противном случае.
>> Так как мы собираемся определить, является ли это слово в нашем Trie?
Мы видим здесь, что, как и раньше, мы собираемся использовать курсор для перебора
через нашу Trie.
Теперь, вот, мы собираемся итерации над всем нашим словом.
Так итерации слова мы прошло, мы собираемся определить
индекс в массиве детей, что соответствует слово кронштейна I.
Так что это будет выглядеть так же, как Нагрузка, где, если слово кронштейн я является
апостроф, то мы хотим использовать индекс алфавит минус 1, потому что мы определили
то есть, куда мы идем для хранения апострофы.
>> Остальное мы собираемся использовать ToLower Слово кронштейн я.
Так что помните, что слово может иметь произвольное капитализация, и поэтому мы
хотите, чтобы убедиться, что мы используем строчной версией вещей.
А потом вычесть из этой нижнем регистре чтобы, опять же, дают нам
алфавитный положение из этого символа.
Так что это будет наш индекс в массиве детей.
>> И теперь, если что индекс в интересах детей Массив является пустым, что означает, что мы
больше не может продолжать итерации вниз нашей Trie.
Если это так, то это слово не может возможно, будет в нашем Trie, так как, если он
были, это будет означать, что будет Путь вниз к этому слову, и вы бы
никогда не сталкиваются нуль.
Так встречая нуль, мы возвращаемся False.
Слово отсутствует в словаре.
Если бы не нуль, то мы собираемся продолжение итераций, так что мы собираемся
обновить наш курсор, чтобы указать на что конкретный узел по этому индексу.
>> Таким образом, мы продолжать делать это на протяжении все слово.
Предположим, что мы никогда не ударил нуль, что означает мы смогли пройти через весь
мир и найти узел в нашем Trie, но мы еще не закончили еще.
Мы не хотим, чтобы просто вернуть True.
Мы хотим вернуться курсора ошибке слово так, помните, опять же, если кошка не
в наш словарь и катастрофа, тогда мы будем успешно пройти
слово кошка, но курсор слово будет Ложь и неправда.
Так мы возвращаемся курсора слово для обозначения ли этот узел на самом деле слово,
и вот оно что для проверки.
>> Так давайте проверим Размер.
Так Размер будет довольно легко так, помните, в Load, мы
увеличивая размер словаря для каждое слово, что мы сталкиваемся с.
Так Размер только собирается вернуться размер словаря, и вот оно что.
>> Ладно, наконец, у нас есть Unload.
Так выгрузка, мы собираемся использовать рекурсивная функция на самом деле делать все
работы для нас, поэтому нашей функции собирается назвать Разгрузчик.
Что Разгрузчик собираетесь делать?
Мы видим здесь, что Разгрузчик собирается перебора всех детей в
этот конкретный узел, и если ребенок узел не является нулевым, то мы собираемся
выгрузить дочерний узел.
>> Так это будет рекурсивно выгрузить все наши дети.
После того, как мы уверены, что все наши дети были выгружены, то мы
может освободиться, поэтому разгрузить OURSELF.
Так что это будет рекурсивно выгрузить Весь Trie, а затем один раз это
сделано, мы можем просто вернуть True.
Выгрузка не может потерпеть неудачу, мы просто освобождая вещи.
Поэтому, как только мы закончим освобождая все, вернуться Правда.
И это все.
Меня зовут Боб, и это был [неразборчиво].