[MUSIK SPELA] TALARE 1: Okej. Alla välkomna tillbaka till avsnitt. Jag hoppas att ni alla är framgångsrikt återhämtat sig från din frågesport från förra veckan. Jag vet att det är lite galet ibland. Som jag sa tidigare, om du är inom standardavvikelsen, egentligen inte oroa dig för det, i synnerhet för en mindre bekväm sektion. Det handlar om var du ska vara. Om du gjorde bra, så häftigt. Kudos till dig. Och om du känner att du behöver lite mer hjälp, tveka inte att nå ut till någon av TF: er. Vi är alla här för att hjälpa. 

Det är därför vi undervisar. Det är därför jag är här varje måndag för dig killar och på kontoret timmar på torsdagar. Så är du välkommen att låta mig veta om du är orolig för vad som helst eller om det finns något på frågesport att du verkligen vill ta itu med. 

Så dagordningen för idag allt om datastrukturer. Några av dessa är bara kommer att bli precis att få dig förtrogen med dessa. Du kanske aldrig genomföra dem i denna klass. Några av dem kommer du, som för din speller pset. 

Du har ditt val mellan hashtabeller och försök. Så vi kommer definitivt att gå över dem. Det kommer att bli definitivt mer av slag av ett avsnitt på hög nivå i dag, men, eftersom det finns en hel del av dem, och om Vi gick in på detaljer implementerings På alla dessa, vi skulle inte ens få igenom länkade listor och kanske lite hashtabeller. 

Så ha tålamod med mig. Vi kommer inte att göra så mycket kodning denna gång. Om du har några frågor om det eller om du vill se det genomfört eller prova själv, Jag rekommenderar definitivt kommer att study.cs50.net, vilket har exempel på alla dessa. Det kommer att ha mina Powerpoints med de anteckningar som vi tenderar att använda såväl som viss programmering övningar, speciellt för saker som länkade listor och binära träd stackar och köer. Så lite mer hög nivå, vilket kan vara trevligt för er. 

Så med det, ska vi komma igång. Och även, yes-- frågesporter. Jag tror att de flesta av er som är i min avdelning har dina frågesporter, men någon kommer in eller av någon anledning inte gör det, de är här i fronten. 

Så länkade listor. Jag vet att den här typen av går att backa innan din frågesport. Det var veckan innan att vi lärt oss om detta. Men i detta fall, vi ska bara gå lite mer på djupet. 

Så varför skulle vi välja en lista kopplad över en array? Det som skiljer dem? Ja? 

PUBLIK: Du kan expandera en länkad lista kontra en arrays fast storlek. TALARE 1: Rätt. En array har fast storlek medan en länkad lista har en variabel storlek. Så om vi inte vet hur mycket vi vill lagra, en länkad lista ger oss en stor sätt att göra det eftersom vi kan bara lägga på en annan nod och lägg på annan nod och lägga på en annan nod. Men vad som kan vara en kompromiss? Kommer någon ihåg avvägningen mellan arrayer och länkade listor? Mmhmm? 

PUBLIK: Du måste gå igenom hela vägen via den länkade listan hitta ett element i en lista. I en array, kan du bara hitta ett element. 

TALARE 1: Rätt. Så med arrays-- 

PUBLIK: [OHÖRBAR]. 

TALARE 1: Med matriser, vi har vad som kallas random access. Innebär att om vi vill ha det någonsin den femte punkten i en lista eller femte punkten i vår array, kan vi bara ta tag i den. Om det är en länkad lista, vi har att iterera igenom, eller hur? Så åtkomst till en del av en array är konstant tid, medan med en länkad lista skulle det sannolikt vara linjär tid eftersom kanske vår del är hela vägen i slutet. Vi måste söka igenom allt. Så med alla dessa uppgifter strukturer vi kommer att spendera lite mer tid på, Vad är plussidan och negativ. När kan vi vill använda en över den andra? Och det är typ av större sak att ta bort. 

Så vi har här definitionen av en nod. Det är som en del i vår länkad lista, eller hur? Så vi är alla bekanta med våra typedef structs, som vi gick över i gransknings förra gången. Det var i princip bara att skapa annan datatyp som vi kunde använda. 

Och i det här fallet, är det någon nod som kommer att hålla några heltal. Och vad är den andra delen här? Någon? 

PUBLIK: [OHÖRBAR]. 

TALARE 1: Ja. Det är en pekare till nästa nod. Så detta borde egentligen vara här uppe. Detta är en pekare av typ nod till nästa sak. Och det är vad de omfattar vår nod. Cool. 

Okej, så med sökandet, som vi var bara säga innan handen, om du är kommer att söka igenom, du måste verkligen iterera via din länkad lista. Så om vi är ute efter numret 9, skulle vi börja på vårt huvud och det leder oss i början av vår länkad lista, eller hur? Och vi säger, OK, gör detta nod innehåller nummer 9? Nej? 

Okej, gå till nästa. Följ den. Innehåller den nummer 9? Nej. Följ nästa. 

Så vi måste verkligen iterera genom vår länkad lista. Vi kan inte bara gå direkt till där 9 är. Och om ni verkligen vill Hitta pseudokod uppe. Vi har några sökfunktion här som tar in-- vad tar det i? Vad tycker du? Så lätt en. Vad är detta? PUBLIK: [OHÖRBAR]. SPEAKER 1: Antalet vi letar efter. Rätt? Och vad skulle det motsvara? Det är en pekare till? 

Publik: En nod. 

TALARE 1: En nod i listan att vi tittar på, eller hur? Så har vi några noder är pekare här. Detta är en punkt som kommer att faktiskt iterera igenom vår lista. Vi sätter det lika med lista eftersom det är bara att ställa in den är lika med den start av vår länkad lista. 

Och även om det inte är NULL, medan vi har fortfarande saker i vår lista, kontrollera om den noden har Antalet vi söker. Return true. Annars uppdatera den, eller hur? 

Om det är NULL, vi avsluta vår while-slinga och returnera false eftersom det innebär att vi inte har hittat den. Får alla människor hur det fungerar? OK. 

Så med insättning, du har tre olika sätt. Du kan infoga före, du kan lägga till och du kan infoga i diverse. I det här fallet är vi kommer att göra ett prefix. Vet någon hur de tre fall kan skilja? 

Så prepend innebär att du sätter det på framsidan av din lista. Så det skulle innebära att oavsett vad din nod är, oavsett vad värdet är, du kommer att rätta till det här framför, OK? Det kommer att bli den första element i listan. 

