[Powered by Google Translate] [Walkthrough - Problem Set 5] [Zamyla Chan - Harvarduniversitetet] [Detta är CS50. - CS50.TV] 

Okej. Hej, alla, och välkomna till Walkthrough 5. 

Pset5 är felstavningar, där vi kommer att göra en stavningskontroll. Spell-pjäser är oerhört viktigt. Har detta någonsin hänt dig? Du arbetar mycket, mycket hamstra på ett papper för en sammandrabbning och sedan ändå i slutändan får en mycket glöd Rade som en D-eller D = och allt eftersom du är den leverkorv spoiler i valen breda ordet. Ja, korrekturläsning dina paprika är en fråga av den största impotens. Detta är ett problem som drabbar manliga, manliga studenter. Jag var en gång höra av min Sith grad torterare att jag aldrig skulle få till en bra kollega. Och det är allt jag någonsin velat, det är allt någon unge vill i min ålder, bara för att få till en bra kollega. Och inte bara någon kollega. Nej, jag ville gå till en Ivory Juridisk kollega. Så om jag inte bättre, skulle gått vara mina drömmar om att gå till Harvard, Jale, eller fängelse - ni vet, i fängelset, New Jersey. Så jag fick mig en stavningskontroll. Det är lite utdrag från en av mina favorit spoken word artister Taylor Mali. Hur som helst, som han säger, är vikten av att ha en stavningskontroll mycket viktigt. 

Så välkommen till Walkthrough 5, där vi kommer att tala om pset5: felstavningar, där vi kommer att göra vår egen stavningskontroll. Verktygslådan för denna vecka, distribution koden, kommer att bli viktigt att titta på bara för att förstå de olika funktionerna som din ordlista kommer att ha. Vi är faktiskt kommer att ha flera. C filer som tillsammans utgör vår pset. Och så tittar genom de olika aspekterna, även om vi faktiskt inte är redigering en av filerna, speller.c, att veta hur det fungerar i förhållande till dictionary.c, som vi kommer att skriva, kommer att bli ganska viktigt. I pset spec innehåller också en hel del användbar information i form av saker som du kan anta, regler och sånt, så se till att läsa pset spec noga för tips. Och om du är osäker på en regel eller något liknande, då alltid hänvisa till pset spec eller diskutera. Denna pset kommer att starkt beroende pekare, så vi vill se till att vi förstår skillnaden mellan att lägga stjärnor framför pekaren namn och et-tecken, hur man befria dem, osv Så är en mästare på pekare kommer att vara till stor hjälp i detta problem uppsättning. Vi kommer att undersöka länkade listor lite mer, där vi har element som vi kallar noder som har både ett värde och en pekare till nästa nod, och så i huvudsak koppla olika element efter varandra. Det finns några olika alternativ att genomföra din faktiska ordbok. Vi kommer att undersöka två huvudsakliga metoder, vilket är hashtabeller och sedan försöker. I båda dessa, de innebär någon slags begreppet en länkad lista där du har element kopplade till varandra. Och så ska vi se över hur man skulle kunna arbeta runt länkade listor, skapa dem, navigera i termer av hur till exempel infoga en nod i det eller fri alla noder samt. När det gäller att befria noder, det är verkligen viktigt att när vi malloc minne, efteråt vi befria det. Så vi vill se till att ingen pekare går unfreed, att vi inte har några minnesläckor. Vi kommer att införa ett verktyg som heter Valgrind som kör ditt program och kontrollerar om allt det minne som du tilldelade sedan frigörs. Din pset är färdig först när den fungerar och det har full funktionalitet, men också, berättar Valgrind du att du inte har hittat några minnesläckor. Slutligen, för det här pset, jag vill verkligen understryka - Jag menar, som vanligt, är jag definitivt en anhängare av att använda penna och papper på ditt problem apparater, men för detta en, tror jag att penna och papper kommer att bli särskilt viktigt när du vill vara rita pilar för att saker och förstå hur saker och ting fungerar. Så definitivt försöka använda papper och penna för att rita saker innan du får kodning eftersom det kan bli lite rörigt. 

Först, låt oss gå in i länkade listor lite. Länkade listor består av noder, där varje nod har ett värde i samband med det, samt en pekare till nästa nod efter det. Ett par saker viktiga med de länkade listor är att vi måste komma ihåg där vår första noden är, och sedan när vi vet var den första noden är, så vi kan få tillgång till noden att den första noden pekar på och sedan den ena efter det och ett efter detta. Och sedan det sista elementet i din länkade listan är att nodens pekare kommer alltid att peka på NULL. När en nod pekar till NULL, då vet du att du har nått slutet av listan, att den noden är den sista, att det finns inget efter det. Här i denna schematiska ser du att pilarna är pekare, och den blå delen är där värdet lagras, och sedan den röda rutan med pekaren till det är nodens pekaren pekar till nästa nod efter det. Och så du ser här, skulle D-noden pekar på NULL eftersom det är det sista elementet i listan. 

Låt oss titta på hur vi kan definiera en struct för en nod. Och eftersom vi vill ha flera noder, detta kommer att bli en typedef struct där vi kommer att ha flera olika instanser av noder. Och så vi definierar det som en ny datatyp. Här har vi en typedef struct nod. I det här exemplet, vi arbetar med heltal noder, så vi har ett heltal heter värde och sedan har vi en annan pekare, och i detta fall är det en pekare till en nod, så vi har en struct nod * kallas nästa. Och vi kallar det hela nod. Se till att du följer den här syntaxen. Lägg märke till att noden faktiskt refereras upp ovan samt under klammerparenteser. Sen att hålla reda på var min första noden är i detta länkad lista, då har jag en nod pekare kallas huvud, och jag malloc utrymme nog för storleken på en nod. Observera dock att huvudet faktiskt en nod pekare i stället för en faktisk nod själv. Så huvudet faktiskt inte innehåller något värde, den pekar endast beroende den första noden i min länkad lista är. 

