ZAMYLA Чан: Да се ​​направи проверка на правопис. Ако отворите speller.c, тогаш ќе видите дека повеќето од функционалност за проверка текстуална датотека против речник е веќе направен за вас. . / Правопис, минувајќи во речник текст датотека, и потоа друг текст фајл, ќе провери дека текстуална датотека против речникот. 

Сега, речник текстуални датотеки ќе содржат валидни зборови, по еден на линија. Тогаш speller.c ќе се јавите Вчитај на речникот текст фајл. Тоа ќе се јавите на функција наречена Проверете на секој збор во внесуваат текст фајл, печатење на сите погрешно напишани зборови. 

Speller.c, исто така, ќе се јавите Големина да се утврди бројот на зборови во речник и повик Бриши за да се ослободи меморија. speller.c, исто така, ќе ги пратите на тоа како колку време се користи за да се спроведе на овие процеси, но ние ќе добиете за таа подоцна. 

Значи она што ние треба да направам? Ние треба да се пополни во dictionary.c. Во dictionary.c, имаме помошник функција оптоварување, кое го вчитува речникот. Функцијата Проверете, која проверува дали даден збор е во речникот. Функцијата Големина враќа бројот на зборови во речникот. И, конечно, имаме бриши, која ослободува речникот од меморијата. 

Значи прво, да се справи со оптоварување. За секој збор во речникот текст датотека, оптоварување ќе се сместат тие зборови во речникот податочна структура на вашиот избор, или хеш табелата или TRIE. Јас ќе одам над двата во оваа прошетка низ. 

Прво нека зборува за хеш табели. Велат дека имал 10 билијард топки и ти сакаше да ги чува. Може да ги стави сите во кофа, и кога ви се потребни специфични нумерирани топката, ќе се земе една од кофата на време во потрага по таа топка. И со само 10 топки, треба да бидат можат да се најдат на вашиот топката во разумен количина на време. 

Но, што ако сте имале 20 топки? Тоа би можело да потрае малку подолго, сега. Што е со 100? 1000? Сега, тоа ќе биде многу полесно ако сте имале повеќе кофи. Можеби една кофа за топки нумерирани нула преку девет, друг корпата за топки нумерирани од 10 до 19, и така натаму. 

Сега кога ви се потребни за да се погледне за специфични топка, можете да автоматски одат на една специфична кофата и пребарување низ кои кофа. И ако секоја канта има околу 10 топки, тогаш лесно може да пребарувате низ него. 

Сега, бидејќи ние сме се занимаваат со речници, една кофа за сите зборови во речникот ќе веројатно се премногу малку кофи. Па ајде да ги разгледаме во хеш табели. 

Сфатете го тоа како низа на кофи. И во овој случај, кофи се нашите поврзани листи. И ние ќе го дистрибуирате сите наши зборови меѓу овие повеќе поврзани листи во организиран начин си користење на хеш функција, кои ќе ни каже кои кофа дадениот клуч, даден збор, му припаѓа. 

Ајде да ја претставува оваа шематски. Сини кутии тука содржи вредности и црвени кутии до друга точка вредност покажувачот пар. Ние ќе го нарекуваме овие парови јазли. Сега, секоја канта, како што реков порано, е поврзана листа. Во поврзани листи, секој јазол има вредност, како и покажувач на следната вредност. 

Сега, кои се занимаваат со поврзани листи, тоа е многу важно што ќе не губат какви било врски. И уште еден факт да се запамети е дека последните јазол, ако не се укаже на друг јазол, укажува на нула. 

Така како ние да ја претставува оваа во C? Ние се дефинираат нашите struct тука. И вредноста во овој случај е на знак низа од должина. Должина плус 1, каде што должина е Максималната должина на секој збор, плус 1 за нула терминатор. И тогаш имаме покажувач друг јазол наречен Next. 

Па ајде направи мал поврзана листа. Прво, ќе сакате да го Примерок вашиот јазол, кои создаваат простор во меморијата на големината на вашиот јазол тип. И направи уште еден јазол, повторно mallocing. 

Сега ако сакате да се додели вредност на збор, тогаш може да се каже node1 стрелка Зборот е еднакво на "Здраво". Ова стрелките оператор dereferences покажувачот и пристапи променливи на struct е. Овој начин, ние не треба да се користи и точката и ѕвезда оператор. 

