[Музыка играет] 

ROB BOWDEN: Привет. Я Роб. И давайте это решение вне. И вот мы собираемся реализовать Общая таблица. Мы видим, что структура узел Наши таблица будет выглядеть следующим образом. Так что это будет иметь сЬаг слово Массив Размер + 1. Не забывайте, + 1, поскольку максимальная слово в словаре 45 символов. А потом мы собираемся нужно один дополнительный символ для нуля обратной косой. 

А потом наш хеш в каждом ведро собирается хранить связанный список узлов. Мы не делаем линейную зондирования здесь. И поэтому для того, чтобы связать к следующему элемент в ведро, мы должны структура узла * следующий. ОК. Так вот что узел выглядит. 

Теперь вот декларация нашей хэш-таблице. Это будет иметь 16 834 ведер. Но это число не имеет значения. И, наконец, мы собираемся иметь глобальная переменная размер хеш, который собирается начать как ноль. И это будет отслеживать, как много слов в нашем словаре. 

Так что давайте взглянем на нагрузке. Обратите внимание, что нагрузки, она возвращает логическое значение. Вы возвращаетесь верно, если это было успешно загружены, и в противном случае. И это занимает константный символ * словарь, который является словарь что мы хотим открыть. Так вот первое, что мы собираемся сделать. 

Мы собираемся открыть поток, словарь для чтения. И мы собираемся иметь, чтобы сделать уверен, что это удалось. Так что, если он вернулся NULL, то мы не сделали успешно открыть словарь. И мы должны вернуться ложным. Но если предположить, что это было успешно открыто, то мы хотим, чтобы прочитать словарь. Так что держите цикл, пока не найдем некоторые Причина, чтобы вырваться из этого цикла, которые мы увидим. Так что держите цикла. 

И теперь мы собираемся Malloc один узел. И, конечно, мы должны проветривать проверьте еще раз. Так что если mallocing не удалось, то мы хотим, чтобы разгрузить любой узел, который мы случилось с таНос раньше, закрыть словарь и вернуться ложным. Но игнорируя, что, предполагая, что мы удалось, то мы хотим использовать fscanf читать ни одного слова из нашего словарь в нашу узла. Так что помните, что вступление> слово является символ Слово буфер размером Lenghth + 1 что мы собираемся хранить слово дюйма 

Так fscanf собирается возвращать 1, до тех пор, , как это было в состоянии успешно прочитать слово из файла. Если один происходит ошибка, или мы дойдете до конца файла, то не вернет 1. В этом случае он не возвращает 1, мы, наконец, собирается вырваться из это в то время как петля. Итак, мы видим, что как только у нас есть успешно читать слово в запись> слово, то, что мы собираемся, что слово с помощью нашего хэш-функцию. 

Давайте взглянем на хэш-функция. Таким образом, вы действительно не нужно чтобы понять это. А на самом деле мы просто вытащил этот хэш функционировать из Интернета. Единственное, что вы должны признать это что это занимает константный символ * слово. Так это занимает строку в качестве входных данных, и возвращения без знака Int как выход. Так что все хэш-функция, это принимает в качестве входных данных и дает индекс в хэш-таблице. 

Обратите внимание, что мы Moding по NUM_BUCKETS, так что значение, возвращенное на самом деле является индексом в хэш-таблице и не индексирует за Границы массива. Поэтому, учитывая, что функция, мы собираемся чтобы прояснить слово, что мы читаем словарь. А потом мы собираемся использовать что хэш вставить вступление в хэш-таблице. 

Теперь хеш хэш текущий связано список в таблице. И очень возможно, что это просто NULL. Мы хотим, чтобы вставить нашу запись в в начале этого связанного списка. И таким образом мы будем иметь нашу ток Точка входа к тому, что хеш-таблица В настоящее время указывает. А потом мы собираемся хранить, в хэш-таблице на хэш, текущая запись. Таким образом, эти две линии успешно вставить вступление в начале Связанный список по этому индексу в хэш-таблице. 

После того, как мы закончим с этим, мы знаем, что мы нашли еще одно слово в словарь, и мы увеличиваем снова. Таким образом, мы продолжать делать это до fscanf наконец, вернулся что-то не-1 на чего помните, что мы должны на свободный въезд. Так здесь мы malloced запись. И мы старались, чтобы читать то из словаря. И мы не успешно прочитаны что-то из словаря, в этом случае нам нужно освободить запись что мы никогда не введен в хеш, и, наконец, сломать. 

Как только мы вырваться мы должны видеть, ну, же мы вырваться, потому что Произошла ошибка чтения из файла? Или мы ломаем, потому что мы достигли конца файла? Если произошла ошибка, то мы хотим вернуться ложным. Потому что нагрузка не удалось. И в этом процессе мы хотим, чтобы разгрузить все слова, которые мы читаем в и закрыть файл словаря. 