För att få en bättre känsla för länkade listor, eftersom det är mycket viktigt att hålla reda på att se till att du behåller kedjan, Jag gillar att tänka på det som människor i en rad håller varandra i handen, där varje person hålla hand med nästa. Du kan inte se på denna ritning, men i grunden de är pekar till nästa person som är i sin kedja. Och så om du vill passera en länkad lista där dessa människor - föreställa alla dessa människor har värden associerade med dem och också peka på nästa person i raden - om du vill korsa den länkade listan, till exempel att antingen ändra värdena eller sök efter ett värde eller något liknande, då du vill ha en pekare till den specifika personen. Så vi kommer att ha en data pekartyp nod. För detta fall, låt oss kalla det markören. Ett annat vanligt sätt att namnge detta skulle vara iterator eller något liknande eftersom det iteration över och faktiskt flytta vilken nod det pekar på. Detta här blir vår markören. Vår markören först peka på det första elementet i vår lista. Och så vad vi vill göra är att vi skulle i princip att fortsätta markören, flytta den från sida till sida. I det här fallet vill vi flytta den till nästa element i listan. Med arrayer, vad vi skulle göra är att vi bara skulle säga att vi ökar index med 1. I detta fall är det vi måste göra faktiskt hitta vilken person det aktuella personen pekar på, och det kommer att bli nästa värde. Så om markören är bara en nod pekare, vad vi vill göra är vi vill få till det värde som markören pekar på. Vi vill komma till den nod och sedan, när vi är på den noden, hitta vart det pekar på. För att komma till själva noden att markören pekar på, brukar vi visar det genom (* markör). Det skulle ge dig den verkliga noden som markören pekar på. Och sedan efter det, vad vi vill göra är att vi vill ha tillgång till vad det nod nästa värde. För att göra det, för att komma till värden inne i struct har vi punktoperatorn. Så skulle det vara (* markör). Nästa. Men detta är lite rörigt när det gäller att ha fästena runt * markören, och så vi byter hela denna uttalande med markör->. Detta är ett streck och sedan en större än-tecken, så gör en pil. Markören-> nästa. Som faktiskt kommer att få dig den nod som markören pekar på. Detta värde är nästa. Så istället för att ha stjärnan och pricken, du ersätta det med en pil. Var mycket noga med att se till att du försöker använda den här syntaxen. 

Nu när vi har vår markör, om vi vill komma åt värdet, tidigare hade vi markör-> nästa, utan att komma åt värdet vid noden att markören pekar på, vi bara helt enkelt säga nod-> värde. Därifrån är det av datatyp vad vi har definierat de värderingar och noderna att vara. Om det är en int nod, sedan markören-> värde bara kommer att vara ett heltal. Så vi kan göra operationer på det, kolla likheter, tilldela den olika värden, etc. Så vad du vill göra om du vill flytta markören till nästa person, du ändrar faktiskt värdet av markören. Eftersom markören är en nod pekare, ändrar du den faktiska pekaradress till adressen för nästa nod i listan. Detta är bara lite kod där du kan iterera. Där jag har kommentaren göra något, det är där du förmodligen kommer att få tillgång till värdet eller göra något för att göra med just den noden. Till att börja den, säger jag att min markör initialt kommer att peka på det första elementet i den länkade listan. Och så längre fram, definierade jag det som huvudet av noden. 

Som jag nämnde tidigare, är att befria verkligen viktigt. Du vill vara säker på att du gratis varje element i listan när du är klar med det. När du inte behöver referera någon av dessa pekare längre, du vill vara säker på att du befriar alla dessa pekare. Men du vill vara mycket försiktig här att du vill undvika minnesläckor. Om du fri en person i förtid, då alla de tips som den noden pekar på kommer att gå förlorade. Att gå tillbaka till den person exemplet för att göra det lite mer high stakes, låt oss ha dessa människor, utom i det här fallet de svävar över en sjö med ett monster. Vi vill se till att när vi befriar vi inte förlorar och släppa alla noder innan vi har faktiskt befriat dem. Till exempel, om du skulle helt enkelt ringa gratis på den här killen här, då skulle han befrias, men då alla dessa killar skulle gå förlorad och de skulle glida iväg och falla ner. Så vi vill se till att istället vill vi upprätthålla en länk till resten. Vår huvud pekare, som pekar på det första elementet i listan. Det är ungefär som ett rep förankring den första personen. Vad du kanske vill göra när du befriar en lista har - Om du vill frigöra det första elementet först, sedan kan du få en tillfällig pekare som pekar på vad det första elementet är. Så du har ditt tillfälliga pekaren pekar här. På så sätt har vi en tag av den första noden. Och sedan, eftersom vi vet att den första noden kommer att frigöras, då kan vi flytta rep, detta ankare, huvudet, att faktiskt peka på vad det första ett pekar på. Så denna huvud pekar faktiskt det andra elementet nu. Nu är vi tillåts att frigöra allt lagras i temp, och så att vi kan radera det utan att det äventyrar alla andra noder i vår lista. Ett annat sätt att du kan göra detta kan vara varje gång du frigöra bara det sista elementet i listan eftersom de är garanterade att inte pekade på någonting. Så du kan bara befria denna, sedan fri här, sedan fri här. Som definitivt fungerar men är lite långsammare på grund av arten av de länkade listor, Vi kan inte bara direkt hoppa till den sista. Vi måste passera varje element i den länkade listan och kontrollera om att man pekar på NULL, kontrollera varje gång, och sedan när vi når slutet, sedan fri att. Om du skulle göra den här processen, skulle du faktiskt kolla här, kontroll här, sedan kontrollera här frigör den, sedan gå tillbaka, kontroll hit, kontroll här, befria det, kontroll här, och sedan frigöra den. Det tar lite längre tid. Ja. 

[Elev] Skulle det vara möjligt att göra en länkad lista som lagrar en utgång pekaren till slutet? Som definitivt skulle vara möjligt. För att upprepa frågan, är det möjligt att ha en länkad lista struktur så att du har en pekare som pekar till slutet av den länkade listan? Jag skulle säga att det är möjligt, och varje gång du sätter något i din länkade lista du måste uppdatera pekaren och sånt. Du skulle ha en nod * svans, till exempel. Men när du genomföra den här funktionen måste du tänka på avvägningar, gillar hur många gånger jag kommer att iterera över detta, Hur svårt är det att vara att hålla reda på svansen och huvudet liksom min iterator, och sådana saker. Betyder det -? >> [Elev] Ja. Det är möjligt, men när det gäller designbeslut, du måste väga alternativen. 

