[За възпроизвеждане на музика] 

ROB BOWDEN: Hi. Аз съм Роб. И нека това решение навън. Така че тук ние ще се приложат обща таблица. Виждаме, че структурата на възел на нашата маса ще изглежда по този начин. Така че няма да има Чар дума масив на площ ДЪЛЖИНА + 1. Да не забравяме и + 1, тъй като максималната дума в речника е 45 символа. И тогава ние ще трябва едно допълнително характер за обратно наклонена черта нула. 

И тогава нашата Hashtable във всяка кофа ще се съхранява свързан списък от възли. Ние не правим линейна сондиране тук. И така, за да се свърже към следващата елемент в кофата, ние се нуждаем от структура възел * следващия. OK. Така че това е, което възел изглежда. 

Сега тук е декларацията на нашата Hashtable. Тя ще има 16 834 кофи. Но този номер няма значение. И накрая, ние ще имаме глобална променлива размер изпробван звукът, който ще започнем като нула. И това се случва, за да следите как много думи са в нашия речник. 

Така че нека да разгледаме най-натоварване. Забележете, че товара, то връща булев. Ще се върнете вярно, ако това беше успешно заредена, и лъжа в противен случай. И това отнема Конст Чар * речник, който е речника че искаме да се отвори. Така че това е първото нещо, ние ще направим. 

Отиваме да Fopen на речник за четене. И ние ще трябва да се направи уверите, че тя успя. Така че, ако го връща NULL, тогава ние не направихме успешно отворите речника. И ние трябва да се върне фалшиви. Но ако приемем, че го е направил успешно отворен, след това ние искаме да прочетете речник. Така че продължавайте да примка, докато не се намери някои причина да се измъкнат от този цикъл, , които ще видим. Така че продължавайте да примка. 

И сега ние ще изчистване на един възел. И разбира се, ние трябва да излъчи проверете отново. Така че, ако mallocing не успее, тогава ние искаме да се разтоварят всеки възел, който ние случило с изчистване преди, затворете речник и връщане фалшиви. Но пренебрегвайки факта, че, ако се приеме, че успял, тогава искаме да използваме fscanf за да прочетете една-единствена дума от нашия речника в нашия възел. Така че не забравяйте, че влизането> дума е Чар Думата буфер с размер LENGHTH + 1 че отиваме да съхранявате думата инча 

Така fscanf ще се върне един, толкова дълго, , тъй като е в състояние да успешно прочетете една дума от файла. Ако някоя грешка се случва, или ние достигнат края на файла, да го няма да се върне един. В този случай тя не се връща 1, ние сме най-накрая ще се измъкнат от тази линия, докато. Така ние виждаме, че след като имаме успешно прочетете една дума в влизане> дума, след това отиваме в които дума с помощта на нашата хеш функция. 

Нека да разгледаме най- функцията за сегментиране. Така че наистина не се нуждаят да се разбере това. И всъщност ние просто извади този хеш функционира от интернет. Единственото нещо, което трябва да се признае, е че това отнема Конст Чар * дума. Така че това е като низ като вход, и връщане неподписан Int като продукция. Така че това е всичко, функция за сегментиране се, е, че се в един вход и ви дава индекс в Hashtable. 

Забележете, че ние сме Модинг от NUM_BUCKETS, така че стойността се връща всъщност е индекс в Hashtable и не индекс на отвъдното границите на масива. Така че, предвид факта, че функция, отиваме за сегментиране на думата, която четем речник. И тогава започваш да се използва че хеш да вмъкнете влизане в Hashtable. 

Сега Hashtable хеш е токът свързан списък в таблицата. И това е много възможно че това е просто NULL. Искаме да вмъкнете влизането ни в началото на този свързан списък. И така ние ще имаме ток входна точка на това, което Hashtable В момента сочи към. И тогава ние ще се съхранява, в Hashtable в хашиш, текущият запис. Така че тези две линии успешно вмъкват влизането в началото на свързан списък в този форум в Hashtable. 

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

След като избухне ние трябва да видим, добре, не сме се измъкнат, защото има четеше грешка от файла? Или пък можем да избухне, защото ние достигнала края на файла? Ако е налице грешка, тогава ние искаме да се върне фалшиви. Защото натоварване не успее. И в този процес искаме да разтоварим всички думи, които четем в, и затворете файла речник. 