Предположим, что мы преуспели, то мы просто еще нужно закрыть словарь файл, и, наконец, вернуться верно, так как мы успешно загружен словарь. И это все на груз. Так что теперь проверить, учитывая загруженный хеш, будет выглядеть следующим образом. Поэтому проверить, она возвращает логическое значение, которое собирается указать, является ли прошло в символ * слова, будь то прошло в строке находится в нашем словаре. Так что, если он находится в словаре, если он находится в нашей хэш-таблице, мы вернемся правда. А если это не так, мы вернемся ложным. 

Учитывая это прошло в слове, мы собирается хэш слово. Теперь главное, чтобы признать, что в нагрузке мы знали, что все слова, которые мы собираемся быть в нижнем регистре. Но здесь мы не так уверены. Если мы взглянем на наш хэш-функции, наш хэш-функция на самом деле ниже корпуса каждый символ слова. Поэтому, независимо от капитализации Слово, наш хэш-функция является возвращение аналогичный показатель по тем или иным капитализация, так как он должен был бы вернулись на совершенно нижнем регистре вариант слова. Хорошо. Это наш индекс в HashTable для этого слова. 

Теперь это цикл собирается перебора связанного списка это было по этому индексу. Так заметить мы инициализации запись указать на то индекс. Мы собираемся продолжить в то время как запись! = NULL. И помните, что обновление указатель в наш связанный список запись = запись> следующая. Так что наш текущий точку входа Следующий пункт в связанном списке. 

Таким образом, для каждой записи в связанном списке, мы собираемся использовать strcasecmp. Это не StrComp. Потому что в очередной раз, мы хотим сделать что-то случай бесчувственно. Поэтому мы используем strcasecmp сравнить Слово, которое пропускают через этот Функция против слова то есть в данной записи. Если она возвращает ноль, это означает, что было матч, в этом случае мы хотим вернуться верно. Мы успешно нашли Слово в нашей хэш-таблице. 

Если бы не было матча, то мы собирается цикле снова и посмотреть на Следующая запись. И мы будем продолжать зацикливание в то время как есть являются записи в этой связанного списка. Что произойдет, если мы нарушаем из этого для цикла? Это означает, что мы не нашли запись, соответствует это слово, в каком случае мы вернуться ложным, чтобы указать, что наш хеш не содержат это слово. И это проверка. 

Так что давайте взглянем на размер. Теперь размер будет довольно просто. Так помните нагрузки, для каждого слова мы нашли, мы увеличивается глобальная переменный размер хеш. Таким образом, функция размер только собирается вернуться глобальной переменной. И это все. 

Теперь, наконец, мы должны выгрузить словарь, как только все будет сделано. Так как мы собираемся это сделать? Прямо здесь мы пробегаем по все ведра нашем столе. Таким образом, есть NUM_BUCKETS ведра. И для каждого связанного списка в нашем хеш, мы собираемся цикла по полнота связанного списка, освобождая каждый элемент. 

Теперь мы должны быть осторожны. Так вот у нас временную переменную который хранения указатель на следующий элемент в связанном списке. А потом мы собираемся бесплатно текущий элемент. Мы должны быть уверены, что мы делаем это, так как мы не могу просто освободить текущий элемент , а затем попытаться перехода к следующей указатель, так как только мы освободили его, память становится недействительным. 

Так что мы должны держать вокруг указатель на на следующий элемент, то мы можем освободить текущий элемент, и тогда мы сможем обновить наш текущий элемент, чтобы указать на следующий элемент. Мы будем цикл в то время как есть элементы в этом связанном списке. Мы сделаем это для всех связан Списки в хэш-таблице. И как только мы закончим с этим, мы полностью разгрузили хеш-таблицу, и мы закончили. Так что это невозможно для выгрузки чтобы когда-либо вернуться ложным. А когда мы закончим, мы просто вернуть верно. 

Давайте это решение попробовать. Итак, давайте посмотрим, что наш структура узел будет выглядеть. Здесь мы видим, что мы собираемся иметь логическое значение слово и структура узла * дети Кронштейн АЛФАВИТ. Поэтому первое, что вы могли бы быть интересно, почему АЛФАВИТ ред определяется как 27? Ну, помните, что мы собираемся нужно быть обработки апостроф. Так что это будет своего рода Особый случай всей этой программы. 

Теперь вспомните, как синтаксического дерева на самом деле работает. Скажем мы индексации слово "кошки". Тогда из корня синтаксического дерева, мы будем смотреть на детей Массив, и мы будем смотреть на индекс, который соответствует букве С. Так что будет индексироваться 2. Поэтому, учитывая, что, что воля дать нам новый узел. И тогда мы будем работать с этим узлом. 