Här är ett skelett av kod som gör att du kan frigöra varje element i en länkad lista. Återigen, eftersom jag iteration över en länkad lista, jag kommer att vilja ha någon form av markör eller iterator. Vi iteration tills markören är NULL. Du vill inte att iterera när markören är NULL eftersom det innebär att det inte finns något i listan. Så så här jag gör en tillfällig nod * pekar på vad jag funderar är den första på min lista, och då jag flyttar min markör framåt 1 och sedan fri vad jag hade i tillfällig förvaring. 

Nu kommer vi att infoga i länkade listor. Jag har tre noder i min länkad lista, och låt oss gå med det enkla fallet där vi vill infoga en annan nod i slutet av vår länkad lista. För att göra det, allt vi skulle göra skulle vi passera att hitta där den nuvarande änden av länkade listan är så beroende nod pekar på NULL - Det är detta en - och sedan säga, faktiskt, är detta inte kommer att vara den sista noden; vi faktiskt kommer att ha en annan. Så vi skulle ha denna ström en punkt till vad vi sätter. Så nu denna röda personen blir här den sista noden i den länkade listan. Och så karakteristiska för den sista noden i den länkade listan är att den pekar till NULL. Så vad vi skulle behöva göra är att ställa in röd kille pekare till NULL. Där. 

Men vad händer om vi ville infoga en nod mellan den andra och tredje? Att man är inte riktigt så enkelt eftersom vi vill se till att att vi låter inte gå någon nod i vår länkad lista. Vad vi skulle behöva göra är att se till att vi förankrar oss till var och en. Till exempel, låt oss kalla det den andra. Om du sagt det andra en pekar nu på denna nya och du gjorde bara en pekare där, då skulle resultera i den här killen går förlorade eftersom det inte finns någon koppling till honom. Istället - Jag ska göra det här igen. Ursäkta mina konstnärliga förmågor. Vi vet att vi inte bara kan länka direkt 2 till den nya. Vi måste se till att vi håller fast vid den sista. Vad vi kanske vill göra är att ha en tillfällig pekare till elementet som kommer att läggas på. Så då har vi en temporär pekare där. Eftersom vi vet att denna tredje hålls reda på, 2 kan nu länka till vår nya. Och om detta nya röda killen kommer att vara mellan 2 och 3, vad är att killen pekare kommer att peka på? >> [Elev] Temp. Temp. Ja. Så då denna röda killen nästa värde kommer att vara temp. När du sätter in länkade listor, såg vi att vi kunde enkelt lägga till något till slutet genom att skapa en tillfällig array, eller om vi ville lägga till något i mitten av vår grupp, då det skulle ta lite mer blanda runt. Om du vill, till exempel, har en sorterad länkad lista, då måste man typ av väga kostnaderna och fördelarna med det för om du vill ha en sorterad array, innebär det att varje gång du sätter i den, det kommer att ta lite längre tid. Men om du vill senare, när vi hittar vi vill, söka igenom en länkad lista, kan det vara lättare om du vet att allt är i sin ordning. Så du kanske vill väga kostnaderna och fördelarna med det. 

Ett annat sätt att infoga i en länkad lista är att infoga i början av en lista. Om vi ​​drar vårt ankare här - det är vår huvud - och sedan har dessa personer knutna till den, och sedan har vi en ny nod som skall införas i början, vad kan vi vill göra? Vad skulle vara fel med att bara säga jag vill länka den röda till blå, eftersom det är den första? Vad skulle hända här? Alla dessa tre skulle gå vilse. Så vi vill inte göra det. Återigen har vi lärt oss att vi måste ha någon form av tillfällig pekare. Låt oss välja att ha en tillfällig punkt till den här killen. Då kan vi ha den blå en punkt till den tillfälliga och sedan den röda punkten till blå. Anledningen till att jag använder folk här är att vi verkligen vill visualisera hålla fast vid människor och se till att vi har en länk till dem innan vi släpper en annan hand eller något liknande. 

Nu när vi har en känsla av länkade listor - hur vi kan skapa en länkad lista och skapa strukturer för den som består av typen definitionen för en nod och sedan se till att vi har en pekare till chefen för den länkade listan - när vi har det och vi vet hur man färdas genom en matris, få tillgång till olika delar, vet vi hur man sätter i och vi vet hur man befria dem, då kan vi få in felstavningar. Som vanligt har vi en del frågor som kommer att få dig brukade arbetar med länkade listor och olika strukturer som köer och stackar. Då kan vi flytta in felstavningar. 

Felstavningar har i distributionen koden ett par filer i vikt. Först märker vi att vi har denna Makefile här, som vi inte har riktigt stött på tidigare. Om du såg innanför pset5 mappen, skulle du märka att du har en. H. fil, så har du två. C-filer. Vad detta Makefile gör är tidigare skulle vi skriver bara göra och sedan programnamnet och då skulle vi se alla dessa argument och flaggor gick in i kompilatorn. Vad Makefile gör är låter oss att sammanställa flera filer samtidigt och passerar i flaggorna som vi vill. Här ser vi bara det finns en huvudfil här. Sedan har vi faktiskt två källfiler. Vi har speller.c och dictionary.c. Du är välkommen att redigera Makefile om du vill. Observera att här om du skriver ren, vad den gör faktiskt bort allt som är kärnan. Om du har en segmenteringsfel, i princip får du en central soptipp. Så denna fula lilla filen visas i din katalog som heter kärna. Du vill ta bort det för att göra den ren. Det tar bort alla exe-filer och. O-filer. 

