ZAMYLA Чан: Давайте зробимо перевірка орфографії. Якщо ви відкриєте speller.c, то ви побачите, що більшість функціональних можливостей для перевірки текстовий файл проти словник вже зроблено для вас. . / Правописної, проходячи в словнику тексту файл, а потім інший текстовий файл, перевірятиме, що текстовий файл проти словнику. 

Тепер, словник текстові файли будуть містити дійсні слова, по одному в рядку. Тоді speller.c подзвонить Load на словника текстового файлу. Це подзвоню функція називається Перевірка на кожне слово в введеної текстовий файл, друк всіх слів з помилками. 

Speller.c також викличе Розмір для визначити кількість слів у словник і викликати вивантаження щоб звільнити пам'ять. speller.c також відстежувати, як скільки часу використовується для проведення з них процеси, але ми будемо до цього пізніше. 

Так що ж ми повинні робити? Нам потрібно заповнити dictionary.c. У dictionary.c, у нас є помічник Функція завантаження, яка завантажує словник. Функція Перевірити, який перевіряє, якщо дане слово є в словнику. Функція Розмір повертає кількість слів у словнику. І, нарешті, ми Вивантаження, які звільняє словник з пам'яті. 

Отже, спочатку давайте візьмемося Load. Для кожного слова у словнику тексту файл, навантаження буде зберігати ці слова в словник структура даних за вашим вибором, або хеш-таблиці або синтаксичного дерева. Я піду за як в це йти через. 

Спочатку, давайте поговоримо про хеш-таблиці. Скажімо, у вас було 10 більярдні кулі та ви хотіли, щоб зберегти їх. Ви можете помістити їх усіх в відро, і коли ви потребували специфічного пронумеровані м'яч, ви б взяти один з відра в той час шукає, що м'яч. І тільки з 10 кульками, ви повинні бути в змозі знайти свій м'яч в розумний кількість часу. 

Але що, якщо у вас було 20 м'ячів? Це може зайняти трохи більше часу тепер. А як щодо 100? 1000? Тепер, було б набагато легше, якщо у вас було кілька відер. Може бути, один ківш для куль номер нуль до дев'яти, ще відро для куль, пронумерованих від 10 до 19, і так далі. 

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

Тепер, так як ми маємо справу з словники, одна ківш для всі слова в словнику буде ймовірно, буде занадто мало відра. Так що давайте поглянемо на хеш-таблиці. 

Думайте про це як масив відра. І в цьому випадку, відра наші зв'язані списки. І ми будемо поширювати на всі наші слова серед цих кількох пов'язаних списків в організовано з використанням хеш-функції, який покаже, які відро конкретний ключ, даний Слово, належить. 

Давайте представити це схематично. Сині коробки тут містять значення і червоні коробки вказують на інше значення Покажчик пара. Ми назвемо ці пари вузлів. Тепер кожен відро, як я вже сказав раніше, є зв'язаний список. У зв'язаних списків, кожен вузол має значення, а також покажчик на Наступне значення. 

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

Так як же ми представляємо це в C? Ми визначаємо структуру тут. І цінність у цьому випадку символ масив довжини. Довжина плюс 1, де довжина Максимальна довжина будь-якого слова, плюс 1 для нульова термінатор. І тоді у нас є вказівник на інший вузол називається Наступна. 

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

Тепер, якщо ви хочете, щоб привласнити значення слово, то ми могли б сказати node1 стрілку Слово одно "Привіт". Цей оператор стрілка разименовивает покажчик і доступ змінні в структуру в. Таким чином, ми не повинні використовувати обидва точка і зірка оператор. 

Так то у мене є node2 стрілка слово одно "Мир". І там, ці значення населений в моїх вузлів. Щоб посилання, я передам в node1 стрілку поруч, доступ до цієї вузла зірку, що покажчик вузол, дорівнює node2, вказуючи node1 щоб node2 два. І там у нас є зв'язаний список. 

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

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

Добре, але де ж наш м'яч? Ну, ми в першу чергу необхідно є м'яч, чи не так? Так що давайте Malloc вузол для кожен нове слово, що у нас є. вузол * new_node одно Танос (SizeOf (вузол)). 

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

Далі ми хочемо, щоб прояснити, що Слово використанням хеш-функції. Хеш-функція приймає рядок і повертає індекс. У цьому випадку індекс повинен бути менше, ніж кількість відра, що у вас є. 

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

Це ніби як бібліотеки. Коли ви берете книгу, засновану на автор, ви знаєте, які полки треба продовжуватися, будь число полку один, два, або три. І ця книга завжди буде належати на або полки один, два, або три. 

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

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

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

Але що, якщо ви хочете, щоб ваш список, який буде упорядковано, тому що, упорядковано пов'язані Список може бути простіше для пошук його в подальшому? Ну, для цього вам потрібно знати як пройти пов'язаних списків. 