Поэтому, учитывая, что узел, мы в очередной раз будем смотреть на массиве детей. И мы будем смотреть на нулевой индекс чтобы соответствовать А в кот. Итак, мы собираемся пойти на этот узел, и учитывая, что узел мы собираемся искать в конце это соответствует Т. и перейти к этому узлу, наконец, мы полностью посмотрел через наше слово "кот". А теперь Ьоо слово предполагается указать, является ли это данное слово на самом деле слово. 

Так почему же мы должны, что частный случай? Ну то, что слова «катастрофа» находится в нашем словаре, но Слово "кот" не является? Так и смотрел, если слово "кот" находится в нашем словаре, мы собирается успешно просматривать индексы С-А-Т в области узла. Но это только потому, что катастрофа произошло создать узлы на пути от С-А-Т, вплоть до конец слова. Так BOOL слово используется, чтобы указать, это особое расположение на самом деле указывает на слово. 

Хорошо. Так что теперь мы знаем, что это синтаксического дерева является будет выглядеть, давайте посмотрим на загрузить функцию. Так нагрузка будет возвращать логическое значение для того мы успешно или безуспешно загружалась словарь. И это будет словарь что мы хотим загрузить. 

Так первое, что мы хотим сделать, это открыть до этого словаря для чтения. И мы должны убедиться, мы не провалился. Так, если в словаре не было успешно открыт, то он вернет нуль, в каком случае мы собирается вернуться ложным. Но если предположить, что он успешно открыл, то мы можем на самом деле читать через словаре. 

Так первое, что мы собираемся хочу сделать, это у нас есть это глобальная переменная корень. Теперь корень будет узел *. Это вершина нашего синтаксического дерева, что мы будет итерации. Таким образом, первое, что мы собираемся хотят сделать, это выделить память для нашего корня. Обратите внимание, что мы используем calloc Функция, которая в основном то же самое как функция таНос, за исключением, что это гарантированно вернуть то, что является полностью обнуляется. Так что, если мы использовали таНос, мы должны были бы пройти через все указатели в нашей узел, и убедитесь, что они все нуль. Так calloc сделает это за нас. 

Теперь же, как таНос, мы должны сделать уверен, что распределение было на самом деле успешным. Если это возвращается нуль, то нужно закрыть или словарь файл и вернуться ложным. Так, предполагая, что распределение было успешно, мы собираемся использовать узел * курсор для перебора нашего синтаксического дерева. Таким образом, наши корни никогда не собирается менять, но мы собираемся использовать курсор на самом деле идти от узла к узлу. 

Так что в этом цикле мы читаем через файл словаря. И мы используем fgetc. Fgetc собирается захватить один персонаж из файла. Мы собираемся продолжить захват символов в то время как мы не доходят конец файла. 

Есть два случая, которые мы должны справиться. Первый, если символ не новая линия. Итак, мы знаем, было ли это новая линия, то мы собираемся перейти к новым словом. Но если предположить, что это не было новой линии, то здесь мы хотим выяснить, Индекс мы собираемся индекса в в массиве детей, что мы смотрели на перед. 

Так что, как я уже говорил, мы должны Особый случай апостроф. Обратите внимание, что мы используем тройных оператор здесь. Так что мы собираемся, чтобы прочитать это как, если характер мы читаем, был апостроф, то мы собираемся установить индекс = "АЛФАВИТ" -1, который будет быть индекс 26. 

В противном случае, если это не было апостроф, есть мы собираемся установить индекс равна с -. Так что помните сравнению с ранее р-наборов, с - а будет давать нам алфавитный позиция С. Так что если С буква А, это будет дать нам нулевой индекс. Для письма B, это даст нам индекс 1, и так далее. 

Так что это дает нам индекс в дети массив, который мы хотим. Теперь, если этот показатель в настоящее время нулевой в дети, это означает, что узел в настоящее время не существует с этого пути. Так что мы должны выделить узел для этого пути. Это то, что мы будем делать здесь. 

Так что мы собираемся снова использовать calloc Функция, так что мы не должны обнулить все указатели. И мы снова должны проверить что calloc не провалился. Если calloc ничего не получится, то мы должны выгрузить все, закрываем словарь, и вернуться ложным. Так предполагая, что он не преминул, то это создаст нового ребенка для нас. А потом мы пойдем в этого ребенка. Наша курсор итерации до этого ребенка. 

Теперь, если это не было пустой для начала, то курсор можно просто перебрать до этого ребенка, фактически не того, чтобы выделить ничего. Это тот случай, когда мы впервые произошло выделить слово «кот». И это означает, что, когда мы идем выделить "Катастрофа", нам не нужно создавать узлы для C-A-T снова. Они уже существуют. 

