JASON Hirschhorn: Välkommen alla till avsnitt sju. Vi är i vecka sju av kursen. Och denna kommande torsdag är Halloween så jag är klädd som en pumpa. Jag kunde inte böja sig och sätta på mina skor, så det är därför jag är bara bära strumpor. Jag är dessutom inte bär något under detta, så att jag inte kan ta bort det om det är distraherande för dig. Jag ber om ursäkt för det. Du behöver inte att föreställa sig vad som händer. Jag har på mig boxare. Så det är allt bra. 

Jag har en längre historia om varför jag är klädd som en pumpa, men jag ska spara det för senare i det här avsnittet eftersom jag vill komma igång. Vi har en massa spännande saker att gå över denna vecka. De flesta av dem är direkt kopplade till detta veckans problem set, felstavningar. Vi kommer att gå över länkade listor och hashtabeller för hela sektionen. Jag sätter denna lista upp varje vecka, en förteckning över resurser för dig att hjälpa dig med materialet på den här kursen. Om det vid en förlust, eller om du letar efter något mer information, kolla in en av dessa resurser. 

Återigen är pset6 felstavningar, veckans pset. Och det uppmuntrar dig också, och jag uppmuntrar dig att använda något annat resurser speciellt för denna pset. I synnerhet tre jag har listade på skärmen - gdb, som vi har varit bekant med och använt ett tag nu, är kommer att vara till stor hjälp i veckan. Så jag lägger upp det här. Men när du arbetar med C, Du bör alltid använda gdb till felsöka dina program. Denna vecka Valgrind också. Är det någon som vet vad valgrind gör? 

PUBLIK: Den kontrollerar för minnesläckor? 

JASON Hirschhorn: Valgrind kontrollerar minnesläckor. Så om du malloc något i ditt program, du ber om minnet. I slutet av ditt program, måste du att skriva fritt om allt du har malloced att ge minnet tillbaka. Om du inte skriver fritt i slutet och programmet kommer till en slutsats, allting automatiskt friges. Och för små program, det är inte så stor en affär. Men om du skriver en längre löpning program som inte sluta, nödvändigtvis, i ett par minuter eller en par sekunder, sedan minnesläckor kan bli en stor affär. 

Så för pset6, är förväntningen att du kommer att ha noll minnesläckor med ditt program. För att kontrollera minnesläckor, kör valgrind och det kommer att ge dig några trevliga utgång så att du vet om eller allt var inte gratis. Vi kommer att öva med den senare i dag, förhoppningsvis. 

Slutligen kommandot diff. Du använde något som liknar det i pset5 med peek verktyget. Tillåtit dig att titta in. Du brukade också diff också, per problemet set spec. Men i tillåtit jämföra två filer. Du kan jämföra bitmappsfilen och info rubriker av en personal-lösning och din lösning i pset5 om du väljer att använda den. Diff gör att du kan göra det, liksom. Du kan jämföra det rätta svaret för veckans problem in på ditt svar och se om den är i linje eller se där felet är. 

Så de är tre bra verktyg som du bör använda för denna vecka, och definitivt kolla ditt program med dessa tre verktyg innan du slår i. Återigen, som jag har nämnt varje vecka, om du har någon feedback för mig - både positiva och konstruktiva - tveka inte att gå till webbplatsen längst ner på den här bilden samt ingång det där. Jag uppskattar verkligen alla och all feedback. Och om du ger mig vissa saker som Jag kan göra för att förbättra eller att jag är går bra att ni vill att jag ska fortsätta, jag tar det till sig och verkligen försöka hårt för att lyssna för din feedback. Jag kan inte lova att jag kommer att göra allt, men, som att bära en pumpa kostym varje vecka. 

Så vi kommer att tillbringa större delen av avsnitt, som jag nämnde, talar om länkade listor och hashtabeller, vilket kommer att vara direkt tillämplig på problem ställa denna vecka. Länkade listor går vi över relativt snabbt eftersom vi har tillbringat en hel del tid att gå över den i avsnitt. Och så vi kommer att få rakt in i kodningsproblem för länkade listor. Och sedan i slutet vi pratar om hashtabeller och hur de tillämpas på detta veckas problem inställd. 

Du har sett den här koden innan. Detta är en struct, och det är att definiera något nytt kallas en nod. Och inuti en nod där är ett heltal just här och det är en pekare till en annan nod. Vi har sett det här förut. Det har kommit upp för ett par veckor nu. Den kombinerar pekare, som vi har varit arbetar med, och structs, som tillåter oss att kombinera två olika saker i en datatyp. 

Det finns mycket som händer på skärmen. Men allt det borde vara relativt bekant med dig. På den första raden, vi deklarera en ny nod. Och sedan inuti den nya noden, ställer jag heltalet i den noden till ett. Vi ser på nästa rad jag gör en printf kommandot, men jag har nedtonade kommandot printf eftersom verkligen viktig del är denna linje här - new_node.n. Vad innebär pricken detta? 

PUBLIK: Gå till noden och bedöma värdet n för det. 

JASON Hirschhorn: Det är exakt rätt. Dot betyder tillgång till n delen av denna nya noden. Denna nästa rad gör vad? Michael. 

PUBLIK: Det skapar en annan nod som kommer att peka till den nya noden. 

JASON Hirschhorn: Så det gör inte skapa en ny nod. Det skapar en vad? 

PUBLIK: En pekare. 

JASON Hirschhorn: En pekare till en nod, vilket framgår av denna nod * här. Så det skapar en pekare till en nod. Och vilken nod det pekar till Michael? 

PUBLIK: Ny nod? 

JASON Hirschhorn: Ny nod. Och den pekar där eftersom vi har gett den adressen till nya noden. Och nu i den här raden ser vi två olika sätt att uttrycka samma sak. Och jag ville påpeka hur dessa två saker är desamma. På första raden, vi dereference pekaren. Så vi går till noden. Det är vad denna stjärna betyder. Vi har sett det förut med pekare. Gå till den noden. Det är inom parentes. Och sedan komma åt via punktoperatorn n element i den noden. 

Så det tar syntaxen vi såg just här och nu använda den med en pekare. Visst, det blir lite upptagen om du skriver dessa parenteser - som stjärna och prick. Det blir lite upptagen. Så vi har några syntaktiska socker. Och denna linje här - ptr_node-> n. Det gör exakt samma sak. Så dessa två rader kod är likvärdiga och kommer att göra exakt samma sak. 

Men jag ville peka dem innan vi går vidare så att du förstår som verkligen denna sak här är bara syntaktisk socker för dereferencing pekaren och sedan gå till n del av den strukt. Har du frågor om denna bild? OK. 

Så vi kommer att gå igenom ett par av verksamheten som du kan göra på länkade listor. En länkad lista, minns, är en serie av noder som pekar på varandra. Och vi börjar i allmänhet med en pekare kallad huvud, i allmänhet, punkterna som till den första på listan. Så på den första raden här, vi har vår ursprungliga L först. Så att man kan tänka på - detta text här kan du komma på som bara pekaren vi har lagrat någonstans att punkter till det första elementet. Och i denna länkade lista Vi har fyra noder. Varje nod är en stor låda. Den större rutan inne i stora box är heltalsdelen. Och sedan har vi en pekare del. 

Dessa boxar är inte dras till skala för hur stor är ett heltal i byte? Hur stor nu? Fyra. Och hur stor är en pekare? Fyra. Så egentligen, om vi skulle dra detta för att skala båda rutorna skulle vara av samma storlek. I det här fallet, vi vill infoga något i den länkade listan. Så du kan se här nere vi sätter in fem Vi färdas genom länkad lista, hitta där fem går, och sedan sätta in det. 

Låt oss bryta ner det och gå lite långsammare. Jag kommer att peka på tavlan. Så vi har vår nod fem som vi har skapat i mallocs. Varför är alla skrattar? Skojar bara. OK. Så vi har malloced fem. Vi har skapat denna nod någon annanstans. Vi ha den redo att gå. Vi börjar på framsidan av vår lista med två. Och vi vill infoga i en sorterad mode. 

