ZAMYLA CHAN: La oss gjøre en stavekontroll. Hvis du åpner speller.c, så vil du se at det meste av funksjonalitet for sjekker en tekstfil mot en ordbok er allerede gjort for deg. . / Stavekontroll, passerer i en ordbok tekst fil og deretter en annen tekstfil, vil sjekke at tekstfil mot ordlisten. 

Nå vil ordbok tekstfiler inneholder gyldige ord, ett per linje. Deretter vil speller.c ringe Load på ordlisten tekstfil. Det vil kalle en funksjon kalt Sjekk på hvert ord i inputted tekstfil, utskrift av alle feilstavede ord. 

Speller.c vil også ringe størrelse til bestemme antall ord i ordbok og ringe Last ut å frigjøre minne. speller.c vil også holde styr på hvor mye tid blir brukt til å drive disse prosesser, men vi vil komme til det senere. 

Så hva trenger vi å gjøre? Vi trenger å fylle ut dictionary.c. I dictionary.c, har vi hjelperen funksjon Load, som laster ordbok. Funksjonen Check, som sjekker om et gitt ord er i ordboken. Funksjonen Size returnerer antall av ord i ordboken. Og til slutt, har vi losse, som frigjør ordlisten fra minnet. 

Så først, la oss takle Load. For hvert ord i ordlisten tekst fil, vil Load lagre disse ordene i ordlisten datastruktur som du selv velger, enten en hash tabell eller en trie. Jeg skal gå over både i dette går gjennom. 

Først la oss snakke om hash tabeller. Si at du hadde 10 billiard baller og du ønsket å lagre dem. Du kan sette dem alle i en bøtte, og når du trengte en bestemt nummerert ball, vil du ta en ut av skuffen om gangen på jakt etter den ballen. Og med bare 10 baller, bør du være i stand til å finne ballen din i en rimelig tidsperiode. 

Men hva hvis du hadde 20 baller? Det kan ta litt lengre tid nå. Hva med 100? 1000? Nå ville det være mye lettere hvis du hadde flere bøtter. Kanskje en bøtte for baller nummerert fra null gjennom ni, en annen bøtte for baller nummerert 10 gjennom 19, og så videre. 

Nå når du trengte å lete etter spesifikke ball, kan du automatisk gå til en bestemt bøtte og søke gjennom at bøtte. Og hvis hver bøtte har ca 10 baller, så du kan enkelt søke gjennom den. 

Nå, siden vi har med å gjøre ordbøker, én bøtte for alle ordene i ordlisten vil sannsynligvis være altfor få bøtter. Så la oss ta en titt på hash tabeller. 

Tenk på det som en matrise av bøtter. Og i dette tilfellet, de bøtter er våre lenkede lister. Og vi vil distribuere alle våre ord blant disse flere lenkede lister i en organisert måte ved hjelp av en hash-funksjon, som vil fortelle oss hvilke bøtte en gitt nøkkel, en gitt ord, tilhører. 

La oss representerer dette skjematisk. De blå boksene her inneholder verdier og røde boksene peker til en annen verdi pekeren pair. Vi kaller disse parene noder. Nå, hver bøtte, som jeg sa tidligere, er en lenket liste. I lenkede lister, har hver node en verdi, samt en peker til neste verdi. 

Nå arbeider med koblede lister, det er svært viktig at du ikke mister noen linker. Og et annet faktum å huske er at siste node, hvis det ikke peker til en annen node, peker på null. 

Så hvordan skal vi representerer dette i C? Vi definerer vår struct her. Og verdien i dette tilfellet er en røye array av lengde. Lengde pluss 1, hvor lengden er Maksimal lengde på noen ord, pluss en for den avsluttende null. Og så har vi en peker til en annen node kalt Next. 

Så la oss gjøre et lite lenket liste. Først vil du ønsker å malloc din noden, som skaper plass i minnet på størrelsen på nodetypen. Og foreta en ny node, igjen mallocing. 

Nå hvis du ønsker å tilordne en verdi til en Ordet, så vi kan si node1 pil Ordet er lik "Hei." Denne pilen operatør dereferences pekeren og aksesserer struct variabler. På denne måten trenger vi ikke å bruke både prikken og stjernen operatør. 