Что это еще? Это состояние, при котором кондиционер был косая черта п, где кондиционер был новая линия. Это означает, что мы успешно завершила слово. Теперь то, что мы хотим сделать, когда мы успешно завершила слово? Мы собираемся использовать это поле слово внутри нашего структуры узла. Мы хотим, чтобы установить, что к истине. Так что указывает, что этот узел указывает успешным Слово, фактический слово. 

Теперь установите, что к истине. Мы хотим, чтобы сбросить нашу курсор к точке в начале синтаксического дерева снова. И, наконец, увеличить наш словарь размер, так как мы нашли другой работы. Так что мы собираемся продолжать делать это, чтение в посимвольно, построения новых узлов в нашей синтаксического дерева и для каждого слова в словаре, до мы, наконец, достичь C! = EOF, в котором случае мы вырваться из файла. 

Теперь есть два случая под которые мы могли бы попасть EOF. Первый, если произошла ошибка чтение из файла. Так что, если произошла ошибка, мы нужно сделать типичный. Выгрузка все, близко файл, возвращение ложным. Предполагая, что не было ошибок, которые просто означает, что мы на самом деле попал в конце файл, в каком случае, мы закрываем файл и вернуться верно, так как мы успешно загружен словарь в нашей синтаксического дерева. 

Так что теперь давайте проверим чек. Глядя на функции проверки, мы видим, , что регистрация будет возвращать логическое значение. Это возвращает истину, если это слово, что это передается в нашей синтаксического дерева. Это возвращает ложь в противном случае. Так как же определить, является ли это слово в нашем синтаксического дерева? 

Мы видим здесь, что, как и раньше, мы собираемся использовать курсор для перебора через нашу синтаксического дерева. Теперь вот мы собираемся итерации над всем нашим словом. Так итерации слова мы прошлое, мы собираемся определить индекс в массиве детей, что соответствует слово кронштейна I. Таким образом, это будет выглядеть так же, как нагрузка, где, если слово [я] является апостроф, то мы хотим использовать индекс «алфавит» - 1. Потому мы решили, что, что Здесь мы собираемся хранить апострофа. 

Остальное мы собираемся использовать два нижних слово Кронштейн И. Так что помните, что слово может иметь произвольную капитализации. И поэтому мы хотим, чтобы убедиться, что мы используя строчную версию вещей. А потом вычесть от "а" до одного раза снова дать нам алфавитном Положение этого символа. Так что это будет наш индекс в массиве детей. 

А теперь, если это индекс в детей Массив является пустым, что означает, что мы больше не может продолжать итерации вниз нашего синтаксического дерева. Если это так, то это слово не может возможно, будет в нашем синтаксического дерева. Поскольку если бы это было, что бы означает, что будет путь до этого слова. И вы никогда не столкнетесь с нуль. Так встречая нуль, мы вернуться ложным. Слово отсутствует в словаре. Если бы не нуль, то мы собирается продолжить итерации. 

Так что мы собираемся там курсор , чтобы указать, что особенно узел по этому индексу. Мы продолжаем делать это на протяжении все слово, предполагая, мы никогда не ударил нуль. Это означает, что мы смогли пройти через все слово и найти узел в нашей попытки. Но мы еще не закончили еще. 

Мы не хотим, чтобы просто вернуть верно. Мы хотим вернуться курсора> слово. Так помните опять же, "кошка" не в нашем словаре, и «катастрофа» будет, то мы будем успешно мы получаем через слово "кот". Но курсора Слово будет ложным, а не правда. Так мы возвращаемся курсора слово для обозначения ли этот узел на самом деле слово. И это все для проверки. 

Так давайте проверим размер. Так размер будет довольно легко так, помните, в нагрузке, мы увеличивая размер словаря для каждое слово, что мы сталкиваемся с. Так размер только собирается вернуться размер словаря. И это все. 

Так, наконец, мы выгрузить. Так выгрузить, мы собираемся использовать рекурсивная функция на самом деле делать все часть работы за нас. Таким образом, наша функция будет быть вызван разгрузки. Что разгрузочное собираетесь делать? Мы видим здесь, что разгрузочная собирается перебора всех детей в именно этот узел. А если ребенок узел не нулю, то мы собираемся выгрузить дочерний узел. 

Так что это вы рекурсивно выгрузить всех наших детей. После того, как мы уверены, что все наши дети были выгружены, то мы может освободиться, так выгрузить себя. Это будет работать рекурсивно выгрузить весь синтаксического дерева. А потом, как только это будет сделано, мы можем просто вернуть верно. Выгрузка не может подвести. Мы просто освобождая вещи. Поэтому, как только мы закончим освобождая все, вернуться верно. И это все. Меня зовут Боб. И это было правописания. 

[Музыка играет]