Ако приемем, че ние успяхме, тогава ние просто Все още трябва да се затвори речника Файл, а най-накрая се върнете вярно, тъй като ние успешно зареден речника. И това е за натоварване. Така че сега се провери, като се има зареден Hashtable, ще изглежда по този начин. Така че проверете, тя връща булев, което е ще посочи дали преминава в Чар * дума, дали преминава в низ е в нашия речник. Така че, ако това е в речника, ако това е в нашия Hashtable, ние ще се върне вярно. И ако не е, ще се върне фалшиви. 

Като се има предвид това, приет през дума, ние сме ще сегментиране на думата. Сега важно нещо е да се признае, че при натоварване ние знаехме, че всички думи Отиваме да бъде по-ниска случай. Но тук ние не сме толкова сигурни. Ако можем да погледнем в нашата хеш функция, нашата хеш функция всъщност е по-нисък корпус всеки знак на думата. Така че независимо от капитализацията на дума, нашата хеш функция е завръщането на същия показател за каквото и да било на капитализация е, тъй като той ще има върнато за съвсем малки букви версия на думата. Добре. Това е нашият форум е в HashTable за тази дума. 

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

Така че за всяко влизане в свързан списък, ние ще използваме strcasecmp. Това не е strcomp. Защото за пореден път, ние искаме да правят неща случай безчувствено. Така че ние използваме strcasecmp да се сравни дума, която се прекарва през този функция срещу думата , която е в този пост. Ако това се връща на нула, това означава, че не е един мач, в който случай ние искаме да връщане вярно. Ние успешно намери дума в нашия Hashtable. 

Ако там не беше мач, а след това ние сме Ще цикъл отново и погледнете в следващия запис. И ние ще продължим примка, докато има са вписвания в тази свързан списък. Какво ще стане, ако се прекъсне от това за цикъл? Това означава, че ние не се намери запис, който съвпадащи тази дума, в който случай ние връщане фалшиви да покаже, че нашата Hashtable не съдържа тази дума. И това е чек. 

Така че нека да разгледаме най-размер. Сега размер ще е доста проста. Откакто се помни в натоварване, за всяка дума ние открихме, ние увеличава в световен променлив размер Hashtable. Така функцията размер е просто ще да се върне глобална променлива. И това е всичко. 

Сега най-накрая, ние трябва да се разтоварим речник След като всичко е готово. Така че как ще го направиш? Точно тук ние използваме цикъл всички кофи на нашата трапеза. Така че има NUM_BUCKETS кофи. И за всеки свързан списък в нашата Hashtable, отиваме да отскача над целостта на свързан списък, освобождавайки всеки елемент. 

Сега ние трябва да бъдем внимателни. Така че тук имаме временна променлива това е съхранение на показалеца към следващата елемент в свързан списък. И след това отиваме на свободно текущия елемент. Ние трябва да бъдем сигурни, че правим това, тъй като ние Не може просто да освободи текущия елемент и след това се опитайте да влезете в следващия показалеца, тъй като веднъж сме го освободи, паметта става невалиден. 

Така че ние трябва да се запази около указател към следващия елемент, тогава можем да се освободи текущия елемент, а след това можем да се актуализира сегашната ни елемент да сочи към на следващия елемент. Ще контур докато има елементи в този свързан списък. Ние ще направим това за всички свързани списъци в Hashtable. И след като сме готови с това, ние сме напълно разтоварени на Hashtable, и сме готови. Така че това е невъзможно за разтоварване някога да се върне фалшиви. И когато сме готови, ние просто връщане вярно. 

Нека дадем това решение опитам. Така че нека да разгледаме какво ни структура възел ще изглежда така. Тук виждаме, че ще има булев дума и структура възел * деца скоба азбука. Така че първото нещо, което може да бъде чудех, защо е ПИСМЕНОСТ Ед определя като 27? Е, не забравяйте, че ние ще трябва да се борави с апостроф. Така че това ще бъде до известна степен на специален случай в цялата тази програма. 

Сега си спомням как един Trie действително работи. Да кажем, че ние сме индексиране думата "котки." Тогава от корена на Trie, ние ще разгледаме децата масив, и ние отиваме да погледнем в индекс, който отговаря на буквата С така, че да бъдат индексирани 2. Така че, имайки предвид, че тази воля ни даде нов възел. И тогава ние ще работим от този възел. 

Така че, имайки предвид, че възел, ние сме отново Ще погледнем към децата масива. И ние отиваме да погледнем индекса нула да съответства на А в котка. Така че след това ние ще отидем до този възел, и предвид това, че възел отиваме да погледнем в крайна сметка това е А съответства Т. и да преминат към този възел, Най-накрая, ние сме напълно погледна чрез нашата дума "котка." И сега булев дума е предназначена да посочи дали дадената дума всъщност е дума. 

