>> 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.