[Музика грає] 

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

А потім наш хеш в кожному відро збирається зберігати зв'язаний список вузлів. Ми не робимо лінійну зондування тут. І тому для того, щоб зв'язати до наступного елемент у відро, ми повинні структура вузла * наступний. ОК. Так ось що вузол виглядає. 

Тепер ось декларація нашої хеш-таблиці. Це матиме 16834 відер. Але це число не має значення. І, нарешті, ми збираємося мати глобальна змінна розмір хеш, який збирається почати як нуль. І це буде відслідковувати, як багато слів в нашому словнику. 

Так що давайте поглянемо на навантаженні. Зверніть увагу, що навантаження, вона повертає логічне значення. Ви повертаєтеся вірно, якщо це було успішно завантажені, і в іншому випадку. І це займає константних символ * словник, який є словник що ми хочемо відкрити. Так ось перше, що ми збираємося зробити. 

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

Решту ми збираємося використовувати два нижніх слово Кронштейн І. Так що пам'ятайте, що слово може мати довільну капіталізації. І тому ми хочемо, щоб переконатися, що ми використовуючи строчную версію речей. А потім відняти від "а" до одного разу знову дати нам алфавітному Положення цього символу. Так що це буде наш індекс в масиві дітей. 

А тепер, якщо це індекс в дітей Масив є порожнім, що означає, що ми більше не може продовжувати ітерації вниз нашого синтаксичного дерева. Якщо це так, то це слово не може можливо, буде в нашому синтаксичного дерева. Оскільки якби це було, що б означає, що буде шлях до цього слова. І ви ніколи не зіштовхнетеся з нуль. Так зустрічаючи нуль, ми повернутися помилковим. Слово немає у словнику. Якби не нуль, то ми збирається продовжити ітерації. 

Так що ми збираємося там курсор , Щоб вказати, що особливо вузол за цим індексом. Ми продовжуємо робити це протягом все слово, припускаючи, ми ніколи не вдарив нуль. Це означає, що ми змогли пройти через все слово і знайти вузол в нашій спроби. Але ми ще не закінчили ще. 

Ми не хочемо, щоб просто повернути вірно. Ми хочемо повернутися курсору> слово. Так пам'ятайте знову ж, "кішка» не в нашому словнику, і «катастрофа» буде, то ми будемо успішно ми отримуємо через слово "кіт". Але курсора Слово буде хибним, а не правда. Так ми повертаємося курсора слово для позначення Чи цей вузол насправді слово. І це все для перевірки. 

Так давайте перевіримо розмір. Так розмір буде досить легко так, пам'ятайте, в навантаженні, ми збільшуючи розмір словника для кожне слово, що ми стикаємося з. Так розмір тільки збирається повернутися розмір словника. І це все. 

Так, нарешті, ми вивантажити. Так вивантажити, ми збираємося використовувати рекурсивна функція насправді робити все частину роботи за нас. Таким чином, наша функція буде бути викликаний розвантаження. Що розвантажувальне збираєтеся робити? Ми бачимо тут, що розвантажувальна збирається перебору всіх дітей у саме цей вузол. А якщо дитина сайт не нулю, то ми збираємося вивантажити дочірній вузол. 

Так що це ви рекурсивно вивантажити всіх наших дітей. Після того, як ми впевнені, що всі наші діти були вивантажені, то ми може звільнитися, так вивантажити себе. Це буде працювати рекурсивно вивантажити весь синтаксичного дерева. А потім, як тільки це буде зроблено, ми можемо просто повернути вірно. Вивантаження не може підвести. Ми просто звільняючи речі. Тому, як тільки ми закінчимо звільняючи все, повернутися вірно. І це все. Мене звуть Боб. І це було правопису. 

[Музика грає]