Om du lägger det, det kommer att gå till baksidan av din lista. Och sätt in i diverse innebär att du ska sätta faktiskt till platsen där den håller din länkad lista sortering. Återigen, hur du använder dem och när du använder dem kommer att variera beroende på ditt ärende. Om det inte behöver sorteras, tenderar prepend vara vad de flesta människor använda eftersom du inte måste gå igenom hela listan att finna i slutet för att lägga den på, eller hur? Du kan bara hålla det rätt in. 

Så vi kommer att gå igenom en insättning 1 just nu. Så en sak som jag kommer att rekommenderar den här pset är att dra ut saker, som alltid. Det är mycket viktigt att du uppdaterar dina pekare i rätt ordning för om du uppdatera dem något ur funktion, du kommer att hamna förlora delar av din lista. 

Så till exempel i det här fallet är vi berättar chefen att bara peka på 1. Om vi ​​gör just det utan att spara detta 1, Vi har ingen aning om vad 1 ska peka på nu eftersom vi har förlorat vad huvudet pekade. Så en sak att komma ihåg När du gör en prefix är att rädda vad huvud pekar på första, sedan dela ut det och sedan uppdatera vad din nya noden ska peka på. I det här fallet, är detta ett sätt att göra det. 

Så om vi hade gjort det så här där vi bara omplacerad huvudet, vi förlorar i princip vår hela listan, eller hur? Ett sätt att göra det är att ha 1 poäng till nästa, och sedan har hornspunkten till 1. Eller du kan göra ungefär som tillfällig lagring, som jag talade om. 

Men omtilldelning din pekare i rätt ordning kommer att bli mycket, mycket viktigt att detta pset. Annars kommer du att få en hash bord eller ett försök som bara kommer att bli endast en del av de ord som du vill ha och sedan you're-- mmhmm? PUBLIK: Vad var det tillfälliga förvarings sak du pratade om? SPEAKER 1: Den tillfälliga förvaringen. Så i princip en annan sätt du kan göra detta är lagra huvudet av något, som lagra den för temporär variabel. Tilldela den till 1 och sedan uppdatera 1 till punkt till vad huvudet används för att peka på. På detta sätt är uppenbarligen mer elegant eftersom du behöver inte en tillfällig värde, men bara erbjuda ett annat sätt att göra det. Och vi faktiskt har lite kod för detta. Så för länkad lista, vi faktiskt har någon kod. Så sätt in här, detta är prepending. Så det här går den i spetsen. 

Så första måste du skapa ditt nya noden, naturligtvis, och kontrollera NULL. Alltid bra. Och sedan måste du tilldela värdena. När du skapar en ny nod, du vet inte vad den pekar på nästa, så du vill initiera den till null. Om den gör det i slutändan pekar på något annars, det blir omplacerad och det är bra. Om det är det första i listan, behöver den att peka på NULL eftersom det är slutet på listan. 

Så då att infoga det ser vi här vi tilldelar nästa värdet av vår nod att vara vad huvudet, vilket är vad vi hade här. Det är vad vi just gjorde. Och då kommer vi att tilldela huvud till punkt till vår nya noden, eftersom kom ihåg, ny är några pekare till en nod, och det är precis vad chefen är. Det är just därför vi har denna pil åtkomst. Cool? Mmhmm? 

PUBLIK: Har vi till initiera ny bredvid NULL först, eller kan vi bara initiera den till huvudet? 

SPEAKER 1: Ny nästa måste vara NULL för att börja eftersom du inte vet där det kommer att bli. Dessutom är denna typ av precis som ett paradigm. Du anger det lika med NULL bara för att göra Se till att alla dina grunder omfattas innan du gör något omfördelning så att du är alltid garanterad att det kommer peka till ett specifikt värde kontra som en skräp värde. Därför att, ja, vi tilldelar nya nästa automatiskt men det är mer bara som en god praxis att initiera den på det sättet och sedan tilldela. 

OK, så dubbelt länkade listor nu. Vad tycker vi? Vad är annorlunda med dubbelt länkade listor? 

Så i våra länkade listor, kan vi endast röra sig i en riktning, eller hur? Vi har bara nästa. Vi kan bara gå framåt. 

Med en dubbellänkad lista, Vi kan också gå bakåt. Så vi har inte bara nummer som vi vill lagra, Vi har då det pekar på nästa och där vi bara kom från. Så detta möjliggör vissa bättre traverse. 

Så dubbelt länkade noder, mycket lika, eller hur? Enda skillnaden är nu vi har en annan och tidigare. Det är den enda skillnaden. 

Så om vi skulle infoga före eller append-- vi inte har någon kod för detta upp här-- men om du skulle försöka för in den, det viktiga är du måste göra att du tilldelar både tidigare och din nästa pekaren på rätt sätt. Så i detta fall, skulle du inte bara initiera nästa, du initierar tidigare. Om vi ​​är i toppen av listan, vi skulle inte bara göra huvudet lika nytt, men vår nya tidigare bör peka på huvudet, eller hur? 

Det är den enda skillnaden. Och om du vill ha mer praktik med dessa med länkade listor, med insättning, med att ta bort, med insats i en blandad lista, behaga kontrollen ut study.cs50.net. Det finns en massa bra övningar. Jag rekommenderar dem. Jag önskar att vi hade tid att gå igenom dem men det finns en hel del datastrukturer att få igenom. 

OK, så hashtabeller. Detta är förmodligen den mest användbar bit för din pset här eftersom du kommer att bli genomföra en av dessa, eller ett försök. Jag gillar verkligen hashtabeller. De är ganska cool. 

Så i princip vad händer är en hashtabell är när vi verkligen behöver snabb insättning, radering och sökning. Det är dessa saker som vi är prioritering i en hashtabell. De kan bli ganska stora, men som vi ser med försök, Det finns saker som är mycket större. 

Men i grund och botten, alla en hash tabell är en hash-funktion som talar om vilken hink att sätta varje dina data, alla dina element i. Ett enkelt sätt att tänka på en hashtabell är att det är bara hinkar med saker, rätt? Så när du sorterar saker med som den första bokstaven i deras namn, det är ungefär som en hashtabell. 

Så om jag skulle grupp ni är i grupper om vem namn börjar med A över här, eller vem är födelsedag är i januari, februari, mars, vad som helst, är att på ett effektivt sätt skapa en hash-tabell. Det är bara att skapa hinkar som du sortera element i så att du kan hitta dem lättare. Så det här sättet när jag behöver att hitta en av er, Jag behöver inte söka genom var och en av era namn. Jag kan vara som, åh, jag vet att Dani födelsedag är in-- PUBLIK: --April. TALARE 1: April. Så jag tittar på mitt april hink, och med lite tur, hon ska vara den enda i det och min tid var konstant i den meningen, medan om jag måste titta genom en hel massa människor, det kommer att ta mycket längre tid. Så hashtabeller är egentligen bara hinkar. Enkelt sätt att tänka på dem. 