Så om vi ser två och vi vill sätta i fem, vad gör vi när vi ser något mindre än oss? Vad? Vi vill infoga fem i detta länkad lista, hålla den sorteras. Vi ser nummer två. Så vad gör vi? Marcus? 

PUBLIK: Kalla pekaren till nästa nod. 

JASON Hirschhorn: Och varför vi går till nästa? 

PUBLIK: För att det är den nästa nod i listan. Och vi vet bara att andra plats. 

JASON Hirschhorn: Och fem är större än två, i synnerhet. Eftersom vi vill hålla det sorterade. Så fem är större än två. Så vi går vidare till nästa. Nu når vi fyra. Och vad händer när vi når fyra? 

Fem är större än fyra. Så vi hålla. Och nu är vi på sex. Och vad ser vi på sex? Ja, Carlos? 

PUBLIK: Sex är större än fem. 

JASON Hirschhorn: Sex är som är större än fem. Så det är där vi vill att infoga fem. Men kom ihåg att om vi bara har en pekare här - detta är vår extra pekare som är traversera genom listan. Och vi pekar på sex. Vi har tappat koll på vad kommer före sex. Så om vi vill infoga något i denna lista hålla den sorteras, vi förmodligen behöver hur många pekare? 

PUBLIK: Två. 

JASON HIRSCHORN: Två. One att hålla reda på den nuvarande en och en för att hålla reda på den föregående. Detta är bara ett enskilt länkad lista. Den går endast en riktning. Om vi ​​hade en dubbelt länkad lista, där allt pekade på saken efter den och den saken innan det, då Vi skulle inte behöva göra det. Men i det här fallet vill vi inte förlora koll på vad som kom före oss i fall Vi måste sätta in fem någonstans i mitten. Säg vi sätter i nio. Vad skulle hända när Vi fick till åtta? 

PUBLIK: Du skulle behöva få den nollpunkten. Istället för att ha nollpunkten du skulle ha att lägga till ett element och sedan har det pekar på nio. 

JASON HIRSCHORN: Exakt. Så vi får åtta. Vi kommer till slutet av listan eftersom Detta pekar på null. Och nu, i stället för att det pekar på null vi har det peka på vår nya noden. Och vi sätter pekaren i vår nya noden på null. Är det någon som har några frågor om att sätta in? Vad händer om jag inte bryr mig om hålla listan sorterad? 

PUBLIK: Stick det till början eller slutet. 

JASON HIRSCHORN: Stick den på början eller slutet. Vilken ska vi göra? Bobby? Varför slutet? 

PUBLIK: Eftersom början är redan fylld. 

JASON HIRSCHORN: OK. Början är redan fylld. Vem vill argumentera mot Bobby. Marcus. 

PUBLIK: Tja du förmodligen vill sticka den i början eftersom annars om du lägger den på slutet du måste korsa hela listan. 

JASON HIRSCHORN: Exakt. Så om vi tänker på runtime, den runtime att infoga i slutet skulle vara n, storleken på denna. Vad är den stora O runtime för att infoga i början? Konstant tid. Så om du inte bryr sig om att hålla något som sorteras, mycket bättre att bara sätt in i början av denna lista. Och det kan göras i konstant tid. 

OK. Nästa funktion är att hitta, som andra - Vi har formulerat detta som sökning. Men vi kommer att titta igenom länkad lista för vissa objekt. Ni har sett kod för söka tidigare i föreläsningen. Men vi liksom bara gjorde det med infoga, eller åtminstone sätta in något sortering. Du ser igenom, kommer nod efter nod, tills du hittar det nummer som du söker. Vad händer om du når I slutet av listan? Säg Jag letar efter nio och jag nå slutet av listan. Vad gör vi? 

PUBLIK: Återgå falskt? 

JASON HIRSCHORN: returnera false. Vi hittade inte det. Om du kommer till slutet av listan och du inte hittar det nummer du är söker, det är inte där. Eventuella frågor om att hitta? Om detta var en sorterad lista, vad skulle vara olika för vårt sökande? Yeah. 

PUBLIK: Det skulle finna det första värdet som är större än den du letar efter och sedan returnera false. 

JASON HIRSCHORN: Exakt. Så om det är en sorterad lista, om vi får något som är större än vad vi söker, behöver vi inte behöver hålla på till slutet av listan. Vi kan på den punkten returnera false eftersom vi inte kommer att hitta den. Frågan är nu, vi har pratat om hålla länkade listor sorteras, hålla dem osorterat. Det kommer att bli något du är förmodligen kommer att behöva tänka på vid kodning problem set fem om du välja en hashtabell med separat kedja synsätt, vilket Vi ska tala om senare. 

Men är det värt att hålla listan sorteras och sedan kunna kanske ha snabbare sökningar? Eller är det bättre att snabbt sätta in något i ständig runtime men sedan har längre söker? Det är en avvägning just där som du får bestämma vad som är lämpligare för ditt specifika problem. Och det är inte nödvändigtvis en helt rätt svar. Men det är verkligen ett beslut som får att göra, och förmodligen bra för att försvara som i, säg, en kommentar eller två varför du väljer en över den andra. 

Slutligen, ta bort. Vi har sett att ta bort. Det är ungefär som att söka. Vi letar efter elementet. Säg att vi försöker ta bort sex. Så hittar vi sex här. Det som vi måste se till att vi gör är att det som pekar på sex - som vi ser i steg två här nere - vad är pekar på sex behov till hoppa sex nu och ändras till vad sex pekar på. Vi vill inte någonsin överge resten av vår lista genom att glömma att ställa in det föregående pekaren. Och så ibland, beroende på programmet, de ska bara bort denna nod helt. Ibland kommer du att vilja återvända det värde som finns i denna nod. Så det är hur du tar bort arbeten. Har du frågor om ta bort? 

PUBLIK: Så om du ska ta bort det, skulle du bara använda gratis eftersom förmodligen var det malloced? 

JASON HIRSCHORN: Om du vill frigöra något som är precis rätt och du malloced den. Säg att vi ville återvända detta värde. Vi kan gå tillbaka sex och sedan fri denna nod och samtal är gratis på den. Eller vi skulle nog ringa gratis först och sedan återvända sex. 

OK. Så låt oss gå vidare till praktik kodning. Vi kommer att koda tre funktioner. Den första heter insert_node. Så du har kod som jag mailade dig, och om du tittar på det här senare du kan komma åt koden i linked.c på CS50 webbplats. Men i linked.c, det finns en del skelett kod som redan skrivits för dig. Och så finns det ett par funktioner du behöver för att skriva. 

Först ska vi skriva insert_node. Och vad insert_node gör säga infogar ett heltal. Och du ger heltalet in i en länkad lista. Och framför allt, behöver du att hålla listan sorterad från minsta till största. Dessutom behöver du inte vill in några dubbletter. Till sist, som ni kan se insert_node returnerar en bool. Så du ska låta användaren veta huruvida insatsen var eller inte framgångsrik genom att returnera sant eller falskt. I slutet av detta program - och för detta steg du inte behöver att oroa sig för att frigöra något. Så allt du gör är att ta ett heltal och sätter in det i en lista. 

Det är vad jag ber dig att göra nu. Återigen, i linked.c, som du alla har, är skelettet kod. Och du bör se mot botten provfunktionsdeklarationen. Men innan vi går in i kodning det i C, uppmanar jag dig starkt att gå genom de steg vi har varit tränar varje vecka. Vi har redan gått igenom en bild av detta. Så du bör ha viss förståelse om hur detta fungerar. Men jag vill uppmuntra dig att skriva lite pseudokod innan du dyker i. Och vi kommer att gå över pseudokod som en grupp. Och sedan när du har skrivit ditt pseudokod, och när vi har skrivit vår pseudokod som en grupp, kan du gå in kodning det i C. 

Som en heads up, det insert_node funktionen är förmodligen den svåraste av de tre vi ska skriva för jag lagt till några ytterligare begränsningar för programmeringen, särskilt att du kommer inte att sätta in något dubbletter och att listan bör förbli sorteras. Så detta är en icke-trivial program att du måste koda. Och varför inte ta 5-7 minuter bara för att få arbeta på pseudokod koden. Och då kommer vi börja går som en grupp. Återigen, om du har några frågor bara räcka upp handen och jag ska komma runt. . 