Па тогаш имам node2 стрелките збор еднаква на "Свет". И таму, вредностите се населени во мојот јазли. Да се ​​направи линкови, јас ќе помине во node1 стрелката, пристап до тој јазол ѕвезда, тој јазол покажувач, е еднаква на node2, покажувајќи node1 node2 да два. И таму имаме поврзана листа. 

Така што беше само еден поврзана листа, но хаш табелата е цела низа на поврзани листи. Па, ќе го имаат истиот јазол структура како порано. Но, ако сакавме вистински хаш табелата, тогаш ние само може да се направи јазол покажувачот низа тука. На пример, големината 500. 

Сега најава, таму се случува да биде трговска оф меѓу големината на вашиот хеш табелата и големината на вашиот поврзани листи. Ако имате навистина голем број на кофи, замислувајќи да се кандидира назад и назад на ред за да најдете вашиот кофа. Но вие исто така не сакаат мал број кофи, затоа што тогаш ние сме назад кон оригиналниот проблем за тоа како да се има премногу топки во нашата кофа. 

Добро, но каде што нашата топката оди? Па, ние прво треба да се имаат топката, нели? Па ајде Примерок јазол за секоја нов збор што го имаме. јазол * new_node еднаквите Примерок (sizeof (јазол)). 

Сега кога имаме оваа структура, ние да ги скенирате во, со користење на функцијата fscanf, низа од нашите датотека, ако тоа е речник датотека, во new_node стрелките збор, каде new_node стрелките на зборот е нашата дестинација на тој збор. 

Следниот, ние ќе сакате да хаш дека зборот со користење на хаш функција. Хеш функција зема низа и се враќа на индекс. Во овој случај, индексот треба да биде помал од бројот на кофи што го имате. 

Сега, хаш функции, кога ќе се обидуваш да се најде еден и да се создаде една од свој, се сеќавам дека тие мора да биде детерминистичка. Тоа значи дека со иста вредност треба да мапа на истиот кофа во секое време дека ќе ја хаш. 

Тоа е вид на како библиотека. Кога ќе се земе книга, врз основа на авторот, знаете што полица што треба одат за, без разлика дали тоа е полица број еден, два или три. И таа книга секогаш ќе припаѓаат на или полица еден, два или три. 

Значи, ако new_node стрелките збор има збор од речникот, тогаш hashing new_node стрелките зборот ќе ни даде индексот на кофа со хеш табелата. А потоа ние ќе вметнете дека во таа специфични поврзана листа е наведено од страна на се врати вредноста на нашата хеш функција. 

Да ги погледнеме на пример на вметнување на јазол во почетокот на поврзани листа. Ако главата е еден јазол покажувач кој покажува на почетокот на поврзани листа, и new_node укажува на нови јазол кој сакате да го внесете во, само доделување глава до new_node ќе го изгубат врската со остатокот на листата. Па ние не сакаме да го направите тоа. 

Наместо тоа, ние сакаме да се осигураме дека ние се држи до секој еден јазол во нашата програма. Па трчање new_node стрелката еднаквите главата, а потоа главата еднаква new_node ќе ги зачува сите на врски и да не губат било. 

Но што ако сакате вашата листа за да биде подредени, бидејќи имаат сортирани поврзани листа може да биде полесно за во потрага тоа подоцна? Па, за тоа, ќе треба да знаете како да напречни поврзани листи. 

Да напречни поврзана листа, ајде да јазол покажувач, јазол *, да дејствува како курсорот, што укажува кои јазол сте во, почнувајќи на првиот елемент. Looping до курсорот е нула, можеме да спроведе одредени процеси, а потоа унапредување на курсорот кога треба користење на курсорот стрелка вредност. 

Запомнете, ова е истото како велејќи ѕвезда курсорот, dereferencing курсорот, а потоа со помош на точка оператор вредност. Значи ажурирање курсорот е со доделување курсорот до курсорот стрелката. 

Велат дека се утврди дека Д станува во помеѓу C и E. За да ја вметнете јазол, имаат new_node D точка на јазол Е, кој е покажувачот следната. И потоа C, курсорот, тогаш може да укаже да Д На тој начин, ќе се одржи на листата. Бидете внимателни да не да се изгуби вашиот линкови на поместување на стрелките на покажувачот до Д веднаш. 

Во ред е. Па тоа е како може да се вметне јазли, вчитување на нив во, оптоварување зборови во тие јазли, и да ги вметнете во вашиот хаш табелата. Па сега ајде да погледнеме на обидува. 