Så en mycket viktig sak om en hash-tabell är en hashfunktion. Så de saker som jag just talat om, liksom din första bokstaven i ditt förnamn eller din födelsedag månad, dessa är idéer som verkligen korrelerar till en hashfunktion. Det är bara ett sätt att avgöra vilken hink du är elementet går in, OK? Så för denna pset, kan du slå upp ganska mycket hash funktion du vill. 

Behöver inte vara din egen. Det finns några riktigt coola och kära ut det som gör alla möjliga galna matte. Och om du vill göra din stavningskontrollen supersnabb, Jag skulle definitivt titta in i en av dem. 

Men det finns också de enkla sådana, som compute summan av de ord, som Varje bokstav har ett nummer. Beräkna summan. Som bestämmer skopan. De har också de enkla de som är precis som alla av A: s här, alla B är här. Någon av dem. 

I grund och botten, bara säger det dig som fältindex ditt element ska gå in. Bara beslut om bucket-- Det är allt en hashfunktion är. Så här har vi ett exempel som är bara den första bokstaven i strängen som jag just talade om. 

Så du har lite hash det är bara första bokstaven i din sträng minus A, vilket kommer att ge dig några tal mellan 0 och 25. Och vad du vill göra är att se till att detta är storleken på din hash table-- hur många hinkar finns. Med många av dessa hashfunktioner, de är kommer att åter värden som kanske vara långt över det antal hinkar att du faktiskt har i din hashtabell, så du måste göra säker och mod av dem. Annars kommer det att säga, Åh, bör det vara i skopan 5000 men du har bara 30 hinkar i din hashtabell. Och naturligtvis, vi vet alla att det är kommer att resultera i några galna misstag. Så se till mod av storleken på hash-tabellen. Cool. Så kollisioner. Är alla bra så här långt? Mmhmm? 

PUBLIK: Varför skulle det returnera sådan massiv värde? 

TALARE 1: Beroende på algoritmen att din hashfunktion används. Några av dem kommer att göra galet multiplikation. Och det handlar om att få en jämn fördelning, så de gör några riktigt galna saker ibland. Det är allt. Något annat? OK. 

Så kollisioner. I grund och botten, som jag sade tidigare, i bästa fall, varje hink jag ser in är kommer att ha en sak, så jag behöver inte titta på alla, eller hur? Jag antingen vet att det är där eller är det inte, och det är vad vi verkligen vill. Men om vi har tiotusentals datapunkter och mindre än det antal av skopor, vi kommer att ha kollisioner där småningom något kommer att behöva hamna i en skopa som redan har ett element. 

Så frågan är, vad gör vi i så fall? Vad gör vi? Vi har redan något där? Får vi bara kasta ut? 

Nej. Vi måste hålla dem båda. Så det sätt som vi brukar göra som är vad? Vad är datastrukturen vi bara pratade om? Publik: Länkad lista. TALARE 1: En länkad lista. Så nu, istället för var och en av dessa hinkar bara ha ett element, det kommer att innehålla en länkad lista med de element som hash in i den. OK, gör alla slags får den idén? Eftersom vi inte kunde ha en array eftersom vi inte vet hur många saker kommer att vara där. En länkad lista, tillåter oss att bara det exakta antalet som är hashas i hinken, eller hur? 

Så linjär avkänningsriktningen är i grund och botten detta idea-- Det är ett sätt att ta itu med en kollision. Vad du kan göra är om, i det här fall var berry hashed in 1 och vi har redan något där, du bara fortsätt tills du hittar en tom plats. Det är ett sätt att hantera det. Det andra sättet att hantera det är med vad vi just called-- den länkade lista kallas chaining. 

Så denna idé fungerar om ditt hashtabell du tror är mycket större än dina data inställt eller om du vill försöka minimera kedja tills det är absolut nödvändigt. Så en sak är linjär sondering naturligtvis innebär att din hashfunktion är inte riktigt lika användbar eftersom du kommer att sluta med din hashfunktion, att komma till en punkt, Du linjär sond ner till någon plats som är tillgänglig. Men nu, naturligtvis, något annat som hamnar där, du kommer att behöva söka ännu längre ner. 

Och det finns mycket mer Sök kostnad som går in i inmatning av ett element i hashtabell nu, eller hur? Och nu när du går och försöka hitta berry igen, du kommer att hash det, och det kommer att säga, åh, titta i hink 1, och det kommer inte att vara i skopan 1, så du är kommer att behöva korsa genom resten av dessa. Så det är ibland användbart, men i de flesta fall, vi kommer att säga att kedja är vad du vill göra. 

Så vi pratade om det här tidigare. Jag fick lite före mig själv. Men kedja är i grunden att varje hink i din hashtabell är bara en länkad lista. 

Så ett annat sätt, eller mer teknisk sätt att tänka på en hashtabell är att det är bara en array av länkade listor, vilket När du skriver din ordlista och du försöker ladda den, tänker på det som en matris av länkade listor kommer att göra det mycket lättare för dig att initiera. 

PUBLIK: Så hashtabell har en förutbestämd storlek, som en [OHÖRBAR] av skopor? 

TALARE 1: Rätt. Så det finns ett visst antal hinkar som du determine-- som ni bör tveka inte att leka med. Det kan vara ganska cool för att se vad som händer när du ändrar ditt antal hinkar. Men ja, den har en ange antal hinkar. Vad gör att du kan passa som många element som du behöver är det separat kedja där du har kopplat listor i varje hink. Det innebär att din hashtabell kommer att vara exakt storlek att du behöver det vara, eller hur? Det är hela poängen med länkade listor. Cool. 

Så alla OK där? Okej. Ah. Vad var det som hände? Verkligen nu. Gissa någon dödar mig. 

OK vi ska gå in i försök, som är lite galen. Jag gillar hashtabeller. Jag tycker de är riktigt coola. Försöker är cool också. 

Så är det någon som kommer ihåg vad ett försök är? Du bör ha gått över det kort i föreläsning? Kommer du ihåg typ hur det fungerar? PUBLIK: Jag bara nickar att vi gick över den. TALARE 1: Vi gå över den. OK, vi verkligen kommer att gå över det nu är vad vi säger. 

PUBLIK: Det är för en hämtning träd. 

TALARE 1: Ja. Det är en hämtningsträd. Grymt. Så en sak att notera här är att vi tittar på enskilda tecken här, eller hur? 

Så innan vår hashfunktion, vi letade på orden som helhet, och nu tittar vi mer på karaktärerna, eller hur? Så vi har Maxwell hit och Mendel. Så i princip en try-- ett sätt att tänka om detta är att varje nivå här är en samling av bokstäver. Så det här är din rotnoden här, eller hur? Detta har alla tecknen i alfabet för starten av varje ord. 