Så da har jeg node2 pil ord lik "Verden." Og det er verdiene befolket i mine noder. For å gjøre koblingene, vil jeg passere i node1 arrow neste, tilgangen til denne noden stjerne, at node pekeren, lik node2, peker node1 å node2 to. Og der har vi en lenket liste. 

Så det var bare en lenket liste, men en hash table er en hel rekke lenkede lister. Vel, vi har den samme node strukturere som før. Men hvis vi ønsket en faktisk hash table, da kan vi bare gjøre en node peker matrise her. For eksempel, størrelsen 500. 

Nå varsel, kommer det til å være en avveining off mellom størrelsen på nøkkeltabell og størrelsen av dine lenkede lister. Hvis du har et virkelig høyt antall bøtter, forestille å måtte kjøre tilbake og tilbake i en linje for å finn din bøtte. Men du også ønsker ikke et lite antall av bøtter, for da er vi tilbake til den opprinnelige problemet med hvordan ha altfor mange baller i vår bøtte. 

OK, men hvor kommer vår ballen gå? Vel, må vi først har en ball, ikke sant? Så la oss malloc en node for hver nytt ord som vi har. node * new_node likemenn malloc (sizeof (node)). 

Nå som vi har denne strukturen, vi kan skanne inn ved hjelp av funksjonen fscanf, en streng fra vår fil, hvis det er en ordbok fil, inn new_node pil ord, hvor new_node pil ord er vår målet for det ordet. 

Deretter vil vi ønsker til hasj som ordet med en hash-funksjon. En hash-funksjon tar en streng og returnerer en indeks. I dette tilfellet har indeksen til være mindre enn antallet bøtter som du har. 

Nå, hash funksjoner, når du prøver å finne en og skape en av din egen, husk at de må være deterministisk. Det betyr at den samme verdi må kart til samme bøtte hver gang at du hash det. 

Det er litt som et bibliotek. Når du tar en bok, basert på forfatter, vet du hvilken hylle den skal gå på, enten det er hyllenummer en, to, eller tre. Og at boken vil alltid hører hjemme på enten hylle en, to, eller tre. 

Så, har hvis new_node pil ordet ord fra ordboken, deretter hashing new_node pil ord vil gi oss indeksen for bøtte med hash tabellen. Og så får vi sette det inn i den spesifikke lenket liste indikeres av returnere verdien av vår hash-funksjon. 

La oss se på et eksempel på sette inn en node inn i begynnelsen av en lenket liste. Hvis hodet er en node peker som angir I begynnelsen av en koblet liste, og new_node angir nye node som du ønsker å komme inn, bare tildele hodet til new_node ville miste koblingen til resten av listen. Så vi ønsker ikke å gjøre dette. 

Snarere ønsker vi å sørge for at at vi holder fast ved hver enkelt node i vårt program. Så kjører new_node pilen ved likhets hodet og deretter hodet tilsvarer new_node vil bevare alle linker og ikke miste noen. 

Men hva hvis du vil at listen for å være sortert, fordi det å ha en sortert knyttet Listen kan være lettere for søker det senere? Vel, for det, vil du trenger å vite hvordan å traversere lenkede lister. 

Å krysse en lenket liste, la oss ha en node peker, en node *, for å fungere som markøren, som angir hvilke node du er på, starter på det første element. Looping inntil markøren er null, kan vi gjennomføre visse prosesser og deretter flytte markøren når vi trenger bruker markørpilen verdi. 

Husk, dette er det samme som sier stjerne markøren, dereferencing markøren, deretter bruke dot operatør verdi. Så oppdaterer markøren ved å tildele markøren til markørpilen ved. 

Si du finner ut at D blir i mellom C og E. For å sette noden, har new_node D punktet til node E, som er markøren ved siden av. Og så C, markøren, kan deretter peke til D. På den måten opprettholder du en liste. Vær forsiktig så du ikke mister koblingene ved flytte markøren pilen ved siden av D med en gang. 

OK. Så det er slik du kan sette noder, laste dem inn, last ord inn i de noder, og sett dem inn i hash table. Så nå la oss se på prøver. 

