>> [MUSIK SPELA]
>> ANDI PENG: Välkommen till vecka 6 i avsnitt.
Vi avvikit från vår standard avsnitt tid tisdagen
eftermiddag till denna härliga söndag morgon.
Tack för alla som anslöt sig till mig idag, men på allvar,
en applåd.
>> Det är en ganska stor ansträngning.
Jag nästan inte ens göra det i tid, men det var OK.
Så jag vet att ni alla har bara gjort det till frågesporten.
Först av allt, välkommen till den andra sidan av det.
>> För det andra kommer vi att tala om det.
Vi pratar om testet.
Vi pratar om hur du gör i klassen.
Du kommer att bli bra.
Jag har dina frågesporter för dig i slutet av här,
så om ni vill ta En titt på det, helt bra.
>> Så snabbt innan vi börjar, den agenda för idag är följande.
Som ni kan se, vi är princip snabb bränning
genom en hel del datastrukturer verkligen, verkligen, verkligen snabbt.
Så som sådant kommer det inte att vara super interaktiv idag.
Det ska bara vara mig slags skrika saker som ni, och om jag förvirra dig,
om jag går för fort, låt mig veta.
De är bara olika data strukturer, och som en del
din pset för detta kommande veckan, kommer du
bli ombedd att genomföra en av dem, kanske två av them-- två av dem
i pset.
OK, så jag ska bara börja med några tillkännagivanden.
Vi ska gå över stackar och köer mer i djup än vad vi gjorde innan testet.
Vi ska gå över kopplade listan igen, återigen,
mer ingående än vad vi hade före testet.
Och då kommer vi att tala om hash tabeller, träd och försöker, som
är alla ganska nödvändig för din pset.
Och sedan ska vi gå igenom några användbara tips för pset5.
>> OK, så quiz 0.
Den genomsnittliga var en 58%.
Det var mycket låg, och så ni alla gjorde mycket, mycket bra i enlighet
med det.
>> Ganska mycket, är tumregel om du är inom en standardavvikelse från medelvärdet
framför allt eftersom vi är i en mindre bekväma avsnitt, du är helt bra.
Du är på rätt spår.
Livet är bra.
>> Jag vet att det är skrämmande att tro att Jag fick som en 40% på det här testet.
Jag kommer att misslyckas den här klassen.
Jag lovar dig, du är inte kommer att misslyckas klassen.
Du är helt bra.
>> För er som fick över medelvärdet, imponerande, imponerande,
som, på allvar bra gjort.
Jag har dem med mig.
Känn dig fri att komma få dem i slutet av avsnittet.
Låt mig veta om du har några frågor, frågor med dem.
Om vi ​​lägger upp dina poäng fel, låt oss veta.
>> OK, så pset5, är detta ett riktigt konstig vecka för Yale i den meningen
att vår pset beror Onsdag kl inklusive
den sena dagen, så det är faktiskt teoretiskt grund tisdag kl.
Förmodligen ingen klar tisdag kl.
Det är helt bra.
Vi kommer att ha kontorstid ikväll samt måndag kväll.
Och alla avsnitten här veckan kommer faktiskt förvandlas till workshops,
så känn dig fri att pop i varje avsnitt som du vill,
och de kommer att vara slags mini-pset workshops för hjälp om det.
Så som sådan, är detta den enda avsnitt där vi undervisningsmaterial.
Alla de andra delarna kommer att fokusera uteslutande på hjälp för pset.
Ja?
>> PUBLIK: Var är kontorstid?
>> ANDI PENG: Kontorstider tonight-- oh, bra fråga.
Jag tror kontorstid ikväll är i kricka eller Commons.
Om du kolla på nätet CS50 och du går till kontorstid,
det bör finnas ett schema som berättar om alla av dem är.
>> Jag vet antingen ikväll eller i morgon är kricka,
och jag tror att vi kan ha allmänningar för andra natten.
Jag är inte säker.
Bra fråga.
Kontrollera på CS50.
>> Cool, frågor om schema för nästa som tre dagar?
Jag lovar er killar som David sagt, detta är toppen av kullen.
Ni är nästan där.
Bara tre dagar.
Dit, och sedan kommer vi alla komma ner.
Vi kommer att ha en trevlig CS-fria brytning.
Vi ska komma tillbaka.
Vi kommer att dyka in webb programmering och utveckling,
saker som är väldigt roligt jämfört till några av de andra psets.
Och det ska vara chill, och Vi kommer att ha massor av kul.
Vi kommer att ha mer godis.
Ledsen för godis.
Jag glömde godis.
Det var en tuff morgon.
Så ni är nästan där, och jag är verkligen stolt över er.
>> OK, så stackar.
Vem älskade fråga om Jack och hans kläder på frågesport?
Ingen?
OK, det är bra.
>> Så i huvudsak du kan bild Jack, den här killen här,
gillar att ta kläder ut ur toppen av stacken,
och han sätter tillbaka den på stacken efter att han har gjort.
Så på detta sätt, han aldrig verkar vara att få
till botten av den stack i hans kläder.
Så denna typ av beskriver den grundläggande datastrukturen
av hur en stapel är implementerad.
>> I huvudsak, tänk på en stapla så en stapel av föremål
var du lagt saker på toppen, och då du hoppar ut dem uppifrån.
Så LIFO är förkortningen vi gillar att use-- sist in först ut.
Och så sista i till toppen av den stack är den första som kommer ut.
Och så de två begreppen vi vill associera
med som kallas tryck och pop.
När du trycker något på stack, och du pop upp den igen.
>> Och så jag antar att detta är typ av en abstrakt begrepp för dig
som vill se som en faktiska genomförandet av detta
i den verkliga världen.
Hur många av er har skrivit en uppsats kanske som en timme innan det berodde,
och du råkat ta bort en enorm bit av det, som av misstag?
Och vad kontroll gör vi använder för att sätta tillbaka den?
Kontroll-Z, ja?
Kontroll-Z, så antalet gånger att Ctrl-Z har räddat mitt liv,
har räddat min röv, varje gång som är genomförs genom en stapel.
>> I princip all information det är på din Word-dokument,
det blir knuffade och dök efter behag.
Och så i huvudsak när du bort någonting, pop du upp den igen.
Och sedan om du behöver det igen, du driva det, vilket är vad Ctrl-C gör.
Och så verkliga världen funktion av hur enkel datastruktur
kan hjälpa till med din vardag.
>> Så en struct är det sätt som vi faktiskt skapa en stapel.
Vi skriver definiera struct, och sedan vi kallar det stack i botten.
Och inom stapeln, vi har två parametrar
att vi kan i huvudsak manipulera, så vi har röding stjärnan strängar kapacitet.
>> Allt som gör skapar en array
att vi kan lagra vad du vill som vi kan avgöra dess kapacitet.
Kapaciteten är bara max antal objekt kan vi sätta in denna uppsättning.
int storlek är den räknare som håller reda på hur många objekt finns för närvarande
i stapeln.
Så då kan vi hålla reda på, A, både hur stor själva stapeln är,
och B, hur mycket av det stack fyllde vi eftersom vi inte vill
att svämma över vad vår kapacitet är.
>> Så till exempel, denna härliga Frågan var på frågesport.
I huvudsak hur gör vi driva på toppen av en stapel.
Ganska enkelt.
Om man ser på det, Vi kommer att gå igenom det här.
Om [OHÖRBAR] size-- kom ihåg, när du
vill komma åt alla parameter inom en struct,
du gör namnet på struct.parameter.
>> I detta fall är s namnet på vår stack.
Vi vill komma åt storlek av det, så vi gör s.size.
Så länge som storleken inte är lika med kapacitet eller så länge
eftersom det är mindre än kapacitet, antingen skulle fungera här.
>> Du vill komma åt insidan av din stack, så s.strings,
och du kommer att sätta det nya numret som du vill infoga i det.
Låt oss bara säga att vi kommer att vilja infoga int n på stacken,
vi kunde göra s.strings, konsoler, är lika s.size n.
Eftersom storleken är där vi närvarande finns i stapeln
Om vi ​​ska driva det på, vi bara tillgång
varhelst storleken är, desto nuvarande fullhet av stapeln,
och vi driva int n på det.
Och sedan vill vi se till att vi också stega storlek n,
så att vi kan hålla reda på vi har lagt till en extra sak till stacken.
Nu har vi en större storlek.
Innebär detta här vettigt att alla, hur logiskt det fungerar?
Det var typ av snabb.
PUBLIK: Kan du gå över de s.stringss.strings [s.size] igen?
ANDI PENG: Visst, så vad gör s.size närvarande ge oss?
PUBLIK: Det är den nuvarande storleken.
ANDI PENG: Exakt, så nuvarande index som vår storlek är,
och så vill vi sätta nya heltal att vi vill infoga i s.size.
Betyder det vettigt?
Eftersom s.strings, allt är är namnet på uppsättningen.
Allt som är är tillgång till array inom vår struct,
och så om vi vill placera n till detta index,
vi kan bara komma åt den med byglar s.size.
Häftigt.
>> Okej, pop, jag pseudokod ut för er, men liknande koncept.
Betyder det vettigt?
Om storleken är större än noll, då du
vet att du vill ta något ut eftersom om storleken är inte
större än noll, då du har ingenting i stapeln.
>> Så du bara vill köra denna kod, kan det bara
pop om det finns något att pop.
Så om storleken är större än 0, vi minus storleken.
Vi dekrementera storlek och sedan återvända vad är inne i det eftersom
genom att poppa, vill vi tillgång oavsett lagras
i index för den överst i stacken.
Allt vettigt?
Om jag gjorde ni skriver ut det här, skulle ni kunna skriva ut det?
OK, kan ni leka med den.
Inga bekymmer om du inte får det.
Vi har inte tid att koda det idag eftersom vi har
fick en hel del av dessa strukturer att gå igenom, men i huvudsak
pseudokod, mycket, mycket likt att driva.
Bara följa logiken.
Se till att du tillgång till alla funktioner i din struct korrekt.
Ja?
>> PUBLIK: Kommer dessa bilder och Hela den här grejen upp idag-ish?
ANDI PENG: Alltid, Japp.
Jag ska försöka att sätta detta upp som en timme efter.
Jag kommer att skicka David, kommer David att försöka sätta upp som en timme efter detta.
>> OK, så då vi går in i denna andra vackra datastruktur som kallas en kö.
Som ni kan se här, en kö, för den brittiska bland oss,
allt är det är en linje.
Så till skillnad från vad du tror att en stapel är,
en kö är precis vad logiskt du tycker att det är.
Det innehas av reglerna i FIFO, som är först in, först ut.
Om du är den första ett i raden, du är
först en som kommer ut på linjen.
>> Så vad vi vill kalla detta är dequeueing och enqueueing.
Om vi ​​vill lägga till något till vår kö, köa vi.
Om vi ​​vill avköa, eller ta bort något, avköa vi.
>> Så samma sätt som vi är typ av skapa fast storlek element som vi
kan lagra vissa saker, men vi kan också
ändra där vi placerar parametrar insidan av dem
baserat på vilken typ av funktionalitet vi vill.
Så stackar, ville vi den sista en, N att vara först ut.
Kö är vi vill att första in för att vara det första ut.
>> Så struct-typ definiera, som ni kan se,
Det är lite annorlunda från vad stapeln var
eftersom inte bara vi måste hålla reda på var storleken för närvarande är,
vi vill också att hålla reda på huvudet samt där vi är idag.
Så jag tror att det är lättare om jag drar upp denna.
Så låt oss föreställa oss att vi har en kö, så låt oss säga huvudet är rätt här.
Chefen för linjen, låt oss bara säga att det är för närvarande finns,
och vi vill infoga något i kön.
Jag ska ringa storlek i huvudsak är samma sak som svans,
I slutet av vart din kö är.
Låt oss bara säga storleken är rätt här.
>> Så hur gör man rimligen infoga något i en kö?
Vad index vill vi placera där vi vill infoga i.
Om detta är början av din kö och det är i slutet av det
eller storleken på det, där vi vill lägga nästa objekt?
>> PUBLIK: [OHÖRBAR]
ANDI PENG: Just det, du vill lägga till det beroende på har du skrivit det.
Antingen är tom eller som är tom.
Så du vill lägga till det förmodligen här eftersom om storleken är--
om dessa är alla fulla, du vill till den här, eller hur?
>> Och så det är, medan mycket, mycket enkel, inte riktigt alltid korrekt
eftersom den huvudsakliga skillnaden mellan en kö och en stapel
är att kön kan faktiskt manipuleras
så att huvudet förändringar beroende på var du vill
i början av din kö för att börja.
Och som ett resultat, din svans kommer också att förändras.
Och så ta en titt på denna kod just nu.
Som ni ombads också att skriva ut på frågesport, enqueue.
Kanske ska vi prata igenom varför svaret var vad det var.
>> Jag kunde inte riktigt passar in i denna linje på en, men i huvudsak denna del av koden
ska vara på en rad.
Spendera som 30 sekunder.
Ta en titt och se varför detta är det sätt som det är.
>> Mycket, mycket liknande struct, mycket, mycket liknande struktur som den tidigare
stack utom kanske en kodrad.
Och att en kodrad bestämmer funktionaliteten.
Och det är verkligen skiljer en kö från en stapel.
>> Någon som vill ta ett knivhugg på att förklara varför du har
fick denna komplicerade sak här?
Vi ser återlämnande av vår underbar vän modul.
Som ni snart kommer att känna igen i programmering,
nästan när du behöver något att linda runt någonting,
modul kommer att vara ett sätt att göra det.
Så att veta att någon som vill att försöka förklara att kodraden?
Ja, alla svar är accepterad och välkommen.
PUBLIK: Pratar du med mig?
ANDI PENG: Ja.
Målgrupp: Åh, nej tyvärr.
ANDI PENG: OK, så låt oss gå igenom denna kod.
Så när du försöker lägga till något på en kö,
i den vackra så att huvudet händer att vara just här, är det väldigt lätt för oss
att bara gå till slutet infoga något, eller hur?
Men hela poängen med en kö är att huvudet kan faktiskt dynamiskt
ändras beroende på var vi vill i början av vår q att vara,
och som sådan, svansen kommer också att förändras.
>> Och så föreställa sig att detta inte var den kö, utan det var kö.
Låt oss säga att huvudet är rätt här.
Låt oss säga vår kö såg ut så här.
Om vi ​​ville flytta där början av raden är,
Låt oss säga att vi skiftade huvudet detta sätt och storlekarna här.
>> Nu vill vi lägga till något till denna kö, men som ni kan se,
det är inte så enkelt som att bara lägga till vad är efter storlek
för då kör vi ut ur gränserna för våra faktiska array.
Där vi verkligen vill lägga till är här.
Det är skönheten i en kö är det oss, visuellt det
ser ut linjen går så här, men när det lagras i en datastruktur,
de ger den som som en cykel.
Den sveper slags runt till framsidan på samma sätt
att en linje kan också linda runt beroende på vart du
vill början av raden för att vara.
Och så om vi tar en titta ner här, låt oss
säger vi ville skapa en Funktionen kallas enqueue.
Vi ville lägga int n till att q.
Om q.size q-- vi kallar att våra data structure-- om vår queue.size inte
lika med kapaciteten eller om det är mindre än kapacitet,
q.strings är arrayen inom vår q.
Vi kommer att ställa som är lika med q.heads,
vilket är just här, plus q.size modul av kapaciteten, som
linda oss tillbaka runt här.
>> Så i det här exemplet, index huvud är en, eller hur?
Indexet storlek är 0, 1, 2, 3, 4.
Så vi kan göra ett plus 4 modul av vår kapacitet som är fem.
Vad som ger oss?
Vad är det index som kommer ut av detta?
>> PUBLIK: 0.
>> ANDI Peng: 0, vilket råkar vara just här,
och så vi vill kunna att sätta in just här.
Och så denna ekvation här typ på bara fungerar med alla siffror
beroende på var din huvud och din storlek är.
Om du vet vad de saker är, du vet
precis där du vill infoga vad är efter kön.
Innebär det vettigt att alla?
>> Jag vet lite av en hjärna teaser särskilt eftersom detta
kom i efterdyningarna av din frågesport.
Men förhoppningsvis alla nu kan förstå
varför denna lösning eller detta funktion är det sätt som det är.
Någon lite oklart om det?
OK.
>> Och så nu, om du ville avköa, detta
är där vår huvud skulle flytta Om vi ​​skulle avköa,
vi tar inte ut i slutet av q.
Vi vill ta bort huvudet, eller hur?
Så som ett resultat, är huvudet kommer att förändras, och det är därför när du köa,
du måste hålla reda på där ditt huvud och din storlek
skall kunna sätta in i rätt läge.
>> Och så när du avköa, Jag Pseudokod det också.
Känn dig fri att om du vill att försöka koda detta.
Du vill flytta huvudet, eller hur?
Om jag ville avköa jag skulle flytta huvudet över.
Detta skulle vara huvudet.
>> Och vår nuvarande storlek skulle subtrahera eftersom vi inte längre
har fyra element i arrayen.
Vi har bara tre, och då vill vi att återvända vad förvarades inne
av huvudet eftersom vi vill ta detta värde ut så mycket lik stapeln.
Bara du tar från en annan plats,
och du måste överlåta din pekaren till annan plats som följd.
Logiskt sett alla följa?
Bra.
>> OK, så vi kommer att prata lite mer på djupet om länkade listor
eftersom de kommer att vara mycket, mycket värdefullt för dig under denna veckas
psets.
Länkade listor, som ni kan minnas, allt de är
är noder som är noder av vissa värden för både ett värde och en pekare
som är kopplade till varandra av dessa pekare.
Och så struct om hur Vi skapar en nod här är vi
har int n, vilket är vad värdet i en butik eller sträng n
eller vad du vill kallar det, rödingen stjärnan n.
Struct nod stjärnan som är pekaren som du vill ha i varje nod,
du kommer att ha det pekaren pekar mot nästa.
Du kommer att ha huvudet av en länkad lista som är
kommer att peka till resten av värdena så vidare och så vidare
tills du slutligen når slutet.
Och detta sista noden är bara kommer att inte ha en pekare.
Det kommer att peka på null, är och att när
du vet att du har drabbats slutet av din länkad lista
är när din sista pekaren pekar inte på något.
>> Så vi kommer att gå lite mer djup om hur man skulle kunna
söka i en länkad lista.
Kom ihåg vad är några av de nackdelarna med de länkade listor
vers en array om sökningar.
En array kan du binär sökning, men varför kan du inte göra det i en länkad lista?
>> PUBLIK: Eftersom de är alla anslutna, men du vet inte riktigt var
[OHÖRBAR].
>> ANDI PENG: Ja, precis så kom ihåg att briljans av en matris
var det faktum att vi hade direktminne där
om jag ville värdet från index sex, jag kunde bara säga index sex,
ge mig det värdet.
Och det beror på matriser sorteras i en angränsande utrymme minne
på ett ställe, medan typ av länkade listor
är slumpmässigt varvas runt, och det enda sättet du kan hitta en
är genom en pekare som talar om adressen där att nästa nod är.
>> Och så som ett resultat, är det enda sättet söka igenom en länkad lista
är linjär sökning.
Eftersom jag inte exakt vet var den 12: e värdet i den länkade listan är,
Jag måste korsa helheten av det länkad lista en
med en från huvudet till den första noden, till den andra noden, till den tredje noden,
hela vägen ner tills jag äntligen få där noden jag letar efter är.
Och så i denna mening, sök på en länkad lista är alltid n.
Det är alltid n.
Det är alltid i linjär tid.
>> Och så koden i vilken vi genomföra detta, och detta
är lite nytt för er eftersom ni killar har inte riktigt pratat om eller någonsin
sett pekare i hur man söka igenom pekare,
så vi kommer att gå igenom detta mycket, mycket långsamt.
Så bool ökning, höger, Låt oss föreställa oss att vi vill ha
för att skapa en funktion som kallas sökning som returnerar true
om du hittade ett värde inuti den länkade lista, och returnerar i annat fall false.
Nod stjärna lista är för närvarande bara pekaren
den första punkten i länkad lista.
int n är det värde som du söker efter i listan.
>> Så nod stjärnpekaren lika listan.
Det betyder att vi inställning och skapa en pekare
till det första noden inne i listan.
Alla med mig?
Så om vi skulle gå tillbaka hit, skulle jag ha
initieras en pekare som pekar på chefen för vad denna lista är.
>> Och när du kommer ner hit, medan pekaren inte lika null,
så det är den slinga, i vilken vi är kommer att bli därefter korsa
resten av vår lista eftersom det händer när pekaren är lika med noll?
Vi vet att vi have--
>> PUBLIK: [OHÖRBAR]
>> ANDI PENG: Exakt, så vi vet att Vi har nått slutet av listan, eller hur?
Om du går tillbaka hit, varje nod skall peka till en annan nod
och så vidare och så vidare tills du träffar så småningom
svansen på din länkad lista, som har en pekare som bara
pekar inte någon annanstans än inget.
Och så du i princip vet att listan är fortfarande där uppe
tills visaren inte är lika null eftersom när det är lika med noll,
du vet att det inte finns något mer grejer.
>> Så det är slingan där vi är kommer att ha den faktiska sökt.
Och om pointer-- ser du den typen av pilen fungerar det?
Så om pekaren pekar på n, om pekaren på n är lika med lika n
så det betyder att om pekaren att du är
söker efter på i slutet av varje nod är faktiskt lika med värdet
du letar efter, då du vill return true.
Så i princip, om du är på en nod som har det värde som du letar efter,
du vet att du har varit kunna framgångsrikt söka.
>> Annars, du vill ställa in pekaren till nästa nod.
Det är vad den linjen här gör.
Pointer lika pekare nästa.
Alla se hur det fungerar?
>> Och i huvudsak du ska bara genomlöpa hela den listan,
återställa pekaren varje gång tills du så småningom slog i slutet av listan.
Och du vet att det inte finns några fler noder att söka igenom,
och sedan kan du returnera false eftersom du vet att, åh, ja,
om jag har kunnat söka genom helheten av listan.
Om det i detta exempel, om jag ville att leta efter värdet på 10,
och jag börjar i spetsen, och Jag söker hela vägen ner,
och jag fick så småningom till detta, vilket en pekare som pekar på noll,
Jag vet att, skit, jag antar att 10 inte är i den här listan eftersom jag kunde inte hitta den.
Och jag är i slutet av listan.
Och i vilket fall du känner Jag kommer att returnera false.
>> Låt det verka i en liten bit.
Detta kommer att vara ganska viktigt för din pset.
Logiken i den är mycket enkel, kanske syntaktiskt bara genomföra det.
Ni vill göra Se till att du förstår.
Häftigt.
>> OK, så hur vi skulle vara infoga noder, höger,
i en lista eftersom ihåg vad är det som om fördelarna
av att ha en länkad lista kontra en matris i form av lagring?
>> PUBLIK: Det är dynamisk, så det är lättare att--
>> ANDI PENG: Exakt, så det är dynamiskt, vilket
innebär att det kan expandera och krympa beroende på användarens behov.
Och så, i denna mening, vi behöver inte att slösa onödig minnet eftersom jag
om jag inte vet hur många värden som jag vill att lagra, gör det inte meningsfullt för mig
att skapa en array eftersom om jag vill lagra 10 värden
och jag skapa en array av 1000, det är en hel del bortkastade minne, tilldelas.
Det är därför vi vill använda en länkad Listan för att kunna dynamiskt
ändra eller krympa vår storlek.
>> Och så det gör insättning lite mer komplicerat.
Eftersom vi inte slumpmässigt kan komma åt element det sätt som vi skulle i en array.
Om jag vill infoga ett element in i den sjunde index,
Jag kan bara infoga det in i den sjunde indexet.
På en länkad lista, gör det inte helt fungerar lika enkelt,
och så om vi ville infoga den en här i den länkade listan,
visuellt, är det mycket lätt att se.
Vi vill bara att sätta den där, precis i början av listan,
direkt efter huvudet.
>> Men det sätt på vilket vi måste överlåta pekarna är lite invecklad
eller logiskt, är det vettigt, men du vill vara säker på att du har det
helt ner på grund det sista du vill
är att tilldela en pekar sätt som vi gör här.
Om du dereference den pekaren från topp till 1
då helt plötsligt resten av ditt länkad lista
försvinner eftersom du har faktiskt inte skapas en temporär någonting.
Det är pekade på två.
Om du tilldela pekaren sedan Resten av listan är helt förlorad.
Så du vill vara mycket, mycket försiktig här
att först tilldela pekaren från vad du
vill infoga i varhelst du vill, och sedan
kan dereference resten av listan.
>> Så detta gäller överallt där du försöker sätta in.
Om du vill infoga i huvud, om du vill svara här,
Om du vill infoga slutet, ja, till slut jag
antar att du skulle bara har ingen visare, men du
vill se till att du inte förlorar resten av listan.
Du vill alltid se till att din nya nod pekar
mot vad du vill infoga i,
och då kan du lägga till kedja på.
Alla klart?
>> Detta kommer att bli en av de verkliga frågorna.
En av de mest viktiga frågor du kommer att ha på din pset
är att du kommer att försöka skapa en länkad lista och insats saker
men sedan bara förlorar resten av ditt länkad lista.
Och du kommer att se ut, jag vet inte varför detta händer?
Och det är jobbigt att gå igenom och sök alla dina tips.
>> Och jag garanterar dig på denna pset, skriva och rita dessa noder ut
kommer att vara mycket, mycket bra.
Så du kan helt hålla koll av där alla dina pekare är
vad går fel, där alla dina noder är
vad du behöver göra för att få åtkomst till eller infoga eller ta bort eller någon av dem.
Alla bra med det?
Häftigt.
>> Så om vi ville titta på koden?
Åh, jag vet inte om vi kan se the-- OK, så
på toppen allt är är en funktion namngav insats där vi vill
att sätta int n i den länkade listan.
Vi kommer att gå igenom detta.
Det är en hel del kod, en hel del ny syntax.
Vi ska vara OK.
>> Så upp på toppen, när Vi vill skapa något
Vad behöver vi göra, särskilt om du vill att det ska inte lagras på stacken
men i högen?
Vi går till en malloc, eller hur?
Så vi kommer att skapa en pekare.
Nod, pekare, nya jämlikar malloc storleken på en nod
eftersom vi vill att noden ska skapas.
Vi vill mängden minne som en nod tar upp
tilldelas för Inrättandet av den nya noden.
>> Och sedan ska vi kontrollera se om nya jämlikar är lika med noll.
Kom ihåg vad vi sa?
Vad du malloc, Vad måste du alltid göra?
Du måste alltid kontrollera att se oavsett om det är null.
>> Till exempel, om ditt operativsystem Systemet var helt fullt,
om du hade ingen mer minne på alla och du försöker malloc,
det skulle återvända null för dig.
Och så om du försöker använda det när det pekar på noll,
du inte kommer att kunna att få tillgång till denna information.
Och så som sådan, vi ville göra Se till att när du mallocing,
du alltid kontrollera att se om att minnet du fått är null.
Och om det inte är, då kan vi flytta på med resten av vår kod.
>> Så vi kommer att initiera nya noden.
Vi kommer att göra ett nytt n är lika med n.
Och sedan ska vi göra sätta nya pekaren på nya
till null eftersom just nu gör vi inte ha något för det att peka på.
Vi har ingen aning om det kommer att sätta dig,
och sedan om vi vill infoga det i huvudet,
då kan vi omtilldela pekaren till huvudet.
Har alla följa logiken var som händer?
>> Allt vi gör är att skapa en ny nod, ställa pekaren till noll,
och sedan omfördelning den till huvudet om vi
vet att vi vill infoga det i spetsen.
Och sedan huvudet kommer att pekar mot den nya noden.
Alla OK med det?
>> Så det är en tvåstegsprocess.
You got att först tilldela vad du skapar.
Ställ som pekare till referens, och sedan
kan typ av dereference den första pekaren
och rikta den mot den nya noden.
Vart du vill infoga det, denna logik kommer att hålla sant.
>> Det är ungefär som att tilldela temporära variabler.
Kom ihåg att du har fått att se till att du
inte förlora reda på om du byter.
Du vill vara säker på att du har en temporär variabel den sortens håller
reda på var det där lagras så att du
inte förlorar något värde i samband som att leka med den.
>> OK, så koden kommer att vara här.
Ni tar en titt efter avsnitt.
Det kommer att vara där.
>> Så jag gissa hur gör Detta skiljer sig om vi ville
att infoga i mitten eller slutet?
Finns det någon som har en idé om vad som är pseudokod som den logiska referens
att vi skulle ta om vi ville att infoga den i mitten?
Så om vi ville sätta in den på huvud, är allt vi gör skapa en ny nod.
Vi sätter pekaren i nämnda ny nod till oavsett huvudet,
och sedan vi satt huvudet till den nya noden, eller hur?
Om vi ​​ville sätta in den i mitten av listan, vad skulle vi göra?
>> PUBLIK: Det skulle fortfarande vara en liknande process
som att tilldela pekaren och sedan tilldela den pekare,
men vi skulle behöva hitta där.
>> ANDI PENG: Just det, så exakt samma process förutom att du
måste hitta exakt var du vill den nya pekaren att gå in,
så om jag vill infoga i mitten av länkade list-- OK,
låt oss säga att det är vår länkad lista.
Om vi ​​vill infoga det här, Vi ska skapa en ny nod.
Vi kommer att malloc.
Vi kommer att skapa en ny nod.
Vi kommer att tilldela pekare av denna nod här.
>> Men problemet som skiljer från där huvudet är
är att vi visste exakt där huvudet är.
Det var rätt vid första, eller hur?
Men här har vi att hålla koll var vi sätter in det i.
Om vi ​​sätter vår nod här, har vi
att se till att en tidigare till denna nod
är en som återtilldelar pekaren.
Så då måste man typ av hålla reda på två saker.
Om du hålla reda på var detta nod för närvarande att sätta in i.
Du måste också hålla reda på var föregående nod som du tittar på
var också där.
Alla bra med det?
OK.
>> Vad sägs om att sätta in i slutet?
Om jag ville lägga till den här-- om jag ville att lägga till en ny nod i slutet av en lista,
Hur kan jag gå om att göra det?
PUBLIK: Så för närvarande, den förra ens pekade på null.
ANDI PENG: Ja.
Exakt så här närvarande pekas att veta,
och så jag antar att, i denna mening, är det mycket lätt att lägga till i slutet av en lista.
Allt du behöver göra är att ställa det lika med noll och sedan boom.
Just där, mycket lätt.
Väldigt enkelt.
>> Mycket lik den huvudet, men logiskt du
vill se till att stegen du tar mot att göra något av detta,
du följer med.
Det är väldigt lätt att, i mitten av din kod, fastna på,
åh, jag har fått så många pekare.
Jag vet inte var något pekar på.
Jag vet inte ens vilken nod jag är på.
Vad händer?
>> Slappna av, lugna ner, ta ett djupt andetag.
Dra ut din länkad lista.
Om du säger, jag vet var exakt Jag måste sätta in detta i
och jag vet exakt hur man ska överlåta min pekare, mycket, mycket lättare att föreställa
out-- mycket, mycket lättare att inte vilse i buggar i koden.
Alla OK med det?
OK.
>> Så jag antar att ett koncept som vi inte har verkligen talade om förrän nu,
och jag antar att du förmodligen kommer inte att stöta mycket yet--
det är typ av en avancerad concept-- är att vi faktiskt har en data
struktur som kallas en dubbellänkad lista.
Så när ni kan se, allt vi gör är att skapa
ett ärvärde, en extra pekaren på vart och ett av våra noder
som pekar också på den tidigare nod.
Så inte nog med att vi har vår noder pekar på nästa.
De pekar också på tidigare.
Jag kommer att ignorera dessa två just nu.
>> Så då har du en kedja som kan flytta åt båda hållen,
och då är det lite lättare logiskt följa.
Som här, i stället för hålla reda på, åh, jag
måste veta att denna nod är den som jag måste överlåta,
Jag kan bara gå hit och bara dra den föregående.
Då vet jag exakt var det vill säga, och sedan
behöver inte korsa helheten av den länkade listan.
Det är lite lättare.
>> Men som sådan, har du dubbelt mängden av pekare,
det är dubbelt så mycket minne.
Det är en hel del tips för att hålla reda på.
Det är lite mer komplicerat, men det är lite mer användarvänlig beroende
på vad du försöker åstadkomma.
>> Så denna typ av data struktur finns totalt,
och strukturen för är mycket, mycket enkel utom allt du har är,
i stället för bara en pekare till nästa, Du har också en pekare till tidigare.
Det är hela skillnaden var.
Alla bra med det?
Häftigt.
>> Okej, så nu är jag att verkligen spendera förmodligen
som 15 till 20 minuter eller huvuddelen resten av tiden i avsnittet
talar om hashtabeller.
Hur många av er har läst pset5 spec?
Okej, bra.
Det är högre än 50% av normalt.
Det är ok.
>> Så när ni kommer att se, du utmaningen i pset5
kommer att vara att genomföra en ordbok där du laddar över 140.000 ord
att vi ger dig och stavningskontroll det mot all text.
Vi ger dig slumpmässig bitar av litteratur.
Vi ger dig Odyssey.
Vi ger dig Iliaden.
Vi ger dig Austin Powers.
>> Och din utmaning kommer att vara att stavningskontroll
varje ord i alla av dessa ordböcker
i huvudsak med vårt stavningskontroll.
Och så finns det några delar att skapa denna pset,
först du vill vara kan faktiskt läsa
alla orden i din ordbok, och sedan
vill kunna stavningskontroll dem alla.
Och så som sådan, du kommer att kräva en datastruktur som kan göra detta snabbt
och effektivt och dynamiskt.
>> Så jag antar att det enklaste sätt att göra detta, du
skulle förmodligen skapa en array, eller hur?
Det enklaste sättet att lagring är du kan skapa en rad 140.000 ord
och bara placera dem alla där och sedan korsa dem med binär sökning
eller genom val eller inte-- ledsen som är sortering.
Du kan sortera dem och sedan passera dem genom binär sökning eller bara linjär sökning
och bara sista orden, men att tar en stor mängd minne,
och det är inte mycket effektiv.
>> Och så vi ska börja talar om sätt att göra
vår gångtid mer effektiv.
Och vårt mål är att få konstant tid där
det är nästan som matriser, där du har omedelbar tillgång till.
Om jag ville söka efter något, Jag vill kunna bara,
boom, tycker att det är exakt, och dra ut den.
Och så en struktur i vilken vi kommer att bli mycket nära
för att kunna få tillgång till konstant tid, denna heliga graal
i programmering av konstant tid kallas en hashtabell.
Och så David tidigare nämnts [OHÖRBAR] lite i föredrag,
men vi ska verkligen dyka i djup den här veckan
på en bit som är i fråga hur en hashtabell fungerar.
>> Så det sätt som en hash bords verk, till exempel,
om jag ville att lagra en massa ord, en gäng ord i det engelska språket,
Jag kunde teoretiskt sätta banan, äpple, kiwi, mango, par,
och cantaloupemelon allt på bara en array.
De kunde alla passa in och bli hitta.
Det skulle vara typ av en smärta att söka igenom och tillgång,
men det enklare sätt att göra detta är att vi kan skapa faktiskt en struktur
kallas en hashtabell där vi hash.
Vi driver alla våra nycklar genom en hashfunktion, en ekvation,
som förvandlar dem alla i någon form av ett värde
som sedan kan vi lagrar på huvudsak ett arrangemang av länkad lista.
>> Och så här, om vi ville att lagra engelska ord,
vi kunde potentiellt bara, det gör jag inte vet, slå alla de första bokstäverna
in någon form av en siffra.
Och så, till exempel, om jag ville En vara synonymt med apple--
eller med index på 0, och B att vara synonymt med ett,
vi kan ha 26 poster som bara kan lagra
alla bokstäver i alfabet som vi ska börja med.
Och då kan vi ha äpple på index 0.
Vi kan ha banan vid index 1, cantaloupemelon vid index 2,
och så vidare och så vidare.
Och så om jag ville söka min hash bord och tillgång äpple,
Jag vet att äpple börjar med ett A, och jag vet exakt
att det måste vara och hash bord på index 0 eftersom
av funktionen tidigare tilldelats.
>> Så jag vet inte, vi är en användare där programmet
du kommer att debiteras med arbitrarily-- inte godtyckligt,
med att försöka tänk tänker på goda ekvationer
för att kunna sprida ut alla dina värderingar
på ett sätt som de lätt kan få tillgång till den senare med som en ekvation
att du själv vet.
Så i den meningen om jag ville gå till mango, jag vet, åh, det börjar med m.
Det måste vara indexet för 12.
Jag behöver inte söka igenom någonting.
Jag vet exactly-- jag kunde bara gå till index 12 och dra ut det.
>> Alla tydlig på hur en hashtabell funktion fungerar?
Det är typ av bara en mer komplex uppsättning.
Det är allt det är.
OK.
>> Så jag antar att vi stöter på det här numret av vad
händer om du har flera saker som ger dig samma index?
Så säger vår funktion, allt gjorde var att ta den första bokstaven
och förvandla det till en respektive 0 till 25 index.
Det är helt bra om du har bara en av varje.
Men den andra du börjar med mer, du är
kommer att ha vad som kallas en kollision.
>> Så om jag försöker att infoga begrava i en hash tabell som redan har banan på det,
vad som kommer att hända när du försöker infoga det?
Dåliga saker eftersom banan redan finns inom indexet
som du vill lagra den i.
Berry typ av ser ut, ah, vad ska jag göra?
Jag vet inte vart de ska gå.
Hur löser jag detta?
>> Och så ni kommer slags ser vi gör detta knepig sak
där vi kan slags faktiskt skapa länkad lista i våra matriser.
Och så det enklaste sättet att tänka på detta,
alla hash-tabell är en matris med länkade listor.
Och så, i den meningen, har du denna vackra samling av pekare,
och därefter varje pekare i detta värde, i detta index,
kan faktiskt peka på andra saker.
Och så du har alla dessa separat kedjor som kommer bort av en stor samling.
>> Och så här, om jag ville infoga bär,
Jag vet, OK, jag ska mata det genom min hashfunktion.
Jag ska sluta med index 1, och sedan kommer jag att kunna ha
bara en mindre undergrupp av denna jätte 140.000 ord ordbok.
Och då kan jag bara titta genom 1/26 av det.
>> Och så då kan jag bara in bär antingen före eller efter banan
I det här fallet?
Efter, eller hur?
Och så att du kommer att vilja infoga denna nod efter banan,
och så du kommer att infoga i svansen av den länkad lista.
Jag kommer att gå tillbaka denna föregående bild,
så ni kan se hur hash funktionen fungerar.
>> Så hashfunktion är denna ekvation att du kör typ av din input
genom att få vad index du vill tilldela den mot.
Och så, i detta exempel, allt vi ville att göra var att ta den första bokstaven,
förvandla det till ett index, då vi kan lagra den i vår hash funktion.
Allt vi gör här är att vi är omvandling av den första bokstaven.
Så keykey [0] är bara den första bokstaven oavsett sträng vi har,
vi passerar.
Vi omvandla denna till övre och vi subtrahera med versaler A,
så allt som gör ger oss ett antal
där kan vi hash våra värderingar på.
>> Och sedan ska vi retur hash modul STORLEK.
Var mycket, mycket försiktig eftersom, teoretiskt, här
din hash-värde kan vara oändlig.
Det kunde bara gå på och så vidare.
Det kan vara några riktigt, riktigt stora värde,
men eftersom din hash tabell som du har skapat bara har 26 index,
du vill se till att din modulusing så att du
inte run-- det är samma sak som din queue--
så att du inte kör bort undersidan av hashfunktion.
>> Du vill linda den tillbaka runt på samma sätt i [OHÖRBAR] när
du hade som en mycket, mycket stor bokstav, du
ville inte det till bara köra utanför slutet.
Samma sak här, vill du se till att det går inte ut i slutet genom att linda
runt till början av tabellen.
Så det här är bara en mycket enkel hashfunktionen.
Allt som gjorde var att ta den första skrivelse av vad vår insats var
och förvandla det till ett index som vi kunde sätta i våra hash bord.
>> Ja, och så som jag sade tidigare, det sätt som vi löser kollisioner
i vår hash tabeller har, vad vi kallar, kedja.
Så om du försöker infoga flera ord som börjar med samma sak,
du kommer att ha ett hash-värde.
Avokado och äpple, om du har köra det genom vår hashfunktion,
kommer att ge dig samma nummer, antalet 0.
Och så sätt att lösa detta är att vi faktiskt ganska kan länka dem
varandra via länkade listor.
>> Och så i denna mening, ni kan se snäll
av hur datastrukturer som vi har inställningen tidigare
som ett russin länkad lista slag av kan komma ihop till en.
Och då kan du skapa långt effektivare datastrukturer
som kan hantera större mängder uppgifter, som dynamiskt ändra storlek beroende
på dina behov.
Alla klart?
Alla slags klar om vad som händer här?
>> Om jag ville insert-- vad är en frukt som börjar med, jag vet inte,
B, annat än bär, banan.
>> PUBLIK: Blackberry.
>> ANDI PENG: Blackberry, björnbär.
Vart tar björnbär gå hit?
Tja, vi faktiskt inte har rett detta ännu, men teoretiskt
om vi ville ha detta i alfabetisk ordning,
där ska björnbär gå?
>> PUBLIK: [OHÖRBAR]
>> ANDI PENG: Exakt, efter här, eller hur?
Men eftersom det är mycket svårt att reorder-- Jag antar att det är upp till er.
Ni kan helt genomföra vad du vill.
Ju mer effektivt sätt att göra detta kanske
skulle vara att sortera dina länkade lista i alfabetisk ordning,
och så när du är infoga saker, du vill
vara säker på att infoga dem i alfabetisk ordning
så att då när du är försöker söka dem,
du behöver inte korsa allt.
Du vet exakt var det är, och det är lättare.
>> Men om du typ av har saker varvas slumpmässigt,
du fortfarande kommer att ha att korsa det ändå.
Och så om jag ville bara infoga björnbär här
och jag ville söka efter det, jag vet, åh, björnbär
måste börja med index 1, så jag vet omedelbart bara söka på en.
Och då kan jag typ av korsa den länkade listan
tills jag får till Blackberry, och then-- ja?
>> PUBLIK: Om du försöker create-- Jag antar att så här är en mycket enkel hash
fungera.
Och om vi ville göra flera skikt av det liknande,
OK, vi vill separera i som alla bokstäver
och sedan igen för att ha en annan uppsättning av alfabetiska bokstäver inom det,
lägger vi som en hash tabell i en hash-tabell,
eller som en funktion inom en funktion?
Eller är that--
>> ANDI PENG: Så din hash function-- din hashtabell
kan vara så stor som du vill.
Så i den meningen, jag trodde det var mycket lätt, mycket
enkelt för mig att bara sortera baserat på bokstäverna i det första ordet.
Och så finns det bara 26 alternativ.
Jag kan bara få 26 alternativ från 0 till 25, eftersom de endast kan
börja från A till Z. Men om du ville att lägga till, kanske, mer komplexitet
eller snabbare gångtid till hashtabell, du absolut
kan göra alla möjliga saker.
Du kan göra din egen ekvation som ger dig
mer distribution i din ord, sedan när du söker,
det kommer att bli snabbare.
>> Det är helt upp till er hur du vill genomföra det.
Tänk på det som bara hinkar.
Om jag ville ha 26 hinkar, jag kommer
att sortera saker i dessa hinkar.
Men jag kommer att ha ett gäng saker i varje segment,
så om du vill göra det snabbare och effektivare,
Låt mig få hundra hinkar.
>> Men då måste man räkna ut ett sätt att sortera saker så att de är
i rätt hinken de bör vara i.
Men sedan när du faktiskt vill titta på hinken,
det är mycket snabbare eftersom det finns mindre grejer i varje hink.
Och så, ja, det är faktiskt tricket för er i pset5
är att du kommer att utmanas att bara skapa
vad är det mest effektiva funktionen kan du tänka dig att vara
kunna lagra och kontrollera dessa värden.
>> Helt upp till er men du vill göra det,
men det är en riktigt bra poäng.
Att den typ av logik du vill börja tänka på
är, tja, varför inte jag göra fler hinkar.
Och då måste jag söka mindre saker, och sedan kanske jag
har en annan hash-funktion.
>> Ja, det finns många sätt att göra detta pset, vissa är snabbare än andra.
Jag är helt kommer att bara se hur snabb var snabbaste ni kommer
att kunna få dina funktioner ska fungera.
OK, alla bra ut på CHAI och hashtabeller?
Det är faktiskt som en mycket enkel koncept om man tänker på det.
Allt som är är att separera vad ingångarna är i hinkar,
sortera dem, och sedan söka på listor att det har samband med.
>> Häftigt.
Okej, nu har vi en annan sorts av datastruktur som kallas ett träd.
Låt oss gå vidare och tala om försök vilka är helt olika,
men i samma kategori.
I grunden är allt ett träd i stället organisera data i linjärt sätt
att en hashtabell does-- dig vet, det har fått en topp och en botten
och sedan slags länka bort av det-- en träd har en topp som ni kallar roten,
och då har blad runt den.
>> Och så allt du behöver här är bara toppnoden
som pekar på andra noder, som pekar till flera noder, och så vidare och så vidare.
Och så har du bara dela upp grenar.
Det är bara ett annat sätt att organisera uppgifter, och eftersom vi kallar det ett träd,
ni bara-- det är bara modelleras för att se ut som ett träd.
Det är därför vi kallar det träd.
>> Hashtabell ser ut som en tabell.
Ett träd bara ser ut som ett träd.
Allt som är en separat sätt att organisera noder
beroende på vilka behov du har.
>> Så du har en rot och så har du lämnar.
Det sätt som vi kan särskilt tänker på det är ett binärt träd,
ett binärt träd är bara en specifik typ av ett träd
där varje nod endast punkter att, vid max, två andra noder.
Och så här har du distinkt symmetri i ditt träd
som gör det lättare att typ av ser på vilka värden du är för då
har alltid en vänster eller höger.
Det finns aldrig som en vänster tredjedel från vänster eller kvart från vänster.
Det är bara att du har en vänster och en höger och du kan söka någon av dessa två.
Och så varför är detta bra?
Det sätt som detta är användbart är om du letar
att söka igenom värderingar, eller hur?
I stället för att genomföra binär söka i ett fel matris,
om du ville kunna sätta in noder och ta bort noder på vilja och även
bevara sökning kapacitet binär sökning.
Så på detta sätt, vi är typ av tricking-- minns när vi
sade länkade listor kan inte binär sökning?
Vi slags skapar en datastruktur att tricks som i arbets.
>> Och så på grund länkade listor är linjära, de länkar bara den ena efter den andra.
Vi kan slags måste annan typ av pekare
som pekar på olika noder som kan hjälpa oss med sökning.
Och så här, om jag ville har ett binärt sökträd,
Jag vet att min mitten om 55.
Jag kommer bara att skapa den som min mitten, som min rot,
och sedan kommer jag att ha värden spin off av det.
>> Så här, om jag ska söka efter värdet 66, kan jag börja vid 55.
Det är 66 större än 55?
Ja det är, så jag vet att jag Mus söka v rätt pekare av detta träd.
Jag går till 77.
OK, är 66 mindre än eller större än 77?
Det är mindre än, så du vet, åh, som måste vara den vänstra noden.
>> Och så här vi slags bevara alla de stora sakerna arrayer,
så som dynamisk storleksändring av föremål, som
kunna sätta in och ta bort efter behag, utan att behöva oroa sig för den fasta
mängd utrymme.
Vi bevarar fortfarande alla dessa underbara saker
samtidigt kunna bevara log och sök tid av binär sökning
att vi var bara tidigare kunna få en fras.
>> Cool datastruktur, typ av komplicerade att genomföra, noden.
Som ni kan se, allt är struct av noden
är att du har en vänster och en höger pekare.
Det är allt det är.
Så i stället för att bara med ett x eller tidigare.
Du har en vänster eller höger, och sedan du kan slags länka ihop dem
men du så önskar.
>> OK, vi faktiskt kommer bara ta några minuter.
Så vi kommer att gå tillbaka hit.
Som jag sagt tidigare, Jag slags förklarade
logiken bakom hur vi skulle söka igenom detta.
Vi ska försöka pseudocoding ut det här för att se
om vi slags kan tillämpa Samma logik binär sökning
till en annan typ av datastruktur.
Om ni vill ta som ett par minuter att bara tänka på detta.
OK.
Okej, jag ska faktiskt bara ge er the-- nej,
vi pratar om pseudo först.
Så är det någon som vill för att ge ett hugg på vad
det första du vill göra när du börjat söka är?
Om vi ​​letar efter värdet 66, vad är
det första vi vill göra om Vi vill binära söka detta träd?
>> PUBLIK: Du vill se höger och ser till vänster och se [OHÖRBAR]
större antal.
>> ANDI PENG: Ja, exakt.
Så du kommer att titta på din rot.
Det finns massor av sätt du kan ringa det, dina överordnade nod folk säger.
Jag vilja säga rot eftersom det är som roten av trädet.
Du kommer att titta på din rotnod, och du är
kommer att se är 66 större än eller mindre än 55.
Och om det är större än väl, är det större än där vi vill se?
Var vill vi söker nu, eller hur?
Vi vill söka högra halvan av detta träd.
>> Så vi har, enkelt, en pekare som pekar till höger.
Och så då kan vi ställa vår nya roten att vara 77.
Vi kan bara gå dit pekaren pekar.
Tja, åh, här vi börjar vid 77, och vi kan bara
göra detta rekursivt igen och igen.
På detta sätt, du snäll av en funktion.
Du har ett sätt att söka som du kan bara upprepa om och om och om igen,
beroende på var du vill se tills du så småningom kommer till värdet
att du söker efter.
Vettigt?
>> Jag ska visa dig de faktiska kod, och det är en hel del kod.
Du behöver inte freak out.
Vi kommer att prata igenom det.
>> Faktiskt nej.
Det var bara pseudokod.
OK, det var bara pseudo, vilket är lite komplicerat,
men det är helt bra.
Alla följer med här?
Om roten är null, retur falskt eftersom det innebär
du behöver inte ens har något där.
>> Om root n är värdet, så om det råkar vara den du tittar på,
då du kommer att återvända sant eftersom du vet att du hittat den.
Men om värdet är mindre än roten av n, är du
kommer att söka den vänstra barn eller vänster blad,
vad du vill kalla det.
Och om värdet är större än roten, du kommer att söka rätt trädet,
sedan bara köra funktionen genom sökningen igen.
>> Och om roten är null, att denna innebär att du har nått slutet?
Det innebär att du inte har någon mer mer blad att söka,
då vet du, åh, jag antar att det är inte här
eftersom när jag har tittat igenom det hela och det är inte här,
det bara inte kan vara här.
>> Innebär det vettigt att alla?
Så det är som binär sökning bevara funktionerna i länkade listor.
Cool, och så den andra typen datastruktur ni
kan försöka genomföra på pset, du bara måste välja en metod.
Men kanske en alternativ metod för att hashtabellen är vad vi kallar en trie.
>> Allt en trie är en specifik typ av träd som
har värden som går till andra värden.
Så istället för att ha en binär träd i den meningen att endast en
sak kan peka på två, kan du ha en sak peka på många, många saker.
Du har i huvudsak arrayer insida som du lagrar
pekare som pekar på andra matriser.
>> Så noden om hur vi skulle definiera en trie
är att vi vill ha en Boolean, c ord, eller hur?
Så noden är Boolean som sant eller falskt,
först och främst i spetsen för att array, är det ett ord?
För det andra vill du ha tips till vad resten av dem är.
En lite komplicerat, lite abstrakt, men Jag kommer att förklara vad det alla medel.
>> Så här, i toppen, om man har en matris förklarade redan,
en nod där du har en Boolean värdet som är lagrat vid den främre
som berättar är det ett ord?
Är detta inte ett ord?
Och sedan har du resten av ditt array som
faktiskt lagrar alla möjligheterna för vad det kunde vara.
Så, till exempel, som upptill du har
den första som säger sant eller falskt, ja eller nej, det är ett ord.
>> Och då har du 0 till 26 de bokstäver som du kan lagra.
Om jag ville söka här för bat, jag går till toppen
och jag ser för B. Jag tycker B i mitt array, och så jag vet, OK, är B ett ord?
B är inte ett ord, så på så sätt Jag måste fortsätta söka.
Jag går från B, och jag ser till pekare som B pekar mot
och jag ser en annan uppsättning av information, samma struktur som vi hade tidigare.
>> Och här-- oh, nästa brev i [OHÖRBAR] är A.
Så vi ser i den arrayen.
Vi finner det åttonde värde, och sedan ser vi att se, oh,
hey, det är ett ord, är B-A ett ord?
Det är inte ett ord.
Vi måste fortsätta leta.
>> Och så då ser vi till där pekaren över A-punkter,
och den pekar på ett annat sätt i som vi har mer värde lagras.
Och slutligen, vi får B-A-T, som är ett ord.
Och så nästa gång du ser, du kommer
att ha den kontroll av, ja, Detta Boolean funktion är sant.
Och så i den mening vi är typ att ha ett träd med arrayer.
>> Så då kan du typ av sökning nedåt.
Snarare än hashing en funktion och tilldelning av värden av länkad lista,
du kan bara genomföra en trie som söker downwords.
Riktigt, riktigt komplicerat grejer.
Inte lätt att tänka på att jag är som spotta så många datastrukturer ut
på dig, men gör alla slags förstå hur logiken i detta fungerar?
>> OK bra.
Så B-A-T, och sedan du kommer att söka.
Nästa gång du ska att se, oh, hey, det är sant,
därför vet jag att detta måste vara ett ord.
>> Samma sak för zoo.
Så här är det just nu, om vi ville söka zoo, just nu,
närvarande zoo är inte en ord i vår ordlista
eftersom, som ni kan se, första plats som vi har en Boolean
return true är i slutet av zoom.
Vi har Z-O-O-M.
>> Och så här, vi egentligen inte har ordet, zoo, i vår ordlista
eftersom den här kryssrutan inte är markerad.
Så att datorn inte vet att zoo är ett ord
eftersom det sätt som vi har lagras det, bara en zoom här
faktiskt har ett logiskt värde som har stängts sant.
Så om vi vill infoga ord, zoo, i vår ordlista,
hur skulle vi gå om att göra det?
Vad har vi att göra för att se till att vår dator vet att Z-O-O är ett ord
och inte det första ordet är Z-O-O-M?
>> PUBLIK: [OHÖRBAR]
>> ANDI PENG: Exakt, vi vill se till att detta
Här är det logiskt värde prickas av att det är sant.
Z-O-O, då vi kommer att kontrollera att, så vi vet exakt, hej, är djurparken ett ord.
Jag kommer att tala om dator att det är ett ord så
att när datorn kontroller den vet att zoo är ett ord.
>> Eftersom ihåg alla dessa uppgifter strukturer, är det väldigt lätt för oss
att säga, oh, det bat ett ord.
Zoo är ett ord.
Zoom är ett ord.
Men när du bygger det, datorn har ingen aning.
>> Så du måste berätta det exakt vid vilken tidpunkt är det ett ord?
Vid vilken tidpunkt är det inte ett ord?
Och vid vilken tidpunkt jag behöver söka saker,
och vid vilken tidpunkt behöver jag gå nästa?
Alla borta från det?
Häftigt.
>> Och så då kommer problemet med hur skulle vi
gå om hur du sätter något det är faktiskt inte det?
Så låt oss bara säga att vi vill infoga ordet, bad, i vår trie.
Som ni kan se som för närvarande allt vi har nu är B-A-T,
och denna nya datastruktur Det hade en pint som
pekade på null eftersom vi antar att, åh, det finns inga ord efter B-A-T,
varför vi måste hålla ha saker efter att T.
>> Men problemet uppstår om vi gör du vill ha ett ord som kommer efter
T s.
Om du har bad, du är kommer att ha en H-rätt.
Och så hur vi ska göra det är vi kommer att skapa en separat nod.
Vi är inte tilldela det belopp minne för denna nya uppsättning,
och vi kommer att tilldela pekare.
>> Vi kommer att tilldela H, Först av allt, detta null,
vi kommer att bli av.
Vi kommer att ha H-punkten nedåt.
Om vi ​​ser en H, vi vill ha det att gå till någon annanstans.
>> Här inne kan vi sedan bocka av ja.
Om vi ​​träffar en H efter T, åh, då vet vi att detta är ett ord.
Boolean kommer att return true.
Alla klar över hur det hände?
OK.
>> Så i huvudsak alla dessa datastrukturer
att vi har gått över i dag, jag har gått över dem verkligen, verkligen snabbt
och inte i för mycket detalj, och det är OK.
När du börjar messing med det, kommer du att
hålla reda på var alla pekare är,
vad som händer i din datastrukturer, et cetera.
De kommer att vara till stor nytta, och det är upp till dig
killar att helt räkna ut hur du vill genomföra saker.
>> Och så pset4 av 5-- oh, det är fel.
Pset5 är felstavningar.
Som jag sade tidigare, du kommer att, en gång igen, ladda ner källkoden från oss.
Det kommer att finnas tre huvud saker du ska ladda ner.
Du kommer att ladda ner ordböcker, kers, och texter.
>> Alla dessa saker är är antingen lexikon av ord
att vi vill att du ska kolla eller test av uppgifter
att vi vill att du ska stavningskontroll.
Och så ordböcker Vi ger dig går
för att ge dig de faktiska ord som vi vill du kan lagra något på ett sätt som är
effektivare än en array.
Och då texterna är kommer att bli vad vi är
ber dig att stava kontrollera att alla orden finns riktiga ord.
>> Och så de tre block av program som vi ska ger dig
kallas dictionary.c, dictionary.h och speller.c.
Och så alla dictionary.c gör är vad du blir ombedd att genomföra.
Den laddar ord.
Det stava kontroller dem, och det gör säkert att allt sitter ordentligt.
>> diction.h är bara ett bibliotek fil som förklarar alla dessa funktioner.
Och speller.c, kommer vi att ge dig.
Du behöver inte ändra något av det.
Alla speller.c gör är att ta det, laster det, kontrollerar hastigheten för den,
testar riktmärket som hur snabbt du kan göra saker.
>> Det är en speller.
Bara inte bråka med den, men göra att du förstår vad den gör.
Vi använder en funktion som kallas getrusage som testar prestanda för din spell
checker.
Allt det gör är i grunden testa tid av allt i din ordlista,
så se till att du förstår det.
Var noga med att inte bråka med det eller annars saker och ting inte kommer att köras.
>> Och huvuddelen av denna utmaning är för ni verkligen ändra dictionary.c.
Vi kommer att ge dig 140.000 ord i ordlistan.
Vi kommer att ge dig en text fil som har dessa ord,
och vi vill att du ska kunna organisera dem i en hash-tabell eller en trie
eftersom när vi ber dig att stava check-- tänk om du är spell
kontroll som Homeros Odysséen.
Det är så här stor, stor test.
>> Tänk om varje enskild ord du var tvungen att titta
genom en rad 140.000 värden.
Det skulle ta evigheter för din maskin att köra.
Det är därför vi vill organisera vår data till effektivare datastrukturer
såsom en hashtabell eller en trie.
Och då ni kan snäll av när du söker åtkomst
saker lättare och snabbare.
>> Och så var noga med att lösa kollisioner.
Du kommer att få ett gäng ord av att börja med A.
Du kommer att få en massa ord som börjar med B. Upp till dig
killar hur du vill lösa det.
Kanske det finns mer effektiv hash-funktion
än bara den första bokstaven i något, och så det är upp till dig
killar att sorts göra vad du vill.
>> Kanske du vill lägga till alla bokstäver tillsammans.
Kanske du vill gärna göra konstiga saker att redovisa antalet bokstäver,
vad som helst.
Upp till er hur ni vill göra.
Om du vill göra en hash-tabell, om du vill prova en trie, helt upp till dig.
Jag varnar dig i förväg att de Trie är typiskt lite svårare
bara för att det finns en hel del fler tips för att hålla reda på.
Men helt upp till er.
Det är betydligt mer effektivt i de flesta fall.
Du vill verkligen kunna hålla koll på alla dina tips.
Liksom gör samma sak som jag gjorde här.
När du försöker infoga värden i en hashtabell eller ta bort,
se till att du är verkligen hålla reda
där allt beror på det är verkligen lätt för om jag
försöker infoga som ordet, andy.
Låt oss bara säga att det är en riktigt ord, ord, andy,
till en gigantisk lista över A-ord.
>> Om jag råkar bara överlåta en pekare fel, oops,
Det går helhet resten av mitt länkad lista.
Nu är det enda ord jag har är andy, och nu
alla de andra orden i ordbok har gått förlorade.
Och så du vill vara säker på att du hålla reda på alla dina pekare
eller annat du kommer att få stora problem i koden.
Dra saker noggrant steg för steg.
Det gör det mycket lättare att tänka på.
>> Och slutligen, vill du kunna testa dina prestationer i ditt program
på den stora tavlan.
Om ni tar en titta på CS50 just nu,
vi har vad som kallas den stora styrelsen.
Det är matchprotokollet av de snabbast Stavningskontrollen gånger över hela CS50
just nu, jag tror att toppen som 10 gånger jag tror att åtta av dem är personal.
Vi vill verkligen att ni ska slå oss.
>> Alla av oss försökte genomföra den snabbaste koden som möjligt.
Vi vill att ni försöka utmana oss och genomföra snabbare än alla oss
Kan.
Och så detta är verkligen den första gången som vi är
frågar ni att göra en pset som du kan göra riktigt i vilken metod
du vill.
>> Jag säger alltid, det är mer besläktad till en verklig lösning, eller hur?
Jag säger, hej, jag vill att du gör det här.
Bygg ett program som gör detta för mig.
Gör det hur du vill.
Jag vet bara att jag vill snabbt.
Det är din utmaning för denna vecka.
Ni kommer vi för att ge dig en uppgift.
Vi kommer att ge dig en utmaning.
Och sedan är det upp till er att helt bara räkna ut
vad är det snabbaste och mest effektivt sätt att genomföra detta.
Ja?
>> PUBLIK: Är vi får om ville att forska snabbare sätt
att göra hashtabeller nätet, kan vi göra det och citera någon annans kod?
ANDI PENG: Ja, helt bra.
Så om ni läsa spec, det finns en rad
i spec som säger ni är helt gratis att forska hash
funktioner på vad är några av de snabbare hashfunktioner
att köra saker genom så länge du citerar denna kod.
Så en del människor har redan räknat ut snabbt sätt
att göra stavningskontroller, snabb sätt att lagra information.
Helt upp till er om ni vill bara ta det, eller hur?
Se till att du citerar.
Utmaningen här verkligen att vi försöker testa
är att se till att du vet din väg runt pekare.
Så långt du genomföra den faktiska hashfunktionen
och komma med liknande matten att göra det,
ni kan forska vad metoder på nätet ni vill.
Ja?
>> PUBLIK: Kan vi bara nämna genom att använda [OHÖRBAR]?
>> ANDI PENG: Ja.
Du kan bara i din kommentar Du kan citera som, oh,
tas från yadaen, bla, bla, hashfunktion.
Någon som har några frågor?
Vi faktiskt breezed genom sektion idag.
Jag kommer att vara här uppe till svara på frågor samt.
>> Dessutom, som jag sa, kontor timmar ikväll och i morgon.
Spec denna vecka är faktiskt super lätt och super kort för att läsa.
Jag skulle föreslå att ta en titt, bara läsa igenom hela det.
>> Och Zamyla faktiskt leder dig genom var och en av funktionerna
du behöver för att genomföra, och därför är det mycket, mycket tydligt hur man gör allt.
Bara för att se till att du är hålla reda på pekare.
Detta är en mycket utmanande pset.
>> Det är inte utmanande, eftersom liknande, oh, begreppen är så mycket mer
svårt, eller om du måste lära så mycket nytt syntax vägen
som du gjorde för den sista pset.
Denna pset är svårt eftersom det finns så många pekare,
och då är det väldigt lätt att åter du har en bugg i koden inte kunna
ta reda på var att fel är.
>> Och så komplett och fullkomlig tro på dig killar att kunna slå vår [OHÖRBAR]
stavningar.
Jag har faktiskt inte någon skriftlig gruva ännu, men jag kommer att skriva min.
Så medan du skriver yours, kommer jag att skriva min.
Jag ska försöka göra gruvan snabbare än din.
Vi får se vem som har den snabbaste.
>> Och ja, jag kommer att se alla ni här på tisdag.
Jag kommer att köra ett slag som en pset verkstad.
Alla avsnitt här vecka är PSET workshops,
så ni har massor av möjligheter för att få hjälp, öppettider som alltid,
och jag ser verkligen fram emot läsa alla dina killar "kod.
Jag har frågesporter upp här om du killar vill komma och hämta dem.
Det var allt.