Och vad du vill göra är att säg, OK, har vi några M-ord. Vi kommer att leta efter Maxwell, så vi går till M. Och M pekar på ett helt andra en matris där varje ord, så länge som det är ett ord som har en som den andra bokstaven, så länge det finns ett ord som har B som den andra bokstaven, det kommer att ha en pekare gå till några nästa array. 

Det finns förmodligen inte en ord som MP någonting, så i P-läget i denna array, skulle det bara vara NULL. Det skulle säga, OK, finns det inget ord som har M, följt av ett P, OK? Så om vi tänker på det, varje en av dessa mindre saker är faktiskt en av dessa stora matriser från A till Z. Så vad kan vara en av de saker det är lite av en nackdel med ett försök? 

PUBLIK: En mycket minne. 

TALARE 1: Det finns massor av minne, eller hur? Var och en av dessa block här representerar 26 platser, 26 elementgrupp. Så försöker få oerhört rymd tung. 

Men de är mycket snabba. Så otroligt snabbt, men verkligen utrymmet ineffektivt. Typ av måste lista ut vilken du vill. Dessa är riktigt coolt för din pset, men de tar upp mycket minne, så du handlar av. Yeah? 

PUBLIK: Skulle det vara möjligt att upprätta ett försök och sedan när du har all data i det att du need-- Jag vet inte om det skulle vara meningsfullt. Jag var att bli av med alla de NULL tecken, men sedan du skulle inte kunna index them-- 

TALARE 1: Du behöver dem fortfarande. 

Publik: - på samma sätt varje gång. TALARE 1: Ja. Du behöver NULL tecken för att låta du vet om det finns inte ett ord där. Ben hade du något du vill? OK. Okej, så vi kommer att gå lite mer in i tekniska detaljer bakom ett försök och arbeta igenom ett exempel. 

OK, så det här är samma sak. Medan det i en länkad lista, våran typ of-- vad är ordet jag vill? - som att bygga kvarter var en nod. I ett försök, har vi också en nod, men det definieras olika. 

Så vi har några bool som representerar huruvida ett ord faktiskt existerar på den här platsen, och sedan vi har några array här-- eller snarare, detta är en pekare till en matris med 27 tecken. Och detta är för, i det här fallet, det här 27-- Jag är säker på att ni alla är som, vänta, Det finns 26 bokstäver i alfabetet. Varför har vi har 27? 

Så beroende på hur du genomföra detta, Detta är från en pset som tillåts för apostrofer. Så det är därför den förstnämnda. Du har även i vissa fall null terminator ingår som en av tecken som det är tillåtet att vara, och det är hur de kontrollerar se om det är i slutet av ordet. Om du är intresserad, kolla in Kevins video på study.cs50, samt Wikipedia har några bra resurser där. 

Men vi kommer att gå igenom bara typ på hur du kan arbeta igenom ett försök om du fick en. Så vi har en super enkel här att har orden "bat" och "Zoom" i dem. Och som vi ser här uppe, detta lilla utrymme här representerar vår bool som säger, ja, detta är ett ord. Och då detta är vår arrayer av tecken, eller hur? 

Så vi kommer att gå igenom finna "bat" i detta försök. Så börjar i toppen, eller hur? Och vi vet att B motsvarar det andra indexet, det andra elementet i denna matris, för a och b. Så att ungefär den andra en. 

Och den säger, OK, coola, följer det till nästa array, för om vi kommer ihåg, Det är inte så att var och en av dessa faktiskt innehåller elementet. Var och en av dessa matriser innehåller en pekare, eller hur? Det är en viktig distinktion att göra. 

Jag vet att detta kommer att be-- försök är verkligen svårt att komma på första gången, så även om detta är den andra eller tredje gången och det är fortfarande snäll att verka svårt, Jag lovar, om du går klockan kort igen i morgon, Det kommer nog göra mycket mer känsla. Det krävs mycket för att smälta. Jag fortfarande ibland är liknande, vänta, vad är ett försök? Hur använder jag detta? 

Så vi har b i det här fallet, vilket är vår andra indexet. Om vi ​​hade, säg, c eller d eller någon annan bokstav, Vi måste kartlägga det tillbaka till index av vår matris som som motsvarar. Så vi skulle ta ut rchar och vi bara subtrahera bort en för att kartlägga den till 0-25. Alla bra hur vi kart våra karaktärer? OK. 

Så vi går till den andra, och vi se att, ja, det är inte NULL. Vi kan gå vidare till detta nästa samling. Så vi går vidare till detta nästa samling här. 

Och vi säger, OK, nu har vi måste se om en är här. Är A null eller gör det faktiskt gå framåt? Så en faktiskt rör sig framåt i denna samling. Och vi säger, OK, är t vår sista bokstaven. Så vi går till t vid index. Och då kommer vi gå vidare eftersom det finns en till. Och den här säger i princip att, ja, den säger att det är ett ord här-- att om du följer detta väg, har du kommit på ett ord, som vi vet är "bat". Ja? 

PUBLIK: Är det standard att ha det som index 0 och sedan ha en slags vid 1 eller att ha i slutet? 

SPEAKER 1: Nej. Så om vi ser tillbaka på vår förklaring här, det är en bool, så det är en egen del i din nod. Så det är inte en del av matrisen. Cool. Så när vi avslutar vårt ord och vi är vid denna array, vad vi vill göra är göra en kontroll för detta är ett ord. Och i detta fall, skulle det gå tillbaka ja. 

Så på denna anmärkning, vi vet att "zoo" - vi känner som människor att "zoo" är ett ord, rätt? Men är prova här skulle säga, nej, det är inte. Och det skulle säga att eftersom vi har inte utsett det som ett ord här. Även om vi kan passera fram till denna matris, Detta försök skulle säga att, nej, Djurparken är inte i din ordlista för vi har inte utsett den som sådan. 

Så ett sätt att göra that-- Åh, förlåt, här. Så i detta fall, är inte "zoo" ett ord, men det ligger i vårt försök. Men i den här, säger vi vill ha det införa ordet "bath", vad händer är vi följer through-- b, a, t. Vi är i denna matris, och Vi går för att söka efter h. 

I detta fall, när vi titta på pekaren på h, det pekar på NULL, OK? Så om det inte är uttryckligen pekar på en annan matris, du antar att alla pekare i denna array pekar på null. Så i detta fall, är h pekar till null så vi kan inte göra någonting, så det skulle också återvända falskt, "bad" är inte här. Så nu är vi faktiskt kommer att gå igenom hur skulle vi faktiskt säga att "zoo" är i vårt försök. Hur vi sätter "zoo" i vårt försök? Så på samma sätt som vi började med vår länkad lista, börjar vi vid roten. När du är osäker börjar på roten av dessa saker. 