I en trie, vil hver node inneholde en rekke node pekere, en for hver bokstav i alfabetet pluss en apostrof. Og hvert element i matrisen vil peke til en annen node. Hvis det node er null, så det brevet ikke kommer til å bli den neste bokstaven noen ord i en sekvens, fordi hver Ordet viser om det er den siste karakter av et ord eller ikke. 

La oss se på et diagram. Forhåpentligvis vil ting være litt klarere. I dette diagrammet ser vi at bare bestemte bokstaver og enkelte dels blir listet ut. Så du kan følge visse stier, og alle disse banene vil lede deg til forskjellige ord. 

Så hvordan skal vi representerer dette i C? Vel, hver node nå kommer til å ha en boolsk verdi som angir om at noden er slutten av et gitt ord eller ikke. Og så det vil også ha en rekke node pekere kalt barn, og det kommer til å være 27 av dem. Og husk, du vil også være lurt å holde styr på din første noden. Vi kommer til å kalle det rot. 

Så det er strukturen i en trie. Hvordan kan vi representerer dette som en ordbok? Vel, for å laste ord i, for hver ordbok ord, du kommer til å ønske å reagere gjennom den trie. Og hvert element i barna svarer til en annen bokstav. 

Så sjekker verdien på barn indeksen i, hvor jeg representerer nærmere angitt indeks av brevet at du prøver å sette inn. Vel, hvis det er null, så vil du ønsker å malloc en ny node og har barn Jeg peker på at node. 

Hvis det ikke er null, så det betyr at at gitt gren, at gitt delstreng, finnes allerede. Så da vil du bare flytte til at ny node og fortsetter. Hvis du er på slutten av ordet som du prøver å laste inn i ordbok, så kan du sette at gjeldende node at du er på å true. 

Så la oss se på et eksempel på å sette inn ordet "rev" i vår ordbok. Lat som vi starter med en tom ordbok. Den første bokstaven, F, vil bli plassert hos barn indeks fem av røttene barn array. Så vi setter det i. 

Bokstaven O vil da være i barn indeks 15, etter at F. Og så X vil bli enda under det, forgrener ut av Os barn. Og så fordi X er den siste bokstaven av ordet "rev", så jeg kommer til å farge som grønt for å indikere at det er slutten av ordet. I C, ville det være å sette Is Word boolsk til verdien true. 

Hva nå hvis det neste ordet som du er lasting i er ordet "foo"? Vel, du trenger ikke å malloc noe mer plass for F eller for O, fordi de som allerede eksisterer. Men den siste O i foo? At man, må du malloc. Lag en ny node for det, innstilling Is Word boolsk til sann. 

Så nå skal vi sette inn "hund". Dog vil starte med indeks tre av røttene barn, fordi D har ikke er laget ennå. Og vi vil følge en tilsvarende prosess som før, skaper substrengen hund, hvor er G er farget grønt fordi det er slutten av et ord. 

Nå, hva om vi ønsker å sette inn "gjøre"? Vel, dette er en delstreng av hund, så vi trenger ikke å malloc lenger. Men vi trenger ikke å indikere hvor vi har nådd slutten av det ordet. Så O vil bli farget grønn. Fortsetter denne prosessen for hver enkelt ord i ordlisten, har du lastet dem inn i enten ditt hash table eller din trie. 

speller.c vil passere i strenger for dictionary.c å sjekke dem. Nå har Check-funksjonen for å operere henhold tilfelle ufølsomhet. Det betyr at store bokstaver og små bokstaver og en blanding av begge deler bør alle likestille til sann hvis noen kombinasjon av det som er i ordbok. Du kan også anta at strengene er bare kommer til å inneholde alfabetisk tegn eller apostrofer. 

Så la oss se på hvordan du kan sjekke med en hash tabell struktur. Vel, hvis ordet finnes, så det kan finnes i nøkkeltabell. Så da kan du prøve å finne at ordet i det aktuelle skuffe. 

Så hvilken bøtte ville det ordet være i? Vel, vil du få antall, at indeksen av bøtta, ved hashing det ordet og deretter søke i det lenket liste, krysser gjennom hele lenket liste, ved hjelp av String Sammenligne funksjon. 