Во TRIE, секој јазол ќе содржи спектар на јазол покажувачи, по една за секој буква во азбуката плус апостроф. И секој елемент во низата ќе точка за друг јазол. Ако тој јазол е нула, тогаш тоа писмо нема да биде следната буква од секој збор во низа, бидејќи секој Зборот означува дали тоа е последната карактер на зборот или не. 

Да ги погледнеме на дијаграм. Се надевам дека работите ќе се да биде малку појасна. Во овој дијаграм, гледаме дека само одредени букви и некои поднизи се наведени надвор. Па можете да следат одредени патеки, и сите оние патеки ќе ве доведе до различни зборови. 

Така како ние да ја претставува оваа во C? Па, секој јазол сега се случува да имаат Булова вредност означува дали тој јазол е на крајот на даден збор или не. А потоа, исто така, ќе имаат низа на јазол совети наречена деца, и таму се случува да биде 27 од нив. И запомнете, исто така, ќе сакате да го ги пратите на вашиот прв јазол. Ние ќе се јавам дека корен. 

Па тоа е структурата на TRIE. Како да ја претставуваат оваа како речник? Добро, да се вчита зборови во, за секој речникот збор, ви се случува да сакаат да iterate преку TRIE. И секој елемент кај децата одговара на различни букви. 

Па проверка на вредноста на деца индексот i, каде што ја претставува специфични индексот на писмото што ти се обидуваш да го внесете. Па, ако тоа е нула, тогаш ќе сакате да го Примерок нов јазол и имаат деца јас укажуваат на тој јазол. 

Ако не е нула, тогаш тоа значи дека дека со оглед гранка, што им беше дадена подниза, веќе постои. Па тогаш само ќе се преселат во таа нов јазол и да се продолжи. Ако сте на крајот на зборот што ти се обидуваш да се вчита во речник, а потоа можете да го поставите кои тековната јазол дека сте за да се обистини. 

Па ајде да погледнеме еден пример на вметнување зборот "лисица" во нашите речникот. Преправам почнеме со празен речник. На првата буква, F, ќе се наоѓа кај децата индекс пет од корените деца низа. Па ние се вметне дека внатре 

Буквата О, тогаш ќе биде кај децата индекс 15, после тоа Ф И тогаш X ќе биде уште под тоа, разгранување исклучување на децата на O. , А потоа поради X е последната буква на зборот "лисица", а потоа јас ќе одам да боја која зелена за да се покаже дека тоа е крајот на зборот. Во C, кој ќе биде поставување на Е Зборот Булова на вредноста вистина. 

Сега што ако следниот збор што сте вчитување на е зборот "foo"? Добро, вие не треба да Примерок повеќе простор за F или O, бидејќи оние кои се веќе постои. Но последната O во foo? Оној, ќе мора да Примерок. Направи нов јазол за тоа, поставување на е зборот Булова на true. 

Па сега ајде да се вметне "куче". Кучето ќе започне со индекс три од корените деца, бидејќи D го нема уште не е создадена. И ние ќе го следат сличен процес како пред, создавајќи подниза куче, каде е G е обоена со зелена боја, бидејќи тоа е крајот на зборот. 

Сега, што ако сакаме да внесете "не"? Па, ова е подниза на куче, па ние не треба да Примерок повеќе. Но, ние треба да се посочи каде ние сме до крајот на тој збор. Па О ќе биде обоена со зелена боја. Продолжување на тој процес за секоја збор во речникот, сте натоварен нив во во или вашиот хеш табелата или вашиот TRIE. 

speller.c ќе помине во жици за dictionary.c да ги провери. Сега, проверката функција треба да работат под случај нечувствителност. Тоа значи дека големи букви и мали букви и мешавина на двете сите треба да се изедначува со точно ако било комбинација на тоа е во речникот. Можете исто така да се претпостави дека конците се само ќе содржат азбучен карактери или апострофи. 

Па ајде да погледнеме како може да се провери со хеш табелата структура. Па, ако зборот постои, тогаш тоа може да се најде во хеш табелата. Па тогаш може да се обидете да се најде дека збор во релевантните кофа. 

Така што кофата ќе тој збор да биде во? Па, ќе го добиете бројот, тој индекс на корпата, со hashing тој збор а потоа бараат во што поврзана листа, traversing преку целата поврзана листа, со користење на Стринг Споредете функција. 