Och vi säger, OK, z. z finns i detta, och det gör det. Så du går vidare till nästa array, OK? Och sedan på nästa, vi säger, OK, gör o existerar? Det gör det. Detta igen. 

Och så på vår nästa, har vi sagt, OK, finns "zoo" redan här. Allt vi behöver göra är att ställa in detta lika till true, att det finns ett ord där. Om du hade följt allt fram till innan den punkten, det är ett ord, så bara ställa in den lika med sådant. Ja? 

PUBLIK: Så då gör det innebär att "ba" är ett ord också? 

SPEAKER 1: Nej. Så i detta fall, "ba" vi skulle få här, skulle vi säga är det ett ord, och det skulle fortfarande inte finnas något. OK? Mmhmm? 

PUBLIK: Så när du är det en ord och du säger ja, då är det kommer att innehålla för att gå till m? 

TALARE 1: Så det här har att göra with-- du läser detta. Du säger "zoo" är ett ord. När du går till check-- liknande, säger du vill säga, existerar "zoo" i denna ordbok? Du kommer bara att söka efter "zoo" och sedan kontrollera om det är ett ord. Du kommer aldrig att flytta fram till m för det är inte vad du letar efter. 

Så om vi verkligen ville lägg till "bath" i detta försök, vi skulle göra samma sak som vi gjorde med "zoo" utom vi skulle se att när vi försöka få till h, existerar det inte. Så du kan se det som att försöka att lägga till en ny nod i en länkad lista, så vi skulle behöva lägga till ytterligare en av dessa matriser, som så. Och vad vi gör är att vi bara ställa in h element i denna array som pekar på detta. 

Och vad skulle vi vilja göra här? Lägg det lika med sant eftersom det är ett ord. Cool. Jag vet. Försöker inte den mest spännande. Tro mig, jag vet. 

Så en sak att inse med försök, Jag sa, de är mycket effektiva. Så vi har sett de tar upp massor av utrymme. De är typ av förvirrande. Så varför skulle vi någonsin använda dessa? Vi använder dessa eftersom de är otroligt effektiv. 

Så om du någonsin ser upp ett ord, är du bara som begränsas av längden av ordet. Så om du letar efter en ord som har längden fem, du alltid bara kommer att behöva gör högst fem jämförelser, OK? Så det gör det i stort sett konstant. Liksom insättning och uppslag är i stort sett konstant tid. 

Så om du någonsin kan få något i konstant tid, det är så bra som det blir. Du kan inte få bättre än konstant tid för dessa saker. Så det är en av de stora plus i försök. 

Men det är en hel del utrymme. Så du slags måste bestämma vad är viktigast för dig. Och på dagens datorer, utrymme som ett försök kan ta upp kanske inte påverkar dig så mycket, men kanske du arbetar med något som har långt, långt fler saker, och ett försök är helt enkelt inte rimligt. Ja? 

PUBLIK: Vänta, så du har 26 bokstäver i varenda en? 

TALARE 1: Mmhmm. Ja, du har 26. Du har en del är ordet markör och sedan du har 26 pekare i var och en. Och de point-- 

PUBLIK: Och varje 26, tror de har var 26? 

TALARE 1: Ja. Och det är därför, som du kan se, den expanderar ganska snabbt. Okej. Så vi kommer att få in i träd, som Jag känner för är lättare och kommer förmodligen vara en trevlig liten uppskov från försök där. Så förhoppningsvis de flesta av er har sett ett träd förut. Inte som den vackra de utanför, som jag vet inte om någon gick utomhus nyligen. Jag gick apple plocka i helgen, och Åh min Jisses, det var vackert. Jag visste inte blad skulle kunna se ut som söt. 

Så det här är bara ett träd, eller hur? Det är bara några nod, och det pekar på ett gäng andra noder. Som du ser här, är detta typ av ett återkommande tema. Noderna pekar på noder är typ av kärnan i många datastrukturer. Det beror bara på hur vi har dem pekar på varandra och hur vi färdas genom dem och hur vi infoga saker som avgör deras olika egenskaper. 

Så bara några terminologi, som jag har använt tidigare. Så rot är det som är högst upp. Det är där vi alltid börja. Du kan se det som huvudet också. Men för träd, tenderar vi att hänvisa till det som roten. 

Någonting vid botten här-- på mycket, mycket bottom-- ANSES blad. Så det går tillsammans med hela träd sak, eller hur? Bladen är i kanterna av ditt träd. 

Och då har vi också ett par termer för att tala om noder i förhållande till varandra. Så vi har förälder, barn och syskon. Så i detta fall, är tre av förälder till 5, 6 och 7. Så föräldern är det som är ett steg över vad du är hänvisar till, så det är bara som ett släktträd. Förhoppningsvis är detta alla lite lite mer intuitivt än försöker. 

Syskon är något som har samma förälder, eller hur? De är på samma nivå här. Och sedan, när jag var säger, barn är bara vad är ett steg lägre noden i fråga, OK? Cool. Så ett binärt träd. Kan någon gissa på en av egenskaperna hos det binära trädet? 

Publik: Max två blad. 

TALARE 1: Rätt. Så max två blad. Så i det här innan, hade vi här som hade tre, men i ett binärt träd, du har en max två barn per förälder, eller hur? Det finns en annan intressant egenskap. Är det någon som vet det? Binärt träd. 

Så ett binärt träd har allt på the-- här är inte sorted-- men i ett sorterat binärt träd, allt till höger är större än den överordnade, och allt till vänster är mindre än den överordnade. Och det har varit en frågesport frågan innan, så bra att veta. Så hur vi definierar det, igen, vi har en annan nod. Detta ser mycket liknar vad? Dubbelt 

Publik: Linked listor 

TALARE 1: En dubbel länkad lista, eller hur? Så om vi byter ut med föregående och nästa, detta skulle vara en dubbellänkad lista. Men i det här fallet, vi faktiskt har vänster och höger och det är det. Annars är det exakt samma. Vi har fortfarande elementet du är ute efter, och du bara har två pekare gå till vad som kommer härnäst. Ja, så binärt sökträd. Om vi ​​märker, allt på här är större than-- eller allt omedelbart till höger här är större än, allt här är mindre än. 

Så om vi skulle söka igenom, det bör se mycket nära binär sökning här, eller hur? Utom istället för att titta vid halv arrayen, vi bara titta på antingen vänster sidan eller den högra sidan av trädet. Så det blir lite enklare, tror jag. 