Låt oss ta en titt in i dictionary.h. Det säger att det förklarar en ordbok funktionalitet. Vi har en maximal längd för alla ord i ordboken. Vi säger att detta kommer att bli den längsta möjliga ordet. Det är av längd 45. Så vi inte kommer att ha några ord som överstiger denna längd. Här har vi bara funktionen prototyper. Vi har inte det faktiska genomförandet, eftersom det är vad vi kommer att göra detta pset. Men vad detta innebär är eftersom vi har att göra med större filer här och funktionalitet i större skala, är det bra att ha en. h. fil så att någon annan läser eller använda din kod kan förstå vad som händer. Och kanske de vill genomföra försök om du gjorde hashtabeller eller vice versa. Då skulle de säga min last funktion, det faktiska genomförandet kommer att skilja sig, men denna prototyp kommer inte att ändras. Här har vi kontrollera, vilket returnerar sant om ett givet ord i ordboken. Sen har vi last, som i princip tar i en ordbok fil och därefter laddar in det i vissa datastruktur. Vi har storlek, som när kallas, återvänder storleken på din ordlista, hur många ord lagras i det, och sedan lossa, vilket frigör allt minne som du kan ha tagit upp samtidigt som din ordbok. 

Låt oss ta en titt på dictionary.c. Vi ser att det ser mycket lik dictionary.h, förutom nu bara har alla dessa Todos i den. Och så är ditt jobb. Så småningom kommer du att fylla speller.c med allt i denna kod. Dictionary.c, när det körs, inte verkligen kommer att göra något, så vi ser till speller.c att se det faktiska genomförandet av stavningskontrollen. Även om du inte kommer att redigera någon av denna kod, Det är viktigt att läsa, förstå när är belastningen kallas när jag ringer check, bara för att förstå, kartlägga det, se hur funktionen fungerar. Vi ser att det är kontrollen för rätt användning. Huvudsak när någon kör speller, betyder det att det är frivilligt för dem att passera i en ordbok fil eftersom det kommer att bli en standard ordlista fil. Och så måste passera i texten för att vara stavningskontrolleras. rusage handlar tid eftersom en del av denna pset som vi tar hand om senare inte bara få en fungerande stavningskontroll fungerar men faktiskt få det att vara snabb. Och så då det är där rusage kommer att komma in Här ser vi det första samtalet till en av våra dictionary.c filer, vilket är last. Load returnerar sant eller falskt - sant på framgång, falsk vid fel. Så om ordlistan inte har laddats på rätt sätt, då speller.c kommer tillbaka 1 och sluta. Men om det gör belastningen på rätt sätt, så det kommer att fortsätta. Vi fortsätter, och vi se några I / O-här, där det kommer att ha att göra med att öppna textfilen. Här, vad detta innebär är spell-kontroller vartenda ord i texten. Så vad speller.c gör här är iteration över vart och ett av orden i textfilen och sedan kontrollera dem i ordboken. Här har vi ett booleskt felstavat som kommer att se om kontrollen returnerar sant eller inte. Om ordet faktiskt i ordboken, så kolla återkommer sant. Det innebär att ordet inte är felstavat. Så felstavade skulle vara falsk, och det är därför vi har smäll där indikationen. Vi håller på att gå, och då håller reda på hur många felstavade ord Det finns i filen. Det fortsätter på och stänger filen. Då här, rapporterar den hur många felstavade ord du hade. Den beräknar hur lång tid det tog att ladda ordlistan, hur mycket tid det tog att kontrollera det, hur mycket tid det tog att beräkna storleken, vilket som vi ska gå vidare, bör vara mycket liten, och sedan hur lång tid det tog att lasta i ordlistan. Här ovanför ser vi uppmaningen att lasta här. Om vi ​​kontrollerar för storlek här, då ser vi att här är uppmaningen att storleken där den bestämmer storleken på ordlistan. Toppen. 

Vår uppgift här pset är att genomföra belastning, vilket kommer att belasta ordlistan datastruktur - vilket du väljer, oavsett om det är en hash-tabell eller ett försök - med ord från ordlistan filen. Då har du storlek, vilket kommer att returnera antalet ord i ordlistan. Och om du implementerar belastning på ett smart sätt, så storlek bör vara ganska lätt. Då har du kontrollera vilket kommer att kontrollera om ett givet ord finns i ordlistan. Så speller.c passerar i en sträng, och då måste man kontrollera om den strängen finns i din ordlista. Observera att vi generellt har standard ordböcker, men i detta pset, passerade i stort sett någon ordbok på något språk. Så vi kan inte bara anta att ordet THE är inne. Ordet Foobar kan definieras i en viss lexikon som vi passerar i. Och då har vi lasta, vilket frigör ordlistan från minnet. 

Först vill jag gå över hashtabellen metoden om hur vi kan genomföra alla dessa fyra funktioner, och sedan ska jag gå över försöker metoden, hur vi genomför dessa fyra funktioner, och i slutet tala om några allmänna tips när du gör pset och även hur du skulle kunna använda Valgrind för att kontrollera minnesläckor. 

