>> [MUSIC SPILLE]
>> ANDI PENG: Velkommen til uke 6 av delen.
Vi avvek fra vår standard § tid tirsdag
ettermiddag til denne herlige søndag morgen.
Takk for alle som kom til meg i dag, men seriøst,
en runde med applaus.
>> Det er en ganske stor innsats.
Jeg nesten ikke selv gjøre det opp i tide, men det var OK.
Så jeg vet at alle dere har nettopp gjort det til quiz.
Først av alt, velkommen til baksiden av det.
>> Dernest vil vi snakke om det.
Vi skal snakke om det quiz.
Vi skal snakke om hvordan du gjør i klassen.
Du vil være i orden.
Jeg har dine quizzer for du på slutten av her,
så hvis dere ønsker å ta en ser på det, helt greit.
>> Så raskt før vi begynner, jo agenda for i dag er som følger.
Som du kan se, er vi utgangspunktet rask avfyring
gjennom en hel haug med datastrukturer virkelig, virkelig, virkelig raskt.
Så som sådan, vil det ikke være super interaktiv dag.
Det vil bare være meg slags rope Ting som du, og hvis jeg forvirre deg,
hvis jeg går for fort, gi meg beskjed.
De er bare ulike data strukturer, og som en del
av PSet for dette kommende uke, vil du
bli bedt om å gjennomføre en av dem, kanskje to av them-- to av dem
i PSet.
OK, så jeg skal bare starte med noen kunngjøringer.
Vi vil gå over stabler og køer flere i dybde enn det vi gjorde før quizen.
Vi vil gå over linket liste opp igjen, nok en gang,
mer i dybden enn hva vi hadde før quizen.
Og så får vi snakke om hasj tabeller, trær og prøver, som
er alle ganske nødvendig for PSet.
Og så får vi gå over noen nyttige tips for pset5.
>> OK, så quiz 0.
Gjennomsnittlig var 58%.
Det var svært lav, og så dere alle gjorde det veldig, veldig godt i samsvar
med denne.
>> Ganske mye, er tommelfingerregel hvis du er i løpet av et standardavvik av middelverdien
spesielt siden vi er i en mindre comfy delen, er du helt fint.
Du er på rett spor.
Livet er godt.
>> Jeg vet det er skummelt å tenke på at Jeg fikk som en 40% på denne quizen.
Jeg kommer til å mislykkes denne klassen.
Jeg lover deg, du er ikke kommer til å mislykkes klassen.
Du er helt greit.
>> For de av dere som fikk over middelverdien, imponerende, imponerende,
lignende, seriøst godt gjort.
Jeg har dem med meg.
Føl deg fri til å komme og hente dem på slutten av delen.
Gi meg beskjed hvis du har noen problemer, spørsmål med dem.
Hvis vi legger opp poengsummen din galt, gi oss beskjed.
>> OK, så pset5, er dette en virkelig merkelig uke for Yale i den forstand
at vår PSet skyldes Onsdag på middag inkludert
late dager, så det er faktisk teoretisk grunn tirsdag midt på dagen.
Sannsynligvis ingen ferdig på tirsdag midt på dagen.
Det er helt greit.
Vi kommer til å ha kontortid i kveld samt mandag kveld.
Og alle delene av denne uken vil faktisk bli omgjort til workshops,
så gjerne stikke innom noen del du vil,
og de vil være slags mini-PSet workshops for hjelp på det.
Så som sådan, er dette den eneste delen hvor vi undervisningsmateriell.
Alle de andre delene vil være fokus utelukkende på hjelp for PSet.
Yeah?
>> PUBLIKUM: Hvor er kontortiden?
>> ANDI PENG: Arbeidstid tonight-- oh, godt spørsmål.
Jeg tror kontortiden i kveld er i Teal eller på Commons.
Hvis du sjekker på nettet CS50 og du går til arbeidstid,
det bør være en tidsplan som forteller deg hvor alle av dem er.
>> Jeg vet heller i kveld eller i morgen er blågrønn,
og jeg tror vi kan ha commons for den andre natten.
Jeg er ikke sikker.
Godt spørsmål.
Sjekk på CS50.
>> Cool, spørsmål om plan for de neste som tre dager?
Jeg lover dere liker David sagt, dette er toppen av bakken.
Dere er nesten der.
Bare tre dager.
Komme dit, og da vil vi alle komme ned.
Vi vil ha en fin CS-fri pause.
Velkommen tilbake.
Vi vil dykke inn i web programmering og utvikling,
ting som er veldig morsomt sammen til noen av de andre psets.
Og det vil være chill, og vi vil ha mye moro.
Vi vil ha mer godteri.
Sorry for godteri.
Jeg glemte godteri.
Det var en grov morgen.
Så dere er nesten der, og jeg er veldig stolt av dere.
>> OK, stabler så.
Som elsket spørsmålet om Jack og hans klær på quiz?
Ingen?
OK, det er fint.
>> Så egentlig som du kan Bildet Jack, denne fyren her,
elsker å ta klær ut av toppen av stabelen,
og han setter den tilbake på bunken etter at han er ferdig.
Så på denne måten, han aldri synes å være å få
til bunnen av stable i klærne hans.
Så denne typen beskriver den grunnleggende datastruktur
av hvordan en stabel er implementert.
>> I hovedsak tenker på en stable som noen stakk av gjenstander
hvor du setter ting på toppen, og så du pop dem ut fra toppen.
Så LIFO er akronym vi liker å use-- Sist inn, først ut.
Og så til sist i toppen av stack er den første som kommer ut.
Og så de to begrepene vi liker å assosiere
med som kalles push og pop.
Når du trykker på noe på stable, og du pop den opp igjen.
>> Og så jeg antar dette er litt av en abstrakt begrep for de av dere
som ønsker å se ut som en Selve gjennomføringen av denne
i den virkelige verden.
Hvor mange av dere har skrevet et essay kanskje som en time før det var grunn,
og du ved et uhell slettet en enorm del av det, som ved et uhell?
Og så hva kontrollen gjør vi bruker for å sette den tilbake?
Kontroll-Z, ja?
Kontroll-Z, slik at mengden av tider at Ctrl-Z har reddet livet mitt,
har reddet meg i ræva, hver gang som er innført gjennom en stabel.
>> I hovedsak all informasjon det er i Word-dokumentet,
det blir presset og spratt på vilje.
Og så egentlig når du slette noe, pop du den opp igjen.
Og så hvis du trenger det på igjen, du skyve det, som er det Ctrl-C gjør.
Og så virkelige verden funksjon av hvor enkelt datastruktur
kan hjelpe med hverdagen.
>> Så en struct er den måten at vi faktisk lage en stabel.
Vi skriver definere struct, og deretter Vi kaller det stable på bunnen.
Og innen stabelen, vi har to parametere
at vi kan egentlig manipulere, så vi har røye stjerners strenger kapasitet.
>> Alt som den gjør er å skape en matrise
at vi kan lagre hva du vil som vi kan bestemme sin kapasitet.
Kapasiteten er bare maks mengde elementer vi kan sette inn i denne matrisen.
int størrelse er telleren som holder oversikt over hvor mange elementer er for tiden
i stabelen.
Så da kan vi holde styr på, A, både hvor stor selve stabelen er,
og B, hvor mye av dette stack vi fylt fordi vi ikke ønsker
å renne over hva som vår kapasitet er.
>> Så for eksempel, denne herlige Spørsmålet var på quiz.
Hovedsak hvordan skal vi presse på toppen av en stabel.
Ganske enkel.
Hvis du ser på det, vi vil gå gjennom dette.
Hvis [uhørbart] size-- Husk, når du
vil ha tilgang til alle parameter innen en struct,
du navnet på struct.parameter.
>> I dette tilfelle s er navnet på vår stabelen.
Vi ønsker å få tilgang til størrelse av det, så vi gjør s.size.
Så så lenge størrelsen er ikke lik kapasitet eller så lenge
som det er mindre enn kapasiteten, enten ville fungere her.
>> Du vil ha tilgang til innsiden av stabelen din, så s.strings,
og du kommer til å sette det nye nummeret som du ønsker å sette inn i det.
La oss bare si at vi vil ønske å Sett int n på stakken,
vi kunne gjøre s.strings, parentes, tilsvarer s.size n.
Fordi størrelsen er der vi for tiden er i stakken
hvis vi kommer til å presse den på, vi bare tilgang til
hvor størrelsen er, desto nåværende fylde av stabelen,
og vi skyver int n på den.
Og så ønsker vi å sørge for at vi også økes størrelsen på n,
slik at vi kan holde styr på vi har lagt til en ekstra ting å stabelen.
Nå har vi en større størrelse.
Betyr dette her være fornuftig å alle, hvor logisk det fungerer?
Det var litt rask.
PUBLIKUM: Kan du gå over de s.stringss.strings [s.size] igjen?
ANDI PENG: Jada, så hva gjør s.size tiden gi oss?
PUBLIKUM: Det er den nåværende størrelse.
ANDI PENG: Akkurat, så det gjeldende indeksen at vår størrelse er på,
og så vi ønsker å sette den nye tall at vi ønsker å sette inn i s.size.
Gir det mening?
Fordi s.strings, alt som er er navnet på matrisen.
Alt er det er tilgang til utvalg innen vår struct,
og så hvis vi ønsker å plassere n til at indeksen,
Vi kan bare få tilgang til det ved hjelp av brak s.size.
Kjølig.
>> Greit, pop, pseudo jeg det ut for dere, men lignende konsept.
Gir det mening?
Hvis størrelsen er større enn null, så du
vet at du vil ta noe ut fordi hvis størrelse ikke er
større enn null, så du har ingenting i bunken.
>> Slik at du bare ønsker å kjøre denne koden, kan det bare
pop hvis det er noe å pop.
Så hvis størrelse er større enn 0, vi minus størrelse.
Vi minske størrelsen og deretter returnere hva er på innsiden av det fordi
ved popping, vi ønsker å tilgang uansett er lagret
i indeksen på toppen av stabelen.
Alt fornuftig?
Hvis jeg gjorde dere skrive dette ut, ville dere være i stand til å skrive det ut?
OK, kan dere leke seg med det.
Ingen grunn til bekymring dersom du ikke får det.
Vi har ikke tid til å kode det ut i dag fordi vi har
fikk mye av disse strukturene å gå gjennom, men i hovedsak
pseudokode, veldig, veldig lik presse.
Bare følg langs logikk.
Sørg for at du får tilgang til alle funksjonene i struct riktig.
Yeah?
>> PUBLIKUM: Vil disse lysbilder og dette hele greia være opp i dag-ish?
ANDI PENG: Alltid, Jepp.
Jeg kommer til å prøve å sette dette opp som en time etter.
Jeg vil sende David, vil David prøver å sette den opp som en time etter dette.
>> OK, så da flytter vi inn i denne andre nydelig datastruktur som kalles en kø.
Som dere kan se her, en køen, for britene blant oss,
alt er det er en linje.
Derfor i motsetning til hva du tror en stabel er,
en kø er akkurat hva logisk tror du det er.
Det er holdt av reglene i FIFO, som er først inn, først ut.
Hvis du er den første en i linjen, er du
den første som kommer ut av linjen.
>> Så det vi liker å kalle dette er dequeueing og enqueueing.
Hvis vi ønsker å legge til noe til vår kø, Enqueue vi.
Hvis vi ønsker å dequeue, eller ta noe bort, dequeue vi.
>> Så samme forstand at vi er på en måte skape fast størrelse elementer som vi
kan lagre visse ting, men vi kan også
endre hvor vi plasserer parametere innsiden av dem
basert på hvilken type funksjonaliteten vi ønsker.
Så stabler, ønsket vi den siste en, N for å være den første ut.
Køen er vi ønsker det første i å være den første ut.
>> Så struct-type definere, som du kan se,
det er litt annerledes fra hva stabelen var
fordi ikke bare har vi å holde Sporet etter størrelse er for tiden,
vi ønsker også å holde styr på hodet samt hvor vi er nå.
Så jeg tror det er lettere hvis jeg tegne dette opp.
Så la oss forestille vi har fått en kø, så la oss si at hodet er rett her.
Lederen av linjen, la oss bare si at er der i dag,
og vi ønsker å sette inn noe inn i køen.
Jeg kommer til å ringe størrelse hovedsak er det samme som hale,
slutten av hvor køen er.
La oss bare si størrelsen er rett her.
>> Så hvordan gjør man feasibly sette noe inn i en kø?
Hva indeksen gjør vi ønsker å plassere hvor vi ønsker å sette inn.
Hvis dette er begynnelsen på din kø og dette er slutten av det
eller størrelsen på den, der gjør vi ønsker å legge til neste objekt?
>> PUBLIKUM: [uhørbart]
ANDI PENG: Akkurat, du vil legge det avhengig av har du skrevet det.
Enten dette er tomt eller som er blank.
Så du ønsker å legge det sannsynligvis her fordi hvis størrelsen er--
om disse er alle fulle, vil du å legge det her, ikke sant?
>> Og så det er, mens veldig, veldig enkelt, ikke helt alltid riktig
fordi den største forskjellen mellom en kø og en stabel
er at den kan køen faktisk manipuleres
slik at hode endringer avhengig av hvor du vil
I begynnelsen av køen for å starte.
Og som et resultat, halen også kommer til å endre seg.
Og så ta en titt på denne koden akkurat nå.
Som dere ble også bedt om å skrive ut på quiz, enqueue.
Kanskje vi skal snakke gjennom hvorfor svaret var hva det var.
>> Jeg kunne ikke helt passer denne linjen på en, men i hovedsak dette stykke kode
bør være på en linje.
Tilbring som 30 sekunder.
Ta en titt, og se hvorfor dette er måten som det er.
>> Veldig, veldig lik struct, veldig, veldig tilsvarende struktur som den forrige
stable bortsett kanskje en kodelinje.
Og at en linje med kode bestemmer funksjonalitet.
Og det som virkelig skiller en kø fra en stabel.
>> Alle som ønsker å ta et stikk på å forklare hvorfor du har
fikk dette komplisert ting her inne?
Vi ser avkastningen av vår fantastisk venn modulus.
Som dere vil snart komme å gjenkjenne i programmering,
nesten når du trenger noe å vikle rundt noe,
modulus kommer til å være måten å gjøre det.
Så å vite det, er det noen som vil ha for å prøve å forklare at kodelinje?
Ja, alle svarene er akseptert og velkommen.
PUBLIKUM: Snakker du til meg?
ANDI PENG: Yeah.
PUBLIKUM: Å, nei sorry.
ANDI PENG: OK, så la oss gå gjennom denne koden.
Så når du prøver å legge noe på en kø,
i den vakre tilfelle at hodet skjer å være her, er det veldig lett for oss
å bare gå til slutten sette inn noe, ikke sant?
Men hele poenget med en kø er at hodet kan faktisk dynamisk
endres avhengig av hvor vi Vil starten av vår q for å være,
og som sådan, halen også kommer til å endre seg.
>> Og så forestille seg at dette ikke var kø, men dette var køen.
La oss si at hodet er rett her.
La oss si at vår kø så ut som dette.
Hvis vi ønsket å skifte der begynnelsen av linjen er,
la oss si at vi flyttet hodet på denne måten og størrelser her.
>> Nå ønsker vi å legge noe til denne køen, men som dere kan se,
det er ikke så enkelt som å bare legge til hva er etter størrelsen
fordi da vi kjører ut av grensene av våre faktiske utvalg.
Hvor vi ønsker å virkelig legge til er her.
Det er det fine med en kø kommer det oss, visuelt det
ser ut som linjen går som dette, men når de lagres i en datastruktur,
de som gir det som en syklus.
Det brytes slags rundt til fronten på samme måte
som en linje kan også pakke rundt avhengig av hvor du
vil begynnelsen av linjen for å være.
Og så hvis vi tar en se ned her, la oss
si at vi ønsket å lage en funksjon kalt enqueue.
Vi ønsket å legge til int n til at q.
Hvis q.size q-- vi kaller at våre data structure-- hvis våre queue.size ikke
lik kapasitet eller hvis det er mindre enn kapasiteten,
q.strings er rekke innenfor vår q.
Vi kommer til å sette som lik q.heads,
som er rett her, pluss q.size modulus av kapasiteten, som
vikle oss tilbake rundt her.
>> Så i dette eksempelet, index av hodet er en, ikke sant?
Indeksen for størrelse er 0, 1, 2, 3, 4.
Så vi kan gjøre en pluss fire modulus av vår kapasitet som er fem.
Hva betyr det å gi oss?
Hva er indeksen som kommer ut av dette?
>> PUBLIKUM: 0.
>> ANDI PENG: 0, som skjer for å være akkurat her,
og så vi ønsker å kunne å sette inn her.
Og så denne ligningen her slag for bare fungerer med noen tall
avhengig av hvor hode og din størrelse er.
Hvis du vet hva de ting er, vet du
akkurat der du vil sette inn hva er etter din køen.
Betyr det fornuftig for alle?
>> Jeg vet slag av en hjerne teaser spesielt siden dette
kom i kjølvannet av din quiz.
Men forhåpentligvis alle nå kan forstå
hvorfor denne løsningen eller dette Funksjonen er slik som det er.
Alle som litt uklar på det?
OK.
>> Og så nå, hvis du ønsket å dequeue, dette
er der hodet ville være skiftende fordi hvis vi skulle dequeue,
vi ikke ta av på slutten av q.
Vi ønsker å ta av hodet, ikke sant?
Så som et resultat, er hodet kommer til å endre, og det er derfor når du Enqueue,
du er nødt til å holde styr på hvor hodet og størrelse
skal være i stand til å sette i riktig posisjon.
>> Og så når du dequeue, Jeg har også pseudo det ut.
Gjerne hvis du vil å forsøke koding ut dette.
Du ønsker å bevege hodet, ikke sant?
Hvis jeg ønsket å dequeue, jeg ville flytte hodet over.
Dette ville være leder.
>> Og vår nåværende størrelse ville trekker fordi vi ikke lenger
har fire elementer i tabellen.
Vi har bare tre, og da ønsker vi å returnere det som var lagret inne
av hodet fordi vi ønsker å ta dette verdi ut så meget lik stabelen.
Bare du tar fra et annet sted,
og du må overføre pekeren til annet sted som et resultat.
Logisk, alle følge?
Flott.
>> OK, så vi kommer til å snakke litt mer i dybden om lenkede lister
fordi de vil være veldig, veldig verdifull for deg i løpet av denne uken
psets.
Lenkede lister, som dere kan huske, alt de er
er noder som er noder av visse verdier av både en verdi og en peker
som er knyttet sammen av disse pekere.
Og så struct om hvordan skaper vi en node her er vi
har int n, som er hva verdien i en butikk eller streng n
eller hva du vil kaller det, røye stjerne n.
Struct node stjernen, som er pekeren som du ønsker å ha i hver node,
du kommer til å ha det pekeren peker mot neste.
Du vil ha hodet av en lenket liste som er
kommer til å peke til resten av verdiene så videre og så videre
til du til slutt kommer til enden.
Og denne siste noden er bare skal ikke ha en peker.
Det kommer til å peke på null, og at når er
du vet at du har truffet slutten av lenket liste
er når din siste pekeren peker ikke til noe.
>> Så vi kommer til å gå litt mer i dybden om hvordan en ville muligens
søke en lenket liste.
Husk hva er noen av de ulempene med de koblede lister
vers en rekke angående søk.
En rekke du kan binært søk, men hvorfor kan du ikke gjøre det i en lenket liste?
>> PUBLIKUM: Fordi de er alle koblet til, men du ikke helt vet hvor
[Uhørbart].
>> ANDI PENG: Ja, akkurat så husk at glansen av en matrise
var det faktum at vi hadde random access memory der
hvis jeg ville verdien fra indeks seks, kunne jeg bare si indeksen seks,
gi meg denne verdien.
Og det er fordi arrays er sortert i en sammenhengende plass minne
på ett sted, mens slags lenkede lister
er tilfeldig ispedd rundt, og den eneste måten du kan finne en
er gjennom en peker som forteller deg adressen til der at neste node er.
>> Og så som et resultat, er den eneste måten å søke gjennom en lenket liste
er lineær søk.
Fordi jeg ikke vet nøyaktig hvor 12. verdi i lenket liste er,
Jeg må krysse helhet av at lenket liste én
etter én fra hodet til den første noden, til den andre node, til den tredje node,
helt ned før jeg endelig får til hvor som node jeg leter etter er.
Og så i denne forstand, søk på en lenket liste er alltid n.
Det er alltid n.
Det er alltid i lineær tid.
>> Og så koden der vi gjennomføre dette, og dette
er litt nytt for dere siden dere Gutta har egentlig ikke snakket om eller noen gang
sett tips i hvordan du søke gjennom pekere,
så vi vil gå gjennom dette veldig, veldig sakte.
Så bool søk, høyre, La oss forestille vi ønsker
for å lage en funksjon kalt søk som returnerer true
hvis du har funnet en verdi inne i linket liste, og den returnerer false ellers.
Node stjerne listen er i dag bare pekeren
til det første elementet i lenket liste.
int n er den verdien som du er søker etter på den listen.
>> Så node stjerners pekeren lik listen.
Det betyr at vi er innstillingen og skape en peker
til den første noden innsiden av listen.
Alle med meg?
Så hvis vi skulle gå tilbake her, ville jeg ha
initialisert en peker som peker til hodet av hva den listen er.
>> Og så når du kommer ned hit, mens pekeren ikke er lik null,
slik at sløyfen er der vi kommer til å være i ettertid traversering
resten av vår liste fordi det skjer når pekeren er lik null?
Vi vet at vi have--
>> PUBLIKUM: [uhørbart]
>> ANDI PENG: Akkurat, så vi vet at vi har nådd slutten av listen, ikke sant?
Hvis du går tilbake hit, hver node skal peke til en annen node
og så videre og så videre til du treffer til slutt
halen av din lenket liste, som har en peker som bare
peker ikke noe annet sted enn ingen.
Og så du i utgangspunktet vet at listen er der fortsatt opp
inntil pekeren ikke lik null fordi når den er lik null,
du vet at det er ingen flere ting.
>> Så det er loopen der vi er kommer til å ha selve søket.
Og hvis pointer-- ser du den slags pilen funksjon der?
Så hvis pekeren peker til n, hvis pekeren på n er lik lik n,
så det betyr at hvis pekeren at du er
søker etter på slutten av hvert node er faktisk lik verdien
du leter etter, så du ønsker å returnere true.
Så i utgangspunktet, hvis du er på en node som har verdien du leter etter,
du vet at du har vært i stand til å søke.
>> Ellers vil du sette pekeren til neste node.
Det er hva den linjen her gjør.
Pointer tilsvarer markøren ved siden av.
Alle se hvordan det fungerer?
>> Og egentlig du kommer til å like traversere helheten av listen
nullstilling pekeren hver gang før du til slutt treffer slutten av listen.
Og du vet at det er ingen flere noder å søke gjennom,
og deretter kan du returnere false fordi du vet det, oh, vel,
hvis jeg har vært i stand til å søke gjennom helheten av listen.
Hvis du er i dette eksempelet, hvis jeg ville for å lete etter den verdi på 10,
og jeg starter på hodet, og Jeg søker hele veien ned,
og jeg til slutt fikk til dette, noe som en peker som peker til null,
Jeg vet det, crap, tror jeg 10 er ikke i denne listen fordi jeg kunne ikke finne den.
Og jeg er på slutten av listen.
Og i så fall vet du Jeg kommer til å returnere false.
>> La det trekke inn i en liten bit.
Dette vil være ganske viktig for din PSet.
Logikken i det er veldig enkelt, kanskje syntaktisk bare gjennomføre det.
Dere ønsker å gjøre sikker på at du forstår.
Kjølig.
>> OK, så hvordan vi ville være innsetting noder, høyre,
i en liste fordi huske hva er hva av fordelene
ved å ha en lenket liste versus en rekke i form av lagring?
>> PUBLIKUM: Det er dynamisk, så det er lettere to--
>> ANDI PENG: Akkurat, så det er dynamisk, noe som
betyr at det kan ekspandere og krympe avhengig av brukerens behov.
Og så, i denne forstand, vi trenger ikke å kaste bort unødvendig minne fordi jeg
hvis jeg ikke vet hvor mange verdier jeg ønsker til butikken, betyr det ikke gir mening for meg
for å lage en matrise, fordi hvis jeg ønsker å lagre 10 verdier
og jeg skaper en rekke 1000, det er mye bortkastet hukommelse, tildelt.
Det er derfor vi ønsker å bruke en koblet liste for å være i stand til dynamisk
endre eller krympe vår størrelse.
>> Og så gjør innsetting litt mer komplisert.
Siden vi ikke kan tilfeldig tilgang elementer den måten at vi ville av en matrise.
Hvis jeg ønsker å sette inn et element i den syvende indeksen,
Jeg kan bare sette det i den syvende indeksen.
På en lenket liste, det gjør det ikke helt fungerer like lett,
og så hvis vi ønsket å sette inn den ene her i lenket liste,
visuelt, er det veldig lett å se.
Vi ønsker bare å sette det rett der, helt i begynnelsen av listen,
rett etter hodet.
>> Men på hvilken måte må vi overføre pekerne er litt convoluted
eller, logisk, det er fornuftig, men du vil være sikker på at du har det
helt ned fordi det siste du ønsker
er å tildele en peker til måte som vi gjør her.
Hvis du dereference den pekeren fra hodet til en,
da plutselig den resten av lenket liste
er tapt fordi du har faktisk ikke opprettet en midlertidig noe.
Det er pekt på to.
Hvis du overfører pekeren, deretter Resten av listen er helt tapt.
Så du ønsker å være veldig, veldig forsiktig her
først tildele pekeren fra hva du
vil sette inn dit du ønsker, og deretter
kan dereference resten av listen.
>> Så dette gjelder for uansett hvor du prøver å sette inn.
Hvis du ønsker å sette på hode, hvis du ønsker å svare på her,
Hvis du ønsker å sette på Til slutt, vel, til slutt jeg
antar du ville bare har ingen pekeren, men du
vil være sikker på at du ikke mister resten av listen.
Du ønsker alltid å sørge for at den nye noden peker
mot hva du vil sette inn,
og deretter kan du legge til kjeding på.
Alle klare?
>> Dette kommer til å være en av de virkelige problemene.
En av de fleste store problemer du kommer til å ha på din PSet
er at du kommer til å prøve å lage en lenket liste og sette inn ting
men da bare miste resten av lenket liste.
Og du kommer til å være som, jeg vet ikke hvorfor dette skjer?
Og det er en smerte å gå gjennom og søke alle dine pekere.
>> Og jeg garanterer deg på denne PSet, skrive og tegne disse nodene ut
vil være veldig, veldig nyttig.
Så du kan helt holde styr hvor alle dine pekere er,
hva som går galt, hvor alle noder er,
hva du må gjøre for å få tilgang til eller sette inn eller slette eller noen av dem.
Alle gode med det?
Kjølig.
>> Så hvis vi ønsket å se på koden?
Å, jeg vet ikke om vi kan se the-- OK, så
på toppen alt er det er en funksjon oppkalt innsats der vi ønsker
å sette int n inn i lenket liste.
Vi kommer til å gå gjennom dette.
Det er mye kode, mye ny syntaks.
Vi vil være OK.
>> Så opp på toppen, når Vi ønsker å skape noe
Hva trenger vi å gjøre, spesielt hvis du vil den skal ikke lagres på stakken
men i haugen?
Vi går til en malloc, ikke sant?
Så vi kommer til å lage en peker.
Node, pekeren, nye likemenn malloc på størrelse med en node
fordi vi ønsker at node som skal opprettes.
Vi vil mengden minne om at en node tar opp
å bli tildelt for opprettelse av den nye noden.
>> Og så skal vi sjekke se om nye likemenn er lik null.
Husk hva vi sa?
Uansett hva du malloc, hva må du alltid gjøre?
Du må alltid sjekke for å se hvorvidt det er null.
>> For eksempel, hvis operativsystemet systemet var helt full,
hvis du hadde ikke mer minne på alt og du prøver å malloc,
det vil returnere null for deg.
Og så hvis du prøver å bruke det når det ble peker til null,
du kommer ikke til å kunne å få tilgang til denne informasjonen.
Og så som sådan, ønsket vi å gjøre sikker på at når du mallocing,
du alltid sjekke for å se om som minnet gitt til deg er null.
Og hvis det ikke er det, så vi kan flytte videre med resten av koden vår.
>> Så vi kommer til å initialisere ny node.
Vi kommer til å gjøre nye n er lik n.
Og så skal vi gjøre satt ny pekeren på nytt
til null fordi akkurat nå har vi ikke vil ha noe for det å peke på.
Vi har ingen anelse om hvor det kommer til å sette deg,
og hvis vi ønsker å setter den på hodet,
da kan vi overføre pekeren til hodet.
Har alle følge logikken hvor det skjer?
>> Alt vi gjør er å skape en ny node, sette pekeren til null,
og deretter reassigning den til hodet om vi
vet vi ønsker å sette det på hodet.
Og deretter hodet skal peke mot at ny node.
Alle OK med det?
>> Så det er en to-trinns prosess.
Du må først assign uansett hva du oppretter.
Satt som peker til referanse, og deretter
kan slags dereference den første pekeren
og peker mot den nye noden.
Uansett hvor du ønsker å sette inn det, at logikken kommer til å holde sant.
>> Det er litt som å tildele midlertidige variabler.
Husk, du har å sørge for at du
ikke mister oversikten over hvis du bytter.
Du ønsker å være sikker på at du har en midlertidig variabel den slags holder
rede på hvor den tingen er lagret slik at du
mister ikke noen verdi i løpet som å rote rundt med den.
>> OK, så koden vil være her.
Dere se etter delen.
Det vil være der.
>> Så jeg antar hvordan fungerer Dette avviker hvis vi ønsket
å sette inn i midten eller slutten?
Er det noen som har en idé om hva som er den pseudokode som den logiske referanse
at vi ville ta hvis vi ønsket for å sette det i midten?
Så hvis vi ønsket å sette det på hode, er alt vi gjør opprette en ny node.
Vi setter pekeren over at ny node til hva hodet,
og da vi satt på hodet til den nye noden, ikke sant?
Hvis vi ønsket å sette det inn i midten av listen, hva ville vi gjøre?
>> PUBLIKUM: Det ville fortsatt være en lignende prosess
som å tildele pekeren og deretter tildele at pekeren,
men vi måtte finne der.
>> ANDI PENG: Akkurat, så nøyaktig den samme prosessen bortsett fra at du
må finne hvor akkurat du ønsker at nye pekeren til å gå inn,
så hvis jeg ønsker å sette inn midt knyttet list-- OK,
la oss si det er vår lenket liste.
Hvis vi ønsker å sette det akkurat her, vi kommer til å opprette en ny node.
Vi kommer til malloc.
Vi kommer til å opprette en ny node.
Vi kommer til å tildele pekeren over denne noden her.
>> Men problemet som avviker fra der hodet er
er at vi visste nøyaktig hvor hodet er.
Det var rett på det første, ikke sant?
Men her er vi nødt til å holde styr av hvor vi setter det inn.
Hvis vi setter inn våre node her har vi
å sørge for at man tidligere til denne noden
er den som tilordner pekeren.
Så da har du til slags holde styr på to ting.
Hvis du holde oversikt over hvor dette node for tiden er å sette inn.
Du må også holde styr på hvor den forrige noden som du ser på
var også der.
Alle gode med det?
OK.
>> Hva med å sette inn på slutten?
Hvis jeg ønsket å legge det her-- hvis jeg ønsket å legge til en ny node til slutten av en liste,
hvordan kan jeg gå om du gjør det?
PUBLIKUM: Så i dag, den siste ens pekte på null.
ANDI PENG: Yeah.
Akkurat, så dette tiden peker å vite,
og så jeg antar, i denne forstand, er det svært enkelt å legge til på slutten av en liste.
Alt du trenger å gjøre er å sette det lik null, og deretter boom.
Akkurat der, veldig lett.
Veldig enkelt.
>> Svært lik den hodet, men logisk deg
vil være sikker på at trinnene du tar mot å gjøre noe av dette,
du følger med.
Det er veldig lett å, i midten av koden din, bli fanget opp på,
Å, jeg har fått så mange tips.
Jeg vet ikke hvor noe peker til.
Jeg vet ikke engang hvilken node jeg er på.
Hva er det som skjer?
>> Slappe av, roe ned, ta et dypt åndedrag.
Trekke ut lenket liste.
Hvis du sier, vet jeg hvor Jeg trenger å sette dette inn i
og jeg vet akkurat hvordan du skal overføre min pekere, mye, mye enklere å fore
out-- mye, mye enklere å ikke gå seg vill i de bugs av koden din.
Alle OK med det?
OK.
>> Så jeg antar et konsept som vi ikke har egentlig snakket om før nå,
og jeg antar du sannsynligvis ikke vil møte mye yet--
det er litt av et avansert concept-- er at vi faktisk har en data
struktur kalt en dobbelt lenket liste.
Så som dere kan se, alt vi gjør er å skape
en faktisk verdi, en ekstra pekeren på hver av våre noder
som også peker til foregående noden.
Så ikke bare har vi vår noder peker til den neste.
De peker også på den forrige.
Jeg kommer til å ignorere disse to akkurat nå.
>> Så da har du en kjede som kan flytte begge veier,
og da er det litt enklere til logisk følge med.
Som her, i stedet for holde styr på, oh, jeg
må vite at denne noden er den som jeg har til å overføre,
Jeg kan bare gå her og bare trekke den forrige.
Da vet jeg nøyaktig hvor det er, og du
trenger ikke å krysse helheten i lenket liste.
Det er litt enklere.
>> Men som sådan, har du dobbelt mengden av pekere,
det er dobbelt så mye minne.
Det er en masse tips for å holde styr på.
Det er litt mer komplisert, men det er litt mer brukervennlig avhengig
på hva du prøver å oppnå.
>> Så denne type data struktur helt eksisterer,
og strukturen for er meget, meget enkel bortsett fra alt du har er,
i stedet for bare en peker til neste, du har også en peker til tidligere.
Det er hele forskjellen var.
Alle gode med det?
Kjølig.
>> Greit, så nå er jeg å virkelig tilbringe trolig
som 15 til 20 minutter eller bulk av resten av tiden i seksjonen
snakker om hash tabeller.
Hvor mange av dere har lest pset5 spec?
Greit, bra.
Som er høyere enn 50% av normalt.
Det er greit.
>> Så som dere vil se, du er utfordring i pset5
vil være å implementere en ordbok hvor du laster løpet 140.000 ord
at vi gir deg og stavekontroll det mot all teksten.
Vi gir deg tilfeldig biter av litteratur.
Vi vil gi deg The Odyssey.
Vi vil gi deg Iliaden.
Vi vil gi deg Austin Powers.
>> Og din utfordring vil være å stavekontroll
hvert eneste ord i alt av disse ordbøker
hovedsak med vår stavekontroll.
Og så er det noen få deler å skape denne PSet,
første du ønsker å være stand til å faktisk laste
alle ordene i din ordbok, og deretter
vil kunne stavekontroll dem alle.
Og så som sådan, du kommer til å kreve en datastruktur som kan gjøre dette raskt
og effektivt og dynamisk.
>> Så jeg antar det enkleste Måten å gjøre dette, du
vil trolig skape en matrise, ikke sant?
Den enkleste måten for lagring er du kan skape en rekke 140.000 ord
og bare plassere dem alle der og deretter krysse dem av binære søk
eller ved valg eller not-- beklager det er sortering.
Du kan sortere dem og deretter krysse dem av binære søk eller bare lineær søk
og bare siste ord, men tar en stor mengde minne,
og det er ikke veldig effektivt.
>> Og så vi kommer til å starte snakker om måter å gjøre
vår løpende tid mer effektiv.
Og vårt mål er å få konstant tid der
det er nesten som arrays, hvor du har øyeblikkelig tilgang.
Hvis jeg ønsket å søke etter noe, Jeg ønsker å være i stand til å bare,
boom, synes det er nøyaktig, og trekk den ut.
Og slik at en struktur der vi vil være å bli svært tett
å kunne få tilgang til konstant gang, denne hellige gral
i programmering av konstant gang kalles en hash table.
Og så David tidligere nevnt [Uhørbart] litt i foredraget
men vi kommer til å virkelig dykk i dyp denne uken
på en brikke som er om hvordan en hash table fungerer.
>> Så den måten at en hash bord verk, f.eks
hvis jeg ønsket å lagre en haug med ord, en haug med ord i det engelske språket,
Jeg kan teoretisk sette banan, eple, kiwi, mango, par,
og cantaloupe alle på bare en matrise.
De kunne alle passer inn og bli finne.
Det ville være litt vondt å søke gjennom og tilgang,
men den enklere måte å gjøre dette på er at vi kan skape faktisk en struktur
kalles en hash tabell der vi hasj.
Vi kjører alle våre nøkler gjennom en hash-funksjon, en ligning,
som gjør dem alle inn en slags verdi
at da kan vi lagre på hovedsak en rekke lenket liste.
>> Og så her, hvis vi ønsket å lagre engelske ord,
vi kunne potensielt bare, det gjør jeg ikke vet, slår alle de første bokstavene
inn i noen form for et tall.
Og så, for eksempel hvis jeg ønsket En å være synonymt med apple--
eller med indeks fra 0, og B for å være synonymt med en,
vi kan ha 26 oppføringer som bare kan lagre
alle bokstavene i alfabetet at vi vil begynne med.
Og så kan vi ha eple på indeksen fra 0.
Vi kan ha banan på indeksen for 1, cantaloupe på indeksen på 2,
og så videre og så videre.
Og dermed hvis jeg ønsket å søke min hash table og tilgang eple,
Jeg vet apple starter med en A, og jeg vet nøyaktig
at det må være og hash bord på indeks 0 fordi
av den tidligere tildelte funksjon.
>> Så jeg vet ikke, vi er et brukerprogram der
vil du bli belastet med arbitrarily-- ikke vilkårlig,
med å prøve å ettertenksomt tenke på gode ligninger
å være i stand til å spre ut alle dine verdier
på en måte de enkelt kan få tilgang det senere med som en ligning
at du selv vet.
Så i den forstand hvis jeg ønsket å gå til mango, jeg vet, oh, det begynner med m.
Det må være den indeks over 12.
Jeg trenger ikke å søke gjennom alt.
Jeg vet exactly-- jeg kunne bare gå til indeks over 12 og trekk det ut.
>> Alle klar på hvordan en hash table funksjon fungerer?
Det er slags bare en mer kompleks matrise.
Det er alt det er.
OK.
>> Så jeg antar vi kjører inn dette nummeret av hva
skjer hvis du har flere ting som gir deg den samme indeksen?
Så sier vår funksjon, alt det gjorde var å ta det første brev
og slå den inn i en respektive 0 til 25 indeksen.
Det er helt greit hvis du har bare en av hver.
Men det andre du starte ha mer, er du
kommer til å ha det som kalles en kollisjon.
>> Så hvis jeg prøver å sette inn begrave i en hash tabell som allerede har banan på den,
hva som skal skje når du prøver å sette inn det?
Dårlige ting fordi banan finnes allerede i indeksen
som du ønsker å lagre den i.
Berry slags er, ah, hva gjør jeg?
Jeg vet ikke hvor du skal gå.
Hvordan løser jeg dette?
>> Og så dere vil slags ser vi gjøre dette vanskelig ting
der vi kan slags faktisk lage lenket liste i våre rekker.
Og så den enkleste måten å tenke på dette,
alle hash table er en rekke knyttet lister.
Og så, i den forstand, har du denne vakre rekke pekere,
og deretter hver pekeren denne verdien, ved at indeksen,
faktisk kan peke på andre ting.
Og så har du alle disse separat kjeder kommer ut av ett stort utvalg.
>> Og så her, hvis jeg ønsket å sette inn bær,
Jeg vet, OK, jeg kommer til innspill det gjennom min hash-funksjon.
Jeg kommer til å ende opp med indeks over 1, og så kommer jeg til å være i stand til å ha
bare en mindre undergruppe av denne gigantiske 140 000 ord ordbok.
Og så kan jeg bare se gjennom 1/26 av det.
>> Og så da kan jeg bare sette bær enten før eller etter banan
i denne saken?
Etter, ikke sant?
Og så kommer du til å ønske å Sett denne noden etter banan,
og så kommer du til å sette inn på halen av det lenket liste.
Jeg kommer til å gå tilbake til dette forrige lysbilde,
så dere kan se hvordan hash funksjonen fungerer.
>> Så hash funksjon er denne ligningen at du kjører slags dine innspill
gjennom å få det index du ønsker å tildele den mot.
Og så, i dette eksempelet, ville alt vi å gjøre var å ta det første brevet,
slå den inn i en indeks, så vi kan lagre det i vår hash-funksjon.
Alt vi gjør her er at vi er konvertere den første bokstaven.
Så keykey [0] er bare den første bokstaven av hva strengen vi har,
vi kjører i.
Vi konverterer det til øvre og vi trekke av store bokstaver A,
så alt som gjør gir oss et tall
hvor vi kan hasj våre verdier på.
>> Og så skal vi tilbake hash modulus SIZE.
Være veldig, veldig forsiktig fordi teoretisk her
din hash-verdi kan være uendelig.
Det kunne bare gå videre og videre og videre.
Det kan være noen virkelig, virkelig stor verdi,
men fordi hash tabell som du har laget bare har 26 indekser,
du vil være sikker på din modulusing slik at du
ikke run-- det er det samme ting som queue--
slik at du ikke går av bunnen av hash-funksjon.
>> Du ønsker å vikle den tilbake rundt på samme måte i [uhørbart] når
du hadde som en veldig, svært stor bokstav, du
visste ikke at det skal bare kjøre på slutten.
Samme her, vil du sørge for at den kjører ikke på slutten av innpakning
rundt til toppen av bordet.
Så dette er bare en svært enkel hash funksjon.
Alt som gjorde var å ta det første brev av hva våre innspill var
og slå den inn i en indeks som vi kunne sette inn vår hash table.
>> Ja, og så som jeg sa tidligere, den måten at vi kan løse kollisjoner
i vår hash tabeller har, det vi kaller, kjeding.
Så hvis du prøver å sette inn flere ord som begynner med det samme,
du kommer til å ha en hash-verdi.
Avokado og eple, hvis du har kjøre det gjennom vår hash-funksjon,
kommer til å gi deg samme nummer, antall 0.
Og så måten vi løser det er at vi kan faktisk slags koble dem
sammen via lenkede lister.
>> Og så i denne forstand, dere kan se kind
av hvordan datastrukturer som vi har vært å sette tidligere
som en rosin lenket liste slag av kan komme sammen til én.
Og så kan du opprette langt mer effektive datastrukturer
som kan håndtere større mengder data, som dynamisk endre størrelse avhengig
på dine behov.
Alle klare?
Alle slags klar på hva som skjer her?
>> Hvis jeg ønsket å insert-- hva som er en frukt som starter med, vet jeg ikke,
B, annet enn bær, banan.
>> PUBLIKUM: Blackberry.
>> ANDI PENG: Blackberry, bjørnebær.
Hvor kommer bjørnebær gå her?
Vel, vi faktisk ikke har sortert dette ennå, men teoretisk
hvis vi ønsket å ha dette i alfabetisk rekkefølge,
hvor skal blackberry gå?
>> PUBLIKUM: [uhørbart]
>> ANDI PENG: Nøyaktig etter her, ikke sant?
Men siden det er svært vanskelig å reorder-- Jeg antar det er opp til dere.
Dere kan helt implementere hva du vil.
Jo mer effektivt å gjøre dette kanskje
ville være å sortere linket listen i alfabetisk rekkefølge,
og så når du er setter ting, vil du
å være sikker på å sette dem i alfabetisk rekkefølge
slik at så når du er prøver å søke dem,
du trenger ikke å krysse alt.
Du vet nøyaktig hvor det er, og det er lettere.
>> Men hvis du på en måte har ting ispedd tilfeldig,
du fortsatt kommer til å ha å krysse det anyways.
Og så hvis jeg ønsket å bare Sett bjørnebær her
og jeg ønsket å søke etter det, jeg vet, oh, bjørnebær
må starte med indeks på 1, så jeg vet umiddelbart bare søke på en.
Og så kan jeg slags traversere lenket liste
før jeg kommer til Blackberry, og then-- ja?
>> PUBLIKUM: Hvis du prøver å create-- Jeg antar at dette er en veldig enkel hash
funksjon.
Og hvis vi ønsket å gjøre flere lag av det som,
OK, vi ønsker å skille seg i som alle de alfabetiske bokstaver
og deretter igjen å like et annet sett av alfabetiske bokstaver i det,
vi setter som en hash tabell i en hash table,
eller som en funksjon innenfor en funksjon?
Eller er at--
>> ANDI PENG: Så din hash function-- din hash table
kan være så stor som du vil ha det til.
Så i denne forstand, tenkte jeg det var veldig enkelt, veldig
enkelt for meg å bare liksom basert på bokstavene i det første ordet.
Og så det er bare 26 alternativer.
Jeg kan bare få 26 alternativer fra 0-25 fordi de kan bare
starte fra A til Z. Men hvis du ønsket for å legge til, kanskje, mer kompleksitet
eller raskere kjøretid til din hash table, du absolutt
kan gjøre alle slags ting.
Du kan lage din egen ligning som gir deg
mer distribusjon i din ord, så når du søker,
det kommer til å være raskere.
>> Det er helt opp til dere hvordan du ønsker å implementere det.
Tenk på det som bare bøtter.
Hvis jeg ønsket å ha 26 bøtter, jeg kommer
å sortere ting i disse bøtter.
Men jeg kommer til å ha en haug ting i hver bøtte,
så hvis du ønsker å gjøre det raskere og mer effektivt,
la meg få hundre bøtter.
>> Men da må du regne ut en måte å sortere ting slik at de er
i riktig bøtte bør de være i.
Men så når du faktisk ønsker å se på det bøtte,
det er mye raskere fordi det er mindre ting i hver bøtte.
Og så, ja, det er faktisk Trikset for dere i pset5
er at du vil være utfordret til å bare lage
det som er den mest effektive funksjon du kan tenke på å være
i stand til å lagre og sjekke disse verdiene.
>> Helt opp til dere men du ønsker å gjøre det,
men det er et veldig godt poeng.
At den type logikk deg ønsker å begynne å tenke på
er, vel, hvorfor ikke jeg gjøre flere bøtter.
Og så må jeg søke mindre ting, og så kanskje jeg
har en annen hash-funksjon.
>> Ja, det er mange måter å gjøre dette PSet, noen er raskere enn andre.
Jeg er helt kommer til å bare se hvordan raskt var de raskeste dere vil
kunne få funksjoner skal fungere.
OK, alle bra på CHAINING og hash tabeller?
Det er faktisk som en veldig enkel konsept hvis du tenker på det.
Alt er det er å skille hva innganger er i bøtter,
sortere dem, og deretter søke på viser at det er forbundet med.
>> Kjølig.
Greit, nå har vi en annen type av datastruktur som kalles et tre.
La oss gå videre og snakke om prøver som er tydelig forskjellig,
men i samme kategori.
I hovedsak er alle et tre i stedet organisere data i lineær måte
som en hash table does-- deg vet, det har en topp og en bunn
og deretter du slags kobling av av det-- en Treet har en topp som du kaller det rot,
og da er det har blader hele veien rundt.
>> Og så alt du trenger her er bare toppen node
som peker til andre noder, som peker til flere noder, og så videre og så videre.
Og så må du bare splitte grener.
Det er bare en annen måte å organisere data, og fordi vi kaller det et tre,
dere just-- det er bare modellert ut til å se ut som et tre.
Det er derfor vi kaller det trær.
>> Hash table ser ut som et bord.
Et tre bare ser ut som et tre.
Alt er det er en egen måte å organisere noder
avhengig av hva dine behov er.
>> Så har du en rot og da har du blader.
Den måten at vi kan spesielt tenker på det er et binært tre,
et binært tre er bare en bestemt type av et tre
hvor hver node bare poeng til, på max, to andre noder.
Og så her har du tydelig symmetri i treet
som gjør det lettere å slags se på hvilke verdier du er fordi da
har alltid en venstre eller høyre.
Det er aldri som en venstre tredjedel fra venstre eller en fjerde fra venstre.
Det er bare du har en venstre og en høyre og du kan søke en av de to.
Og så hvorfor er dette nyttig?
Den måte som dette er nyttig er hvis du leter
å søke gjennom verdier, ikke sant?
Snarere enn å implementere binære Søk i en feil array,
hvis du ønsket å være i stand til å sette noder og ta bort noder på vilje og også
bevare søk kapasiteter på binære søk.
Så på denne måten, er vi på en måte tricking-- husker da vi
sa lenkede lister kan ikke binære søk?
Vi slags lage en datastruktur at triks som i arbeids.
>> Og så fordi lenkede lister er lineær, de bare koble den ene etter den andre.
Vi kan slags ha forskjellige slags pekere
som peker til forskjellige noder som kan hjelpe oss med søket.
Og så her, hvis jeg ønsket å har et binært søketre,
Jeg vet at mitt mellomnavn hvis 55.
Jeg skal bare lage den som mitt mellomnavn, som min rot,
og så kommer jeg til å ha verdier spinne ut av det.
>> Så her, hvis jeg skal søke etter verdien av 66, kan jeg begynne på 55.
Det er 66 større enn 55?
Ja, det er, så jeg vet jeg mus søke Jeg n høyre peker av dette treet.
Jeg går til 77.
OK, er 66 mindre enn eller større enn 77?
Det er mindre enn, så du vet, oh, som må være den venstre noden.
>> Og så her vi er slags bevare alle de store tingene om matriser,
slik som dynamisk skalering av gjenstander, som er
i stand til å sette inn og slette på vilje, uten å måtte bekymre seg om fast
mengde plass.
Vi har fortsatt bevare alle de fantastiske tingene
samtidig være i stand til å bevare log og søk tidspunktet for binære søk
at vi var bare tidligere stand til å få en setning.
>> Cool datastruktur, type komplisert å implementere, noden.
Som du kan se, alt det er struct av noden
er at du har en venstre og en høyre peker.
Det er alt det er.
Så i stedet for bare å ha en x eller et foregående.
Du har en venstre eller høyre, og deretter du kan slags koble dem sammen
men du så ønsker.
>> OK, vi faktisk kommer bare ta noen få minutter.
Så vi kommer til å dra tilbake hit.
Som jeg sa tidligere, Jeg slags forklart
logikken bak hvordan vi vil søke gjennom dette.
Vi kommer til å prøve pseudocoding dette ut for å se
hvis vi kan slags bruke samme logikk binære søk
til en annen type datastruktur.
Hvis dere ønsker å ta ut et par minutter å bare tenke på dette.
OK.
Greit, jeg kommer til å faktisk bare gi deg the-- nei,
vi skal snakke om pseudo først.
Så er det noen som vil ha å gi et stikk på hva
det første du vil gjøre når du starter opp søking er?
Hvis vi leter etter verdien av 66, hva er
det første vi vil gjøre hvis vi ønsker til binær søke dette treet?
>> PUBLIKUM: Du ønsker å se rett og se til venstre og se [uhørbart]
større antall.
>> ANDI PENG: Ja, akkurat.
Så du kommer til å se på rot.
Det er mange måter du kan ringe det dine foreldre node folk sier.
Jeg liker å si rot fordi det er som roten av treet.
Du kommer til å se på root node, og du er
kommer til å se er 66 større eller mindre enn 55.
Og hvis det er større enn, vel, det er større enn, der vi ønsker å se?
Hvor ønsker vi å søke nå, ikke sant?
Vi ønsker å søke på høyre halvdel av dette treet.
>> Så vi har, praktisk, en peker som peker til høyre.
Og så da kan vi sette vår nye rot til 77.
Vi kan bare gå dit pekeren peker.
Vel, oh, her vi starter på 77, og vi kan bare
gjøre dette rekursivt igjen og igjen.
På denne måten, du snill av har en funksjon.
Du har en måte å søke som du kan bare gjenta om og om igjen og om igjen,
avhengig av hvor du ønsker å se til du til slutt får til verdien
at du søker etter.
Gir mening?
>> Jeg er i ferd med å vise deg den faktiske kode, og det er mye kode.
Du trenger ikke å frik ut.
Vi skal snakke gjennom det.
>> Faktisk ikke.
Det var bare pseudokode.
OK, det var bare pseudo, som er litt komplisert,
men det er helt greit.
Alle følge med her?
Hvis roten er null, retur falsk fordi det betyr
du trenger ikke engang noe der.
>> Hvis root n er verdien, så hvis det skjer for å være den du ser på,
så du kommer til å returnere true fordi du vet at du har funnet det.
Men hvis verdien er mindre enn roten av n, er du
kommer til å søke venstre barn eller venstre blad,
hva du vil kalle det.
Og hvis verdien er større enn roten du kommer til å søke på riktig treet,
så bare kjør funksjonen gjennom søk på nytt.
>> Og hvis roten er null, at det betyr at du har nådd slutten?
Det betyr at du ikke har noen mer flere blader for å søke,
da vet du, oh, jeg antar det ikke er her
fordi etter at jeg har sett gjennom hele greia og det er ikke her,
det bare ikke kan være her.
>> Betyr det fornuftig for alle?
Så det er som binær søk bevare egenskapene til lenkede lister.
Kult, og så den andre typen av data struktur dere
kan prøve å implementere på ditt PSet, trenger du bare å velge én metode.
Men kanskje en alternativ metode for å hash tabellen er det vi kaller en trie.
>> Alt en trie er er en bestemt type tre som
har verdier som går til andre verdier.
Så i stedet for å ha en binær tre i den forstand at bare ett
ting kan peke på to, kan du ha en ting peker på mange, mange ting.
Du har egentlig arrays innsiden av der du lagrer
pekere som peker til andre arrays.
>> Så noden av hvordan vi ville definere en trie
er vi ønsker å ha en Boolean, c ord, ikke sant?
Så noden er boolsk som sant eller usant,
først av alt på hodet av som matrise, er dette et ord?
Dernest, du vil ha tips til hvilken resten av dem er.
Litt komplisert, litt abstrakt, men Jeg vil forklare hva det betyr.
>> Så her, på toppen, hvis du har en rekke erklært allerede
en node der du har en boolsk verdien som er lagret på forsiden
som forteller deg er dette et ord?
Er ikke dette et ord?
Og så har du resten av matrise som
faktisk lagrer all mulighetene for hva det kunne være.
Så, for eksempel, i likhet på toppen har du
den første som sier sant eller usant, ja eller nei, dette er et ord.
>> Og da har du 0 til 26 av bokstavene som du kan lagre.
Hvis jeg ønsket å søke her for bat, jeg går til toppen
og jeg ser for B. Jeg finner B i min array, og så jeg vet, OK, er B et ord?
B er ikke et ord, slik at dermed Jeg må fortsette å søke.
Jeg går fra B, og jeg ser til peker på at B peker mot
og jeg ser en annen utvalg av informasjon, samme struktur som vi hadde før.
>> Og her-- oh, den neste brev i [uhørbart] er A.
Så vi ser i denne matrisen.
Vi finner den åttende verdi, og deretter vi se å se, oh,
hei, er det et ord, er B-A et ord?
Det er ikke et ord.
Vi er nødt til å holde utkikk.
>> Og så så vi ser hvor pekeren av A-poeng,
og den peker på en annen måte i som vi har mer verdi lagret.
Og til slutt, vi kommer til å B-A-T, som er et ord.
Og så neste gang du ser, du kommer
å ha det sjekk av, ja, dette boolsk funksjon er sant.
Og så i den forstand vi er snille ved å ha et tre med matriser.
>> Så da du kan slags søke ned.
Heller enn en funksjon, og hashing tilordne verdier ved lenket liste,
du kan bare gjennomføre en trie som søker downwords.
Virkelig, virkelig komplisert ting.
Ikke lett å tenke på fordi jeg liker spytter så mange datastrukturer ut
på deg, men gjør alle slags forstå hvordan logikken i dette fungerer?
>> Ok kult.
So B-A-T, og deretter du kommer til å søke.
Neste gang du kommer å se, oh, hey, det er sant,
dermed jeg vet at dette må være et ord.
>> Samme for dyrehagen.
Så her er tingen akkurat nå, hvis vi ønsket å søke etter zoo, akkurat nå,
tiden zoo er ikke en ord i vår ordbok
fordi, som dere kan se, utgangspunktet at vi har en boolsk
return true ligger i enden av zoom.
Vi har Z-O-O-M.
>> Og så her, vi trenger faktisk ikke ordet, zoo, i vår ordliste
fordi denne boksen ikke er merket.
Slik at maskinen ikke vet at zoo er et ord
fordi den måten at vi har lagret det, bare en zoom her
faktisk har en boolsk verdi som er blitt slått sant.
Så hvis vi ønsker å sette inn ord, zoo, i vår ordbok,
hvordan ville vi gå om du gjør det?
Hva må vi gjøre for å sikre at våre datamaskinen vet at Z-O-O er et ord
og ikke det første ordet er Z-O-O-M?
>> PUBLIKUM: [uhørbart]
>> ANDI PENG: Akkurat, vi vil være sikker på at dette
her, er at boolsk verdi krysset av at det er sant.
Z-O-O, så vi kommer til å sjekke det, slik at vi vet nøyaktig, hei, er zoo et ord.
Jeg kommer til å fortelle datamaskin at det er et ord så
at når datamaskinen sjekker, den vet at zoo er et ord.
>> Fordi huske alle disse dataene strukturer, er det veldig lett for oss
å si, oh, er bat et ord.
Zoo er et ord.
Zoom er et ord.
Men når du bygger den, datamaskinen har ingen anelse.
>> Så må du fortelle det akkurat på hvilket punkt er dette et ord?
På hvilket tidspunkt er det ikke et ord?
Og på hvilket punkt gjør jeg trenger å søke ting,
og på hvilket tidspunkt må jeg gå videre?
Alle klar av det?
Kjølig.
>> Og så så kommer Problemet med hvordan ville vi
gå om å sette inn noe det er faktisk ikke det?
Så la oss bare si at vi ønsker å sette inn ordet, bad, inn i vårt trie.
Som dere kan se ut som i dag alt vi har nå er B-A-T,
og denne nye datastrukturen der hadde en halvliter som
pekte på null fordi vi antar at, åh, det er ingen ord etter B-A-T,
hvorfor trenger vi å holde ha ting etter at T.
>> Men problemet oppstår hvis vi gjør du ønsker å ha et ord som kommer etter
T-tallet.
Hvis du har badekar, er du kommer til å ønske en H høyre.
Og så måten vi kommer til å gjøre det på er vi kommer til å opprette en egen node.
Vi er ikke tildele det beløpet minne for denne nye array,
og vi kommer til å overføre pekere.
>> Vi kommer til å tildele H, Først av alt, dette null,
vi kommer til å bli kvitt.
Vi kommer til å ha de H peke nedover.
Hvis vi ser en H, vi vil ha det å gå til et annet sted.
>> I her, kan vi da krysse av ja.
Hvis vi treffer en H etter T, oh, da vet vi at dette er et ord.
Den boolske kommer til å returnere sann.
Alle klare på hvordan det skjedde?
OK.
>> Så egentlig, alle disse datastrukturer
at vi har gått over i dag, har jeg gått over dem virkelig, virkelig raskt
og ikke i for mye detalj, og det er OK.
Når du begynner å rote med det, vil du være
holde styr på hvor alle pekere er,
hva som skjer i ditt datastrukturer, et cetera.
De vil være svært nyttig, og det er opp til deg
gutta å helt finne ut hvordan du ønsker å gjennomføre ting.
>> Og så pset4, av 5-- oh, er det galt.
Pset5 er feilstavinger.
Som jeg sa tidligere, du kommer til, en gang igjen, last ned kildekoden fra oss.
Det kommer til å være tre hoved ting du skal laste ned.
Du vil laste ned ordbøker, kers og tekster.
>> Alle disse tingene er er enten ordbøker av ord
at vi ønsker å sjekke eller test av informasjon
at vi vil at du skal stave sjekk.
Og så ordbøker gir vi deg kommer
for å gi deg faktiske ordene som vi ønsker du lagre liksom på en måte som er
mer effektiv enn en matrise.
Og så er tekstene kommer til å være det vi er
ber deg om å stave sjekke at alle ordene er det virkelige ord.
>> Og så tre blokker av programmer som vi vil gi deg
kalles dictionary.c, dictionary.h, og speller.c.
Og så alt dictionary.c gjør er hva du blir bedt om å gjennomføre.
Den laster ord.
Det stave sjekker dem, og det gjør at at alt er satt inn riktig.
>> diction.h er bare en bibliotekfilen som erklærer alle disse funksjonene.
Og speller.c, kommer vi til å gi deg.
Du trenger ikke å endre noe av det.
All speller.c gjør er å ta det, laster det, kontrollerer hastigheten av den,
tester benchmark som hvordan raskt du klarer å gjøre ting.
>> Det er en stavekontroll.
Bare ikke rotet med det, men gjøre at du forstår hva det gjør.
Vi bruker en funksjon kalt getrusage at tester ytelsen til spell
kontrolløren.
Alt den gjør er i utgangspunktet teste tidspunktet for alt i ordboken,
så sørg for at du forstår det.
Vær forsiktig med å ikke rote med det eller ellers ting vil ikke kjøre skikkelig.
>> Og mesteparten av denne utfordringen er for dere å virkelig endre dictionary.c.
Vi kommer til å gi deg 140.000 ord i en ordbok.
Vi kommer til å gi deg en tekst fil som har disse ordene,
og vi vil at du skal være i stand til å organisere dem inn i en hash tabell eller en trie
fordi når vi ber deg om å stave check-- tenk hvis du er spell
sjekke ut Homers Odysseen.
Det er som dette stor, stor test.
>> Tenk om hver enkelt Ordet du måtte se
gjennom en rekke 140.000 verdier.
Det ville ta en evighet for maskinen å kjøre.
Det er derfor vi ønsker å organisere vår data til mer effektive datastrukturer
for eksempel en hash tabell eller en trie.
Og så dere kan kind av når du søker tilgang
ting lettere og raskere.
>> Og så vær forsiktig med å løse kollisjoner.
Du kommer til å få en haug av ord som starter med A.
Du kommer til å få en haug ord som starter med B. Inntil du
Gutta hvordan du ønsker å løse det.
Kanskje det er mer effektiv hash-funksjon
enn bare den første bokstaven i noe, og slik at det er opp til deg
Gutta til slags gjøre hva du vil.
>> Kanskje du ønsker å legge til alle bokstavene sammen.
Kanskje du vil like å gjøre rare ting å redegjøre antall bokstaver,
samme det.
Opp til dere hvordan dere ønsker å gjøre.
Hvis du ønsker å gjøre en hash table, hvis du ønsker å prøve en trie, helt opp til deg.
Jeg vil advare deg på forhånd at trie er vanligvis litt vanskeligere
bare fordi det er mye flere tips for å holde styr på.
Men helt opp til dere.
Det er langt mer effektiv i de fleste tilfeller.
Du ønsker å virkelig være i stand til å holde styr på alle dine pekere.
Som gjør det samme som jeg gjorde her.
Når du prøver å sette inn verdier inn i en hash tabell eller slette,
forsikre deg om at du er virkelig holde styr
hvor alt er fordi det er veldig lett for hvis jeg er
prøver å sette inn som ordet, andy.
La oss bare si at det er en ekte ord, ord, andy,
inn i en gigantisk liste over A ord.
>> Hvis jeg bare tilfeldigvis overføre en peker feil, oops,
det går helheten av resten av mitt lenket liste.
Nå er det eneste ordet jeg har er andy, og nå
alle de andre ordene i ordboken ha gått tapt.
Og så du vil være sikker på at du holde oversikt over alle dine pekere
eller annet du kommer til å få store problemer i koden din.
Trekke ut ting nøye steg for steg.
Det gjør det mye lettere å tenke på.
>> Og til slutt, vil du være i stand til å teste ytelsen til programmet
på den store bord.
Hvis dere tar en se på CS50 akkurat nå,
vi har det som kalles den store bord.
Det er poengsummen ark med den raskeste stavekontroll ganger på tvers av alle CS50
akkurat nå, tror jeg toppen som 10 ganger jeg tror åtte av dem er ansatte.
Vi ønsker dere å slå oss.
>> Alle av oss prøvde å implementere den raskeste koden som mulig.
Vi ønsker dere å prøve å utfordre oss og implementere raskere enn alle oss
kan.
Og så dette er virkelig første gang at vi er
spør dere til å gjøre en PSet som du virkelig kan gjøre uansett metode
du vil.
>> Jeg alltid sier, dette er mer beslektet til en real-life løsning, ikke sant?
Jeg sier hei, jeg trenger deg til å gjøre dette.
Bygge et program som gjør dette for meg.
Gjør det slik du vil.
Jeg bare vet at jeg ønsker å faste.
Det er din utfordring for denne uken.
Dere skal vi for å gi deg en oppgave.
Vi kommer til å gi deg en utfordring.
Og så er det opp til dere å fullstendig bare finne ut
hva er den raskeste og mest effektiv måte å gjennomføre dette.
Yeah?
>> PUBLIKUM: Er vi lov til hvis ønsket å forske raskere måter
å gjøre hash tabeller på nettet, kan vi gjøre det og sitere andres koden?
ANDI PENG: Ja, helt greit.
Så hvis dere lese spec, det er en linje
i spec som sier dere er helt gratis å forske hash
funksjonene på hva er noen av de raskere hash funksjoner
å kjøre gjennom ting som lenge du sitere denne koden.
Så noen mennesker har allerede funnet ut raske måter
av å gjøre stavekontroller, for fort måter å lagre informasjon.
Helt opp til dere hvis dere ønsker å bare ta det, ikke sant?
Sørg for at du siterer.
Utfordringen her egentlig at vi prøver å teste
er å sørge for at du vet veien rundt pekere.
Så langt du implementere selve hash-funksjon
og kommer opp med lignende regnestykket til å gjøre det,
dere kan undersøke hva metoder online dere ønsker.
Yeah?
>> PUBLIKUM: Kan vi sitere bare ved hjelp av [uhørbart]?
>> ANDI PENG: Yeah.
Du kan bare, i kommentaren din, Du kan sitere liker, oh,
tatt fra yada, yada, yada, hash-funksjon.
Alle som har noen spørsmål?
Vi har faktisk breezed gjennom seksjonen i dag.
Jeg vil være her oppe til svare på spørsmål også.
>> Også, som jeg sa, kontor timer i kveld og i morgen.
Spec denne uken er faktisk super enkelt og super kort til å lese.
Jeg foreslår at du tar en titt, bare lese gjennom helheten av det.
>> Og Zamyla faktisk leder deg gjennom hver av funksjonene
du trenger for å implementere, og så det er veldig, veldig klart hvordan du gjør alt.
Bare for å sikre at du er holde styr på pekere.
Dette er en svært utfordrende PSet.
>> Det er ikke utfordrende fordi liker, oh, begrepene er så mye mer
vanskelig, eller du må lære så mye ny syntaks veien
at du gjorde for den siste PSet.
Dette PSet er vanskelig fordi det er så mange tips,
og da er det veldig, veldig lett å en gang du har en feil i koden din ikke kunne
å finne hvor som feilen er.
>> Og så fullstendig og absolutt tro på deg gutta å kunne slå vår [uhørbart]
stavemåter.
Jeg har faktisk ikke noe skriftlig gruve ennå, men jeg er i ferd med å skrive mine.
Så mens du skriver yours, jeg skal skrive mine.
Jeg kommer til å prøve å gjøre min raskere enn din.
Vi får se hvem som har den raskeste.
>> Og ja, jeg vil se alle dere her på tirsdag.
Jeg vil kjøre en slags som en PSet verksted.
Alle seksjonene denne uke er PSet workshops,
så dere har mange muligheter om hjelp, kontortiden som alltid,
og jeg ser virkelig frem til har lest alle dine gutta "kode.
Jeg har quizer opp her hvis du Gutta ønsker å komme og hente dem.
Det er alt.