Vi har också i allmänhet gör dessa - eller jag vet inte uttryckligen säga att du kan arbeta med människor. Men självklart, jag rekommenderar starkt att du, om du har frågor, be granne sitter bredvid dig eller till och med arbeta med någon annars om du vill. Detta behöver inte vara en enskild tyst aktivitet. 

Låt oss börja med att skriva några pseudokod på tavlan. Vem kan ge mig den första raden i pseudokod för det här programmet? För denna funktion, snarare - insert_node. Alden? 

PUBLIK: Så det första jag gjorde var skapa en ny pekare till noden och jag initialiseras det pekar på samma sak som lista pekar på. 

JASON HIRSCHORN: OK. Så du skapar en ny pekare i listan, inte till den noden. 

PUBLIK: Höger. Yeah. 

JASON HIRSCHORN: OK. Och vad vill vi göra? Vad är efter det? Hur är det med nod? Vi har inte en nod. Vi har bara ett värde. Om vi ​​vill infoga en nod, vad gör vi måste göra först innan vi kan till och med tycker om att sätta in det? 

PUBLIK: Åh, förlåt. vi måste malloc utrymme för en nod. 

JASON HIRSCHORN: Excellent. Låt oss göra - OK. Det går inte att nå så hög. OK. Vi kommer att gå ner, och sedan Vi använder två kolumner. Jag kan inte gå att - OK. Skapa en ny nod. Du kan skapa en pekare till lista eller så kan du bara använda listan som den existerar. Du behöver egentligen inte göra det. 

Så vi skapar en ny nod. Bra. Det är vad vi ska göra först. Vad händer nu? 

PUBLIK: Vänta. Ska vi skapa en ny nod nu eller bör vi vänta med att se till att det finns inga dubbletter av noden på listan innan vi skapa den? 

JASON HIRSCHORN: Bra fråga. Låt oss hålla det för senare på grund av att merparten av den tid vi ska skapa en ny nod. Så vi ska ha det här. Men det är en bra fråga. Om vi ​​skapar den och vi hittar en dubblett, vad ska vi gör innan de återvänder? 

PUBLIK: Befria den. 

JASON HIRSCHORN: Ja. Förmodligen befria den. OK. Vad gör vi när vi skapa en ny nod? Annie? 

PUBLIK: Vi sätter antal i noden? 

JASON HIRSCHORN: Exakt. Vi uppskattar antalet - vi malloc utrymme. Jag kommer att lämna det allt som en rad. Men du har rätt. Vi malloc utrymme, och sedan Vi uppskattar antalet i. Vi kan till och med ställa in pekaren en del av den till null. Det är precis rätt. Och vad om efter det? Vi drog denna bild på tavlan. Så vad gör vi? 

PUBLIK: Vi går igenom listan. 

JASON HIRSCHORN: Gå igenom listan. OK. Och vad kontrollerar vi för vid varje nod. Kurt, vad ska vi kolla för varje nod? 

PUBLIK: Se om n-värdet på denna nod är större än n-värdet av vår nod. 

JASON HIRSCHORN: OK. Jag kommer att göra - Ja, OK. Så det är n - Jag kommer att säga om värdet är större än denna nod, vad gör vi? 

PUBLIK: Ja, då sätter vi saken rätt innan dess. 

JASON HIRSCHORN: OK. Så om det är större än det här, då vill vi att sätta in. Men vi vill sätta in den precis innan eftersom vi också skulle behöva vara hålla reda, då, av det som var innan. Så sätter innan. Så missade vi förmodligen något tidigare. Vi behöver antagligen vara att hålla koll på vad som händer. Men vi ska komma tillbaka dit. Så vad värdet är mindre än? Kurt, vad gör vi om värdet är mindre än? 

PUBLIK: Sedan kan du bara fortsätta om det inte är den sista. 

JASON HIRSCHORN: Jag gillar det. Så gå till nästa nod. Om det inte är den sista - vi förmodligen kontrollera för att i villkoren för ett tillstånd. Men ja, nästa nod. Och det börjar bli för låg, så vi ska flytta hit. Men om - alla kan se det här? Om vi ​​är lika vad gör vi? Om det värde vi försöker sätta in är lika med denna nods värde? Yeah? 

PUBLIK: [OHÖRBAR]. 

JASON HIRSCHORN: Ja. Med tanke på detta - Marcus är rätt. Vi kunde kanske gjort något annat. Men med tanke på att vi har skapat det, här Vi bör frigöra och sedan återvända. Oh boy. Är det bättre? Hur är det? OK. Gratis och vad gör vi tillbaka, [OHÖRBAR]? OK. Saknas något? Så vart ska vi hålla reda enligt känd nod? 

PUBLIK: Jag tror att det skulle gå efter att skapa en ny nod. 

JASON HIRSCHORN: OK. Så i början vi förmodligen - Ja, kan vi skapa en pekare till en ny nod, som en tidigare nod pekare och en aktuell nod pekare. Så låt oss sätta det här. Skapa nuvarande och tidigare pekare till noderna. Men när vi justerar dessa pekare? Var ska vi göra det i koden? Jeff? 

PUBLIK: - värdeförhållanden? 

JASON HIRSCHORN: Vilken en särskilt? 

PUBLIK: Jag är bara förvirrad. Om värdet är större än denna nod, inte det betyda att du vill gå till nästa nod? 

JASON Hirschhorn: Så om vårt värde är som är större än värdet på denna nod. 

PUBLIK: Ja, då skulle du vilja gå längre ner på linjen, eller hur? 

JASON Hirschhorn: Höger. Så vi inte sätta in den här. Om värdet är mindre än denna nod, då vi går till nästa nod - eller då vi sätt in tidigare. 

Publik: Vänta, som är denna nod och vilken är värdet? 

JASON Hirschhorn: Bra fråga. Värde per denna definition funktion är vad vi gett. Så värdet är det antal vi gett. Så om värdet är mindre än detta nod, vi behöver tid för att sätta in. Om värdet är större än denna nod, vi går till nästa nod. Och tillbaka till den ursprungliga frågan, dock, där - 

PUBLIK: Om värdet är större än denna nod. 

JASON Hirschhorn: Och så vad gör vi här? Söt. Det stämmer. Jag ska bara skriva uppdaterings pekare. Men ja, med den nuvarande du vill uppdatera den till peka på nästa en. Något annat vi saknar? Så jag ska skriva här koda in gedit. Och medan jag gör det, kan du ha en par minuter att arbeta med kodning detta i C. 

Så jag har ingång pseudokoden. En snabb anteckning innan vi sätter igång. Vi kanske inte kan helt avsluta detta i alla tre av dessa funktioner. Det finns korrekta lösningar på dem att jag kommer att skicka ut till er efter avsnitt, och det kommer finnas på CS50.net. Så jag inte uppmuntrar dig att gå titta på avsnitten. Jag uppmuntrar dig att prova dessa på äger, och sedan använda den praxis problem att kontrollera dina svar. Alla dessa har utformats för att noggrant relatera till och hålla sig till det som du måste göra på problemet set. Så jag uppmuntrar dig att öva detta på egen hand och sedan använda koden för att kontrollera dina svar. Därför att jag vill gå vidare till hash bord någon gång i sektionen. Så vi kanske inte få igenom det hela. Men vi ska göra så mycket vi kan nu. 

OK. Låt oss börja. Asam, hur skapar vi en ny nod? 

PUBLIK: Du struct *. 

JASON Hirschhorn: Så vi har det här uppe. Åh, förlåt. Du sa struct *. 

PUBLIK: Och sedan [? typ?] nod eller c-noden. 

JASON Hirschhorn: OK. Jag kommer att kalla det new_node så vi kan stanna konsekvent. 

PUBLIK: Och du vill ställa in att till huvud, den första noden. 

JASON Hirschhorn: OK. Så nu denna pekar på - så här har inte skapat en ny nod ännu. Detta är bara pekar på första noden i listan. Hur skapar jag en ny nod? Om jag behöver utrymme för att skapa en ny nod. Malloc. Och hur stor? 

Publik: Storleken på strukt. 

JASON Hirschhorn: Den Storleken på strukt. Och vad är det struct heter? 