Låt oss komma in i hash-tabellen metoden. En hash-tabell består av en lista av skopor. Varje värde varje ord, kommer att gå in i en av dessa hinkar. En hashtabell helst jämnt distribuerar alla dessa värden som du passerar i och sedan fyller dem i hinken så att varje skopa har ungefär lika många värden i den. Strukturen för en hashtabell, har vi en matris med länkade listor. Vad vi gör är när vi passerar ett värde kontrollerar vi om detta värde ska tillhöra, vilket hink den tillhör, och sedan placera det i den länkade listan i samband med den skopa. Här, vad jag har är en hashfunktion. Det är en int hashtabell. Så för första skopan, alla heltal under 10 går in i den första hinken. Alla heltal över 10 men under 20 Gå in i andra, och sedan så vidare och så vidare. För mig är varje hink representerar dessa nummer. Men säger jag skulle passera i 50, till exempel. Det verkar som om de första tre innehåller en rad tio nummer. Men jag vill låta min hashtabell att ta i någon form av heltal, så då skulle jag behöva filtrera bort alla nummer över 30 i den sista skopan. Och så då skulle resultera i en slags obalanserad hashtabell. För att upprepa, är en hash tabell bara en rad av skopor där varje hink är en länkad lista. Och så för att avgöra var varje värde går, vilket hink den går in i, du kommer att vilja vad som kallas en hashfunktion som tar ett värde och sedan säger detta värde motsvarar en viss hink. Så upp ovan i detta exempel, tog min hashfunktion varje värde. Det kontrolleras huruvida det var mindre än 10. Om det var, skulle det sätta den i den första hinken. Den kontrollerar om det är mindre än 20, sätter det i det andra om sant, kontrollerar om det är mindre än 30, och sedan sätter det i den tredje skopan, och sedan allt annat faller bara den fjärde hinken. Så när du har ett värde, din hashfunktion kommer att placera detta värde i lämplig hinken. Hashfunktionen behöver i princip veta hur många skopor du har. Din hash-tabell storlek, antalet skopor du har, det kommer att bli ett fast antal som är upp till dig, för dig att bestämma, men det kommer att bli ett fast antal. Så din hashfunktion kommer att förlita sig på att för att avgöra vilken hink varje nyckel går till så att den jämnt spridda. Liknar vårt genomförande av länkade listor, nu varje nod i hashtabellen faktiskt kommer att ha en typ röding. Så vi har en char array som heter ord och sedan en annan pekare till nästa nod, vilket är rimligt eftersom det kommer att bli en länkad lista. Kommer du ihåg när vi hade kopplat listor, jag gjorde en nod * kallas huvud som pekar till den första noden i den länkade listan. Men för vår hashtabell, eftersom vi har flera länkade listor, vad vi vill är att vi vill att vår hashtabell att vara som, "Vad är en hink?" En hink är bara en lista över pekare nod, och så varje element i skopan faktiskt pekar på dess motsvarande länkad lista. För att gå tillbaka till denna schematiska, ser du att skoporna själva är pilarna, inte faktiska noder. En viktig egenskap hos hash funktioner är att de är deterministiska. Det innebär att när du hash numret 2, Det ska alltid returnera samma hink. Varje enskilt värde som går in i hashfunktion, om de upprepas, måste få samma index. Så din hashfunktion returnerar index för matrisen där detta värde tillhör. Som jag nämnde tidigare, är antalet skopor fast, och så din index som du återvänder måste vara mindre än antalet segment men större än 0. Anledningen till att vi har hashfunktioner istället för bara en länkad enda lista eller en enda array är att vi vill kunna hoppa till ett visst avsnitt lättast om vi vet det karakteristiska för ett värde - istället för att behöva söka igenom hela hela ordboken, att kunna hoppa till en viss del av det. Din hashfunktion bör ta hänsyn till att idealt, varje hink har ungefär samma antal tangenter. Eftersom den hash-tabell är en serie av länkade listor, då länkade listor själva kommer att ha mer än en nod. I föregående exempel, två olika nummer, även om de inte var lika, när hashas, ​​skulle återvända samma index. Så när du arbetar med ord, ett ord när hashas skulle vara samma hashvärde som ett annat ord. Det är vad vi kallar en kollision, när vi har en nod som när hashas, den länkade listan att skopan inte är tom. Den teknik som vi kallar det är linjär sondering, där man går in den länkade listan och sedan hitta där du vill infoga den noden eftersom du har en kollision. Du kan se att det kan finnas en avvägning här, eller hur? Om du har en mycket liten hashtabell, ett mycket litet antal skopor, då du kommer att ha en massa kollisioner. Men om du gör en mycket stor hash-tabell, du förmodligen kommer att minimera kollisioner, men det kommer att bli en mycket stor datastruktur. Det kommer att bli kompromisser med det. Så när du gör din pset, försök att leka mellan kanske gör en mindre hash-tabell men sedan vet att det kommer att ta lite längre tid att passera de olika delarna av dessa länkade listor. 

Vilken belastning kommer att göra är att iterera över varje ord i ordlistan. Det passerar i en pekare till ordlistan filen. Så du kommer att dra nytta av den fil I / O funktioner som du behärskar i pset4 och iterera över varje ord i ordlistan. Du vill att varje ord i ordlistan för att bli en ny nod, och du kommer att placera var och en av dessa noder insidan av din ordlista datastruktur. När du får ett nytt ord, vet du att det kommer att bli en nod. Så du kan gå genast och malloc en nod pekare för varje nytt ord som du har. Här ringer jag min new_node nod pekare och jag mallocing vad? Storleken på en nod. Sedan att läsa själva strängen från en fil, eftersom ordboken faktiskt lagras av ett ord och sedan en ny linje, vad vi kan dra nytta av är funktionen fscanf, varigenom filen är ordlistan fil som vi är passerat i, så det skannar filen för en sträng och platser som sträng i den sista argumentet. Om ni minns tillbaka till en av föreläsningarna, när vi gick över och typ av skalade lagren tillbaka på CS50 biblioteket, vi såg en implementering av fscanf där. För att gå tillbaka till fscanf har vi fil som vi läser från, Vi letar efter en sträng i filen, och sedan vi placera den i Här har jag new_node-> ord eftersom new_node är en nod pekare, inte en verklig nod. Så då jag säger new_node, jag vill gå till den nod som det pekar på och sedan tilldela det värdet till ordet. Vi vill sedan ta det ordet och för in den i hash-tabellen. Inse att vi gjort new_node en nod pekare eftersom vi kommer att vilja veta vad adressen till den nod är när vi sätter det eftersom strukturen av noderna själva, av struct, är att de har en pekare till en ny nod. Så vad är adressen till den nod kommer att peka på? Det adress kommer att bli new_node. Betyder det vettigt, varför vi gör new_node en nod * i motsats till en nod? Okej. Vi har ett ord. Detta värde är new_node-> ord. Som innehåller ord från ordlistan som vi vill mata in. Så vad vi vill göra är att vi vill kalla vårt hashfunktion på den strängen eftersom vår hashfunktionen tar in en sträng och returnerar sedan oss ett heltal, när denna heltal är index där Hashtable vid detta index representerar den hink. Vi vill ta detta index och sedan gå till detta index i hashtabellen och sedan använda den länkade listan för att sätta noden i new_node. Kom ihåg att hur du väljer att sätta in nod, oavsett om det är i mitten om du vill sortera eller i början eller i slutet, bara se till att din sista nod pekar alltid till NULL eftersom det är det enda sättet som vi vet var det sista elementet i vår länkad lista är. 

