>> ZAMYLA CHAN: Låt oss göra en stavningskontroll.
Om du öppnar speller.c Du kommer att se att de flesta av funktionerna för
kontrollera en textfil mot en ordlistan är redan gjord för dig.
. / Speller, passerar i en ordbok text fil och sedan en annan textfil,
kommer att kontrollera att textfilen mot ordboken.
>> Nu kommer ordbok textfiler innehåller giltiga ord, en per rad.
Då speller.c ringer Load på ordboken textfil.
Det ringer en funktion som heter Kolla på varje ord i den inmatade textfilen,
skriva ut alla felstavade ord.
>> Speller.c kommer även ringa storlek till bestämma antalet ord i
lexikon och ringa Unload att frigöra minne.
speller.c kommer också att hålla reda på hur mycket tid används för att utföra dessa
processer, men vi ska kommer till det senare.
>> Så vad behöver vi göra?
Vi behöver fylla på dictionary.c.
I dictionary.c har vi hjälpare funktionen Load, som läser in
ordboken.
Funktionen Check, som kontrollerar om ett givet ord i ordboken.
Funktionen storlek returnerar antalet ord i ordboken.
Och slutligen har vi Lasta, vilket befriar ordlistan från minnet.
>> Så först, låt oss ta itu Load.
För varje ord i ordboken text fil, kommer Load lagra dessa ord i
ordboken datastruktur som du väljer, antingen ett
hash tabell eller en trie.
Jag går över både i detta går igenom.
>> Först ska vi prata om hashtabeller.
Säg att du hade 10 biljardbollar och du ville att lagra dem.
Du kan sätta dem alla i en hink, och när man behövde en viss
numrerad boll, skulle du ta en ut ur skopan vid en tidpunkt
söker den bollen.
Och med bara 10 bollar, bör du vara kunna hitta din boll på ett rimligt
tid.
>> Men tänk om du hade 20 bollar?
Det kan ta lite längre tid nu.
Vad sägs om 100?
1000?
Nu skulle det vara mycket enklare om du hade flera hinkar.
Kanske en hink för bollar numrerade noll till nio, en annan hink för
bollar numrerade 10 till 19, och så vidare.
>> Nu när du behövs för att leta efter specifika boll, kan du automatiskt
gå till en specifik hink och söka igenom hinken.
Och om varje hink har cirka 10 bollar, då kan du enkelt söka
genom den.
>> Nu, eftersom vi har att göra med ordböcker, en enda hink för
alla ord i ordlistan kommer förmodligen vara alltför få hinkar.
Så låt oss ta en titt på hashtabeller.
>> Se det som en array av skopor.
Och i detta fall skoporna är våra länkade listor.
Och vi kommer att dela ut alla våra ord bland dessa flera länkade listor i
ett organiserat sätt genom att använda en hash-funktion, som kommer att tala om för oss vilka
hink en viss nyckel, en viss ord, tillhör.
>> Låt oss föreställa denna schematiskt.
De blå rutorna här innehåller värderingar och röda lådor pekar på ett annat värde
pekarparet.
Vi kallar dessa par noder.
Nu, varje hink, som sagt tidigare, är en länkad lista.
I länkade listor, har varje nod ett värde, såväl som en pekare till
nästa värde.
>> Nu, som handlar om länkade listor, det är mycket viktigt att du
inte förlorar några länkar.
Och ett annat faktum att komma ihåg är att det sista noden, om den inte pekar på
annan nod, pekar på null.
>> Så hur ska vi företräder här i C?
Vi definierar vår struct här.
Och värdet i det här fallet är en char array med längden.
Längd plus ett, där längden är det Längsta tid för ord, plus 1 för
noll terminator.
Och sedan har vi en pekare till annan nod som kallas Next.
>> Så låt oss göra en liten länkad lista.
Först vill du malloc din nod, vilket skapar utrymme i minnet för
storleken på din nodtyp.
Och gör en annan nod, igen mallocing.
>> Nu om du vill tilldela ett värde till en ord, då vi kan säga node1 pil
Ordet är lika med "Hej." Denna pil operatör dereferences pekaren och
accessar struct variabler.
På så sätt behöver vi inte använda båda pricken och stjärnan operatören.
>> Så då har jag node2 pil ord lika "Värld." Och där, är värdena
befolkat i mina noder.
För att göra länkarna, jag ska passera i node1 arrow nästa, komma åt den noden stjärna,
den noden pekare, lika node2, pekar node1 att node2 två.
Där har vi en länkad lista.
>> Så det var bara en länkad lista, men en hash-tabell är en hel rad av
länkade listor.
Tja, vi har samma nod strukturera som tidigare.
Men om vi ville ha en verklig hash-tabell, då kan vi bara göra en nod pekare
array här.
Till exempel, storlek 500.
>> Nu varsel, det kommer att bli en handels off mellan storleken på din
hashtabell och storleken av länkade listor.
Om du har ett riktigt stort antal hinkar, inbillar behöva springa tillbaka
och tillbaka i en linje till hitta din hink.
Men du vill inte heller ett litet antal av skopor, för då är vi tillbaka till
det ursprungliga problemet med hur har för många bollar i vår hink.
>> OK, men vart tar vår boll går?
Tja, måste vi först har en boll, eller hur?
Så låt oss malloc en nod för varje nya ord som vi har.
node * new_node jämlikar malloc (sizeof (nod)).
>> Nu när vi har denna struktur, vi kan skanna in, med hjälp av funktionen
fscanf, en sträng från vår fil, om det är en ordbok fil, i
new_node pilen ord, där new_node pil ord är vår
destinationen för det ordet.
>> Därefter ska vi vill hash som ordet med en hash-funktion.
En hashfunktion tar en sträng och returnerar ett index.
I detta fall har de index till vara mindre än antalet
hinkar som du har.
>> Nu, hashfunktioner, när du försöker att hitta en och skapa en av
egen hand, kom ihåg att de måste vara deterministisk.
Det betyder att samma värde måste mappas till samma hink varje gång
att du hash det.
>> Det är ungefär som ett bibliotek.
När man tar en bok, baserat på den författare, vet du vilken hylla den ska
gå på, oavsett om det är hyllnummer en, två, eller tre.
Och att boken kommer alltid att tillhöra den antingen hylla en, två, eller tre.
>> Så, har om new_node pil ord den ord från din ordlista, sedan
hashing new_node pil ord kommer ge oss index för
hink med hash-tabellen.
Och sedan ska vi sätta in det i det specifika länkad lista som anges av
returnera värdet på vår hashfunktion.
>> Låt oss titta på ett exempel på sätta in en nod i
början av en länkad lista.
Om huvudet är en nod pekare som indikerar I början av en länkad
listan, och new_node indikerar den nya nod som du vill skriva in, precis
tilldela huvud till new_node skulle förlora länken till resten av listan.
Så vi vill inte göra det här.
>> I stället vill vi se till att att vi håller på att varje
enda nod i vårt program.
Så kör new_node pilen jämlikar huvud och sedan huvudet lika new_node
kommer att bevara alla av länkar och inte förlora något.
>> Men om du vill att listan ska vara sorteras, eftersom att ha en sorterad länkad
Listan kan vara lättare för söka den senare?
Jo, för det måste du veta hur man korsa länkade listor.
>> För att gå igenom en länkad lista, låt oss ha en nod pekare, en nod *, för att fungera som
markören, som anger vilka nod du är på, börjar
vid det första elementet.
Looping tills markören är noll, kan vi genomföra vissa processer och sedan
föra markören när vi behöver med hjälp av markörpilen värde.
>> Kom ihåg, det här är samma sak som säger stjärnan markör, dereferencing
markören, sedan använda punktopera värde.
Så uppdatera markören genom att tilldela markören till markörpilen bredvid.
>> Säg att du bestämmer att D blir i mellan C och E. För att infoga noden,
har new_node D punkten till nod E, som är markör bredvid.
Och sedan C, markören, kan peka till D. På så sätt hålla dig en lista.
Var noga med att inte förlora dina länkar med flytta markören pilen bredvid D
direkt.
>> Okej.
Så det är hur du kan infoga noder, ladda dem, last ord till dem
noder, och sätt in dem in i din hash-tabell.
Så nu ska vi titta på försök.
>> I en trie, kommer varje nod innehåller ett matris av noder pekare, en för varje
bokstav i alfabetet plus en apostrof.
Och varje element i arrayen kommer att peka på en annan nod.
Om denna nod är noll, då skrivelsen kommer inte att bli nästa bokstav i
varje ord i en sekvens, eftersom varje ord visar om det är det sista
karaktären av ett ord eller inte.
>> Låt oss titta på ett diagram.
Förhoppningsvis kommer vara lite tydligare.
I det här diagrammet ser vi att endast vissa bokstäver och vissa delsträngar
håller listade ut.
Så du kan följa vissa vägar, och alla dessa stigar leder dig till
olika ord.
>> Så hur ska vi företräder här i C?
Tja, varje nod nu kommer att ha ett booleskt värde som anger om
den noden är i slutet av ett givet ord eller inte.
Och då kommer också ha en rad nod pekare kallas barn och
det kommer att bli 27 av dem.
Och kom ihåg, du kommer också vill hålla koll på din första noden.
Vi kommer att kalla det rot.
>> Så det är strukturen i en trie.
Hur vi representerar här som ett lexikon?
Jo, för att ladda ord, för varje ord i ordlistan, du kommer att vilja
att iterera igenom trie.
Och varje element i barnens motsvarar en annan bokstav.
>> Så kontrollera värdet på barn index i, där jag representerar
specifika index för brev som du försöker sätta in.
Tja, om det är noll, då du kommer att vilja malloc en ny nod och har barn
Jag pekar på den noden.
>> Om det inte är noll, då det innebär att som viss gren, att med tanke
delsträng, finns redan.
Så då kommer du bara flytta till det ny nod och fortsätta.
Om du är i slutet av ordet som du försöker läsa in i
ordbok, då kan du ställa in att nuvarande nod som du är på till true.
>> Så låt oss titta på ett exempel på att sätta in ordet "räven" i vår
ordboken.
Låtsas vi börjar med en tom ordboken.
Den första bokstaven, F, kommer att ligga i barn index fem av rötterna
barn array.
Så vi sätter den i.
>> Bokstaven O kommer då att vara i barn index 15, därefter F. Och sedan X
kommer att bli ännu lägre än den som, förgrening bort av O: s barn.
Och då eftersom X är den sista bokstaven av ordet "räv", då kommer jag att
färg som grönt för att indikera att det är i slutet av ordet.
I C, skulle det vara att ställa in Is Word Boolean till värdet true.
>> Nu tänk om nästa ord som du är fyller på är ordet "foo"?
Tja, behöver du inte att malloc mer utrymme för F eller O, eftersom
de som redan finns.
Men den sista O i foo?
Att man, måste du malloc.
Gör en ny nod för att ställa Is Word Boolean till true.
>> Så nu ska vi sätta "hund." Dog kommer börja med index tre av rötterna
barn, eftersom D har inte skapats ännu.
Och vi kommer att följa en liknande process som tidigare, skapar träng hund,
var är G är grön eftersom det är i slutet av ett ord.
>> Nu, tänk om vi vill infoga "göra"?
Nåväl, detta är en delsträng av hund, så Vi behöver inte malloc längre.
Men vi behöver för att ange var vi har nått slutet av det ordet.
Så O kommer att färgas grönt.
Att fortsätta denna process för varje enskild ord i din ordlista, du har
lastade dem i antingen din hash bord eller din trie.
>> speller.c kommer att passera i strängar för dictionary.c att kontrollera dem.
Nu har Kontrollera funktionen att driva under ärende okänslighet.
Det betyder att versaler och gemener och en blandning av båda
bör alla motsvara sant om någon kombination av det är i
ordboken.
Du kan också anta att strängar är endast kommer att innehålla alfabetisk
tecken eller apostrofer.
>> Så låt oss titta på hur du kan kontrollera med en hashtabell struktur.
Tja, om ordet existerar, då det kan hittas i hash-tabellen.
Så då kan du försöka hitta det ord i den relevanta hink.
>> Så vilken hink skulle det ordet vara i?
Tja, skulle du få numret att index av skopan, genom hashing det ordet
och sedan söka i den länkade listan, korsar genom hela
länkad lista, med hjälp av String Jämför funktion.
>> Om slutet av den länkade listan är nåtts, vilket innebär att markören
når noll, då ordet inte hittas i ordboken.
Det kommer inte vara i någon annan skopa.
Så här kan du se hur det kanske vara en avvägning mellan att ha antingen
sorterade länkade listor eller osorterade sådana.
Antingen kommer att ta mer tid under ladda eller mer tid under kontroll.
>> Hur kan du checka in en trie struktur?
Vi kommer att resa nedåt i trie.
För varje bokstav i den inmatade ordet att vi kollar, vi ska gå till den
motsvarande element i barnen.
>> Om detta element är noll, då det betyder att det inte finns några understrängar
innehåller vår ingång ord, så ordet är felstavat.
Om det inte är noll, kan vi gå till nästa bokstav i ordet som vi är
kontroll och fortsätta denna process tills vi når slutet
av ingångsordet.
Och då kan vi kolla Om Is Ord är sant.
Om det är, då stor.
Ordet är korrekt.
Men om inte, även om det träng finns i trie, är ordet
felstavat.
>> När funktionen Storlek heter, storlek ska returnera antalet ord som
är i din tanke dictionary datastruktur.
Så om du använder en hashtabell, du kan antingen gå igenom varenda
länkad lista i varje enskild hink räkna antalet
ord finns där.
Om du använder en trie kan du gå igenom varje icke null
sökvägen i din trie.
Eller medan du laddar ordlistan in, kanske du kan hålla reda på hur
många ord du läser in i.
>> När speller.c avslutar kontroll av textfil mot ordlistan, då
det är gjort och så kallar Unload, där ditt jobb är att frigöra något
att du har malloced.
Så om du använder en hashtabell, då du måste vara särskilt noga med att undvika
minnesläckor genom att inte frigöra något tidigt och hålla på varje
enda länk innan du fri.
>> Så för varje element i hash-tabellen och för varje nod i den länkade listan,
du vill frigöra den noden.
Hur gör man om att frigöra en länkad lista?
Ställa din nod pekaren markören till huvudet, till början av den
länkad lista, sedan när markören inte är noll, kan du ställa in en tillfällig
nod pekare till din markör.
Avancera sedan markören.
Och då kan du gratis att tillfälligt värde samtidigt som du håller på att
allt efteråt.
>> Vad händer om du använder en trie?
Då det bästa sättet att göra detta är att lossa från den mycket
botten till toppen.
Genom att resa till lägsta möjliga nod, kan du befria alla pekare i
att barn och sedan backa uppåt, vilket frigör alla element i alla
av barnens arrayer, tills du träffar dina bästa rotnoden.
Här är där rekursion kommer väl till hands.
>> För att vara säker på att du förmodligen har befriat allt som du har malloced,
du kan använda Valgrind.
Köra Valgrind kommer att köra ditt program räkna hur många byte minne
du använder och se till att du har befriade dem alla, berättar
där du kan ha glömt att gratis.
Så kör det och när Valgrind berättar och ger klartecken, då
du är klar lasta.
>> Nu, ett par tips innan du går av och börja genomföra din
ordboken.
Jag skulle rekommendera att gå i en mindre ordlistan när du försöker testa
saker och felsökning med BNP.
Användningen av speller visas. / Speller, en valfri ordbok, och sedan en text.
>> Som standard läser det i tjockt ordboken.
Så du kanske vill gå i den lilla ordbok, eller kanske till och med göra din
egna, skräddarsy din ordlista och din textfil.
>> Och slutligen, jag skulle också rekommendera att ta en penna och papper och rita
saker före, under, och efter du har skrivit all din kod.
Se bara till att du har dessa pekare precis rätt.
>> Jag önskar er lycka till.
Och när du är klar, om du vill att utmana den stora styrelsen och
se hur snabbt ditt program jämförs med dina klasskamrater ", så uppmuntrar jag
dig att kolla som.
>> Med det har du klar det stavnings Pset.
Mitt namn är Zamyla, och detta är CS50.