PUBLIK: Node? 

JASON Hirschhorn: Node. Så malloc (sizeof (nod)); ger oss utrymme. Och är denna linje - en sak är fel på den här linjen. Är new_node en pekare till en struct? Det är ett generiskt namn. Vad är det - nod, exakt. Det är en nod *. Och vad gör vi direkt efter vi malloc något, Asan? Vad är det första vi gör? Vad händer om det inte fungerar? 

PUBLIK: Åh, kolla om det pekar på noden? 

JASON Hirschhorn: Exakt. Så om du new_node lika jämlikar null, vad gör vi? Detta returnerar en bool, denna funktion. Exakt. Ser bra ut. Något att lägga till där? Vi kommer att lägga till saker i slutet. Men det hittills ser bra ut. Skapa nuvarande och tidigare pekare. Michael, hur gör jag detta? 

PUBLIK: Du skulle ha att göra en nod *. Du skulle behöva göra en inte för new_node men för noder som vi redan har. 

JASON Hirschhorn: OK. Så den aktuella noden vi är på. Jag ringer det STRÖM. Okej. Vi har bestämt att vi vill behålla två eftersom vi behöver veta vad som finns innan det. Vad tror de får initieras till? 

PUBLIK: Deras värde i vår lista. 

JASON Hirschhorn: Så vad är det första på vår lista? Eller hur vet vi var början på vår lista är? 

PUBLIK: Är det inte gått i funktion? 

JASON Hirschhorn: Höger. Det antogs i här. Så om det passerat in i funktion, start av listan, vad ska vi inställd ström lika med? 

PUBLIK: List. 

JASON Hirschhorn: List. Det är precis rätt. Nu har adressen till början på vår lista. Och hur är det tidigare? 

PUBLIK: Lista minus ett? 

JASON Hirschhorn: Det finns ingenting innan. Så vad kan vi göra för att betyda någonting? 

PUBLIK: Null. 

JASON Hirschhorn: Ja. Det låter som en bra idé. Perfect. Tack. Gå igenom listan. Konstantin, hur länge ska vi att gå igenom listan? 

PUBLIK: Tills vi når noll. 

JASON Hirschhorn: OK. Så om, samtidigt, för slinga. Vad gör vi? 

PUBLIK: Kanske en for-loop? 

JASON Hirschhorn: Låt oss göra en for-loop. OK. 

PUBLIK: Och vi säger till - tills den aktuella pekar inte är lika med noll. 

JASON Hirschhorn: Så om vi känner till tillstånd, hur kan vi skriva en loop baserat av detta villkor. Vad är det för en slinga ska vi använda? 

PUBLIK: Medan. 

JASON Hirschhorn: Ja. Det är mer förnuftigt baserad bort av vad du sa. Om vi ​​vill bara gå in vi det skulle bara vet det där, skulle det göra meningsfullt att göra en while-slinga. Även om nuvarande inte är lika null, Om värdet är mindre än denna nod. Akshar, ge mig denna linje. 

PUBLIK: Om ström-> n n mindre än värdet. Eller vända det. Slå det fäste. 

JASON Hirschhorn: Förlåt. 

PUBLIK: Byt fästet. 

JASON Hirschhorn: Så om det är större än värdet. Därför att det är förvirrande med comment ovan, kommer jag att göra det. Men ja. Om vårt värde är lägre än detta nod, vad gör vi? Oh. Jag har det här. Infoga tidigare. OK. Hur gör vi det? 

PUBLIK: Är det mig fortfarande? 

JASON Hirschhorn: Ja. 

PUBLIK: Du - new_node-> nästa. 

JASON Hirschhorn: Så vad är som kommer att vara lika? 

PUBLIK: Det kommer att lika stor ström. 

JASON Hirschhorn: Exakt. Och så den andra - vad behöver vi för att uppdatera? 

PUBLIK: Kontrollera om tidigare är lika med noll. 

JASON Hirschhorn: Om bakåt - så om föregående lika med noll. 

PUBLIK: Det betyder att det kommer att bli den huvud. 

JASON Hirschhorn: Det innebär det har blivit huvudet. Så vad gör vi? 

PUBLIK: Vi gör huvudet lika new_node. 

JASON Hirschhorn: Head lika new_node. Och varför gå här, inte lista? 

PUBLIK: Eftersom huvudet är en global variabel, som är startplatsen. 

JASON Hirschhorn: Sweet. OK. Och - 

PUBLIK: Då du annars prev-> nästa lika new_node. Och sedan återvänder sant. 

JASON Hirschhorn: Vari vi satt new_node slut? 

PUBLIK: Jag skulle - Jag satt som i början. 

JASON Hirschhorn: Vad linje? 

PUBLIK: Efter if kontrollera om det är känt. 

JASON Hirschhorn: Här? 

PUBLIK: Jag skulle göra new_node-> n lika värde. 

JASON Hirschhorn: Låter bra. Förmodligen är det klokt - vi gör inte måste veta vad listan är vi på eftersom vi endast behandlar med en lista. Så en bättre funktionsdeklaration för detta är bara för att bli av med helt och bara sätta in ett värde i huvudet. Vi behöver inte ens veta vilken lista som vi är i. Men jag kommer att hålla det för nu och sedan ändra det på att uppdatera bilderna och kod. Så det ser bra ut för nu. Om värde - som kan göra den här linjen? Om - vad gör vi här, Noah. 

PUBLIK: Om värdet är större än nuvarande-> n - 

JASON Hirschhorn: Hur vi går till nästa nod? 

PUBLIK: Curr-> n är lika med new_node. 

JASON Hirschhorn: Så n är vilken del av struct? Heltalet. Och new_node är en pekare till en nod. Så vilken del av curr ska vi uppdatera? Om inte n, vad är den andra? Noa, vad är den andra delen. 

PUBLIK: Åh, nästa. 

JASON Hirschhorn: Next, exakt. Exakt. Nästa är den rätta. Och vad mer behöver vi uppdatera, Noah? 

PUBLIK: Den pekare. 

JASON Hirschhorn: Så Vi uppdaterade ström. 

PUBLIK: Föregående-> nästa. 

JASON Hirschhorn: Ja. OK, vi ska göra en paus. Vem kan hjälpa oss här? Manu, vad ska vi göra? 

PUBLIK: Du måste ställa in det motsvarar nuvarande-> nästa. Men gör det före den tidigare linjen. 

JASON Hirschhorn: OK. Något annat? Akshar. 

PUBLIK: Jag tror inte att du är tänkt att ändra nuvarande-> nästa. Jag tror att du tänkt att göra STRÖM jämlikar STRÖM-> nästa att gå till nästa nod. 

JASON Hirschhorn: Så ledsen, var? På vilken linje? Denna linje? 

PUBLIK: Ja. Gör curr lika curr-> nästa. 

JASON Hirschhorn: Så det är rätt eftersom strömmen är en pekare till en nod. Och vi vill att det ska peka på nästa nod av vad som komma idag pekade. Curr själv har en nästa. Men om vi skulle uppdatera curr.next, vi skulle uppdatera den faktiska anteckning sig själv, inte var det pekaren pekade. Vad sägs om den här linjen, dock. Avi? 

PUBLIK: Föregående-> nästa lika curr. 

JASON Hirschhorn: Så återigen, är om föregående en pekare till en nod, nästa är prev-> den faktiska pekare i noden. Så detta skulle vara att uppdatera en Pekare i en nod till STRÖM. Vi vill inte att uppdatera en pekare i en nod. Vi vill uppdatera tidigare. Så hur gör vi det? 

PUBLIK: Det skulle bara vara bakåt. 

JASON Hirschhorn: Höger. Föregående är en pekare till en nod. Nu ska vi ändra den till en ny pekare till en nod. OK Låt oss flytta ner. Slutligen, det sistnämnda villkoret. Jeff, vad gör vi här? 

PUBLIK: Om värdet är lika med nuvarande-> n. 

JASON Hirschhorn: Förlåt. Åh herregud. Vad? Värde == curr-> n. Vad gör vi? 

PUBLIK: Du skulle befria vårt new_node, och sedan du skulle returnera false. 