Om storleken är ett heltal som representerar antalet ord i ett lexikon, därefter ett sätt att göra detta är att när storleken kallas Vi går igenom varje element i vår hashtabell och sedan iterera igenom varje länkad lista i hash-tabellen och sedan beräkna längden på det, öka vår disk 1 av 1. Men varje gång som storleken heter, det är kommer att ta lång tid eftersom vi kommer att vara linjärt sondering varenda länkad lista. Istället kommer det att bli mycket enklare om du håller koll på hur många ord förs in Så då om du har en räknare i din last funktion att uppdateringar som behövs, sedan disk, om du ställer den till en global variabel, kommer att kunna nås av storlek. Så vilken storlek skulle helt enkelt göra är en linje, bara returnera räknarvärdet, storleken på ordlistan som du redan behandlats i lasten. Det är vad jag menade när jag sa att om du implementerar last i ett användbart sätt, då storleken kommer att bli ganska lätt. 

Så nu får vi se. Nu är vi har att göra med ord från den ingående textfil, och så vi kommer att kontrollera om alla dessa ingångsord är faktiskt i ordlistan eller inte. I likhet med Scramble vill vi möjliggöra för fall okänslighet. Du vill vara säker på att alla ord gick in, trots att de är gemener, när kallas med snöre jämföra, är likvärdiga. Orden i filerna ordbok texten är faktiskt gemener. En annan sak är att du kan räkna med att varje ord passerade, varje sträng, kommer att vara antingen alfabetisk eller innehålla apostrofer. Apostrofer kommer att vara giltiga ord i vår ordlista. Så om du har ett ord med apostrof S, det är en verklig legitim ord i din ordlista det kommer att bli en av noderna i ditt hashtabell. Kontrollera arbetar med om ordet finns, så det måste vara i vår hashtabell. Om ordet är i ordlistan, då alla ord i ordboken är i hash-tabellen, så låt oss titta på detta ord i hashtabellen. Vi vet att eftersom vi genomfört vår hashfunktion så att varje unikt ord alltid hashas till samma värde, då vet vi att i stället för att söka igenom hela vår hela hashtabell, Vi kan faktiskt hitta den länkade lista som det ordet skulle tillhöra. Om det var i ordlistan så skulle det vara i den hink. Vad vi kan göra, om ordet är namnet på vår sträng som skickas in, Vi kan bara hash att ord och titta på den länkade listan på värdet av Hashtable [hash (ord)]. Därifrån, vad vi kan göra är att vi har en mindre delmängd av noder för att söka efter detta ord, och så att vi kan gå igenom den länkade listan, med hjälp av ett exempel från tidigare i genomgången, och sedan ringa sträng jämföra på ordet där markören pekar på, det ordet, och se om de jämföra. Beroende på hur du organiserar din hashfunktion, om det är sorterade, kanske du kan returnera false lite tidigare, men om det är osorterat, då du vill fortsätta gå igenom igenom länkad lista tills du hittar den sista delen av listan. Och om du fortfarande inte har hittat ordet med den tid du har nått slutet av den länkade listan, som innebär att dina ord inte finns i ordlistan, och så att ordet är ogiltig, och kontroll ska returnera false. 

Nu kommer vi till lasta, där vi vill befria alla de noder som vi har malloc'd, så fri alla noder inom vår hashtabell. Vi kommer att vilja iterera över alla länkade listor och fria alla noder i det. Om du tittar ovan i genomgången till exempel där vi frigöra en länkad lista, då du kommer att vilja upprepa denna process för varje element i hash tabellen. Och jag ska gå över detta i slutet av genomgång, men Valgrind är ett verktyg där du kan se om du har rätt befriat Varje nod som du har malloc'd eller något annat som du har malloc'd, någon annan pekare. Så det är hashtabeller, där vi har ett begränsat antal skopor och en hashfunktion som tar ett värde och sedan tilldela det värdet till en viss hink. 

Nu kommer vi till försök. Försöker typ av ser ut så här, och jag kommer även dra ut ett exempel. I grunden har du en hel rad potentiella bokstäver, och sedan när du bygger ett ord, skrivelsen kan kopplas till en ordlista till ett brett utbud av möjligheter. Några ord börjar med C men sedan fortsätta med, men andra fortsätter med O, till exempel. En trie är ett sätt att visualisera alla de möjliga kombinationer av dessa ord. En trie kommer att hålla reda på den sekvens av bokstäver som utgör ord, förgreningar vid behov, när en bokstav kan följas av en multipel av bokstäver, och vid slutet visar vid varje punkt om det ordet är giltigt eller inte för om du stava ordet MAT, MA Jag tror inte ett giltigt ord, men mattan. Och så i trie, skulle det tyda på att efter MAT det är faktiskt ett giltigt ord. Varje nod i vår trie faktiskt kommer att innehålla en rad noder pekare, och vi kommer att ha, särskilt 27 av dessa noder pekare, en för varje bokstav i alfabetet samt apostrof tecken. Varje element i matrisen är själv kommer att peka till en annan nod. Så om den noden är NULL, om det inte finns något efter det, då vet vi att det inte finns några ytterligare bokstäver i det ordet sekvens. Men om den noden inte är NULL, innebär det att det finns fler bokstäver i detta brev sekvens. Och sedan vidare indikerar varje nod om det är det sista tecknet i ett ord eller inte. 