Ако на крајот на поврзани листа е постигнат, што значи дека вашиот курсорот достигне нула, тогаш зборот не е да се најде во речникот. Тоа нема да биде во било која друга кофа. Па овде, можеби ќе се види како таму би можеле да биде трампа помеѓу имаат или подредени поврзани листи или вон оние. Или ќе биде потребно повеќе време во текот на оптоварување или повеќе време при проверка. 

Како што може да се провери во на TRIE структура? Ние ќе се патува надолу во TRIE. За секоја буква во внесуваат збор дека ние сме проверка, ќе одиме на тоа соодветните елемент во деца. 

Ако тој елемент е нула, тогаш тоа значи дека дека не постојат поднизи кои содржат нашите влез збор, па зборот е погрешно напишан. Ако не е нула, ние може да се движи кон следната буква од зборот, дека ние сме проверка и продолжи овој процес додека не ги добиеме на крајот на влез збор. А потоа може да се провери ако е зборот е вистина. Ако е така, тогаш одлично. Зборот е точно. Но ако не, и покрај тоа што подниза постои во TRIE, зборот е погрешно напишани. 

Кога функцијата Големина се нарекува, големина треба да се врати на број на зборови кои се во вашиот дадена речник податочна структура. Значи, ако сте со користење на хаш табелата, можете или да одат низ секој поврзана листа во секој кофа пребројување на бројот на зборовите се таму. Ако сте со користење на TRIE, можете да поминат низ секој не нула пат во вашиот TRIE. Или додека сте вчитување речникот во, можеби може да ги пратите на тоа како многу зборови сте вчитување внатре 

Откако speller.c завршува проверка на текстуална датотека против речник, потоа тоа е направено и така го нарекува бриши, каде вашата работа е да се ослободи ништо дека сте malloced. Значи, ако имате потреба при користење на хаш табелата, тогаш ќе треба да бидат особено внимателни за да се избегне меморија протекување со тоа што не си заштедувате ништо предвреме и задржување на секој еден линк, пред да бесплатно. 

Значи за секој елемент во хеш табелата и за секој јазол во поврзана листа, ќе сакате да се ослободи тој јазол. Како да одите за ослободување поврзан листа? Поставување на вашиот јазол покажувачот на курсорот до на главата, на почетокот на поврзана листа, а потоа додека курсорот не е нула, можете да поставите привремена јазол покажувач на курсорот. Тогаш напредуваат на курсорот. А потоа можете да слободното дека привремено вредност, додека сеуште држи за да сè што после тоа. 

Што ако сте со користење на TRIE? Тогаш најдобар начин да го направите ова е да се исклучи од самиот дното до врвот. Патувајќи до најниска можна јазол, можете да ги ослободи сите покажувачи во дека децата, а потоа одјавување нагоре, ослободувајќи сите елементи во сите на децата низи, додека ќе погоди вашиот топ root јазол. Тука е местото каде рекурзијата ќе ни се најде. 

Да бидете сигурни дека сте веројатно ослободени сè што сте malloced, можете да го користите Valgrind. Вклучување Valgrind ќе се кандидира на вашиот програма броење колку бајти меморија сте користење и правење на сигурни дека сте ослободени сите нив, ти го кажувам каде што би можеле да имаат заборавил да бесплатно. Така да работи таа и уште Valgrind ви кажува и ти дава зелено светло, тогаш ќе завршите со бриши. 

Сега, неколку совети пред да одите и да почне спроведувањето на вашиот речникот. Јас му препорачувам да помине во помал речник кога ќе се обидуваш да се тестираат работи надвор и дебагирање со БДП. Користење на правопис е. / Правопис, на изборен речник, а потоа и текстот. 

По дифолт, го товари во големите речникот. Па можеби ќе сакате да се помине во мали речник, или можеби дури и го направи вашиот сопствена земја, со измената на вашиот речник и вашиот текст фајл. 

А потоа конечно, би, исто така, препорачуваме да земе пенкало и хартија и да подготви работи надвор пред, за време и по што сум напишал на сите ваши код. Само бидете сигурни дека имате оние совети само десно. 

Ви посакувам најдоброто од среќа. И штом еднаш ќе завршите, ако сакате да се спротивстават на голема табла и види колку брзо вашата програма е во споредба со своите соученици, тогаш јас ве охрабруваме да се провери тоа. 

Со тоа, ќе завршите со на правопис PSet. Моето име е Zamyla, а тоа е CS50.