JASON Hirschhorn: Detta är vad vi har skrivit hittills. Är det någon som har något att lägga till innan vi gör? OK. Låt oss prova. Kontroll kan nå slutet av ett icke-void funktion. Avi, vad som händer? 

PUBLIK: Ska man sätta retur sant utanför while-slingan? 

JASON Hirschhorn: Jag vet inte. Vill du ha mig till? 

PUBLIK: Glöm det. Nej. 

JASON Hirschhorn: Akshar? 

PUBLIK: Jag tror att du menade att sätta retur falskt i slutet av while-slingan. 

JASON Hirschhorn: Så där vill du att det ska gå? 

PUBLIK: Liksom utanför while-slingan. Så om du avslutar while-slinga som medel att du har nått slutet och ingenting har hänt. 

JASON Hirschhorn: OK. Så vad gör vi här? 

PUBLIK: Du returnera false där också. 

JASON Hirschhorn: Åh, vi göra det på båda ställena? 

PUBLIK: Ja. 

JASON Hirschhorn: OK. Ska vi gå? Åh herregud. Jag är ledsen. Jag ber om ursäkt för skärmen. Det är typ av freaking på oss. Så välj ett alternativ. Noll, per kod, avslutas programmet. Man lägger in något. Låt oss sätta tre. Insatsen var inte lyckat. Jag kommer att skriva ut. Jag har ingenting. OK. Kanske det var bara en lyckträff. Sätt i ett. Inte lyckat. OK. Låt oss gå igenom GDB riktigt snabbt för att kolla vad som händer. 

Minns gdb. / Namnet på din Programmet får oss in i GDB. Är det mycket att hantera? Den blinkande? Förmodligen. Blunda och ta några djupa andetag om du tröttnar att se på det. Jag är i GDB. Vad är det första jag gör i GDB? Vi måste räkna ut vad som händer här. Låt oss se. Vi har sex minuter till figur ut vad som händer. Break. Och vad ska jag göra? Carlos? Kör. OK. Låt oss välja ett alternativ. Och vad gör N göra? Nästa. Yeah. 

PUBLIK: Har du inte nämner - sa du inte att huvudet var det initialiseras till noll vid början. Men jag tyckte du sa att det var OK. 

JASON Hirschhorn: Låt oss - låt oss titta i GDB, och sedan går vi tillbaka. Men det låter som du redan har några idéer om vad som händer. Så vi vill infoga något. OK. Vi har infoga. Ange en int. Vi kommer att sätta in tre. Och så är jag på den här raden. Hur går jag starta debugging insatsen kända funktion? Åh herregud. Det är en hel del. Är det freaking mycket? 

PUBLIK: Åh, dog den. 

JASON Hirschhorn: Jag bara drog ut den. OK. 

PUBLIK: Kanske är det andra änden av kabeln. 

JASON Hirschhorn: Wow. Så den nedersta raden - vad sa du? 

PUBLIK: Jag sa det ironiska i tekniska svårigheter i denna klass. 

JASON Hirschhorn: Jag vet. Om bara jag hade kontroll över den delen. [OHÖRBAR] Det låter bra. Varför inte ni börja tänka på vad vi kunde ha gjort fel, och vi kommer att vara tillbaka i 90 sekunder. 

Avica, jag ska fråga dig hur man ska gå inne insert_node att felsöka den. Så det är där vi senast slutade. Hur kan jag gå in insert_node, Avica, för att undersöka vad som händer? Vad GDB-kommandot? Break skulle inte ta mig in. Har Marquise vet? 

PUBLIK: Vad? 

JASON Hirschhorn: Vad GDB-kommandot Jag använder för att gå in den här funktionen? 

PUBLIK: Steg? 

JASON Hirschhorn: Steg via S. Det tar mig inne. OK. New_node mallocing lite utrymme. Att allt ser ut som det kommer. Låt oss undersöka new_node. Det har lite minnesadress. Låt oss kolla - det är allt rätt. Så allt här verkar att arbeta på rätt sätt. 

PUBLIK: Vad är skillnaden mellan P och display? 

JASON Hirschhorn: P står för utskrift. Och så du frågar vad är det Skillnaden mellan det och det? I detta fall, ingenting. Men generellt finns det vissa skillnader. Och du bör titta i GDB manualen. Men i detta fall, ingenting. Vi tenderar att använda skriva ut, men eftersom Vi behöver inte göra mycket mer än skriva ut ett enskilt värde. 

OK. Så vi är på rad 80 i vår kod, inställning nod * STRÖM lika med listan. Låt oss skriva ut Curr. Det är lika med listan. Söt. Vänta. Det är lika med något. Det verkar inte rätt. Så där. Det är för att i GDB, rätt, om det är den linje du är på det har inte exekveras än. Så du måste verkligen skriva bredvid exekvera linjen innan du ser resultatet. Så här är vi. Vi avrättades just denna linje, tidigare lika med noll. Så återigen, om vi skriver ut tidigare Vi kommer inte se något konstigt. Men om vi faktiskt utför det linje, sedan får vi se att den linjen arbetade. 

Så vi har curr. De är båda bra. Rätt? Nu är vi på den här linjen här. Även curr inte lika null. Tja, vad gör STRÖM lika? Vi såg bara det motsvarade noll. Vi skrivs ut. Jag ska skriva ut den igen. Så är att medan slinga kommer att köra? 

PUBLIK: Nej. 

JASON Hirschhorn: Så när jag skrev att linje, ser du att vi hoppade hela vägen ner till botten, return false. Och då kommer vi att returnera false och gå tillbaka till vårt program och så småningom skriva ut, som vi såg, insatsen var inte lyckat. Så, någon som har några idéer om vad vi behöver göra för att fixa detta? Jag kommer att vänta tills jag ser ett par händer gå upp. Vi ville inte köra här. Tänk, det var den första sak som vi gjorde. Jag tänker inte göra ett par. Jag kommer att göra några. Eftersom ett par betyder två. Jag väntar på mer än två. 

Den första insättnings, Curr, som standard är lika med noll. Och denna slinga endast utför om curr inte är noll. Så hur kan jag komma runt detta? Jag ser tre händer. Jag väntar på mer än tre. Marcus, vad tror du? 

PUBLIK: Tja, om du behöver det för att köra mer än en gång, du bara ändra den till en gör-while-slinga. 

JASON Hirschhorn: OK. Kommer att lösa våra problem, men? 

PUBLIK: I detta fall nej på grund av det faktum att den är tom. Så då har du förmodligen bara behöver lägga till ett uttalande att om de slingutgångarna då måste man vara i slutet av listan, då du kan bara infoga det. 

JASON Hirschhorn: Jag gillar det. Det är vettigt. Om slingan går ut - eftersom det kommer att returnera false här. Så om de slingutgångarna, då är vi på I slutet av listan, eller kanske börja på en lista om det finns ingenting i den, som är densamma som i slutet. Så nu vill vi sätta in något här. Så hur koden ser ut, Marcus? 

PUBLIK: Om du redan har noden malloced, kan du bara säga new_node-> nästa lika med noll, eftersom det måste vara i slutet. Eller new_node-> nästa lika med noll. 

JASON Hirschhorn: OK. Ursäkta. New_node-> nästa lika med noll eftersom vi är i slutet. Det betyder inte lägga den i. Hur ska vi lägga den i listan? Rätt. Det är bara att sätta den lika med. Nej hur gör vi faktiskt lägga den på listan? Vad är det som pekar på slutet av listan? 

PUBLIK: Head. 

JASON Hirschhorn: Förlåt? 

PUBLIK: Head pekar till slutet av listan. 

JASON Hirschhorn: Om det finns ingenting i listan, är huvudet pekar på slutet av listan. Så det kommer att arbeta för första insättningen. Vad händer om det finns ett par saker i listan? Än vi inte vill ställa head lika med new_node. Vad vill vi göra där? Yeah? Förmodligen föregående. Kommer det att fungera? Minns att föregående är bara en pekare till en nod. Och tidigare är en lokal variabel. Så denna linje kommer att sätta en lokal variabel, tidigare, är lika med eller pekar på den nya noden. Det kommer faktiskt inte lägga den i vår lista, men. Hur ska vi lägga den i vår lista? Akchar? 