Låt oss gå in ett exempel på en trie. Först har jag plats för 27 noder i denna array. Om jag har ordet BAR - Om jag har ordet bar och jag vill infoga det i, den första bokstaven är B, så om min trie är tom, B är den andra bokstaven i alfabetet, så jag ska välja att sätta detta här på detta index. Jag ska ha B här. B kommer att vara en nod som pekar på en annan uppsättning av alla möjliga tecken som kan följa efter bokstaven B. I det här fallet, jag arbetar med ordet bar, så en kommer att gå hit. Efter en, jag har bokstaven R, så då en nu pekar på sin egen kombination, och då R kommer att vara här. BAR är en komplett ord, så då kommer jag att ha R-punkten till en annan nod som säger att detta ord är giltig. Denna nod kommer även att ha en mängd noder, men de kan vara NULL. Men i grunden kan det fortsätta så. Det kommer att bli lite tydligare när vi går till en annan exempel, så bara bära med mig där. Nu har vi BAR inne i vår ordlista. Nu säger vi ordet BAZ. Vi börjar med B, och vi har redan B som en av de bokstäver som finns i vår ordlista. Det är följt med A. Vi har en redan. Men då istället har vi Z-följande. Så då ett element i vår array kommer att bli Z, och så att då man kommer att peka på en annan giltig slutet av ordet. Så vi ser att när vi fortsätter till B och sedan A, Det finns två olika alternativ för närvarande i vår ordlista för ord som börjar med B och A. Säg att vi ville infoga ordet Foobar. Då skulle vi göra en post på F. F är en nod som pekar till en hel rad. Vi skulle hitta O, gå till O, länkar O sedan till en hel lista. Vi skulle ha B och sedan fortsätta, skulle vi ha A och sedan R. Så då Foobar korsar hela vägen ner tills foobar är en korrekt ord. Och så skulle detta vara ett giltigt ord. Nu säger vår nästa ord i ordlistan är faktiskt ordet FOO. Vi skulle säga F. Vad följer F? Jag har faktiskt redan har en plats för O, så jag kommer att fortsätta. Jag behöver inte göra en ny. Fortsätt. FOO är ett giltigt ord i ordlistan, så då kommer jag att visa att det är giltigt. Om jag slutar min sekvens där, det skulle vara korrekt. Men om vi fortsatte vår sekvens från FOO ner till B och bara hade FOOB är FOOB inte ett ord, och det är inte anges som en giltig. I en trie har du varje nod anger om det är ett giltigt ord eller inte, och sedan varje nod har också en rad 27 noder pekare att peka på noder själva. 

Här är ett sätt på hur du kan vill definiera detta. Men precis som i hash tabellen exempel, där vi hade en nod * huvud för att indikera början av vår länkad lista, vi kommer också att vilja något sätt att veta var i början av vår Trie är. En del kallar försöker träd, och det är där roten kommer ifrån. Så vi vill roten av vårt träd att se till att vi håller oss jordade dit vår Trie är. Vi har redan typ av gick över hur du kan tänka om hur du fyller varje ord i ordlistan. Huvudsak för varje ord du kommer att vilja iterera igenom Trie och att veta att varje element i barnen - vi kallade det barn i detta fall - motsvarar en annan bokstav, du kommer att vilja kontrollera de värden vid det visst index som motsvarar bokstaven. Så tänker hela vägen tillbaka till Caesar och Vigenère, att veta att varje bokstav du typ av karta tillbaka till ett kartotek, definitivt A till Z kommer att bli ganska lätt att mappa till ett alfabetiskt brev, men tyvärr apostrofer också en accepterad karaktär i ord. Jag är inte ens säker på vad det ASCII-värdet är, så för att om du vill hitta ett index för att avgöra om du vill att det ska vara antingen den första eller den sista, måste du göra en hård kodad kontroll för att och sedan lägga det i index 26, till exempel. Så då du checkar värdet till barn [i] där [i] motsvarar vad bokstav du är på. Om det är NULL, innebär att det för närvarande inte eventuella bokstäver härrör från den tidigare sekvens, så du kommer att vilja malloc och gör en ny nod och har som barn [i] pekar på det så att du skapar - när vi in ​​ett brev i rektangeln - göra barn utan NULL och peka in i den nya noden. Men om det inte är NULL, som i vår instans av FOO när vi redan hade foobar fortsätter vi, och vi inte någonsin göra en ny nod utan bara sätta is_word till true vid slutet av detta ord. 

Alltså som tidigare, för här har att göra med varje bokstav i taget, det kommer att bli lättare för dig för storlek, i stället för att beräkna och gå igenom hela trädet och beräkna hur många barn har jag och därefter förgreningar, komma ihåg hur många är på vänster sida och på höger sida och sådana saker, det kommer att bli mycket lättare för dig Om du bara hålla reda på hur många ord du lägger i När du arbetar med belastning. Och så då det sättet storlek kan bara returnera en global variabel storlek. 

Nu kommer vi att kontrollera. Samma normer som tidigare, där vi vill att möjliggöra fall okänslighet. Liksom, antar vi att strängarna är endast alfabetiska tecken eller apostrofer eftersom barn är en array med 27 lång, så alla bokstäver i alfabetet plus apostrof. För kolla vad du vill göra är att du vill starta vid roten eftersom roten pekar på en array som innehåller alla möjliga start bokstäverna i ett ord. Du kommer att börja där, och då du kommer att kontrollera är detta värde NULL eller inte, eftersom om värdet är NULL, innebär detta att ordboken inte har några värden som innehåller den bokstaven i den aktuella ordningen. Om det är NULL, då det innebär att ordet är felstavat direkt. Men om det inte är NULL, då kan du fortsätta säga att första bokstaven är en möjlig första bokstaven i ett ord, så nu vill jag kolla om den andra bokstaven, den sekvensen, är inom min ordbok. Så du kommer att gå till indexet för barnen i den första noden och kontrollera om den andra bokstaven finns. Då du upprepa denna process för att kontrollera om den sekvensen är giltigt eller inte i din Trie. När noden barn på att indexpunkter till NULL, du vet att den sekvensen inte finns, men om du når slutet av ordet som du har matas in, då du vill kontrollera nu när jag har slutfört denna sekvens och fann det i min trie är detta ord giltigt eller inte? Och så då du vill kontrollera det, och det är då om du har hittat den sekvensen, då du vill kontrollera om det ordet är giltigt eller inte eftersom minns tillbaka i det tidigare fallet som jag drog där vi hade FOOB, Det var ett giltigt sekvens som vi hittat, men var inte en verklig giltigt ord i sig. 