Så om din rot är NULL, uppenbarligen är det bara falskt. Och om den finns där, det är naturligtvis sant. Om det är mindre än söker vi vänster. Om det är större än, vi söker rätt. Det är precis som binär sökning, bara en annan datastruktur att vi använder. I stället för en matris, det är bara ett binärt träd. 

OK, stackar. Och dessutom ser det ut som vi kanske har lite tid. Om vi ​​gör det, jag är glad att gå över någon av detta igen. OK, så stackar. Kommer någon ihåg vad stacks-- alla kännetecken på en stapel? 

OK, så de flesta av oss, tror jag, äta i matsalen halls-- så mycket som vi kanske inte vill. Men självklart kan du komma på en stapel bokstavligen bara som en stapel av brickor eller en stapel av saker. Och vad som är viktigt att inse är att det är something-- den karaktäristiska som vi kallar det by-- är LIFO. Vet någon vad det står för? Mmhmm? 

PUBLIK: Sist in, först ut. 

TALARE 1: Rätt, sist in, först ut. Så om vi vet, om vi stapla saker upp till det lättaste greppa off-- och kanske det enda vi kan ta av om vår stack är stor enough-- är att toppelementet. Så vad lades på last-- som vi ser här, oavsett sköts på mest recently-- är kommer att bli den första sak som vi lossna, OK? 

Så vad vi har här är annan typedef struct. Detta är verkligen precis som en snabbkurs i datastrukturen, så det finns en hel del kastas på er. Jag vet. Så ännu en struct. Yay för strukturer. 

Och i det här fallet, det är en del pekare till en matris som har en viss kapacitet. Så detta är vår stack Här, liksom våra faktiska array som är hållande våra element. Och så här har vi några storlek. 

Och typiskt, vill du behålla reda på hur stor din stack är eftersom det som det kommer att göra det möjligt dig att göra är om du vet storleken, Det gör att du kan säga, OK, jag är på kapacitet? Kan jag lägga till något mer? Och det berättar också där toppen av din stack är så att du vet vad du kan faktiskt ta av. Och det är faktiskt kommer att vara lite mer tydlig här. 

Så för push, en sak, om du någonsin skulle genomföra skjuta, som jag säger bara, din stack har en begränsad storlek, eller hur? Vår samling hade viss kapacitet. Det är en matris. Det är en fast storlek, så vi måste se till att vi inte är att sätta mer in i vårt utbud än vi faktiskt har plats för. 

Så när du skapar en push funktion, det första du gör är att säga, OK, har jag utrymme i min stack? För om jag inte gör det, ledsen, Jag kan inte lagra ditt element. Om jag gör det, då du vill spara det högst upp i stacken, eller hur? 

Och det är därför vi har att hålla reda på vår storlek. Om vi ​​inte hålla reda på vår storlek, vi vet inte var de ska uttrycka det. Vi vet inte hur många saker är i vår array redan. Som uppenbarligen finns det sätt att kanske du kunde göra det. Du kan initiera allt till NULL och sedan söka efter den senaste NULL, men en mycket enklare sak är bara säga, OK, hålla reda på storlek. Som jag vet att jag har fyra element i min samling, så nästa sak att vi sätter på, vi är kommer att lagra åtmin index 4. Och sedan, naturligtvis, innebär detta att du lyckas har drivit något på din stack, du vill öka storleken så att du vet var du är så att du kan skjuta fler saker på. 

Så om vi försöker pop något utanför stacken, vad som kan vara det första att vi vill kontrollera? Du försöker ta något av din stack. Är du säker på att det finns något i din stack? Nej. Så vad kan vi vill kontrollera? 

PUBLIK: [OHÖRBAR]. SPEAKER 1: Kontrollera om storleken? Storlek. Så vi vill kontrollera om vår storlek är större än 0, OK? Och om det är så vi vill minska vår storlek med 0 och returnera det. Varför? 

I det första en var vi skjuta, vi drivit det på storlek och uppdateras sedan storlek. I det här fallet, vi nedräkna storlek och sedan ta bort det, plocka det från vår samling. Varför skulle vi göra det? Så om jag har en sak på min stack, vad som skulle vara min storlek på den punkten? 1. 

Och där elementet 1 lagras? Vid vilken index? PUBLIK: 0. TALARE 1: 0. Så i detta fall, vi alltid måste göra sure-- stället för att återvända storlek minus 1, eftersom vi vet att vårt inslag är kommer att förvaras i en mindre oavsett vår storlek är, detta bara tar hand om det. Det är en något mer elegant sätt. Och vi stega bara vår storlek och sedan återvända storlek. Mmhmm? 

PUBLIK: Jag antar att bara i allmänhet, varför skulle denna datastruktur vara till nytta? 

TALARE 1: Det beror på din bakgrund. Så för en del av den teori, om du arbetar with-- OK, Låt mig se om det finns en positiv man som gynnar mer än utanför CS. Med stackar, helst du behöver att hålla reda på något som Den senast tillagda är när du kommer att vilja använda en stack. 

Och jag kan inte tänka mig en bra exempel på det just nu. Men när den senaste sak är viktigast för dig, det är då en stapel kommer att vara till nytta. Jag försöker tänka om det finns en god man för detta. Om jag tänker på ett gott exempel i nästa 20 minuter, kommer jag definitivt att berätta. 

Men totalt sett, om det finns något, som sagt mest, där senaste är det viktigaste, det är där en stapel kommer in. Medan köerna är typ av det motsatta. Och alla de små hundarna. Är inte detta stora, eller hur? Jag känner att jag borde bara ha en kanin video rätt i mitten av avsnitt för er eftersom detta är en intensiv sektion. 

Så en kö. I grund och botten en kö är som en linje. Ni killar jag är säker på att använda detta varje dag, precis som i våra matsalar. Så vi måste gå in och få våra brickor, jag är att du har att vänta i rad att svepa eller få din mat. 

Så skillnaden här är att detta är FIFO. Så om LIFO senast var i första ut, är FIFO först in, först ut. Så det är här vad du sätter På första är din viktigaste. Så om du väntade i en line-- kan du tänk om du gick till gå och hämta den nya iPhone och det var en stack där sista personen i kön fick det första, människor skulle döda varandra. 

Så FIFO, vi är alla väl förtrogna med i den verkliga världen här, och det hela har att göra med faktiskt slags återskapa hela denna linje och köande struktur. Så medan med stapeln, Vi har tryck och pop. Med en kö, vi har enqueue och dequeue. Så enqueue princip innebär lägga den på ryggen, och dequeue medel ta bort från framsidan. Så vår datastruktur är en lite mer komplicerat. Vi har en andra sak att hålla reda på. 

Så utan huvud, detta är exakt en bunt, eller hur? Detta är samma struktur som en stapel. Det enda som skiljer nu är att vi har detta huvud, vilket vad tror du kommer att hålla reda på? 