Hvis slutten av lenket liste er nådd, noe som betyr at markøren når null, da ordet ikke å finne i ordlisten. Det vil ikke være i en hvilken som helst annen bøtte. Så her kan du se hvordan det kan være en avveining mellom å ha enten sortert lenkede lister eller usorterte seg. Enten vil ta mer tid under laste eller mer tid under innsjekking. 

Hvordan kan du sjekke inn en trie struktur? Vi kommer til å reise nedover i trie. For hver bokstav i inputted ordet at vi sjekker, vil vi gå til det tilsvarende element i barna. 

Hvis dette elementet er null, så det betyr at det ikke er noen dels inneholder våre innspill ord, så ordet er feilstavet. Hvis det ikke er null, kan vi flytte til neste bokstav i ordet at vi er kontroll og fortsette denne prosessen før vi når slutten av inngangsordet. Og så kan vi sjekke If er Word er sant. Hvis det er, så flott. Ordet er riktig. Men hvis ikke, selv om det substring eksisterer i trie, er ordet feilstavet. 

Når funksjonen Size kalles, størrelse skal returnere antall ord som er i din gitt ordbok datastruktur. Så hvis du bruker en hash table, du kan enten gå gjennom hver enkelt lenket liste i hver enkelt bøtte telle antall av ordene er der. Hvis du bruker en trie, kan du gå gjennom alle ikke null banen i din trie. Eller mens du laster ordlisten i, kanskje du kan holde styr på hvor mange ord du lasting i. 

Når speller.c ferdig sjekke tekstfil mot ordboken, deretter det er gjort og så det kaller losse, hvor din jobb er å frigjøre noe at du har malloced. Så hvis du bruker en hash table, så du må være spesielt nøye med å unngå minnelekkasjer ved ikke å frigjøre noe tidlig og holder på hver single link før du gratis. 

Så for hvert element i hash table og for hver node i lenket liste, vil du ønsker å frigjøre den noden. Hvordan du går om å frigjøre en lenket liste? Innstilling din node pekeren til hodet, til begynnelsen av lenket liste, deretter mens markøren er ikke null, kan du sette en midlertidig node pekeren til markøren. Deretter flytte markøren. Og så kan du frigjøre at midlertidig verdi mens du fremdeles holder på å alt etterpå. 

Hva hvis du bruker en trie? Så den beste måten å gjøre dette er å losse fra selve bunnen til toppen. Ved å reise til lavest mulig node, kan du frigjøre alle pekere i at barn og deretter backtrack oppover, frigjør alle elementene i alle av barnas arrays, inntil du treffer din topp rotnoden. Her er der Rekursjon vil komme godt med. 

For å være sikker på at du har sikkert frigjort alt som du har malloced, du kan bruke Valgrind. Kjører Valgrind vil kjøre programmet telle hvor mange byte minne du bruker, og å sørge for at du har frigjort dem alle, forteller deg hvor du kan ha glemt å fri. Så kjører det og når Valgrind forteller deg og gir deg klarsignal, deretter du er ferdig med å losse. 

Nå, et par tips før du går av og begynne å implementere din ordbok. Jeg vil anbefale å passere i en mindre ordbok når du prøver å teste ting ut og debugging med BNP. Bruken av stavekontroll er. / Stavekontroll, en valgfritt ordbok, og deretter en tekst. 

Som standard laster det i den store ordbok. Så kan det være lurt å passere i den lille ordlisten, eller kanskje til og med lage din egne, tilpasse ordbok og tekstfilen. 

Og så til slutt, jeg vil også anbefale å ta en penn og papir og tegne ting ut før, under og etter du har skrevet alt av koden din. Bare sørg for at du har fått disse pekere akkurat. 

Jeg ønsker deg lykke til. Og når du er ferdig, hvis du ønsker å utfordre den store bord og se hvor fort programmet er i forhold til klassekameratene dine ', så jeg oppfordrer deg til å sjekke det ut. 

Med det, er du ferdig stavekontrollen PSett. Mitt navn er Zamyla, og dette er CS50.