PUBLIK: Jag tror att du gör ström-> nästa. 

JASON Hirschhorn: OK. STRÖM-> nästa. Så återigen, den enda anledningen till att vi är nere här är, vad betyder ström lika? 

PUBLIK: Lika med noll. 

JASON Hirschhorn: Och så vad händer om vi gör null-> next? Vad är det vi kommer att få? Vi får en segmentering fel. 

PUBLIK: Do curr lika med noll. 

JASON Hirschhorn: Det är samma sak som föregående, men eftersom det finns en lokal variabel vi ställer som är lika med detta nya noden. Låt oss gå tillbaka till vår bild för att sätta in något. Säg att vi sätter in i slutet av listan, så här. Vi har en aktuell pekare som är pekar på null och en tidigare punkt som är riktad till 8. Så vad gör vi behöver uppdatera, Avi? 

PUBLIK: Tidigare-> next? 

JASON Hirschhorn: Tidigare-> Nästa är vad vi vill uppdatera eftersom det faktiskt kommer att sätta in den på I slutet av listan. Vi har fortfarande en bugg, fast, att vi kommer att stöta på. Vad är det bugg? Yeah? 

PUBLIK: Det kommer att återvända falskt i det här fallet? 

JASON Hirschhorn: Åh, är är kommer att returnera false. Men det finns en annan bugg. Så vi måste sätta i gengäld sant. 

PUBLIK: Har tidigare fortfarande lika null i toppen av listan? 

JASON Hirschhorn: Så förra fortfarande är lika med noll i början. Så hur kan vi komma över det? Yeah? 

PUBLIK: Jag tror att du kan göra en kontroll innan while-slingan för att se om det är en tom lista. 

JASON Hirschhorn: OK. Så låt oss gå hit. Gör en kontroll. Om - 

PUBLIK: Så om huvudet är lika med är lika med noll. 

JASON Hirschhorn: Om huvudet är lika är lika med noll - som kommer att tala om för oss om det är en tom lista. 

PUBLIK: Och sedan göra huvudet lika nytt. 

JASON Hirschhorn: Head lika new_node? Och vad behöver vi göra? 

PUBLIK: Och då du returnerar sant. 

JASON Hirschhorn: Inte riktigt. Vi missar ett steg. 

PUBLIK: New_node nästa måste peka på null. 

JASON Hirschhorn: Exakt, Alden. Och då kan vi återvända sant. OK. Men det är fortfarande en bra idé att göra saker i slutet av listan, eller hur? Okej. Vi fortfarande kan faktiskt få till slutet av listan. Så är den här koden bra om vi är på slutet av listan och det finns några saker i listan? Rätt? Eftersom vi har fortfarande Marcus idé. Vi skulle kunna gå ur denna slinga, eftersom vi är i slutet av listan. Så gör vi fortfarande vill ha det koden här nere? 

PUBLIK: Ja. 

JASON Hirschhorn: Ja. Och vad behöver vi för att ändra det till? Sant. Låter det bra till alla så långt? Någon som har någon - Avi, har du något att tillägga? 

PUBLIK: Nej. 

JASON Hirschhorn: OK. Så vi har gjort ett par förändringar. Vi har gjort denna kontroll innan vi gick in på en tom lista. Så vi har tagit hand om en tom lista. Och här tog vi hand om att sätta in något i slutet av listan. Så det verkar som om detta medan slinga tagande hand om saker i mellan, någonstans i listan, om det är saker på listan. 

OK. Låt oss köra programmet igen. Inte lyckat. 

PUBLIK: Du gjorde inte det. 

JASON Hirschhorn: Åh, Jag gjorde inte det. Bra punkt, Michael. Låt oss lägga en make knuten. Linje 87 finns det ett fel. Linje 87. Alden, var detta den linje du gav mig. Vad är fel? 

PUBLIK: Det måste vara null. 

JASON Hirschhorn: Excellent. Exakt rätt. Det bör vara noll. Låt oss göra igen. Sammanställ. OK. Låt oss sätta tre. Insatsen var framgångsrik. Låt oss skriva ut den. Åh, om bara vi kunde kontrollera. Men vi har inte gjort det skriva ut fungerar ännu. Låt oss komma in något annat. Vad ska vi komma in? 

PUBLIK: Sju. 

JASON Hirschhorn: Seven? 

PUBLIK: Ja. 

JASON Hirschhorn: Vi har en seg fel. Så vi fick en, men vi klart kan inte få två. Det är 05:07. Så vi kan felsöka detta under tre minuter. Men jag kommer att lämna oss här och gå vidare till hashtabeller. Men återigen, svaren för denna kod Jag kommer att skicka den till dig i lite. Vi är mycket nära den. Jag rekommenderar varmt att du räkna ut vad som händer här och fixa det. Så jag kommer att skicka dig koden som bra plus att den lösning - förmodligen lösningen senare. Först denna kod. 

Det andra jag vill göra innan vi fullföljande är att vi har inte befriat någonting. Så jag vill visa dig vad valgrind ser ut. Om vi ​​kör valgrind gränser på vårt program,. / kopplat. Återigen, enligt denna bild, vi bör köra valgrind med någon typ av alternativ, i detta fall - Läckagekontroll = full. Så låt oss skriva valgrind - Läckagekontroll = full. Så detta kommer att köras valgrind på vårt program. Och nu programmet faktiskt körs. Så vi kommer att köra det precis som innan, sätta något i. Jag kommer att sätta in tre. Det fungerar. Jag tänker inte försöka sätta in något annat för att vi ska få en seg falskt i det fallet. Så jag ska bara sluta. 

Och nu ser här nere läcka och heap sammanfattning. Dessa är de bra saker som du vill checka ut. Så högen sammanfattningen - det står i bruk vid avfart - åtta byte i ett block. Det ena blocket är nod vi malloced. Michael, du sa innan en nod är åtta bites eftersom det har heltalet och pekaren. Så det är vår nod. Och då säger vi använt malloc sju gånger och vi befriade något sex gånger. Men vi aldrig kallade fria, så jag har ingen aning om vad det talar om. 

Men det räcker med att säga att när du programkörningar, är malloc som kallas på vissa andra platser som vi behöver inte oroa dig. Så malloc troligen kallades på vissa ställen. Vi behöver inte oroa dig där. Men detta är verkligen oss. Denna första raden är oss. Vi lämnade det blocket. Och du kan se att här i läckage sammanfattning. Fortfarande nås - åtta byte i ett block. Det innebär att minnet - Vi har läckt ut att minnet. Definitivt förlorade - något försvinner för gott. Generellt kommer du inte se något där. Fortfarande nås är i allmänhet där du kommer att se saker, där du vill att titta för att se vad koden ska du har befriat men du glömde att befria. 

Och sedan, om så inte var fallet, om vi gjorde gratis allt, vi kan kontrollera det. Låt oss bara köra programmet inte att sätta in något. Du ser här nere i bruk vid avfart - noll byte i noll block. Det betyder att vi hade ingenting kvar när programmet avslutas. Så innan du slår i pset6, kör valgrind och se till att du inte har något minne läckor i ditt program. Om du har några frågor med valgrind, tveka inte att nå ut. Men det är hur du använder den. Mycket enkelt - se om du har används vid avfart - några byte i några block. 

Så vi arbetade på skäret nod. Jag hade två andra funktioner här - skriva ut noder och fria noder. Återigen, dessa är funktioner som är kommer att vara bra för dig att träna eftersom de hjälper dig inte bara med dessa prov övningar men också på problemet inställd. De kart på ganska nära till saker du kommer att behöva göra i problem set. Men jag vill se till att vi rör på allting. Och hashtabeller är också avgörande för vad vi gör i avsnittet här vecka - eller i det problemet set. 

Så vi kommer att avsluta avsnittet talar om hashtabeller. Om du märker att jag gjorde en liten hashtabell. Det är inte vad vi pratar om dock. Vi talar om en annan typ av hash-tabeller. Och i sin kärna, en hashtabell är inget annat än en matris plus en hashfunktion. Vi kommer att prata om lite bara för att se till att alla förstår vad en hashfunktion visas. Och jag säger nu att det är inget mer än två saker - en matris och en hashfunktion. Och här är de steg genom som det verkar. 