Publik: Det första en. 

TALARE 1: Rätt, det första som vi lägger in. Chefen för vår kö. Den som är först i kön. Okej, så om vi gör enqueue. Återigen, med någon av dessa datastrukturer, eftersom vi har att göra med en array, Vi måste kontrollera om vi har utrymme. 

Det är ungefär som jag berättar ni, om du öppnar en fil, du måste kontrollera för null. Med någon av dessa staplar och köer, behöver du för att se om det finns utrymme för att vi är att göra med en storlek array fast, som vi ser här-- 0, 1 alla upp till 5. Så vad vi gör i så fall är kontrollen för att se om vi fortfarande har utrymme. Är vår storlek mindre än kapaciteten? 

Om så är fallet, måste vi lagra den på svansen och vi uppdaterar vår storlek. Så vad kan svansen vara i det här fallet? Det är inte tydligt utskrivet. Hur skulle vi förvara det? Vad skulle svansen vara? 

Så låt oss gå igenom det här exemplet. Så detta är en matris med storlek 6, eller hur? Och vi har just nu är 5 vår storlek. Och när vi lägger den i, det kommer att gå in i den femte index, eller hur? Så spara på svansen. 

Ett annat sätt att skriva svans skulle bara vara vår samling vid index av storlek, eller hur? Detta är storlek 5. Nästa sak kommer att gå in i 5. Cool? OK. Det blir lite mer komplicerat när vi börjar jävlas med huvudet. Ja? 

PUBLIK: Betyder det att vi skulle ha förklarat en array som var fem elementen lång och då vi lägger in den? 

SPEAKER 1: Nej. Så i detta fall, är detta en stapel. Detta skulle förklaras som en array av storlek 6. Och i det här fallet, vi bara har en plats kvar. 

OK, så en sak är i detta fall, om huvudet är vid 0, då vi bara kan lägga till den i storlek. Men det blir lite svårare eftersom det faktiskt, de har inte en slid för detta, så jag kommer att dra en eftersom det inte är riktigt så enkelt när du börja att bli av med saker. Så medan med en stack du alltid bara har oroa sig för vad storleken är När du lägger till något på, med en kö som du också måste göra Se till att ditt huvud redovisas, eftersom en cool sak om köer är att om du inte är på kapacitet, du faktiskt kan göra det linda runt. 

OK, så en thing-- oh, Detta är fruktansvärt krita. En sak att tänka på är fallet. Vi ska bara göra fem. OK, så vi kommer att säger chefen är här. Detta är 0, 1, 2, 3, 4. 

Huvudet är där, och vänligen ha saker i dem. Och vi vill lägga till något i, eller hur? Så det som vi måste vet är att huvudet är alltid kommer att flytta på detta sätt och sedan slinga tillbaka runt, OK? 

Så denna kö har plats, eller hur? Den har plats i början, typ av motsatsen till detta. Så vad vi behöver göra är att vi behöva beräkna svansen. Om du vet att din huvudet har inte flyttat, svans är bara din samling på index för den storleken. 

Men i verkligheten, om du använder en kö, huvudet är antagligen uppdateras. Så vad du behöver göra är faktiskt räkna svansen. Så vad vi gör är denna formel här, som jag kommer att låta dig killar tycker om, och då vi ska prata om det. Så det här är kapacitet. 

Så detta kommer faktiskt ge dig ett sätt att göra det. För i så fall vad? Vår huvud är på 1, är vår storlek 4. Om vi ​​mod att med 5, får vi 0, som är där vi ska mata in den. 

Så sedan i nästa fall, om vi skulle göra det, vi säger, OK, låt oss avköa något. Vi avköa detta. Vi tar ut detta element, eller hur? 

Och nu vårt huvud pekar här, och vi vill lägga in en annan sak. Detta är i princip baksidan av vår linje, eller hur? Köer kan linda runt arrayen. Det är en av de viktigaste skillnaderna. Stacks, du kan inte göra det här. 

Med köer, kan du eftersom allt som betyder något är att du vet vad senast var lagt. Eftersom allt kommer att läggas till i denna riktning åt vänster, i detta fall, och sedan linda runt, kan du fortsätta att sätta in nya element på framsidan av matrisen eftersom det inte är riktigt framsidan av matrisen längre. Du kan tänka på i början av array som var huvudet faktiskt är. 

Så denna formel är hur du beräknar din svans. Är det vettigt? OK. OK, dequeue, och sedan ni har 10 minuter att ställa några klargörande frågor mig du vill, för jag vet att det är galet. 

Okej, så i samma way-- Jag vet inte om ni har märkt, men CS handlar om mönster. Saker och ting är ganska mycket Samma, bara med små tweaks. Så samma sak här. Vi måste kontrollera för att se om vi faktiskt har något i vår kö, eller hur? Säg, OK, är vår storlek större än 0? Cool. 

Om vi ​​gör det kommer vi flytta vårt huvud, vilket är vad jag just visat här. Vi uppdaterar våra huvuden för att vara en till. Och då är vi dekrementera vår storlek och returnera elementet. 

Det finns mycket mer konkret kod på study.cs50.net, och jag rekommenderar starkt kommer igenom det om du har tid, även om det bara är en pseudo-kod. Och om ni vill prata igenom att med mig en på en, låt mig vet. Jag skulle gärna. Datastrukturer, om du tar CS 124, du ska vet att datastrukturer blir mycket roligt och det är bara början. 

Så jag vet att det är svårt. Det är OK. Vi kämpar. Jag gör fortfarande. Så oroa dig inte för mycket om det. 

Men det är i grunden din snabbkurs i datastrukturer. Jag vet att det är en hel del. Finns det något som vi skulle vilja gå igen? Allt vi vill prata igenom? Ja? 

Publik: För detta exempel, så den nya svansen är vid 0 över det? TALARE 1: Ja. PUBLIK: OK. Så då går igenom, du skulle ha 1 plus 4 eller-- 

TALARE 1: Så du sa, när vi vill gå göra det igen? PUBLIK: Ja. Så om du räkna out-- var är du beräkna svansen mellan i det? 

TALARE 1: Så svansen var in-- Jag ändrade detta. Så i det här exemplet här, var detta arrayen vi tittar på, OK? Så vi har saker i en, två, tre och fyra. Så vi har vårt huvud är lika med 1 vid denna punkt, och är lika med 4 vår storlek vid denna punkt, eller hur? 

Ni är alla överens om så är fallet? Så vi gör huvudet plus storlek, vilket ger oss 5 och sedan mod vi med 5. Vi får 0, vilket säger oss att 0 är var är vår svans, där vi har utrymme. 

