>> ZAMYLA CHAN: Lad os gøre en stavekontrol.
Hvis du åbner speller.c, så vil du se at de fleste af funktionerne til
kontrol af en tekstfil mod en ordbog er allerede gjort for dig.
. / Speller, der passerer i en ordbog tekst fil og derefter en anden tekstfil,
vil kontrollere, at tekstfil mod ordbogen.
>> Nu vil ordbog tekstfiler indeholder gyldige ord, én pr linje.
Så vil speller.c kalder Load på ordbogen tekstfil.
Det vil kalde en funktion kaldet Tjek på hvert ord i den indtastet tekst-fil,
udskrivning af alle forkert stavede ord.
>> Speller.c vil også ringe størrelse til bestemme antallet af ord i
ordbog og kalder Unload for at frigøre hukommelse.
speller.c vil også holde styr på, hvor meget tid der bruges til at udføre disse
processer, men vi vil komme til senere.
>> Så hvad skal vi gøre?
Vi er nødt til at udfylde dictionary.c.
I dictionary.c har vi hjælper funktion Belastning, der indlæser
ordbogen.
Funktionen Check, som tjekker, om et givet ord findes i ordbogen.
Funktionen Size returnerer antallet af ord i ordbogen.
Og endelig har vi losse, som frigør ordbogen fra hukommelsen.
>> Så det første, lad os tackle Load.
For hvert ord i ordbogen tekst fil, vil Load gemme disse ord i
ordbogen datastruktur efter eget valg, enten et
hash tabel eller en trie.
Jeg vil gå over i både dette gå igennem.
>> Først lad os tale om hash-tabeller.
Sige, at du havde 10 billardkugler og du ønskede at gemme dem.
Du kan sætte dem alle i en spand, og når du havde brug for en specifik
nummererede kugle, ville du tage en ud af spanden på et tidspunkt
udkig efter at bolden.
Og med kun 10 bolde, skal du være i stand til at finde din bold i en rimelig
tid.
>> Men hvad hvis du havde 20 bolde?
Det kan tage lidt længere tid nu.
Hvad med 100?
1.000?
Nu ville det være meget lettere, hvis du havde flere spande.
Måske en skovl til kugler nummereret nul gennem ni anden spand for
kugler nummereret 10 gennem 19, og så videre.
>> Nu når du behov for at søge efter specifikke bold, kunne du automatisk
gå til en specifik spand og søge gennem den spand.
Og hvis hver spand har cirka 10 bolde, så kunne du nemt søge
igennem det.
>> Nu da vi har at gøre med ordbøger, en enkelt spand til
alle de ord i ordbogen, vil sandsynligvis være alt for få spande.
Så lad os tage et kig på hash-tabeller.
>> Tænk på det som en vifte af spande.
Og i dette tilfælde, spande er vores hægtede lister.
Og vi vil distribuere alle vores ord blandt disse mange hægtede lister i
en organiseret måde ved hjælp af en hash-funktion, som vil fortælle os, hvilke
spand en given nøgle, en given ord, tilhører.
>> Lad os repræsentere denne skematisk.
De blå bokse her indeholder værdier og røde kasser peger på en anden værdi
pointer par.
Vi kalder disse par noder.
Nu, hver spand, som jeg sagde tidligere, er en linket liste.
I hægtede lister, hver node har en værdi, samt en pointer til
næste værdi.
>> Nu beskæftiger sig med hægtede lister, det er meget vigtigt, at du
ikke mister nogen links.
Og en anden kendsgerning at huske, er, at sidste node, hvis den ikke peger på
anden node, peger på nul.
>> Så hvordan kan vi repræsentere denne i C?
Vi definerer vores struct her.
Og værdien i dette tilfælde er en char array af længde.
Længde plus 1, hvor længde er den maksimale varighed af enhver ord, plus 1 for
null terminator.
Og så har vi en pointer til anden node kaldet Next.
>> Så lad os gøre en lille linket liste.
Først, vil du ønsker at allokere din node, som skaber plads i hukommelsen
størrelsen på din node type.
Og gøre en anden node, igen mallocing.
>> Nu, hvis du ønsker at tildele en værdi til en ord, så vi kan sige node1 pil
ord er lig med "Hello". Denne pil operatør dereferences markøren og
adgang til struct'er variabler.
Denne måde, behøver vi ikke at bruge både prikken og stjernen operatør.
>> Så jeg har node2 pil ord lig "Verden". Og der er værdierne
befolket i mine noder.
For at gøre links, vil jeg gå i node1 arrow næste, adgang til denne node stjerne,
at node pointer, lig node2, peger node1 at node2 to.
Og der har vi en linket liste.
>> Så det var bare en linkede liste, men en hash tabel er en hel vifte af
hægtede lister.
Nå, vi har den samme knude struktur som før.
Men hvis vi ønskede en egentlig hash tabel, så kan vi bare lave en knude pointer
matrix her.
For eksempel størrelse 500.
>> Nu varsel, er der vil være en handel off mellem størrelsen af ​​din
hash tabel og størrelsen af dine linkede lister.
Hvis du har en virkelig højt antal spande, forestiller at skulle køre tilbage
og tilbage i en linie, find din spand.
Men du ønsker heller ikke et lille antal spande, fordi så er vi tilbage til
det oprindelige problem, hvordan har alt for mange bolde i vores spand.
>> OK, men hvor er vores bold hen?
Nå, vi først nødt til at har en bold, right?
Så lad os malloc en knude for hver nye ord, som vi har.
node * new_node ligemænd malloc (sizeof (node)).
>> Nu, hvor vi har denne struktur, vi kan scanne i, ved hjælp af funktionen
fscanf, en snor fra vores fil, hvis det er en ordbog fil, i
new_node pil ord, hvor new_node pil ord er vores
destination af dette ord.
>> Dernæst vil vi ønsker at hash, der ordet ved hjælp af en hash-funktion.
En hash-funktion tager en streng og returnerer et indeks.
I dette tilfælde indekset skal være mindre end antallet af
spande, som du har.
>> Nu hashfunktioner, når du forsøger at finde en og skabe et af
din egen, så husk, at de være deterministisk.
Det betyder, at den samme værdi skal til det samme spand hver gang
at du hash det.
>> Det er lidt ligesom et bibliotek.
Når du tager en bog, baseret på den forfatter, du ved, hvilken hylde det skal
gå på, om det er hylde nummer en, to eller tre.
Og at bogen vil altid tilhøre på enten hylde en, to eller tre.
>> Så hvis new_node pil ord har ord fra din ordbog, så
hashing new_node pil Word give os indekset for
spand af hash tabellen.
Og så vil vi indsætte det i det specifik linkede liste angives af
returnere værdien af ​​vores hash funktion.
>> Lad os se på et eksempel på indsætning af en knude i
begyndelsen af ​​en linket liste.
Hvis hovedet er et knudepunkt pointer, der angiver begyndelsen af ​​en sammenkædet
listen, og new_node angiver den nye node, du ønsker at komme ind, blot
tildele hoved til new_node ville miste linket til resten af ​​listen.
Så vi ønsker ikke at gøre dette.
>> Snarere, vi ønsker at sikre, at vi holder fast i hver
enkelt node i vores program.
Så kører new_node pil ud ligemænd hoved og derefter hoved lig new_node
bevarer alle de links og ikke miste nogen.
>> Men hvad nu hvis du vil have din liste til at være sorteres, fordi at have en ordnet forbundet
Listen kan være lettere for søge det senere?
Tja, for det, du behøver at vide hvordan at krydse hægtede lister.
>> At krydse en sammenkædet liste, lad os få en knude Pointeren, et knudepunkt * at virke som
markøren, angiver, hvilke node du er på, startende
på det første element.
Looping indtil markøren er nul, kan vi foretage visse processer og derefter
flytte markøren, når vi har brug for hjælp markørpil værdi.
>> Husk, det er det samme som siger stjerne cursor, dereferere
markøren, og derefter ved hjælp af dot operatør værdi.
Så opdatere markøren ved at tildele markøren til markørpil næste.
>> Sig du bestemme, at D bliver i mellem C og E. Hvis du vil indsætte noden,
har new_node D peger på node E, som er markøren ud.
Og så C, markøren, kan derefter pege til D. Denne måde, du vedligeholde en liste.
Vær forsigtig med ikke at miste dine links ved flytte markøren pilen ved siden af ​​D
højre væk.
>> Ok.
Så det er, hvordan du kan indsætte noder, indlæse dem i, load ord i dem
knudepunkter, og indsætte dem ind i din hash tabellen.
Så lad os nu se på forsøg.
>> I en trie vil hver node indeholde en matrix node pegepinde, en for hver
bogstav i alfabetet plus en apostrof.
Og hvert element i arrayet vil pege på en anden node.
Hvis denne node er nul, så dette bogstav kommer ikke til at være det næste bogstav i
et ord i en rækkefølge, fordi hver ord angiver, om det er den sidste
karakter af et ord eller ej.
>> Lad os se på et diagram.
Forhåbentlig vil tingene være lidt tydeligere.
I dette diagram, ser vi, at kun visse bogstaver og visse delstrenge
er ved at blive opført ud.
Så du kan følge visse stier, og alle disse stier vil føre dig til
forskellige ord.
>> Så hvordan kan vi repræsentere denne i C?
Nå, hver node nu kommer til at have en boolesk værdi, der angiver, om
dette knudepunkt er slutningen af et givet ord eller ej.
Og så vil det også have en bred vifte af node pointers kaldet børn, og
Der kommer til at være 27 af dem.
Og husk, vil du også ønsker at holde styr på din første node.
Vi kommer til at kalde det rod.
>> Så det er strukturen af ​​en trie.
Hvordan kan vi repræsentere denne som en ordbog?
Nå, for at indlæse ord, for hver ordbog ord, du vil ønsker
at gentage gennem trie.
Og hvert element i børnenes svarer til et andet bogstav.
>> Så kontrollere værdien på børn indeks i, hvor jeg repræsenterer
specifik indeks af brevet, at du forsøger at indsætte.
Tja, hvis det er nul, så vil du ønsker at malloc en ny node og få børn
Jeg peger på denne node.
>> Hvis det ikke er null, så det betyder, at at i betragtning gren, der givet
substring, findes allerede.
Så vil du bare flytte til det ny node og fortsætte.
Hvis du er i slutningen af ​​det ord, du forsøger at indlæse i
ordbog, så du kan indstille, at aktuelle node, at du er på sand.
>> Så lad os se på et eksempel på at indsætte ordet "ræv" i vores
ordbogen.
Lad som om vi starter med en tom ordbog.
Det første bogstav, F, vil blive placeret børn indeks fem af rødderne
børn array.
Så vi indsætter det i.
>> Bogstavet O vil derefter være i børn indeks 15, efter at F. Og så X
vil være endnu lavere end det, der forgrener off af O børn.
Og så fordi X er det sidste bogstav af ordet "ræv", så jeg har tænkt mig at
farve, at grøn for at angive, Det er slutningen af ​​ordet.
I C, ville det være indstilling er Word Boolean værdien sandt.
>> Hvad nu hvis det næste ord, at du er lastning i er ordet "foo"?
Nå, behøver du ikke at allokere mere plads til F eller O, fordi
de findes allerede.
Men den sidste O i foo?
At man, er du nødt til malloc.
Lav en ny knude til at sætte Is Word Boolean til sand.
>> Så lad os nu indsætte "hund". Dog vil starte med indeks tre af rødderne
børn, fordi D har ikke blevet oprettet endnu.
Og vi vil følge en lignende proces som før, skaber understreng hund,
hvor er G er farvet grøn, fordi det er slutningen af ​​et ord.
>> Hvad nu, hvis vi ønsker at indsætte "gøre"?
Nå, dette er en delstreng af hund, så vi behøver ikke at malloc længere.
Men vi har brug for at angive, hvor vi har nået slutningen af ​​det ord.
Så O vil blive farvet grøn.
Fortsat denne proces for hver enkelt ord i din ordbog, du har
indlæst dem i ind i enten din hash tabel eller din trie.
>> speller.c vil passere i snore for dictionary.c at kontrollere dem.
Nu Kontrollér funktionen har til at operere under tilfælde ufølsomhed.
Det betyder, at store bogstaver og små bogstaver og en blanding af begge
bør alle svare til sand, hvis nogen kombination, der er i
ordbogen.
Du kan også antage, at strenge er kun kommer til at indeholde alfabetisk
tegn eller apostrof.
>> Så lad os se på, hvordan du kan kontrollere med en hash tabel struktur.
Tja, hvis ordet findes, så er det kan findes i hash tabellen.
Så kan du prøve at finde, ord i den pågældende spand.
>> Så der spand ville dette ord være i?
Nå, ville du få nummeret, at indekset af spanden, ved hashing det ord
og derefter søge i den linkede liste, gennemkører gennem hele
linkede liste, ved hjælp af String Sammenlign funktion.
>> Hvis enden af ​​den sammenkædede liste nået, hvilket betyder, at markøren
når nul, så ordet ikke findes i ordbogen.
Det vil ikke være i en anden spand.
Så her kan du se, hvordan der måske være et trade-off mellem at have enten
sorteret hægtede lister eller usorterede dem.
Enten vil tage mere tid under indlæse eller mere tid under kontrol.
>> Hvordan kan du tjekke en trie struktur?
Vi kommer til at rejse nedad i trie.
For hvert bogstav i indtastet ord at vi tjekker, vil vi gå til at
tilsvarende element i børnene.
>> Hvis dette element er nul, så det betyder, at der ikke er delstrenge
indeholder vores input ord, så ordet er stavet forkert.
Hvis det ikke er nul, kan vi flytte til næste bogstav i ordet, at vi er
kontrol og fortsætte denne proces indtil vi når til slutningen
af input-ord.
Og så kan vi kontrollere IF er Word er sandt.
Hvis det er, så stor.
Ordet er korrekt.
Men hvis ikke, selvom det substring findes i trie ordet er
stavet forkert.
>> Når funktionen Størrelse kaldes, størrelse skal returnere antallet af ord,
er i din given ordbog datastruktur.
Så hvis du bruger en hash tabel, du kan enten gå gennem hver enkelt
forbundet liste i hvert enkelt spand tælle antallet
ord er der.
Hvis du bruger en trie, kan du gå igennem alle ikke null
sti i din trie.
Eller mens du lægger ordbogen i, måske kan du holde styr på, hvordan
mange ord du lægger i.
>> Når speller.c færdig kontrollere tekstfil mod ordbogen, så
det er gjort, og så det kalder Unload, hvor dit job er at frigøre noget
at du har malloced.
Så hvis du bruger en hash tabel, så du skal være særlig omhyggelig med at undgå
memory leaks ved ikke at frigøre noget tidligt og holde på hver
enkelt link, før du gratis.
>> Så for hvert element i hash tabellen og for hver node i den linkede liste,
du ønsker at frigøre denne node.
Hvordan kan du gå om at frigøre en sammenkædet liste?
Indstilling af din node pointer markøren til hovedet, til begyndelsen af ​​den
linkede liste, så mens markøren ikke er nul, kan du indstille en midlertidig
node pointer til din markør.
Derefter rykke markøren.
Og så kan du frigøre det midlertidige værdi, mens du stadig holder på
alt bagefter.
>> Hvad hvis du bruger en trie?
Så den bedste måde at gøre dette er at losse fra den meget
bunden til toppen.
Ved at rejse til den lavest mulige node, kan du frigøre alle pejlemærker i
at børn og derefter bakke opad, hvilket frigør alle elementer i alle
børnenes arrays, indtil du rammer din top rodnoden.
Her er hvor Rekursion vil komme i handy.
>> For at sikre at du har sikkert befriet alt det, du har malloced,
kan du bruge Valgrind.
Løb Valgrind vil køre dit program tælle, hvor mange bytes af hukommelse
du bruger, og at sikre, at du har befriede dem alle, fortæller dig
hvor du måske har glemt at fri.
Så kører det, og når Valgrind fortæller dig og giver dig gå videre, så
du er færdig med unload.
>> Nu, et par tips, før du går slukket og begynde at gennemføre din
ordbogen.
Jeg vil anbefale at passere i et mindre ordbogen, når du forsøger at teste
ting ud og debugging med BNP.
Brugen af ​​Speller. / Speller, en valgfri ordbog og derefter en tekst.
>> Som standard, indlæser i den store ordbog.
Så du måske ønsker at videregive i den lille ordbog, eller måske endda gøre din
egne, tilpasse din ordbog og din tekstfil.
>> Og så endelig, jeg vil også anbefale at tage en pen og papir og tegne
ting ud før, under og efter du har skrevet alle dine kode.
Bare sørg for, at du har fået disse pejlemærker lige højre.
>> Jeg ønsker dig held og lykke.
Og når du er færdig, hvis du gerne vil at udfordre den store bestyrelse og
se, hvor hurtigt dit program er i forhold til dine klassekammerater ', så opfordrer jeg
dig til at tjekke det ud.
>> Med det, har du færdig speller PSET.
Mit navn er Zamyla, og det er CS50.