Det är vår samling. Det är vår uppgift. I synnerhet hashfunktioner behöver göra ett par saker med detta. Jag ska prata specifikt om detta problem set. Det kommer förmodligen att ta i en sträng. Och vad kommer det att återvända? Vilken datatyp? Alden? Din hashfunktion tillbaka? Ett heltal. Så detta är vad hash Tabellen består av - en tabell i form av matris och en hashfunktion. Hur fungerar det? Det fungerar i tre steg. Vi ger det en nyckel. I det här fallet kommer vi att ge det ett snöre. Vi kallar hashfunktionen per steg ett på nyckeln och vi får ett värde. 

Specifikt ska vi säga vi får ett heltal. Att heltal, det finns mycket specifika gränser för vad som heltal kan vara. I det här exemplet, vår array är av storlek tre. Vilka siffror kan det heltal vara. Vad är utbudet av giltiga värden för som heltal, returtypen av detta hashfunktion? Noll, ett och två. Poängen med hashfunktionen är att räkna ut den plats i arrayen där vår nyckel går. Det finns bara tre möjliga platser här - noll, ett eller två. Så här fungerar bättre avkastning noll, ett eller två. Några giltig indice i denna samling. 

Och sedan beroende på var den återvänder, ni ser finns array öppen bracket värdet. Det är där vi sätter nyckeln. Så vi kastar i pumpan, vi får ut noll. Vid array fäste 0, sätter vi pumpa. Vi kastar i katter, vi får ut en. Vi sätter katten på en. Vi lägger i spindel. Vi får ut två. Vi lägger spindel på array fäste två. Det skulle vara så trevligt om det fungerade så. Men tyvärr, så vi får se, det är lite mer komplicerat. 

Innan vi kommer dit, några frågor om denna grundläggande installation av en hash-tabell? Detta är en bild av exakt vad vi ritade på tavlan. Men eftersom vi drog det på tavlan, jag tänker inte gå in på det längre. I huvudsak nycklar, den magiska svarta lådan - eller i detta fall, kricka låda - av en hashfunktionen sätter dem i hinkar. Och i det här exemplet är vi inte sätta namnet. Vi sätter den tillhörande telefon antal namn i hinken. Men du kan mycket väl bara sätta namn i hinken. 

Detta är bara en bild av vad Vi drog på tavlan. Vi har potentiella fallgropar, dock. Och det finns två särskilt diabilder som jag vill gå över. Den första är om en hashfunktion. Så jag ställde frågan, vad gör en bra hashfunktion? Jag ger två svar. Den första är att det är deterministisk. Inom ramen för hashfunktioner, vad innebär det? Ja? 

PUBLIK: Det kan hitta den index i konstant tid? 

JASON Hirschhorn: Det är inte vad det betyder. Men det är en bra gissning. Någon annan har en gissning vad detta betyder? Att en bra hashfunktion är deterministisk? Annie? 

PUBLIK: Att en nyckel endast kan kartläggas till en plats i hash-tabellen. 

JASON Hirschhorn: Det är exakt rätt. Varje gång du sätter på pumpa, det alltid returnerar noll. Om du sätter i pumpa och ditt hash returnerar noll, men har ett sannolikhet att återvända något annat större än noll - så kanske det kan återvända en ibland eller två andra tillfällen - som inte är en bra hashfunktion. Du har helt rätt. Din hashfunktion ska returnera exakt samma tal, i detta fall, för exakt samma sträng. 

Kanske den returnerar exakt samma heltal för samma exakta strängen oavsett kapitalisering. Men i så fall är det fortfarande deterministisk eftersom flera saker mappas på samma värde. Det är bra. Så länge som det finns endast en utgång för en viss ingång. 

OK. Det andra är att det returnerar giltiga index. Vi tog upp det tidigare. Denna hash-funktion - oh boy - en hashfunktion bör returnera giltiga index. Så säger - låt oss gå tillbaka till det här exemplet. Min hashfunktion räknar upp bokstäverna i ordet. Det är hashfunktionen. Och returnerar det heltal. Så om jag har ordet A, är det kommer att återvända en. Och det kommer att sätta ett här. Vad händer om jag lägger i ordet fladdermus? Det kommer att gå tillbaka tre. Vart tar bat vägen? 

Det passar inte. Men det måste gå någonstans. Det här är min hashtabell trots allt, och allt måste gå någonstans. Så var ska bat gå? Några tankar? Gissningar? Goda gissningar? 

PUBLIK: Noll. 

JASON Hirschhorn: Varför noll? 

PUBLIK: Eftersom tre modulo tre är noll? 

JASON Hirschhorn: Tre modulo tre är noll. Det är en bra gissning, och det är rätt. Så i det här fallet det ska förmodligen gå på noll. Så ett bra sätt att se till att denna hash returnerar endast giltiga index att modulo det av storleken på tabellen. Om du modulo oavsett denna avkastning genom tre, du alltid kommer att få någonting mellan noll, ett, och två. Och om detta alltid återvänder sju, och du alltid modulo av tre, är du alltid kommer att få samma sak. 

Så det är fortfarande deterministiska om du modulo. Men det kommer att se till att du aldrig få något - en ogiltig industrin. Generellt bör det modulo hända inuti din hashfunktion. Så du behöver inte oroa dig för detta. Du kan bara se till att detta är ett giltigt indice. Eventuella frågor om detta potentiell fallgrop? 

OK. Och där går vi. Nästa potentiell fallgrop, och Detta är den stora. Vad händer om två tangenter karta till samma värde? Så det finns två sätt att hantera detta. Den första heter linjär sondering, som jag är inte kommer att gå över. Men du bör känna till hur som fungerar och vad det är. 

Det andra jag kommer att gå över eftersom det är den som många människor kommer förmodligen att hamna beslutar att använda i deras problem set. Naturligtvis behöver du inte till. Men om problemet set, många människor tenderar att välja att skapa en hashtabell med separat chaining för att genomföra deras ordlista. Så vi kommer att gå igenom vad det innebär för att skapa en hash-tabell med separat kedja. 

Så jag satte på pumpa. Den returnerar noll. Och jag satte pumpa här. Sedan satte jag in - vad är en Halloween-tema sak? 

PUBLIK: Candy. 

JASON Hirschhorn: Godis! Det är en stor en. Jag satte i godis, och godis ger mig också noll. Vad ska jag göra? Några idéer? Eftersom du alla slags vet vad separat kedja är. Så några idéer vad göra? Yeah. 

PUBLIK: Att sätta strängen faktiskt i hash-tabellen. 

JASON Hirschhorn: Så vi ska dra bra här borta. OK. 

PUBLIK: Har hashtable [OHÖRBAR] den pekare som pekar på I början av en lista. Och sedan har pumpa vara det första värdet i den länkade listan och godis vara det andra värdet i den länkade listan. 

JASON Hirschhorn: OK. Marcus, som var enastående. Jag kommer att bryta ner det. Marcus säger inte skriva över pumpa. Det skulle vara dåligt. Lägg inte godis någon annanstans. Vi kommer att sätta dem båda på noll. Men vi kommer att ta itu med sätta dem på noll skapa en lista på noll. Och vi kommer att skapa en lista med allt som mappas till noll. Och det bästa sättet vi lärt oss att skapa en lista som kan växa och krympa dynamiskt inte är inom annan matris. Så inte en flerdimensionell array. Men att bara skapa en länkad lista. 

Så vad han föreslog - Jag ska få ett nytt - är att skapa en array med pekare, en array av pekare. OK. Någon idé eller ledtråd vad typ av denna pekare bör vara? Marcus? 

PUBLIK: Pekare till - 

JASON Hirschhorn: Eftersom du sade en länkad lista, så - 

PUBLIK: Node pekare? 

JASON Hirschhorn: Node pekare. Om saker i vår länkade Listan är noder då de bör vara nod pekare. Och vad gör de lika från början? 

PUBLIK: Null. 

JASON Hirschhorn: Null. Så det är vår tomt sak. Pumpa återgår noll. Vad gör vi? Walk mig igenom det? Egentligen Marcus gav mig redan. Någon annan gå mig igenom det. Vad vi gör när vi - detta är mycket lik vad vi gör bara. Avi. 