Така че, защо имаме нужда от този специален случай? Ами какво да кажем за думата "катастрофа" е в нашия речник, но Думата "котка" не е? Затова и гледам да се види дали думата "котка" е в нашия речник, ние сме Ще успешно гледам през индексите C-A-T в района на възел. Но това е само заради катастрофа се случи, за да създадете възли по пътя от C-A-T, чак до на края на думата. Така булев дума се използва, за да посочи дали това определено място, всъщност означава думата. 

Добре. Така че сега, че ние знаем какво е Trie ще изглежда така, нека да разгледаме най- зареди функция. Така че натоварването ще се върне булев за това дали ние успешно или безуспешно се зарежда речника. И това ще бъде в речника че искаме да се зареди. 

Така че първото нещо, което искаме да направим, е отворен нагоре, че речник за четене. И ние трябва да се уверете, че ние не се провали. Така че, ако речника не беше успешно отворен, той ще се върне нула, в който случай ние сме ще се върне фалшиви. Но ако приемем, че тя успешно отвори, тогава ние действително могат да четат чрез речника. 

Така че първото нещо, което започваш да искате да направите, е да имаме тази променлива корен глобален. Сега корен ще бъде възел *. Тя е на върха на нашата Trie, че сме ще бъде итерации чрез. Така че първото нещо, което ние ще да искате да направите, е да се разпределят памет за нашия корен. Забележете, че ние сме с помощта на calloc функция, която е по същество същата като функцията за изчистване, освен това е гарантирано да се върне нещо, което е напълно на нула. Така че, ако ние използвахме изчистване, ние ще трябва да мине през всички насоки в нашата възел, и се уверете, че всички те са нула. Така calloc ще направи това за нас. 

Сега просто като изчистване, ние трябва да се направи уверите, че разпределението е всъщност успешно. Ако това се връща нула, тогава можем Трябва да затворите или речник подаде и връщане фалшиви. Така че, ако се приеме, че разпределянето е успешно, ние ще използваме един възел * курсора, за да превъртате чрез нашия Trie. Така че нашите корени никога няма да се промени, но ние ще използваме курсора действително отиде от възел до възел. 

Така че в тази линия за четем чрез файла речник. И ние използваме fgetc. Fgetc ще вземете една-единствена символ от файла. Отиваме да продължи вземете символи, докато ние не достигат край на файла. 

Има два случая, които трябва да се справя. Първият, ако характер не е на нов ред. Така че ние знаем, ако това е нов ред, а след това ние сме на път да се премине към нова дума. Но ако приемем, че не е на нов ред, а след това Тук искаме да разбера индекс отиваме да индекс в в масива, че децата разгледахме преди. 

Така че, както казах и преди, ние трябва да специален случай апостроф. Забележете, ние сме с помощта на трикомпонентни оператор тук. Така че ние ще чете това като, ако характера четем в е апостроф, след това отиваме да настроите индекс = "азбука" -1, което ще е индекс 26. 

Иначе, ако не беше апостроф, има отиваме да зададете индекс равна на с - един. Така че не забравяйте преди това обратно от р-комплекти, C - един ще ни даде на азбучен ред от C. Така че, ако C е буквата А, това ще ни даде индекс нула. За буквата Б, тя ще даде ни индекс 1, и така нататък. 

Така че това ни дава индекса в деца масив, който ние искаме. Сега, ако този показател в момента е нула в децата, това означава, че една възлова точка понастоящем не съществува от този път. Така че ние трябва да се разпределят възел за този път. Това е, което ние ще направим тук. 

Така че ние отиваме отново да използвате calloc функция, така че ние не трябва да се нула, за всички указатели. И ние отново трябва да се провери че calloc не пропусна. Ако calloc се провали, тогава ние трябва да се разтоварят всичко, затворете ни речник, и връщане фалшиви. Така че, ако се приеме, че той не се провали, след това това ще създаде ново дете за нас. И тогава ние ще отидем на това дете. Нашата курсора ще обхождане свежда до това дете. 

Сега, ако това не е нула, за да започнем с това, след курсора може просто да превъртите свежда до това дете, без всъщност да се налага да заделят нищо. Това е случаят, когато за първи път се е случило разпредели на думата "котка". И това означава, че когато отидем да се разпределят "Катастрофа", ние не трябва да се създаде възли за C-A-T отново. Те вече съществува. 

