ROB BOWDEN: Hi. Аз съм Роб, и хашиш нека да това решение навън. Така че тук ние ще се приложат обща таблица за хашиш. Виждаме, че структурата на възел на нашата хеш маса ще изглежда по този начин. Така че няма да има Чар дума масив от размер дължина плюс един. Да не забравяме и една от максимално дума в речника е 45 герои, а след това ние ще нужда от един допълнителен характер по наклонена черта 0. 

И тогава нашата хеш таблица във всяка кофа ще се съхранява свързан списък от възли. Ние не правим линейна сондиране тук. И така, за да се свърже към следващата елемент в кофата, ние се нуждаем от структура възел * следващия. Така че това е, което възел изглежда. Сега, тук е декларацията на нашата хеш таблица. Тя ще има 16 384 кофи, но този номер няма значение. И накрая, ние ще имаме глобална променлива hashtable_size, които ще започнем като 0, а това е Ще следим колко думи са в нашия речник. Добре. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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