PUBLIK: Vad är ett tak? 

TALARE 1: Kapaciteten. Ursäkta. Så det är storleken på din array. Ja? 

PUBLIK: [OHÖRBAR] innan vi tillbaka elementet? 

TALARE 1: Så vi flyttar huvudet eller returnera ögonblicket? Så om vi flyttar en, dekrementera storlek? Håll ut. Jag glömde definitivt en annan. Glöm det. Det finns inte en annan formel. Ja, skulle du vilja återvända huvudet och sedan flytta tillbaka den. 

PUBLIK: OK, eftersom det vid denna punkt, var huvudet vid 0, och sedan vill återvända index 0 och sedan göra huvud 1? 

TALARE 1: Rätt. Jag tror det finns en annan formel ungefär som det här. Jag har inte det på toppen mitt huvud som Jag vill inte ge dig fel. Men jag tror att det är helt korrekt att säg, OK, lagra denna element-- oavsett huvudets del är-- dekrementera din storlek, flytta huvudet över och retur oavsett vad det elementet är. Det är helt giltiga. OK. Jag tycker detta är inte som den most-- du inte kommer att gå ut härifrån liksom, ja, jag vet försök. Jag fick det hela. Det är OK. Jag lovar. Men datastrukturer är något som Det tar mycket tid att vänja sig. Förmodligen en av de svåraste saker, tror jag, i kursen. 

Så det definitivt tar repetition och ser at-- jag visste inte riktigt länkade listor tills jag gjorde alldeles för mycket med dem, på samma sätt som jag inte verkligen förstår pekare tills jag har haft att lära ut det för två år och göra mina egna psets med det. Det tar mycket upprepning och tid. Och så småningom kommer det slags klicka. 

Men under tiden, om du har typ av en hög nivå förståelse av vad dessa gör, deras för- och cons-- vilket är vad vi verkligen tenderar att betona, speciellt i intro kursen. Liksom, varför skulle vi använder ett försök under en array? Liksom, vad är positiva och negativ av var och en av dem? 

Och förstå avvägningar mellan var och en av dessa strukturer är det som är mycket viktigare just nu. Det kan finnas en galen fråga eller två som är kommer att be er att genomföra skjuta eller genomföra pop eller enqueue och dequeue. Men för det mesta, har det högre förståelse nivå och mer av ett intuitivt grepp är viktigare än faktiskt att kunna genomföra det. 

Det skulle vara riktigt häftigt om er alla kunde gå ut och gå att genomföra ett försök, men vi förstår att det är inte nödvändigtvis det mest rimliga sak just nu. Men du kan i ditt pset, om du vill till, och sedan får du praktik, och då kanske du kommer verkligen förstå det. Ja? 

PUBLIK: OK, så vilka som är Vi menade att användas i pset? Behöver jag använda en av dem? TALARE 1: Ja. Så du har ditt val. Jag antar att i det här fallet, kan vi tala om pset lite eftersom jag sprang genom dessa. Så i ditt pset, har du din Valet av försök eller hashtabeller. Vissa människor kommer att försöka och använda standard filter, men de är inte tekniskt korrekt. På grund av deras probabilistisk natur, de ger falska positiva ibland. De är coolt utseende till, dock. Rekommendera ute på dem åtminstone. Men du har ditt val mellan en hashtabell och ett försök. Och det kommer att bli när du laddar i din ordlista. 

Och du måste välja din hashfunktion, måste du välja hur många skopor du har, och den kommer att variera. Som om du har fler hinkar, kanske det kommer att springa snabbare. Men kanske du slösar bort en mycket utrymme på det sättet, men. Du måste räkna ut det. Mmhmm? 

PUBLIK: Du sa förut att vi kan använda andra hashfunktioner, att vi inte behöver skapa en hashfunktion? 

TALARE 1: Ja, just det. Så bokstavligen för din hashfunktion, som google "hashfunktion" och leta efter några häftiga sådana. Du förväntas inte bygga egna hashfunktioner. Människor tillbringar sin teser om dessa saker. 

Så oroa dig inte om att bygga din egen. Hitta en på nätet till att börja med. Några av dem måste du manipulera lite att se till att typer retur matcha upp och allt, så i början, Jag skulle rekommendera att använda något verkligen lätt att kanske bara hashar på den första bokstaven. Och sedan när du har att arbeta, införliva en kylare hashfunktion. Mmhmm? 

PUBLIK: Skulle ett försök att vara eller effektivt men bara svårare att, like-- 

TALARE 1: Så ett försök, tror jag, är intuitivt svårt att genomföra men är mycket snabb. Dock tar upp mer utrymme. Återigen kan man optimera både av dem som olika sätt och det finns sätt att-- PUBLIK: Hur ska vi graderad på detta? Är det matter-- 

TALARE 1: Så du graderade normalt sätt. Du kommer att graderas på design. Vilket sätt du gör, du vill se till att det är lika elegant som det kan vara och så effektivt som det kan vara. Men om du väljer ett försök eller hash bord, så länge det fungerar, vi är nöjda med. Och om du använder något som hashar på den första bokstaven, det är bra, som kanske gillar designmässigt. Vi är också når punkt i detta semester-- Jag vet inte om du killar noticed-- om du är pset kvaliteter minskar lite på grund av design och allt, det är väl bra. Det börjar bli till en punkt där din program blir mer komplicerat. Det finns fler platser du kan förbättra. 

Så det är helt normalt. Det är inte så att du är göra värre på pset. Det är bara vi vara hårdare på dig nu. Så alla är känsla det. Jag graderade bara alla dina psets. Jag vet att alla känner det. 

Så var inte orolig för det. Och om du har några frågor om tidigare psets eller sätt du kan förbättra, Jag försöker och kommentera den specifika ställen, men ibland är det för sent och jag blir trött. Finns det några andra saker om datastrukturer? Jag är säker på att ni inte riktigt vill prata om dem längre, men om det finns, jag är glad att gå över dem, liksom allt från föreläsning detta tidigare veckan eller förra veckan. 

Jag vet att förra veckan var allt recension, så vi kan ha hoppat över någon recension från föreläsning. Alla andra frågor som jag kan svara? OK, okej. Nåväl, ni får ut 15 minuter för tidigt. 

Jag hoppas att detta var halv hjälp åtminstone, och jag kommer att se er nästa vecka, eller torsdag kontorstid. Finns det begär för mellanmål för nästa vecka, det är grejen? Eftersom jag glömde godis idag. Och jag tog godis sist vecka, men det var Columbus Day, så det var som sex personer som hade fyra påsar med godis till sig själva. Jag kan ta med Starbursts igen om du vill. Starbursts? OK, låter bra. Ha en bra dag, grabbar.