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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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