Какво е това друго? Това е състояние, при което е в наклонена черта н, където С е на нов ред. Това означава, че ние имаме успешно завършен дума. Сега това, което искаме да правим, когато успешно завършено дума? Ние ще използваме тази дума поле във вътрешността на нашата структура възел. Искаме да настроите, че за да е истина. Така че показва, че този възел показва успешното дума, действително дума. 

Сега настроите, че за да е истина. Искаме да изчисти нашия курсора до точка в началото на TRIE отново. И най-накрая, нарастване нашия речник размер, тъй като ние открихме друга работа. Така че ние ще продължим да правим това, четене в знак по знак, изграждане на нови възли в нашата Trie и за всяка дума в речника, докато ние най-накрая достигне C! = EOF, в които случай ние се измъкнат от файла. 

Сега има два случая, при които бихме могли да са хит EOF. Първият е, ако е имало грешка четене от файла. Така че, ако е имало грешка, ние трябва да направите характерния. Разтоварете всичко, в близост файла, връщане фалшиви. Ако приемем, че не е грешка, че просто означава, че ние всъщност се удари в края на файла, като в този случай, ние затворете подаде и да се върнете вярно, тъй като ние успешно зареден речник в нашата Trie. 

Така че сега нека проверим проверка. С поглед към функцията за проверка, ние виждаме, че проверка ще се върне булев. Тя връща истина, ако тази дума, че това е да се прехвърлят в наш Trie. Тя връща лъжа в противен случай. Така че как се определя дали тази дума е в нашата Trie? 

Виждаме, че тук, точно както и преди, отиваме да използвате курсора, за да превъртате чрез нашия Trie. Сега тук отиваме да превъртите над цялата ни дума. Така итерации върху думата ние сме минали, ние отиваме да се определи индекс в масива на децата, които съответства на дума скоба I. Така че това ще изглежда точно като натоварване, където, ако думата [в] е апостроф, а след това ние искаме използването на индексите "азбука" - 1. Тъй като установихме, че това е мястото, където отиваме да съхранявате апострофи. 

Иначе ние ще използваме два ниска дума скоба I. Така че не забравяйте, че думата може да имат произволна капитализация. И така, ние искаме да сме сигурни, че сме с помощта на малки букви версия на нещата. И след това се изважда от тази "а" до веднъж отново ни даде Буквеното позиция на този характер. Така че това ще бъде нашият форум в деца масива. 

И сега, ако този индекс в децата масив е нула, това означава, че ние вече не може да продължи итерации надолу нашия Trie. Ако това е така, тази дума не може да евентуално да бъде в нашия Trie. Тъй като, ако се каже, че би означава, че ще има път определени за тази дума. И никога не би срещнало нищожна. Така че се натъкват на нула, ние връщане фалшиви. Думата не е в речника. Ако не беше нула, след това ние сме ще продължи итерации. 

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

Ние не искаме просто да се върне вярно. Ние искаме да се върне на курсора> дума. Тъй като си спомня отново, е "котка" не е в нашия речник, и "катастрофа" е, тогава ние ще можем успешно да чрез думата "кат." Но курсора Думата ще бъде фалшива и не е вярно. Така че ние се върнете курсора дума за обозначаване дали този възел всъщност е дума. И това е за проверка. 

Така че нека да се провери размера. Така размер ще бъде доста лесно тъй като, не забравяйте, в натоварване, ние сме увеличаване размера на речник за всяка дума, която се сблъскваме. Така размер е просто ще върнете речник размер. И това е всичко. 

Така че най-накрая сме се разтоварят. Така се разтоварят, отиваме да се използва рекурсивна функция действително да направим всичко на работата за нас. Така че нашата функция ще бъде повикан за разтоварване. Какво е за разтоварване смяташ да правиш? Виждаме тук, че за разтоварване ще се обхождане на всички деца в този конкретен възел. И ако детето възел не е нула, след това отиваме да разтоварят дете възел. 

Така че това е, че рекурсивно разтоварят всички от нашите деца. След като ние сме сигурни, че всички наши деца са били разтоварени, тогава ние да се освободим, така разтоварят себе си. Това ще работи рекурсивно разтоварят целия TRIE. И тогава, след като това е направено, ние може просто да се върне вярно. Разтоварете не може да се провали. Ние просто се освобождава неща. Така че след като сме готови освобождавайки всичко, върнете вярно. И това е всичко. Моето име е Роб. И това е правопис. 

[За възпроизвеждане на музика]