[MUSIC SPILLE]
SPEAKER 1: All right.
Alle velkommen tilbake til seksjonen.
Jeg håper dere alle er vellykket utvinnes fra din quiz
fra forrige uke.
Jeg vet det er litt gal til tider.
Som jeg sa før, hvis du er innenfor standardavviket,
trenger egentlig ikke bekymre deg for det, spesielt for en mindre komfortable delen.
Det er omtrent der du skal være.
>> Hvis du gjorde bra, så fantastisk.
Kudos til deg.
Og hvis du føler at du trenger litt mer hjelp, kan du
gjerne nå ut til hvilken som helst av TFS.
Vi er alle her for å hjelpe.
>> Det er derfor vi underviser.
Det er derfor jeg er her hver mandag for deg gutter og på kontoret timer på torsdager.
Så kan du gjerne gi meg beskjed hvis du er bekymret for noe
eller om det er noe på quiz at du ville virkelig liker å ta opp.
>> Så dagsorden for i dag er alt om datastrukturer.
Noen av disse er bare kommer til å være like å få deg kjent med disse.
Du kan ikke noensinne implementere dem i denne klassen.
Noen av dem du vil, som for stavekontroll PSet.
>> Du vil ha ditt valg mellom hash tabeller og prøver.
Så vi definitivt kommer over dem.
Det kommer til å være definitivt mer av slag fra et høyt nivå seksjon dag, skjønt,
fordi det er mange av dem, og hvis vi gikk inn i gjennomføringen detaljer
på alle disse, ville vi ikke selv komme gjennom lenkede lister
og kanskje en liten bit av hash tabeller.
>> Så bærer med meg.
Vi kommer ikke til å gjøre så mye som koder dette tidspunktet.
Hvis du har noen spørsmål om det eller du ønsker å se det implementert
eller prøve det selv, Jeg anbefaler
kommer til å study.cs50.net, som har eksempler på at alle disse.
Det vil ha mine Powerpoints med notatene som vi
pleier å bruke, så vel som noen programmering øvelser, spesielt for ting
som lenkede lister og binære trær stabler og pekepinner.
Så litt mer høyt nivå, noe som kan være fint for dere.
>> Så med det, vil vi komme i gang.
Og også, yes-- quizer.
Jeg tror de fleste av dere som er i min seksjon har dine quizzer,
men noen kommer inn eller annen grunn ikke gjør det, de er rett her i front.
>> Så koblet lister.
Jeg vet at denne typen går å sikkerhets før quiz.
Det var uken før at vi har lært om dette.
Men i dette tilfellet, vil vi bare gå litt mer i dybden.
>> Så hvorfor kan vi velge et lenket liste over en rekke?
Hva skiller dem?
Ja?
>> PUBLIKUM: Du kan utvide en koblet liste versus en matrise er fast størrelse.
SPEAKER 1: Høyre.
En rekke har fast størrelse, mens en lenket liste har en variabel størrelse.
Så hvis vi ikke vet hvordan mye vi ønsker å lagre,
en lenket liste gir oss en god måte å gjøre det fordi vi kan bare
legge på en annen node og legge på annen node og legge på en annen node.
Men hva som kan være en trade-off?
Er det noen som husker den trade-off mellom arrays og koblede lister?
Mmhmm?
>> PUBLIKUM: Du må gå gjennom hele veien
gjennom lenket liste finne et element i en liste.
I en matrise, kan du bare finne et element.
>> SPEAKER 1: Høyre.
Så med arrays--
>> PUBLIKUM: [uhørlig].
>> SPEAKER 1: Med arrays, har vi det som kalles tilfeldig tilgang.
Betyr at hvis vi vil ha det som er gang den femte punktet i en liste
eller femte punktet i vår array, kan vi bare ta tak i det.
Hvis det er en lenket liste, har vi å iterere gjennom, ikke sant?
Så tilgang til et element i en matrise er konstant tid,
mens med en lenket liste ville det mest sannsynlig være lineær tid fordi kanskje
våre elementet er helt på slutten.
Vi må søke gjennom alt.
Så med alle disse dataene strukturer vi skal
til å tilbringe litt mer tid på, hva er de positive og negative.
Når kan vi ønsker å bruke en over den andre?
Og det er typen av større ting å ta unna.
>> Så vi har her Definisjonen av en node.
Det er som ett element i vår lenket liste, ikke sant?
Så vi er alle kjent med våre typedef structs,
som vi gikk over i en vurdering forrige gang.
Det var i utgangspunktet bare skape en annen datatype som vi kunne bruke.
>> Og i dette tilfellet, er det noen node som vil holde noen heltall i.
Og så hva er den andre delen her?
Anyone?
>> PUBLIKUM: [uhørlig].
>> SPEAKER 1: Yeah.
Det er en peker til den neste noden.
Så dette bør faktisk være her oppe.
Dette er en peker av typen node til neste ting.
Og det er det de omfatter vår node.
Cool.
>> All right, så med søket, som vi var bare si før hånd, hvis du er
kommer til å søke gjennom, du må faktisk iterere
gjennom lenket liste.
Så hvis vi ser for antall 9, ville vi starter på vårt hode
og som peker oss i begynnelsen av vår lenket liste, ikke sant?
Og vi sier, OK, gjør dette node inneholder tallet 9?
Nei?
>> All right, gå til den neste.
Følge den.
Betyr det inneholde nummer 9?
Nei.
Følg den neste.
>> Så vi må faktisk iterere gjennom vår lenket liste.
Vi kan ikke bare gå direkte til der 9 er.
Og hvis dere faktisk ønsker å se noen pseudo-kode der oppe.
Vi har noen søkefunksjonen her som tar in-- hva tar det inn?
Hva tror du?
Så enkel en.
Hva er dette?
PUBLIKUM: [uhørlig].
SPEAKER 1: Tallet vi leter etter.
Høyre?
Og hva ville dette tilsvare?
Det er en peker til?
>> PUBLIKUM: En node.
>> SPEAKER 1: En node til liste at vi ser på, ikke sant?
Så vi har noen noder er pekeren her.
Dette er et punkt som kommer til å faktisk iterere gjennom vår liste.
Vi setter den lik liste fordi det er bare
å sette den lik start av vår lenket liste.
>> Og mens det ikke er NULL, mens vi har fortsatt ting i vår liste,
sjekk for å se om det node har antallet vi leter etter.
Returnere true.
Ellers oppdatere den, ikke sant?
>> Hvis det er NULL, vi avslutter vår mens loop og return false
fordi det betyr at vi ikke har funnet den.
Har alle får hvordan det fungerer?
OK.
>> Så med innsetting, du har tre forskjellige måter.
Du kan foran, du kan legge til og du kan sette inn i assortert.
I dette tilfellet er vi kommer til å gjøre en foranstilt.
Vet noen hvordan de tre tilfeller kan avvike?
>> Så foranstilte betyr at du setter det på forsiden av listen.
Slik det ville bety at uansett hva din noden er, uansett
hva verdien er, du kommer for å si det rett her foran, OK?
Det kommer til å bli den første element i listen din.
>> Hvis du føyer det, kommer det til å gå til baksiden av listen.
Og sett inn assortert betyr at du er kommer til å sette faktisk inn i stedet
hvor den holder lenket liste sortert.
Igjen, hvordan du bruker de og når du bruker
dem vil variere avhengig av ditt tilfelle.
Hvis den ikke trenger å sorteres, har en tendens til foranstilte
å være hva folk flest bruke fordi du ikke
må gå gjennom hele listen å finne slutten for å legge den på, ikke sant?
Du kan bare stikke den rett i.
>> Så vi vil gå gjennom en innsetting en akkurat nå.
Så en ting som jeg kommer til å anbefaler på denne PSet
er å trekke ting ut, som alltid.
Det er veldig viktig at du oppdaterer dine pekere i riktig rekkefølge
fordi hvis du oppdaterer dem litt ute av drift,
du kommer til å ende opp miste deler av listen din.
>> Så for eksempel, i dette tilfellet, er vi forteller hodet for å bare peke til 1.
Hvis vi bare gjøre det uten å lagre dette en,
Vi aner ikke hva En skal peke til nå
fordi vi har mistet det hodet pekte på.
Så én ting å huske når du gjør en foranstilt
er å spare hva hode peker på først,
deretter overføre den, og deretter oppdatere hva din nye noden skal peke til.
I dette tilfellet, er dette en måte å gjøre det.
>> Så hvis vi hadde gjort det på denne måten der vi bare omplassert hodet,
vi mister i utgangspunktet vår hele listen, ikke sant?
En måte å gjøre det på er å ha en peker til neste, og så hodet punkt til 1.
Eller du kan gjøre typen som mellomlagring, som jeg snakket om.
>> Men reassigning din pekere i riktig rekkefølge
kommer til å bli veldig, veldig viktig for denne PSet.
Ellers kommer du til å ha en hash tabell eller en prøve som bare kommer til å være
bare en del av ordene som du ønsker og deretter you're-- mmhmm?
PUBLIKUM: Hva var den midlertidige oppbevarings ting du snakket om?
SPEAKER 1: Den midlertidige lagring.
Så i utgangspunktet en annen måten du kan gjøre dette
er lagre leder av noe, som lagre det midlertidig variabel.
Tilordne den til en og deretter oppdatere en å peke
til hvilken hodet brukes til å peke til.
På denne måten er åpenbart mer elegant fordi du
ikke trenger en midlertidig verdi, men bare tilby en annen måte å gjøre det.
Og vi faktisk har noen kode for dette.
Så for lenket liste, vi faktisk har noen kode.
Så setter du inn her, dette er prepending.
Så dette går den på hodet.
>> Så første, må du opprette den nye noden, selvfølgelig,
og se etter NULL.
Alltid godt.
Og så må du tilordne verdiene.
Når du oppretter en ny node, du vet ikke hva det peker til neste,
slik at du ønsker å initialisere den til NULL.
Hvis det ikke ender opp som peker til noe annet, det blir omplassert, og det er greit.
Hvis det er det første i listen, må det
å peke til NULL fordi det er slutten av listen.
>> Så da å sette den, ser vi her vi tilordner den neste verdien av vår node
å være hva hodet er, som er hva vi hadde her.
Det er det vi nettopp gjorde.
Og så skal vi tildele hodet til punkt til vår nye node, fordi husk,
nye er noen peker til en node, og det er akkurat hva hodet er.
Det er nettopp derfor vi har denne pilen tilbehør.
Cool?
Mmhmm?
>> PUBLIKUM: Må vi initial nye neste til NULL først,
eller kan vi bare initialisere den til hodet?
>> SPEAKER 1: Ny neste må være NULL å starte
fordi du ikke vet hvor det kommer til å bli.
Dessuten er denne type akkurat som et paradigme.
Du setter den lik NULL bare for å gjøre sikker på at alle baser er dekket
før du gjør noe omdisponering slik at du er alltid garantert at det vil
peke mot en bestemt verdi versus som en søppel verdi.
Fordi, ja, vi tildele nye neste automatisk,
men det er mer akkurat som en god praksis for å initialisere den
på den måten, og deretter overføre.
>> OK, så dobbelt knyttet lister nå.
Hva tror vi?
Hva er annerledes med Dobbelt knyttet lister?
>> Så i våre lenkede lister, kan vi bare bevege seg i en retning, ikke sant?
Vi har bare neste.
Vi kan bare gå fremover.
>> Med en dobbelt lenket liste, Vi kan også gå bakover.
Så vi har ikke bare tall som vi ønsker å lagre,
vi har der den peker til neste og hvor vi kom fra.
Så dette gir mulighet for noen bedre traversering.
>> Så dobbelt koblede noder, svært like, ikke sant?
Eneste forskjellen nå er vi har en neste og forrige.
Det er den eneste forskjellen.
>> Så hvis vi skulle foran eller append-- vi har ikke noen kode for dette opp her--
men hvis du skulle prøve og sett det, det viktigste
er du trenger å gjøre at du tilordner
både den forrige og din neste pekeren riktig.
Så i dette tilfellet, ville du ikke bare initial neste,
du initial forrige.
Hvis vi er på hodet av listen, vi vil ikke bare gjøre hodet lik nye,
men vår nye forrige bør peker mot hodet, ikke sant?
>> Det er den eneste forskjellen.
Og hvis du vil ha mer praksis med disse med lenkede lister, med innsetting,
med å slette, med innlegg inn en assortert listen,
kan du sjekke ut study.cs50.net.
Det er en haug med flotte øvelser.
Jeg anbefaler dem.
Jeg skulle ønske vi hadde tid til å gå gjennom dem men det er mye av datastrukturer
å komme gjennom.
>> OK, så hash tabeller.
Dette er sannsynligvis den mest nyttig bit for din PSet
her fordi du kommer til å være implementere en av disse, eller en prøve.
Jeg liker hash tabeller.
De er ganske kult.
>> Så i utgangspunktet hva skjer er en hash table
er når vi virkelig trenger rask innsetting, sletting, og oppslag.
De er de tingene som vi er prioritering i en hash table.
De kan bli ganske store, men som vi skal se med prøver,
det er ting som er mye større.
>> Men innerst inne, alt en hash Tabellen er en hash-funksjon
som forteller deg hvilken bøtte å sette hver av dine data, hver av elementene i.
En enkel måte å tenke på en hash table er at det er bare bøtter med ting,
ikke sant?
Så når du sorterer ting ved som den første bokstaven i navnet sitt,
det er litt som en hash table.
>> Så hvis jeg skulle gruppen dere er inn i grupper på hvem navn starter
med A over her, hvem er eller bursdag er i januar, februar, mars,
uansett, er at effektivt skape en hash table.
Det er bare å lage bøtter som du sortere elementer inn
slik at du kan finne dem lettere.
Så denne måten når jeg trenger å finne en av dere,
Jeg trenger ikke å søke gjennom hver av navnene dine.
Jeg kan være som, oh, jeg vet at Danielle bursdag er in--
PUBLIKUM: --April.
SPEAKER 1: April.
Så jeg ser i min april bøtte, og med litt hell,
hun vil være den eneste der og min tid var konstant i den forstand,
mens hvis jeg må se gjennom en hel haug med folk,
det kommer til å ta mye lengre tid.
Så hash tabeller er egentlig bare bøtter.
Enkel måte å tenke på dem.
>> Så en veldig viktig ting om en hash table er en hash-funksjon.
Så de tingene jeg nettopp har snakket om, som den første bokstaven i fornavnet ditt
eller bursdagen din måned, disse er ideer som
virkelig relatere til en hash-funksjon.
Det er bare en måte å bestemme hvilke bøtte deg er element går inn, OK?
Så for denne PSet, kan du slå opp stort sett alle hash-funksjon du vil.
>> Trenger ikke å være din egen.
Det er noen virkelig kule seg ut det som gjør alle slags sprø matematikk.
Og hvis du ønsker å gjøre din stavekontroll super rask,
Jeg ville definitivt ser inn i en av disse.
>> Men det finnes også enkle reglene, som databehandlings
summen av ord, som hver bokstav har en rekke.
Beregn summen.
Som bestemmer bøtte.
De har også de enkle de som er akkurat som alle A her,
alle B her.
Hvilken som helst av disse.
>> I utgangspunktet, det bare forteller deg hvilke matrise indeksere element bør gå inn.
Bare bestemmer bucket-- det er alt en hash-funksjon er.
Så her har vi et eksempel som er bare den første bokstaven i strengen
at jeg bare snakker om.
>> Så du har litt hasj det er bare første bokstaven i strengen minus A,
som vil gi deg litt tall mellom 0 og 25.
Og hva du ønsker å gjøre er sørge for at dette representerer
størrelsen på hash table-- hvor mange bøtter er det.
Med mange av disse hash funksjoner, de er
kommer til å være tilbake verdier som kanskje være langt over antall bøtter
at du faktisk har i hash table,
så du trenger å gjøre sikker og mod av dem.
Ellers kommer det til å si, oh, bør det være i bøtte 5000
men du har bare 30 bøtter i din hash table.
Og selvfølgelig, vi alle vet at det er kommer til å resultere i noen sprø feil.
Så sørg for å mod av størrelsen på hash table.
Cool.
Så kollisjoner.
Er alle bra så langt?
Mmhmm?
>> PUBLIKUM: Hvorfor skulle det returnere en slik massiv verdi?
>> SPEAKER 1: Avhengig av algoritmen at hash-funksjon bruker.
Noen av dem vil gjøre gal multiplikasjon.
Og det handler om å få en jevn fordeling,
slik de gjør noen virkelig gale ting noen ganger.
Det er alt.
Noe mer?
OK.
>> Så kollisjoner.
I utgangspunktet, som jeg sa tidligere, i beste fall,
noen bøtte jeg se nærmere på er kommer til å ha en ting,
så jeg trenger ikke å se i det hele tatt, ikke sant?
Jeg enten vet det er der, eller det er ikke, og det er det vi egentlig ønsker.
Men hvis vi har titusenvis av datapunkter og mindre enn det antall
av bøtter, kommer vi til å ha kollisjoner der til slutt noe
er nødt til å ende opp i en bøtte som allerede har et element.
>> Så spørsmålet er, hva gjør vi i så fall?
Hva gjør vi?
Vi har allerede noe der?
Har vi bare kaste den ut?
>> Nei.
Vi må holde dem begge.
Så den måten at vi vanligvis gjør som er hva?
Hva er datastrukturen vi nettopp snakket om?
PUBLIKUM: Linked-listen.
SPEAKER 1: En lenket liste.
Så nå, i stedet for hver av disse bøtter bare ha ett element,
det kommer til å inneholde en lenket liste over de elementer som ble hashed inn i den.
OK, gjør alle slags få den ideen?
Fordi vi ikke kunne ha en matrise fordi vi ikke vet hvor mange ting
kommer til å være der.
En lenket liste tillater oss å ha bare det nøyaktige antallet som
er hashet til at bøtte, ikke sant?
>> Så lineær sonder er utgangspunktet denne idea--
det er en måte å håndtere en kollisjon.
Det du kan gjøre er hvis, i dette tilfelle, bær ble hashet inn en
og vi har allerede noe der, du bare
holde det gående ned til du finner en tom plass.
Det er en måte å håndtere det.
Den andre måten å håndtere det er med det vi nettopp
called-- den koblede Listen kalles kjeding.
>> Så denne ideen fungerer hvis din hash table du tror
er mye større enn dataene satt, eller hvis du
ønsker å prøve og minimere kjeding før det er absolutt nødvendig.
Så en ting er lineær sondering åpenbart betyr
at hash-funksjon er ikke fullt så nyttig
fordi du kommer til å ende opp med å bruke din hash-funksjon, å komme til et punkt,
du lineær sonde ned til et sted som er tilgjengelig.
Men nå, selvfølgelig, noe annet som ender opp der,
du er nødt til å søke enda lenger nede.
>> Og det er mye mer Søke utgift som
går inn å legge inn et element i hash table nå, ikke sant?
Og nå når du går og prøve og finne bær igjen, du kommer til hasj det,
og det kommer til å si, oh, se i bøtte 1,
og det kommer ikke til å være i bøtte en, slik at du er
nødt til å traversere gjennom resten av disse.
Så det er noen ganger nyttig, men i de fleste tilfeller
vi kommer til å si at kjeding er hva du ønsker å gjøre.
>> Så vi snakket om dette tidligere.
Jeg fikk litt foran meg selv.
Men kjeding er utgangspunktet at hver bøtte i hash table
er bare en lenket liste.
>> Så en annen måte, eller mer teknisk måten å tenke på en hash table
er at det er bare en matrise av lenkede lister, som
når du skriver ordbok og du prøver å laste den,
tenker på det som en utvalg av lenkede lister
vil gjøre det mye lettere for deg å initialisere.
>> PUBLIKUM: Så hash table har en forutbestemt størrelse,
som en [uhørbart] bøtter?
>> SPEAKER 1: Høyre.
Så det har et gitt antall bøtter som du determine--
som dere bør gjerne spille med.
Det kan være ganske kult å se hva som skjer
som du endrer antall bøtter.
Men ja, det har en satt antall bøtter.
Hva gjør du for å passe så mange elementer som du trenger
og er en egen kjeding der du har knyttet lister i hver bøtte.
Det betyr at hash table vil være nøyaktig den størrelsen
at du trenger det for å være, ikke sant?
Det er hele poenget med lenkede lister.
Cool.
>> Så alle OK det?
OK.
Ah.
Hva skjedde?
Virkelig nå.
Gjett noen dreper meg.
>> OK vi kommer til å gå inn prøver, som er litt gal.
Jeg liker hash tabeller.
Jeg tror de er veldig kult.
Prøver er kult, også.
>> Så er det noen som husker hva en prøve er?
Du bør ha gått over det kort på forelesning?
Husker slags hvordan det fungerer på?
PUBLIKUM: Jeg bare nikker at vi gikk over den.
SPEAKER 1: Vi går over det.
OK, vi virkelig kommer til å gå over det nå er hva vi sier.
>> PUBLIKUM: Det er for en henting treet.
>> SPEAKER 1: Yeah.
Det er en henting treet.
Awesome.
Så en ting å legge merke til her er at vi ser på enkelttegn
her, ikke sant?
>> Så før med vår hash-funksjon, vi var ute på ordene som helhet,
og nå ser vi mer på karakterene, ikke sant?
Så vi har Maxwell over her og Mendel.
Så i utgangspunktet en try-- en måte å tenke om dette er at alle nivåer her
er en rekke bokstaver.
Så dette er din rotnoden her, ikke sant?
Dette har alle tegnene i alfabetet for starten av hvert ord.
>> Og hva du ønsker å gjøre er si, OK, har vi noen M ord.
Vi kommer til å lete etter Maxwell, så vi går til M. Og M poeng til en helhet
andre en matrise der hver ord, så lenge der
er et ord som har A som den andre bokstaven,
så lenge det er et ord som har B som det andre brevet,
det vil ha en peker gå til noen neste array.
>> Det er nok ikke en ord som MP noe,
så på P posisjon i dette array, ville det bare være NULL.
Det vil si, OK, det er ingen ord som har M etterfulgt av en P, OK?
Så hvis vi tenker på det, hver en av disse mindre ting
er faktisk en av disse store matriser fra A til Z.
Så hva kan være en av de tingene som er en slags ulempe med en prøve?
>> PUBLIKUM: Mye minne.
>> SPEAKER 1: Det er massevis av minne, ikke sant?
Hver av disse blokkene her representerer 26 plasser, 26 element array.
Så prøver får utrolig plass tung.
>> Men de er veldig fort.
Så utrolig fort, men virkelig plass ineffektiv.
Slags må finne ut hvilken du vil ha.
Dette er skikkelig kult for din PSet, men de tar opp mye minne,
slik at du bytter ut.
Yeah?
>> PUBLIKUM: Ville det være mulig å sette opp en prøve, og deretter
når du har all data i det at du need--
Jeg vet ikke om det ville være fornuftig.
Jeg begynte å bli kvitt alle NULL tegn, men deretter
du ville ikke være i stand til å indeksere them--
>> SPEAKER 1: Du fortsatt trenger dem.
>> PUBLIKUM: - på samme måte hver gang.
SPEAKER 1: Yeah.
Du trenger NULL tegn til å la vet du om det er ikke et ord der.
Ben hadde du noe du ønsker?
OK.
Greit, så vi kommer å gå litt mer
inn i tekniske detaljer bak en prøve og jobbe gjennom et eksempel.
>> OK, så dette er den samme.
Mens det i en lenket liste, vår viktigste slag of-- hva er ordet jeg vil? -
som å bygge blokken var en node.
I en prøve, har vi også en node, men det er definert ulikt.
>> Så vi har litt bool som representerer enten et ord faktisk
Det finnes på dette stedet, og deretter vi har noen matrise her-- eller rettere sagt,
Dette er en peker til en utvalg av 27 tegn.
Og dette er for, i dette tilfelle, denne 27-- Jeg er sikker på at dere alle er like, vent,
det er 26 bokstaver i alfabetet.
Hvorfor har vi 27?
>> Så, avhengig av måten du implementerer denne,
dette er fra en PSet som tillatt for apostrofer.
Så det er derfor ekstra en.
Du vil også ha i noen tilfeller null terminator
er inkludert som ett av tegn på at det er tillatt å være,
og det er hvordan de kontrollerer se om det er på slutten av ordet.
Hvis du er interessert, sjekk ut Kevins video på study.cs50,
samt Wikipedia har noen gode ressurser der.
>> Men vi kommer til å gå gjennom bare slags på hvordan du kan arbeide gjennom en prøve
hvis du får en.
Så vi har en super enkel en her at har ordene "bat" og "zoom" i dem.
Og som vi ser her oppe, denne lille plassen her
representerer vår bool som sier, ja, dette er et ord.
Og så dette har vår matriser av tegn, ikke sant?
>> Så vi kommer til å gå gjennom å finne "bat" i denne prøve.
Så begynner på toppen, ikke sant?
Og vi vet at b tilsvarer den andre indeks, det andre elementet
i denne matrise, fordi a og b.
Så omtrent den andre.
>> Og den sier, OK, kult, følger det inn neste rekke, fordi hvis vi husker,
det er ikke slik at hver av disse faktisk inneholder elementet.
Hver og en av disse matriser inneholder en peker, ikke sant?
Det er et viktig skille å gjøre.
>> Jeg vet at dette kommer til å be-- prøver er veldig vanskelig å få på første gang,
slik at selv om dette er andre eller tredje gang
og det er fortsatt en slags for å virke vanskelig,
Jeg lover hvis du går watch kort igjen i morgen,
det vil sannsynligvis gjøre mye mer fornuftig.
Det tar mye å fordøye.
Jeg fortsatt noen ganger er lignende, vent, hva er en prøve?
Hvordan bruker jeg dette?
>> Derfor har vi B i dette tilfellet som er vår andre indeksen.
Hvis vi hadde, sier, c eller d eller hvilken som helst annen bokstav,
vi trenger å kartlegge det tilbake til indeksen av vår matrise som som svarer til.
Så vi ville ta like rchar og vi bare trekke ut en å kartlegge det inn 0-25.
Alle gode hvordan vi kartlegge vår karakter?
OK.
>> Så vi går til den andre, og vi se at, ja, det er ikke til NULL.
Vi kan gå videre til dette neste array.
Så vi går videre til dette neste rekke her.
>> Og vi sier, OK, nå er vi trenger å se om en er her.
Er en null eller gjør det faktisk gå videre?
Så en faktisk flytter fremover i denne matrisen.
Og vi sier, OK, t er vår siste bokstav.
Så vi går til t på indeksen.
Og da vi beveger oss fremover fordi det er en annen.
Og dette sier i utgangspunktet at, ja, det står at det er et ord her--
at hvis du følger denne banen, har du kommet
på et ord, som vi vet er "bat".
Ja?
>> PUBLIKUM: Er det vanlig å ha det som indeks 0 og deretter har en slags 1
eller til å ha på slutten?
>> SPEAKER 1: Nei.
Så hvis vi ser tilbake på vår erklæring her, er det en bool,
så det er et eget element i node.
Så det er ikke en del av tabellen.
Cool.
Så når vi er ferdige med ord og vi er på denne matrisen, hva vi ønsker å gjøre
er å gjøre en sjekk for dette er et ord.
Og i dette tilfellet, ville det tilbake ja.
>> Så på dette notatet, vet vi at "zoo" - vi kjenner som mennesker at "zoo" er et ord,
ikke sant?
Men er prøve her ville si, nei, det er ikke det.
Og det vil si at fordi vi har ikke utpekt det som et ord her.
Selv om vi kan traversere gjennom til denne matrisen,
dette prøve vil si at, nei, Dyrehagen er ikke i ordboken
fordi vi ikke har utpekt det som sådan.
>> Så en måte å gjøre at-- oh, sorry, denne.
Så i dette tilfellet, er ikke "zoo" et ord, men det er i vår prøve.
Men i denne, sier vi vil ha det introdusere ordet "bad", hva skjer
er vi følger through-- b, a, t.
Vi er i denne tabellen, og vi går for å søke etter h.
>> I dette tilfellet, når vi se på pekeren på h,
den peker til NULL, OK?
Så med mindre det er uttrykkelig peker til en annen array,
du antar at alle pekere i denne matrisen peker til null.
Slik at i dette tilfellet, er H peker til null, slik at vi ikke kan gjøre noe,
slik at det ville også returnere usant, "bad" er ikke her inne.
Så nå er vi faktisk kommer til å gå gjennom
hvordan ville vi faktisk si at "zoo" er i våre forsøk.
Hvordan setter vi "zoo" inn i vårt forsøk?
Så på samme måte som vi startet med vår lenket liste, starter vi ved roten.
Når du er i tvil, starter på roten av disse tingene.
>> Og vi vil si, OK, z.
z eksisterer i dette, og det gjør det.
Så du går videre til din neste array, OK?
Og deretter på den neste, vi sier, OK, ikke eksisterer o?
Det gjør.
Dette igjen.
>> Og så på vår neste, har vi sagt, OK, allerede eksisterer "zoo" her.
Alt vi trenger å gjøre er å sette denne lik til sann, at det er et ord der.
Hvis du hadde fulgt alt opp til før det punktet,
det er et ord, så bare sette den lik slike.
Ja?
>> PUBLIKUM: Så da gjør det mener at "ba" er et ord også?
>> SPEAKER 1: Nei.
Så i dette tilfellet, "ba" vi ville få her, ville vi si det er et ord,
og det vil fortsatt være noen.
OK?
Mmhmm?
>> PUBLIKUM: Så når du er det en ord, og du sier ja, så er det
vil inneholde for å gå til m?
>> SPEAKER 1: Så dette har å gjøre with-- du legger dette på.
Du sier "zoo" er et ord.
Når du går til check-- liker, si at du ønsker å si,
betyr "zoo" eksisterer i dette ordbok?
Du bare kommer til å søke etter "zoo", og deretter sjekke for å se om det er et ord.
Du kommer aldri til å flytte gjennom til m, fordi det er ikke
det du leter etter.
>> Så hvis vi faktisk ønsket å legge til "bad" i denne prøve,
Vi ville gjøre det samme som vi gjorde med "zoo",
bortsett fra at vi ville se at når vi prøve og få til h, betyr det ikke eksisterer.
Så du kan tenke på dette som prøver å legge til en ny node i en lenket liste,
så vi måtte legge til en annen en av disse matriser, som så.
Og så det vi gjør er vi bare sette h element i denne matrise peker til dette.
>> Og så hva ville vi ønsker å gjøre her?
Legg det lik sant fordi det er et ord.
Cool.
Jeg vet.
Prøver er ikke den mest spennende.
Stol på meg, jeg vet.
>> Så én ting å realisere med forsøk, Jeg sa, de er svært effektive.
Så vi har sett de ta opp massevis av plass.
De er slags forvirrende.
Så hvorfor skulle vi noen gang bruke disse?
Vi bruker disse fordi de er utrolig effektiv.
>> Så hvis du noen gang ser opp et ord, er du bare
avgrenset av lengden av ordet.
Så hvis du leter etter en ord som er lengden av fem,
du er bare noen gang nødt til å gjøre på de fleste fem sammenligninger, OK?
Så det gjør det i utgangspunktet en konstant.
Som innsetting og oppslag er stort sett konstant tid.
>> Så hvis du noen gang kan få noe i konstant tid,
det er så godt som det blir.
Du kan ikke bli bedre enn konstant tid for disse tingene.
Så det er en av store plusser prøver.
>> Men det er mye plass.
Så du slags må bestemme hva er mer viktig for deg.
Og på dagens datamaskiner, i plass som et forsøk kan ta opp
kanskje ikke påvirker deg så mye, men kanskje
du arbeider med noe som har langt, langt flere ting,
og en prøve er bare ikke rimelig.
Ja?
>> PUBLIKUM: Vent, så du har 26 bokstaver i hver eneste en?
>> SPEAKER 1: Mmhmm.
Ja, du har 26.
Du har noen er ordet markør, og deretter har du 26 tips i hver eneste en.
Og de er point--
>> PUBLIKUM: Og hver 26, gjør de hver har 26?
>> SPEAKER 1: Ja.
Og det er derfor, som du kan se, det utvider seg ganske raskt.
OK.
Så vi kommer til å komme inn i trær, som Jeg føler er lettere og vil trolig
være en fin liten utsettelse fra forsøk der.
Så forhåpentligvis de fleste av dere har sett et tre før.
Ikke som den vakre de utenfor, som jeg
vet ikke om noen gikk ute nylig.
Jeg gikk apple plukke denne helgen, og oh my gosh, det var vakkert.
Jeg visste ikke blader kunne se at pen.
>> Så dette er bare et tre, ikke sant?
Det er bare noen node, og det peker på en haug med andre noder.
Som du ser her, er dette slag av en tilbakevendende tema.
Noder peker til noder er slags essensen av mange datastrukturer.
Det avhenger bare av hvordan vi få dem til å peke til hverandre
og hvordan vi traversere gjennom dem og hvordan vi
sette inn ting som avgjør deres forskjellige egenskaper.
>> Så bare noen terminologi, som jeg har brukt før.
Så rot er det som er på toppen.
det er der vi alltid starte.
Du kan tenke på det som hodet også.
Men for trær, har vi en tendens til å referere til det som roten.
>> Noe nederst her-- på veldig, veldig bottom--
er ansett blader.
Så det går sammen med Hele tre ting, ikke sant?
Bladene er på kantene av treet.
>> Og så har vi også et par vilkårene for å snakke om noder i forhold
til hverandre.
Så vi har forelder, barn og søsken.
Så i dette tilfellet er det tre forelder til 5, 6 og 7.
Så foreldrene er det som er ett skritt over hva du er
refererer til, så bare som et familietre.
Forhåpentligvis er dette alt litt litt mer intuitivt enn prøver.
>> Søsken er noen som har samme overordnede, ikke sant?
De er på samme nivå her.
Og så, som jeg var sier, barn er bare
hva er ett skritt nedenfor noden i spørsmålet, OK?
Cool.
Så et binært tre.
Kan noen gjette på en av egenskapene til den binære treet?
>> PUBLIKUM: Maks to blader.
>> SPEAKER 1: Høyre.
Så maks to blader.
Så i dette før, hadde vi denne ene som hadde tre, men i et binært tre,
du har en maks to barn per forelder, ikke sant?
Det er en annen interessant trekk.
Vet noen det?
Binærtre.
>> Så et binært tre vil ha alt på the-- dette er ikke sorted--
men i en sortert binært tre, alt på høyre
er større enn moder, og alt på venstre
er mindre enn moder.
Og det har vært en quiz spørsmålet før, så godt å vite.
Så måten vi definerer dette, igjen, har vi en annen node.
Dette ser veldig likt det?
Dobbelt
>> Målgruppe: Linked lister
>> SPEAKER 1: Et dobbelt lenket liste, ikke sant?
Så hvis vi erstatte denne med forrige og neste år,
Dette ville være en dobbelt lenket liste.
Men i dette tilfellet, vi faktisk har venstre og høyre og det er det.
Ellers er det akkurat det samme.
Vi har fortsatt elementet du leter etter,
og du bare har to pekere kommer til hva som er neste.
Ja, så binært søketre.
Hvis vi legger merke til, alt på akkurat her er større than--
eller alt umiddelbart til høyre her
er større enn, alt her er mindre enn.
>> Så hvis vi skulle søke gjennom, det bør se svært nær binære søk
her, ikke sant?
Bortsett fra i stedet for å se til halve array,
vi bare ser på enten venstre side eller den høyre side av treet.
Så det blir litt enklere, tror jeg.
>> Så hvis din rot er NULL, tydeligvis er det bare falsk.
Og hvis det er det, selvsagt det er sant.
Hvis det er mindre enn, søk vi til venstre.
Hvis det er større enn, vi søker den rette.
Det er akkurat som binære søk, bare en forskjellig datastruktur
som vi bruker.
I stedet for en matrise, det er bare et binært tre.
>> OK, stabler.
Og også, ser det ut som vi kan ha en liten bit av gangen.
Hvis vi gjør det, er jeg glad for å gå over noen av dette igjen.
OK, stabler det.
Er det noen som husker hva stacks-- noen kjennetegn ved en stabel?
>> OK, så de fleste av oss, tror jeg, spise i spise halls--
så mye som vi kanskje ikke liker det.
Men selvsagt, kan du tenke på en stabel bokstavelig talt bare som en stabel med magasiner
eller en stabel av ting.
Og det som er viktig å innse er at det er
something-- den karakteristiske som vi kaller det by-- er LIFO.
Vet noen hva det står for?
Mmhmm?
>> PUBLIKUM: sist inn, først ut.
>> SPEAKER 1: Høyre, sist inn, først ut.
Så hvis vi vet, hvis vi stable ting opp, til den enkleste ting ta off--
og kanskje det eneste vi kan hente av hvis stacken er stor enough--
er at øverste element.
Så uansett hva ble satt på last-- som vi ser her,
hva ble presset på de fleste recently-- er
kommer til å bli den første ting som vi pop off, OK?
>> Så det vi har her er annen typedef struct.
Dette er egentlig bare som en lynkurs i datastrukturen,
så det er mye kastet på dere.
Jeg vet.
Så enda en struct.
Yay for strukturer.
>> Og i dette tilfellet, er det noen peker til en matrise som har en viss kapasitet.
Så dette representerer vår stack her, som vår faktiske matrise
som holder våre elementer.
Og så her har vi en viss størrelse.
>> Og vanligvis, vil du holde styr på hvor stor stabel din er
fordi hva det kommer til å tillate deg å gjøre er hvis du vet størrelsen,
det tillater deg å si, OK, jeg er på kapasitet?
Kan jeg legge til noe mer?
Og det forteller deg også der toppen av stabelen din
er slik at du vet hva du faktisk kan ta av.
Og det er faktisk kommer til å være litt mer tydelig her.
>> Så for push, en ting, hvis du var stadig å implementere push,
som jeg bare sa, din stack har en begrenset størrelse, ikke sant?
Vårt utvalg hadde en viss kapasitet.
Det er en matrise.
Det er en fast størrelse, så vi trenger å sørge for at vi ikke setter mer
inn i vårt utvalg enn vi faktisk har plass til.
>> Så når du oppretter en push funksjon, første du gjør er å si, OK,
har jeg plass i bunken min?
Fordi hvis jeg ikke gjør det, beklager, Jeg kan ikke lagre ditt element.
Hvis jeg gjør det, så du vil lagre den på toppen av bunken, ikke sant?
>> Og dette er grunnen til at vi har å holde orden på vår størrelse.
Hvis vi ikke holder orden på vår størrelse, vi vet ikke hvor du skal plassere den.
Vi vet ikke hvor mange ting er i vårt utvalg allerede.
Som åpenbart finnes det måter at kanskje du kunne gjøre det.
Du kan initialisere alt til NULL og deretter se etter den nyeste NULL,
men en mye enklere ting er bare å si, OK, holde styr på størrelse.
Som jeg vet at jeg har fire elementer i mitt utvalg, slik at den neste tingen
at vi satt på, vi er skal lagre på index 4.
Og så, betyr selvfølgelig dette at du har lastet skjøvet noe
på stabelen din, du ønsker å øke størrelsen
slik at du vet hvor du er så at du kan skyve flere ting på.
>> Så hvis vi prøver å pop noe av stabelen,
hva som kan være det første at vi ønsker å se etter?
Du prøver å ta noe av stabelen din.
Er du sikker på at det er noe i bunken din?
Nei.
Så hva kan vi ønsker å sjekke?
>> PUBLIKUM: [uhørlig].
SPEAKER 1: Sjekk for størrelsen?
Størrelse.
Så vi ønsker å sjekke for å se om vår størrelse er større enn 0, OK?
Og hvis det er, så vi ønsker å redusere vår størrelse med 0 og returnere det.
Hvorfor?
>> I det første ble en vi skyve, dyttet den vi
på størrelse og deretter oppdateres størrelse.
I dette tilfellet er vi minske størrelsen og deretter ta den av, plukker det
fra vår array.
Hvorfor kan vi gjøre det?
Så hvis jeg har en ting på min stabel, hva ville være min størrelse på det tidspunktet?
1.
>> Og hvor er elementet en lagret?
På hvilken indeks?
PUBLIKUM: 0.
SPEAKER 1: 0.
Så i dette tilfelle vi alltid trenger å gjøre sure--
stedet for å returnere størrelse minus 1, fordi vi
vet at våre elementet er kommer til å bli lagret på en mindre
hva vår størrelse er dette bare tar vare på den.
Det er en litt mer elegant måte.
Og vi bare minske vår størrelse og deretter returnere størrelse.
Mmhmm?
>> PUBLIKUM: Jeg antar bare generelt, Hvorfor skulle dette datastruktur
være gunstig?
>> SPEAKER 1: Det avhenger av konteksten.
Så for noen av teorien, hvis du arbeider with-- OK,
la meg se om det er en gunstig ett som er fordelaktig til mer enn utenfor
av CS.
Med stabler, helst du trenger å holde styr på noe som
er den mest nylig lagt til er når du kommer til å ønske å bruke en stabel.
>> Og jeg kan ikke tenke på en god eksempel på det akkurat nå.
Men når den siste ting er viktigst for deg,
det er da en stabel kommer til å være nyttig.
Jeg prøver å tenke hvis det er en god en for dette.
Hvis jeg tenker på et godt eksempel i neste 20 minutter, vil jeg definitivt si deg.
>> Men alt i alt, hvis det er noe, som jeg sa de fleste, der siste
er viktigst, det er der en stabel kommer inn i bildet.
Mens køene er slags motsatt.
Og alle de små hundene.
Er ikke dette bra, ikke sant?
Jeg føler at jeg burde bare har en kanin video
rett i midten av seksjon for dere
fordi dette er en intens delen.
>> Så en kø.
I utgangspunktet er en kø som en linje.
Dere Jeg er sikker bruk dette hver dag, akkurat som i våre spisesaler.
Så vi må gå i og få våre skuffer, jeg er
at du må vente i kø å sveipe eller få mat.
>> Så forskjellen her er at dette er FIFO.
Så hvis LIFO ble sist inn, først ut, er FIFO først inn, først ut.
Så det er her hva du putter på først er din viktigste.
Så hvis du har ventet i en line-- kan du
tenk hvis du gikk til gå få den nye iPhone
og det var en stabel der siste personen i kø fikk det først,
folk ville drepe hverandre.
>> Så FIFO, vi er alle veldig kjent med i den virkelige verden her,
og det hele har å gjøre med faktisk slags gjenskape hele denne linjen
og kø struktur.
Så mens med stabelen, vi har push og pop.
Med en kø, har vi enqueue og dequeue.
Så enqueue utgangspunktet betyr sette den inn på baksiden,
og dequeue del ta ut fra forsiden.
Så vår datastruktur er en litt mer komplisert.
Vi har en annen ting å holde styr på.
>> Så uten hode, denne er akkurat en stabel, ikke sant?
Dette er den samme struktur som en stabel.
Det eneste annerledes nå er vi har dette hodet, som hva tror du
kommer til å holde styr på?
>> PUBLIKUM: Den første.
>> SPEAKER 1: Høyre, den første at vi satt i.
Lederen for vår køen.
Den som er først i køen.
All right, så hvis vi gjør enqueue.
Igjen, med hvilken som helst av Disse datastrukturer,
siden vi har å gjøre med en matrise, vi trenger å sjekke om vi har plass.
>> Dette er typen som meg forteller dere, hvis du åpner en fil,
du må sjekke for null.
Med noen av disse stabler og køer, må du
for å se om det er plass fordi vi er arbeider med en fast størrelse array,
som vi ser her-- 0, 1 helt opp til 5.
Så det vi gjør i dette tilfellet er sjekk for å se om vi fortsatt har plass.
Er vår størrelse mindre enn kapasiteten?
>> I så fall må vi lagre den på halen og vi oppdaterer vår størrelse.
Så hva kan halen være i dette tilfellet?
Det er ikke eksplisitt skrevet ut.
Hvordan ville vi lagre det?
Hva ville halen være?
>> Så la oss gå gjennom dette eksemplet.
Så dette er en matrise av størrelse 6, ikke sant?
Og vi har akkurat nå, er vår størrelse 5.
Og når vi setter det i, det kommer å gå inn i den femte indeksen, ikke sant?
Så lagre på halen.
>> En annen måte å skrive halen ville bare være vårt utvalg på indeks for størrelsen, ikke sant?
Dette er størrelse 5.
Neste ting kommer til å gå inn i fem.
Cool?
OK.
Det blir litt mer komplisert når vi begynner å rote med hodet.
Ja?
>> PUBLIKUM: Betyr det at vi ville ha erklært en matrise som
var fem elementer lang og da vi legger på det?
>> SPEAKER 1: Nei.
Så i dette tilfelle, er dette en stabel.
Dette ville bli erklært som en matrise av størrelse 6.
Og i dette tilfellet, vi har bare én plass til venstre.
>> OK, så en ting er i dette tilfelle, hvis hodet er på 0,
da vi bare kan legge den på størrelse.
Men det blir litt mer komplisert fordi faktisk, de
ikke har et lysbilde for dette, så jeg kommer
å trekke en fordi det ikke er fullt så enkelt når du
begynne å bli kvitt ting.
Så mens med en stabel du bare trenger
å bekymre deg for hva størrelsen er når du legger noe på,
med en kø må du også gjøre sikker på at hodet ditt er regnskapsført,
fordi en kul ting om køer er at hvis du ikke er på kapasitet,
du kan faktisk gjøre det brytes rundt.
>> OK, så en thing-- oh, Dette er forferdelig kritt.
En ting å vurdere er tilfelle.
Vi vil bare gjøre fem.
OK, så vi kommer til å si hodet er her.
Dette er 0, 1, 2, 3, 4.
>> Hodet er der, og Vennligst ha ting i dem.
Og vi ønsker å legge noe i, ikke sant?
Så ting som vi trenger for å vet er at hodet er alltid
kommer til å flytte denne måten og deretter sløyfe tilbake rundt, OK?
>> Så denne køen har plass, ikke sant?
Den har plass i begynnelsen, slag av det motsatte av dette.
Så det vi trenger å gjøre, er vi trenger å beregne halen.
Hvis du vet at din hodet har ikke flyttet, hale
er bare din matrise på indeksen av størrelsen.
>> Men i virkeligheten, hvis du bruker en kø, hodet er trolig blir oppdatert.
Så hva du trenger å gjøre er faktisk beregne halen.
Så det vi gjør er denne formelen her, som jeg kommer til å la deg
gutta tenke på, og så får vi snakke om det.
Så dette er kapasiteten.
>> Så dette vil faktisk gi deg en måte å gjøre det.
Fordi i dette tilfelle, hva?
Vårt hovedkontor er på 1, er vår størrelse fire.
Hvis vi mod som med 5, får vi 0, som er der vi skal legge den inn.
>> Så deretter i det neste tilfelle, hvis vi skulle gjøre dette,
vi sier, OK, la oss dequeue noe.
Vi dequeue dette.
Vi tar ut dette elementet, ikke sant?
>> Og nå vårt hode peker her, og vi ønsker å legge inn en annen ting.
Dette er i utgangspunktet iden av vår linje, ikke sant?
Køer kan vikle rundt array.
Det er en av de viktigste forskjellene.
Stabler, kan du ikke gjøre dette.
>> Med køer, kan du fordi alt som teller
er at du vet hva ble lagt til sist.
Siden alt kommer til å bli lagt i denne venstrerettet retning, i dette tilfellet,
og deretter vikle rundt, kan du fortsette å sette inn nye elementer
på forsiden av rekken fordi det er egentlig ikke
forsiden av rekken lenger.
Du kan tenke på begynnelsen av matrise som hvor hodet ditt faktisk er.
>> Så denne formelen er hvordan du beregne din halen.
Betyr det fornuftig?
OK.
OK, dequeue, og deretter dere har 10 minutter
å stille meg oppklarende spørsmål du vil, fordi jeg vet det er sprøtt.
>> Greit, så i samme måte-- Jeg vet ikke om dere lagt merke til,
men CS handler om mønstre.
Ting er ganske mye det samme, bare med små tilpasninger.
Så samme her.
Vi må sjekke for å se om vi faktisk har noe i vår kø, ikke sant?
Sier, OK, er vår størrelse større enn 0?
Cool.
>> Hvis vi gjør det, så flytter vi vårt hode, som er hva jeg nettopp demonstrert her.
Vi oppdaterer vårt hode til å være en mer.
Og da vi minske vår størrelse og tilbake i elementet.
>> Det er mye mer konkret kode på study.cs50.net,
og jeg anbefaler å gå gjennom det hvis du har tid,
selv om det bare er en pseudo-kode.
Og hvis dere ønsker å snakke gjennom at med meg en på en, kan du gi meg
vet.
Jeg vil gjerne.
Datastrukturer, hvis du tar CS 124, vil du
vet at datastrukturer får veldig moro, og dette er bare begynnelsen.
>> Så jeg vet det er vanskelig.
Det er OK.
Vi sliter.
Jeg gjør det fortsatt.
Så ikke bekymre deg for mye om det.
>> Men det er i utgangspunktet din lynkurs i datastrukturer.
Jeg vet det er mye.
Er det noe som vi ønsker å gå over igjen?
Noe vi ønsker å snakke gjennom?
Ja?
>> PUBLIKUM: For det eksempelet, så den nye halen er på 0 over det?
SPEAKER 1: Ja.
PUBLIKUM: OK.
Så da går gjennom, du ville ha en pluss 4 or--
>> SPEAKER 1: Så du sa, når vi ønsker å gå gjøre dette igjen?
PUBLIKUM: Yeah.
Så hvis du skulle finne out-- hvor er du beregne halen fra i det?
>> SPEAKER 1: Så halen var in-- Jeg endret dette.
Så i dette eksempelet her, dette var matrisen vi ser på, OK?
Så vi har ting i 1, 2, 3 og 4.
Så vi har vårt hode er lik 1 på dette punktet, og er lik 4 vår størrelse
på dette punktet, ikke sant?
>> Du er alle enige om det er tilfelle?
Så vi gjør hodet pluss størrelse, som gir oss fem, og da vi mod med 5.
Vi får 0, som forteller oss at 0 er hvor er vår hale, hvor vi har plass.
>> PUBLIKUM: Hva er en cap?
>> SPEAKER 1: Kapasiteten.
Unnskyld.
Så det er størrelsen på array.
Ja?
>> PUBLIKUM: [uhørlig] før vi tilbake elementet?
>> SPEAKER 1: Så vi flytter hodet eller returnere øyeblikket?
Så hvis vi flytter en, minske størrelsen?
Hold på.
Jeg definitivt glemte en annen.
Never mind.
Det er ikke en annen formel.
Ja, vil du ønsker å returnere hodet og deretter flytte den tilbake.
>> PUBLIKUM: OK, fordi på dette punkt, var hodet på 0,
og deretter du ønsker å returnere indeks 0 og deretter lage head 1?
>> SPEAKER 1: Høyre.
Jeg tror det er en annen formel typen som dette.
Jeg har ikke den på toppen hodet mitt som Jeg ønsker ikke å gi deg feil en.
Men jeg tror det er helt gyldig til si, OK, lagre denne element-- uansett
hodets element er-- minske din størrelse, bevege hodet over, og avkastningen
uansett hva det elementet er.
Det er helt gyldig.
OK.
Jeg føler at dette ikke er som most-- du ikke
kommer til å gå ut herfra som, ja, jeg vet prøver.
Jeg fikk det hele.
Det er OK.
Jeg lover.
Men datastrukturer er noe som det tar mye tid å venne seg til.
Sannsynligvis en av de vanskeligste ting, tror jeg, i løpet.
>> Så det tar definitivt repetisjon og ser at-- jeg
gjorde egentlig ikke vet lenkede lister før jeg gjorde altfor mye med dem,
på samme måte som gjorde ikke jeg virkelig forstå pekere
før jeg har måtte lære det for to år og gjøre mine egne psets med det.
Det tar mye gjentakelse og tid.
Og til slutt, vil det slags klikk.
>> Men i mellomtiden, hvis du har en slags fra et høyt nivå forståelse av hva
disse gjør, deres fordeler og cons-- som er hva
vi virkelig har en tendens til å understreke, spesielt i intro kurs.
Liker, hvorfor skulle vi bruke en prøve over en array?
Liker, hva er de positive og negativer på hver av dem?
>> Og forstå avveiningene mellom hver av disse strukturene
er det som er mye viktigere akkurat nå.
Det kan være en gal spørsmål eller to som er
kommer til å be deg om å implementere skyve eller implementere pop eller enqueue og dequeue.
Men for det meste, som har som høyere nivå forståelse og mer
av en intuitiv forståelse er viktigere enn faktisk
å være i stand til å gjennomføre det.
>> Det ville være virkelig fantastisk hvis alle dere kunne gå ut og gå gjennomføre en prøve,
men vi forstår det er ikke nødvendigvis den mest fornuftige tingen akkurat nå.
Men du kan i PSet, hvis du vil til, og da vil du få praksis
og så kanskje du vil virkelig forstå det.
Ja?
>> PUBLIKUM: OK, så hvilke som er vi ment å bruke i PSet?
Trenger jeg å bruke en av dem?
SPEAKER 1: Ja.
Så du har ditt valg.
Jeg antar i dette tilfellet, kan vi snakke om PSet litt
fordi jeg kjørte gjennom disse.
Så i din PSet, har du din Valget av prøver eller hash tabeller.
Noen mennesker vil prøve og bruke blomst filtre,
men de teknisk sett ikke er riktige.
På grunn av deres natur probabilistisk, de gir falske positiver noen ganger.
De er kule titt inn, though.
Anbefale ser på dem minst.
Men du har ditt valg mellom en hash-tabell og en prøve.
Og det kommer til å være der du legger i ordboken.
>> Og du må velge din hash-funksjon,
må du velge hvor mange skuffer du har, og det vil variere.
Som hvis du har flere bøtter, kanskje det vil kjøre fortere.
Men kanskje du kaster bort en mye plass på den måten, skjønt.
Du må finne ut av det.
Mmhmm?
>> PUBLIKUM: Du sa tidligere at vi kan bruke andre hash funksjoner,
at vi ikke trenger å opprette en hash-funksjon?
>> SPEAKER 1: Ja, ikke sant.
Så bokstavelig talt for din hash-funksjon, som google "hash-funksjon"
og ser etter noen kule de.
Du er ikke forventet å bygge dine egne hash funksjoner.
Folk bruker deres teser om disse tingene.
>> Så ikke bekymre deg om å bygge din egen.
Finn en på nettet til å begynne med.
Noen av dem må du manipulere litt
å sørge for at returtyper matche opp og whatnot, så i begynnelsen,
Jeg vil anbefale å bruke noe veldig lett at kanskje bare
hashes på den første bokstaven.
Og så når du har det arbeidende, innlemme et kjøligere hash-funksjon.
Mmhmm?
>> PUBLIKUM: Ville en prøve være eller effektive, men bare vanskeligere å, like--
>> SPEAKER 1: Så en prøve, tror jeg, er intuitivt vanskelig å implementere
men er veldig rask.
Men tar mer plass.
Igjen, kan du optimalisere både av de i forskjellige måter og det finnes måter to--
PUBLIKUM: Hvordan skal vi gradert på dette?
Betyr det matter--
>> SPEAKER 1: Så du gradert vanlig måte.
Du kommer til å bli gradert på design.
Uansett hvordan du gjør det, vil du sørge for at det er like elegant som det kan være
og så effektiv som det kan være.
Men hvis du velger en prøve eller hash bord, så lenge det virker,
Vi er fornøyd med det.
Og hvis du bruker noe som hashes på den første bokstaven, er det helt greit,
som kanskje liker design-messig.
Vi er også nå punkt i denne semester--
Jeg vet ikke om du Gutta noticed-- hvis du er
PSet karakterer avta litt på grunn av design og whatnot,
det er helt greit.
Det er å få til et punkt hvor din programmer blir mer komplisert.
Det er flere steder du kan bli bedre på.
>> Så det er helt normalt.
Det er ikke det at du er gjør verre på PSet.
Det er bare vi blir hardere på deg nå.
Så alle som føler det.
Jeg bare gradert alle dine psets.
Jeg vet at alle føler det.
>> Så ikke vær bekymret for det.
Og hvis du har noen spørsmål om tidligere psets eller måter du kan forbedre,
Jeg prøver og kommentere den spesifikke steder, men noen ganger er det for sent
og jeg blir lei.
Er det noen andre ting om datastrukturer?
Jeg er sikker på at dere egentlig ikke ønsker å snakke om dem lenger,
men hvis det er, er jeg glad for å gå over dem, samt noe
fra forelesning denne siste uke eller forrige uke.
>> Jeg vet at forrige uke var all anmeldelse, så vi kan ha hoppet over noen gjennomgang
fra forelesning.
Eventuelle andre spørsmål kan jeg svare?
OK, greit.
Vel, dere får ut 15 minutter for tidlig.
>> Jeg håper dette var semi-nyttig i det minste, og jeg vil se dere neste uke,
eller torsdag kontortid.
Er det forespørsler om snacks for neste uke, det er tingen?
Fordi jeg glemte godteri i dag.
Og jeg tok godteri sist uke, men det var Columbus Day,
så det var som seks personer som hadde fire poser med godteri til seg selv.
Jeg kan bringe Starbursts igjen hvis du vil.
Starbursts?
OK, høres bra ut.
Ha en flott dag, folkens.