Для переміщення зв'язаний список, давайте покажчик вузол, вузол *, в якості курсор, який вказує, які вузлу ви на, починаючи з першого елемента. НЕ Looping до курсору порожній, ми можемо здійснювати певні процеси, а потім переміщення курсору, коли нам потрібно використовуючи значення стрілкою курсору. 

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

Припустимо, ви визначили, що D стає в між С і Е. Щоб вставити вузол, є D точку new_node до вузол E, який є поруч курсор. А потім C, курсор, може вказувати до D. Таким чином, ви підтримувати список. Будьте обережні, щоб не втратити свої посилання на переміщаючи стрілку курсора поруч з D відразу ж. 

Добре. Так от, як ви могли б вставити вузли, завантажити їх в, навантаження слова в тих вузли, і вставити їх в ваш хеш-таблиці. Так що тепер давайте подивимося на спроб. 

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

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

Так як же ми представляємо це в C? Ну, кожен вузол тепер матиме Логічне значення, яке вказує що вузол є кінцем дане слово чи ні. А потім також будете мати масив вузол покажчиків звані діти, і там будуть 27 з них. І пам'ятайте, ви також хочете, щоб стежити за своїм першим вузлом. Ми збираємося викликати цей корінь. 

Так от структура вигляді дерева. Як ми представляємо цей в якості словника? Ну, для завантаження слова в, для кожного словник слово, ви будете хотіти, для перебору синтаксичного дерева. І кожен елемент в дітях відповідає різному письма. 

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

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

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

Буква О тоді буде у дітей індекс 15, після цього F. А потім X буде ще нижче, що, розгалуження від дітей Виходів. А потім, бо X є остання буква слова "лиса", то я збираюся колір, що зелений, показуючи, що це кінець слова. У C, які будуть налаштування ІС Слово Boolean зі значенням істинною. 

А що, якщо наступне слово, що ти вантаження в це слово "Foo"? Ну, вам не потрібно, щоб Malloc більше простір для F або O, тому тих, хто вже існує. Але останній висновок в Foo? Це один, вам доведеться Танос. Створіть новий вузол для того, установка це Слово Логічне до істини. 

А тепер давайте вставити "собаку". Собака буде почати з індексом три коренів діти, тому що D не створена. І ми будемо слідувати аналогічний процес, як перш, створюючи підрядок собаку, де ж G пофарбована в зелений колір, тому що це кінець слова. 

Тепер, що якщо ми хочемо, щоб вставити "робити"? Ну, це підрядок собаки, тому ми не повинні Malloc більше. Але ми повинні вказати, де ми підійшов до кінця цього слова. Так O буде забарвлений в зелений колір. Продовжуючи цей процес для кожного окремого слово в словнику, ви, завантажив їх у в Або Ваш хеш-таблиці або ваш синтаксичного дерева. 

speller.c пройде в рядках для dictionary.c, щоб перевірити їх. Тепер Перевірити функція повинна працювати під нечутливості до регістру. Це означає, що великі літери і малі літери і поєднання того й іншого всі повинні прирівняти до вірно, якщо будь-яка Поєднання тобто в словник. Можна також припустити, що рядки тільки збирається містити алфавітний символів або апострофа. 

Отже, давайте поглянемо на те, як ви можете перевірити зі структурою хеш-таблиці. Ну, якщо слово існує, то він можна знайти в хеш-таблиці. Тоді ви можете спробувати знайти, що слово у відповідному відрі. 

Отже, які відро б, що слово бути в? Ну, ви отримаєте номер, що індекс ковша, шляхом хеширования це слово а потім шукати в цьому пов'язаному списку, обході через весь зв'язаний список, використовуючи рядок Функція порівняння. 

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

Як ви могли б перевірити в синтаксичного дерева структура? Ми збираємося подорожувати вниз в синтаксичного дерева. Для кожної букви в введеного слова що ми перевіряємо, ми підемо в тому, що Відповідний елемент у дітей. 

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

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

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

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

Що робити, якщо ви використовуєте синтаксичного дерева? Тоді найкращий спосіб зробити це це вивантажити з дуже знизу вгору. Подорожуючи за найнижчою можливою вузол, ви можете завантажити всі покажчики в що діти, а потім повернутися вгору, звільняючи всі елементи у всіх не з дітей масивів, поки ви потрапляєте верхню кореневої вузол. Ось де Рекурсія знадобиться. 

Щоб переконатися, що ви, мабуть, звільнені все, що ви malloced, Ви можете використовувати Valgrind. Запуск Valgrind буде запустити програму вважаючи, скільки байт пам'яті ви використовуєте і переконавшись, що у Вас є звільнив їх усіх, кажу вам, де ви, можливо, забули безкоштовно. Так біжіть, і як тільки Valgrind говорить вам і дає вам йти вперед, то Ви закінчили вивантаження. 

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

За замовчуванням, він завантажує в великий словник. Таким чином, ви, можливо, захочете пройти в малому словник, або, можливо, навіть зробити свій самостійно, налаштувавши словник і текстовий файл. 

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

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

При тому, що ви закінчили орфографії PSet. Мене звуть Zamyla, і це CS50.