Likaså för lasta i försök som du vill lasta alla noder i Trie. Ursäkta. I likhet med hashtabeller var i lasta vi frigjort alla noder, i försök vi vill också frigöra alla noder. Lasta faktiskt kommer att arbeta lättast från botten till toppen eftersom dessa är i huvudsak länkade listor. Så vi vill se till att vi håller fast vid alla värden och fri dem alla explicit. Vad du kommer att vilja göra om du arbetar med en trie är att resa till botten och fri lägsta möjliga noden 1. och sedan gå upp till alla dessa barn och sedan fri alla dem, gå upp och sedan fri etc. Ungefär som att hantera bottenskiktet av trie 1. och sedan gå upp topp när du har befriat allt. Detta är ett bra exempel på när rekursiv funktion kan komma till hands. När du har frigjort den nedre lagret av Trie, då du ringer lasta på resten av det, se till att du gratis varje mini - Du kan slags visualisera det som mini försök. Så du har din rot här. Jag bara förenkla det så jag inte behöver dra 26 av dem. Så du har dessa, och då dessa representerar sekvenser av ord där alla dessa små cirklar är bokstäver som är giltiga sekvenser av bokstäver. Låt oss fortsätta bara lite mer. Vad du kommer att vilja göra är gratis botten här och sedan fri detta en och sedan fritt här i botten innan du frigör den övre upp här för om du fri något i den andra nivån här, då du faktiskt skulle förlora detta värde här. Det är därför det är viktigt i lasta en trie att se till att du frigöra botten först. Vad du kanske vill göra är att säga för varje nod Jag vill lasta alla barn. 

Nu när vi har gått över lasta för hashtabellen metoden samt trie metoden, vi kommer att vilja titta på Valgrind. Valgrind kör du med följande kommandon. Du har Valgrind-v. Du kollar på alla läckor när du kör speller gett denna viss text eftersom speller måste ta i en textfil. Så Valgrind kommer att köra ditt program, berätta hur många byte man tilldelats, hur många byte man befriade, och det kommer att berätta om du befriad lagom eller om du inte tillräckligt fri, eller ibland kan du även över-fri, liksom gratis en nod som redan har befriats och så kommer du tillbaka fel. Om du använder Valgrind, kommer det att ge dig några meddelanden anger om du har befriat antingen mindre än tillräckligt, bara tillräckligt, eller mer än tillräckligt många gånger. 

En del av denna pset är det frivilligt att utmana de stora styrelsen. Men när vi har att göra med dessa datastrukturer Det är ganska kul att se hur snabbt och hur effektivt dina datastrukturer skulle kunna vara. Har din hashfunktion resulterar i en massa kollisioner? Eller är din datastorlek riktigt stora? Tar det mycket tid att korsa? I loggen för stavningskontroll matar det hur mycket tid du använder för att ladda, att kontrollera, att genomföra storlek och att lasta, och så de är postade i The Big Board, där du kan tävla mot dina klasskamrater och vissa anställda att se vem som har den snabbaste stavningskontrollen. En sak som jag skulle vilja att notera om hashtabeller är att det finns några ganska enkla hash funktioner som vi kan tänka på. Till exempel, du har 26 hinkar och så varje skopa motsvarar den första bokstaven i ett ord, men det kommer att resultera i en ganska obalanserad hash-tabell eftersom det är mycket mindre ord som börjar med X än start med M, till exempel. Ett sätt att gå speller är om du vill få alla andra funktioner nedåt, sedan bara använda en enkel hashfunktion för att kunna få din kod körs och sedan gå tillbaka och ändra storleken på din hashtabell och definitionen. Det finns en hel del resurser på Internet för hash funktioner, och så för denna pset du får forska hashfunktioner på Internet för några tips och inspiration så länge du uppge var du fick det ifrån. Du är välkommen att titta och tolka några hashfunktion som du hittar på Internet. Tillbaka till det, kanske du kan se om någon använt en trie om deras genomförande är snabbare än din hashtabell eller inte. Du kan skicka till The Big Board flera gånger. Det kommer att spela din senaste inmatning. Så kanske du ändrar din hashfunktion och sedan inser att det faktiskt är mycket snabbare eller mycket långsammare än tidigare. Det är lite av ett roligt sätt. Det finns alltid 1 eller 2 anställda som försöker göra den långsammaste möjliga ordlistan så det är alltid kul att titta på. 

Användningen för pset är du köra speller med en valfri ordbok och sedan en obligatorisk textfil. Som standard när du kör speller med bara en textfil och inte anger en ordbok, det kommer att använda filen ordlistan texten, den stora en i cs50/pset5/dictionaries mappen. Att man har över 100.000 ord. De har också en liten ordlista som har betydligt mindre ord som CS50 har gjort för dig. Du kan dock enkelt bara göra din egen ordlista Om du bara vill att arbeta i små exempel - till exempel om du vill använda gdb och du vet de specifika värden att du vill att din hashtabell att kartlägga till. Så du bara kan göra din egen textfil bara med bar, BAZ, FOO och Foobar, göra det i en textfil, separera dem med vardera 1 rad, och sedan göra en egen textfil som bokstavligen bara innehåller kanske 1 eller 2 ord så att du vet exakt vad utgången ska vara. Några av filerna prov text som The Big Board när du kör utmaning kommer att kontrollera är Krig och fred och en Jane Austen roman eller något liknande. Så när du har börjat, är det mycket lättare att göra dina egna textfiler som innehåller bara ett par ord eller kanske 10 så att du kan förutsäga vad resultatet ska och sedan kontrollera den mot det, så mer av en kontrollerad exempel. Och så eftersom vi har att göra med att förutse och rita saker runt, igen jag vill uppmuntra dig att använda penna och papper eftersom det verkligen kommer att hjälpa dig med detta - dra pilarna, hur hash tabellen eller hur Trie ser ut, när du frigöra något där pilarna är på väg, håller du på att tillräckligt, ser du några länkar försvinner och faller ner i avgrunden av läckt minne. Så snälla, försök att dra ut saker redan innan du kommer att skriva kod ner. Rita saker så att du förstår hur det går att arbeta för då jag garanterar att du kommer stöta på mindre pekaren dramatiska förändringar där. 

Okej. Jag vill önska er lycka till med detta pset. Det är nog den svåraste en. Så försök att börja tidigt, dra ut saker, dra ut saker, och lycka till. Detta var Genomgång 5. 

[CS50.TV]