PUBLIK: Jag kommer att ta en gissning. Så när du får godis. 

JASON Hirschhorn: Ja. Nåväl, vi fick pumpa. Låt oss få vår första. Vi fick pumpa. 

PUBLIK: OK. Pumpa återgår noll. Så du lägga den i det. Eller faktiskt, lägger du den i den länkade listan. 

JASON Hirschhorn: Hur gör vi lägga den i den länkade listan? 

PUBLIK: Åh, den verkliga syntax? 

JASON Hirschhorn: Bara gå - säga mer. Vad gör vi? 

PUBLIK: Du sätter bara den som den första noden. 

JASON Hirschhorn: OK. Så vi har vår nod, pumpa. Och nu hur ska jag sätta in det? 

PUBLIK: Du tilldelar den till pekaren. 

JASON Hirschhorn: Vilken pekare? 

PUBLIK: Pekaren på noll. 

JASON Hirschhorn: Så där gör detta? 

PUBLIK: Att null just nu. 

JASON Hirschhorn: Tja, det pekar på null. Men jag sätter på pumpa. Så var ska den peka? 

PUBLIK: Att pumpa. 

JASON Hirschhorn: Att pumpa. Exakt. Så här pekar på pumpa. Och varifrån kommer denna pekare i pumpa punkt? Till 

PUBLIK: Null. 

JASON Hirschhorn: Att null. Exakt. Så vi bara insatt något i den länkade listan. Vi skrev bara den här koden för att göra detta. Nästan vi nästan fick det helt knäckt. Nu sätter vi godis. Vår godis går också till noll. Så vad gör vi med godis? 

Publik: Det beror på om eller inte vi försöker lösa det. 

JASON Hirschhorn: Det är exakt rätt. Det beror på om eller inte vi försöker lösa det. Låt oss anta att vi inte är kommer att sortera det. 

PUBLIK: Nåväl, när vi diskuterade innan, är det enklaste att bara lägga den alldeles i början så pekaren från noll poäng till godis. 

JASON Hirschhorn: OK. Håll ut. Låt mig skapa godis här. Så denna pekare - 

PUBLIK: Ja, det borde nu peka på godis. Har sedan pekaren från godis peka på pumpa. 

JASON Hirschhorn: Gillar det? Och säga att vi fick en annan sak att kartlägga till noll? 

PUBLIK: Tja, du bara göra samma sak? 

JASON Hirschhorn: Gör samma sak. Så i det här fallet, om vi inte vill hålla det sorteras det låter ganska enkel. Vi tar pekaren i indice som ges av vår hashfunktion. Vi har som pekar på vår nya noden. Och sedan vad det pekade till tidigare - i detta fall noll, i andra fallet pumpa - att, oavsett vad det pekar på tidigare, vi lägger in i nästa av vår nya noden. Vi ska sätta in något i början. I själva verket är detta en mycket enklare än försöker hålla listan sorteras. Men återigen, kommer sökningen att vara mer komplicerat på här. Vi kommer alltid att gå till slutet. 

OK. Eventuella frågor om separat kedja? Hur det fungerar? Fråga dem nu. Jag vill verkligen se till att du hela förstå detta innan vi beger oss ut. 

PUBLIK: Varför sätter pumpa och godis i samma del av hash-tabell? 

JASON Hirschhorn: Bra fråga. Varför vi sätta dem i samma del av hash-tabell? Tja, i det här fallet vår hashfunktion avkastningen noll för dem båda. Så de behöver gå på indice noll eftersom det är där vi ska leta efter dem om vi någonsin vill slå upp dem. Igen, med en linjär sondering tillvägagångssätt Vi skulle inte sätta dem båda på noll. Men i den separata kedjan strategi, vi ska sätta dem båda på noll och sedan skapa en lista från noll. 

Och vi vill inte skriva över pumpa bara för det för då kommer vi anta att pumpa var aldrig införas. Om vi ​​bara hålla en sak i plats som skulle vara dåligt. Då skulle det inte finnas någon chans av oss någonsin - om vi någonsin haft en dubblett, då vi skulle bara radera vår initiala värdet. Så det är därför vi gör detta tillvägagångssätt. Eller det är därför vi valde - men återigen, vi valde separat kedja tillvägagångssätt där det finns många andra metoder man kunde välja. Besvarar det din fråga? 

OK. Carlos. Linjär sondering skulle innebära - om vi hittade en kollision på noll, vi skulle se i nästa plats för att se om det var öppet och lägga den där. Och då vi tittar på nästa idrott och se om det var öppet och lägga den där. Så hittar vi nästa tillgängliga öppen plats och lägga den där. Fler frågor? Ja, Avi. 

Publik: Som en uppföljning till denna, vad menar du med nästa plats? I hashtabell eller i en länkad lista. 

JASON Hirschhorn: För linjär programmering, inga länkade listor. Nästa punkt på hash-tabell. 

PUBLIK: OK. Så hashtabellen skulle vara initialiseras till storleken - liksom antalet strängar att du sätter in? 

JASON Hirschhorn: Du skulle vill att det ska bli riktigt stort. Ja. Här är en bild av vad vi bara drog på tavlan. Återigen har vi en kollision här. vid 152. Och du kommer att se att vi skapade en länkad lista på det. Igen, hashtabell separat kedja tillvägagångssätt är inte den du måste ta för problem inställd sex men är en som många eleverna tenderar att ta. Så på Alltså, låt oss prata en kort stund innan vi beger oss ut om problemet sex, och sedan ska jag dela en berättelse med dig. Vi har tre minuter. 

Problem set sex. Du har fyra funktioner - last, kontrollera, storlek, och lasta. Load - Tja, vi har pågått över lasten just nu. Vi drog belastning på tavlan. Och vi ens börjat koda en hel del föra in i en länkad lista. Så belastningen är inte mycket mer än vad vi just gjort. 

Check är när du har något laddad. Det är samma process som denna. Samma två första delarna där du kastar något i hashfunktionen och få sitt värde. Men nu är vi inte sätter in det. Nu är vi letar efter det. Jag har prov kod skriven för att hitta något i en länkad lista. Jag uppmuntrar dig att träna det. Men intuitivt att hitta något är ganska lik att sätta in något. I själva verket drog vi en bild av att finna något i en länkad lista, flytta igenom tills du kommit till slutet. Och om du fick på slutet och kunde inte tycker att det är, då är det inte där. Så det är kontroll, i huvudsak. 

Nästa är storleken. Låt oss hoppa över storlek. Slutligen har du lasta. Unload är något vi har inte dragit i styrelsen eller kodade ännu. Men jag uppmuntrar dig att försöka koda det i vårt urval länkad lista exempel. Men lasta intuitivt liknar gratis - eller jag menar liknar kolla. Med undantag för nu varje gång du ska igenom, du är inte bara kontrollera att se om du har ditt värde där. Men du tar den noden och befria det, i grunden. Det är vad lasta ber dig att göra. Gratis allt du har malloced. Så du går igenom hela listan igen, gå igenom hela hash bord igen. Den här gången inte kolla för att se vad som finns där. Bara frigöra vad som finns där. 

Och slutligen storlek. Storlek bör genomföras. Om du inte genomför storlek - Jag ska säga det så här. Om du inte genomför storleken på exakt en rad kod, inklusive tillbaka uttalandet, är du gör storlek felaktigt. Så se till storlek, för full design poäng, du gör det på exakt en kodrad, inklusive retur uttalande. 

Och inte packa upp ännu, Akchar. Eager beaver. Jag ville säga tack killar för kommande avsnitt. Ha en lyckliga Halloween. Det här är min dräkt. Jag kommer att ha på sig detta på torsdag Om jag ser dig på kontorstid. Och om du är nyfiken på lite mer bakgrund som till denna dräkt, känner fri att kolla in 2011 avsnitt för en berättelse om varför jag är bär pumpa kostym. Och det är en sorglig historia. Så se till att du har vissa vävnader i närheten. Men på det, om du har någon frågor som jag ska hålla mig runt utanför efter avsnitt. Lycka till på problem set sex. Och som alltid, om du har någon frågor, låt mig veta.