[Musikken afspilles]
SPEAKER 1: Okay.
Alle velkommen tilbage til afsnittet.
Jeg håber du alle er med succes inddrives fra din quiz
fra sidste uge.
Jeg ved det er en lille smule skør til tider.
Som jeg sagde før, hvis du er inden for standardafvigelsen,
egentlig ikke bekymre dig om det, især for en mindre behagelig sektion.
Det handler om, hvor du skal være.
>> Hvis du gjorde stor, så awesome.
Kudos til dig.
Og hvis du føler at du har brug for lidt mere hjælp, kan du
velkommen til at nå ud til nogen af ​​TFS.
Vi er alle her for at hjælpe.
>> Det er derfor, vi underviser.
Det er derfor, jeg er her hver mandag for dig fyre og på kontoret timer om torsdagen.
Så er du velkommen til at lade mig vide hvis du er bekymret om noget
eller hvis der er noget på quiz at du virkelig gerne vil tage fat på.
>> Så dagsordenen for i dag er Alt om datastrukturer.
Nogle af disse er bare at være lige at få dig fortrolig med disse.
Du må aldrig gennemføre dem i denne klasse.
Nogle af dem du vil, lignende for din speller pset.
>> Du har dit valg mellem hash tabeller og forsøger.
Så vi vil helt sikkert være at gå over dem.
Det kommer til at være absolut mere af naturalier af høj sektion niveau i dag, selv om,
fordi der er en masse af dem, og hvis vi gik i detaljer med gennemførelsen
på alle disse, ville vi ikke selv komme igennem hægtede lister
og måske en lille smule hash-tabeller.
>> Så bær over med mig.
Vi kommer ikke til at gøre så meget som koder dette tidspunkt.
Hvis du har spørgsmål om det eller du ønsker at se det gennemført
eller prøv det selv, Jeg helt klart anbefale
vil study.cs50.net, som har eksempler på alle disse.
Det vil have mine PowerPoints med de noter, vi
tendens til at bruge samt nogle programmering øvelser, især for ting
ligesom hægtede lister og binær træer stakke og køer.
Så lidt mere højt niveau, som kunne være rart for jer.
>> Så med dette, vil vi komme i gang.
Og også, yes-- quizzer.
Jeg tror de fleste af jer, der er i min afdeling har dine quizzer,
men nogen kommer i eller anden grund ikke gør det, de er lige her i front.
>> Så hægtede lister.
Jeg kender denne slags går at sikkerhedskopiere før din quiz.
Det var ugen før at vi lærte om dette.
Men i dette tilfælde, vil vi blot gå lidt mere i dybden.
>> Så hvorfor kan vi vælge en sammenkædet liste over en array?
Hvad adskiller dem?
Ja?
>> PUBLIKUM: Du kan udvide en sammenkædet listen versus et array er fast størrelse.
SPEAKER 1: Right.
Et array har fast størrelse mens en linket liste har en variabel størrelse.
Så hvis vi ikke ved, hvordan meget vi ønsker at gemme,
en sammenkædet liste giver os en stor måde at gøre det, fordi vi kan bare
tilføje en anden node og tilføje et andet knudepunkt og tilføje en anden node.
Men hvad der kunne være et trade-off?
Er der nogen der kan huske det trade-off mellem arrays og hægtede lister?
Mmhmm?
>> PUBLIKUM: Du er nødt til gå igennem hele vejen
gennem linkede liste finde et element i en liste.
I et array, kan du bare finde et element.
>> SPEAKER 1: Right.
Så med arrays--
>> PUBLIKUM: [uhørligt].
>> SPEAKER 1: Med arrays, vi har hvad der kaldes random access.
Betyder, at hvis vi ønsker, hvad er nogensinde femte punkt af en liste
eller det femte punkt i vores array, kan vi bare få fat i det.
Hvis det er en linket liste, vi har at gentage gennem, right?
Så at få adgang til et element i et array er konstant tid,
hvorimod med en sammenkædet liste ville det sandsynligvis være lineær tid, fordi måske
vores element er hele vejen i slutningen.
Vi er nødt til at søge gennem alt.
Så med alle disse data strukturer vi kommer
at bruge lidt mere tid på, hvad er plusser og negativer.
Hvornår kan vi ønsker at bruge den ene over den anden?
Og det er sådan det større ting at tage væk.
>> Så vi har her definition af et knudepunkt.
Det er ligesom et element i vores linkede liste, right?
Så vi er alle bekendt med vores typedef structs,
som vi gik over bedømmelsesudvalg sidste gang.
Det var dybest set blot at skabe en anden datatype, som vi kunne bruge.
>> Og i dette tilfælde, det er nogle node der vil holde nogle heltal i.
Og hvad er så den anden del her?
Anyone?
>> PUBLIKUM: [uhørligt].
>> SPEAKER 1: Ja.
Det er en pointer til det næste knudepunkt.
Så dette burde faktisk være her oppe.
Dette er en henvisning af typen node til den næste ting.
Og det er, hvad de omfatter vores node.
Cool.
>> Okay, så med søgning, som vi var bare at sige før hånd, hvis du er
kommer til at søge igennem, du er nødt til rent faktisk at gentage
gennem din linkede liste.
Så hvis vi leder efter det antal 9, vil vi starte på vores hoved
og som peger os i begyndelsen af vores linkede liste, right?
Og vi siger, OK, gør dette node indeholder nummer 9?
Nej?
>> Okay, gå til den næste.
Følg det.
Indeholder det nummer 9?
Nej.
Følg den næste.
>> Så vi er nødt til rent faktisk at gentage gennem vores linkede liste.
Vi kan ikke bare gå direkte til, hvor 9 er.
Og hvis du fyre rent faktisk ønsker at se nogle pseudo-kode deroppe.
Vi har nogle søgefunktionen her der tager in-- hvad tager det i?
Hvad mener du?
Så let.
Hvad er dette?
PUBLIKUM: [uhørligt].
SPEAKER 1: Antallet, vi leder efter.
Right?
Og hvad ville det svare til?
Det er en pointer til?
>> PUBLIKUM: En node.
>> SPEAKER 1: A node til listen at vi kigger på, right?
Så vi har nogle knuder er pointer her.
Det er et punkt, der kommer til faktisk gentage gennem vores liste.
Vi sætter det lige at liste fordi det er bare
sætte den lig med start af vores linkede liste.
>> Og mens det ikke er NULL, mens vi stadig har ting i vores liste,
kontrollere, om denne knude har det nummer, vi leder efter.
Returnere sandt.
Ellers opdatere det, right?
>> Hvis det er NULL, vi afslutte vores mens loop og return false
fordi det betyder, at vi ikke har fundet det.
Skal alle få, hvordan det fungerer?
OK.
>> Så med indsættelse, du have tre forskellige måder.
Du kan tilføjes i begyndelsen, du kan føje og du kan indsætte i assorteret.
I dette tilfælde er vi kommer til at gøre en prepend.
Er der nogen vide, hvordan de tre tilfælde kan afvige?
>> Så prepend betyder, at du lægger det på forsiden af ​​din liste.
Så ville det betyde, at uanset hvad din node er, uanset
hvad værdien er, er du nødt at sætte det her i front, OK?
Det kommer til at være den første element på din liste.
>> Hvis du vedhæfte det, går det at gå til bagsiden af ​​din liste.
Og indsætte i assorterede betyder, at du vil sætte faktisk til stedet
hvor det holder din linkede liste sorteres.
Igen, hvordan du bruger dem, og når du bruger
dem vil variere afhængigt af din sag.
Hvis det ikke er nødvendigt at sorteres, prepend tendens
at være, hvad de fleste mennesker bruge, fordi du ikke
nødt til at gå igennem hele listen at finde enden for at tilføje det på, right?
Du kan bare holde det ret i.
>> Så vi vil gå gennem en indsættelse 1 lige nu.
Så én ting, jeg har tænkt mig at anbefaler på denne pset
er at trække tingene ud, som altid.
Det er meget vigtigt, at du opdaterer dine pejlemærker i den rigtige rækkefølge
fordi hvis du opdaterer dem lidt ud af orden,
du kommer til at ende op miste dele af din liste.
>> Så for eksempel, i dette tilfælde, er vi fortæller hovedet til blot punkt 1.
Hvis vi bare gør det uden at gemme denne 1,
vi har ingen idé om, hvad 1 skal pege på nu
fordi vi har mistet, hvad hovedet pegede på.
Så én ting at huske når du laver en prepend
er at spare, hvad hoved peger på første,
derefter videreoverdrage dem, og derefter opdatere hvad din nye node skal pege på.
I dette tilfælde, dette er en måde at gøre det.
>> Så hvis vi havde gjort det på denne måde hvor vi netop genindtrådt hoved,
vi mister dybest set vores hele listen, right?
En måde at gøre det på er at have 1 point til næste, og så har hoved punkt 1.
Eller du kan gøre lidt ligesom midlertidig oplagring, som jeg talte om.
>> Men omfordeling din pejlemærker i den rigtige rækkefølge
kommer til at være meget, meget vigtigt for denne pset.
Ellers er du nødt til at have en hash tabel eller en prøve, der er bare kommer til at være
kun en del af de ord, du ønsker, og derefter you're-- mmhmm?
PUBLIKUM: Hvad var den midlertidige opbevaring ting, du talte om?
SPEAKER 1: midlertidig opbevaring.
Så dybest set en anden måde du kan gøre dette
er lagre lederen af ​​noget, ligesom gemme det midlertidigt variabel.
Tildele den til 1 og derefter opdatere 1 til punkt
til uanset hoved bruges til at pege på.
Denne måde er naturligvis mere elegant, fordi du
behøver ikke en midlertidig værdi, men bare tilbyde en anden måde at gøre det.
Og vi har faktisk noget kode til dette.
Så for linkede liste, vi faktisk har nogle kode.
Så indsætte her, er dette prepending.
Så dette ind i det ved hovedet.
>> Så første ting, du skal oprette din nye node, selvfølgelig,
og tjekke for NULL.
Altid godt.
Og så er du nødt til at tildele værdier.
Når du opretter en ny node, du ved ikke, hvad det er at pege på næste,
så du ønsker at initialisere den til NULL.
Hvis det ikke ender peger på noget andet, det bliver omfordelt, og det er fint.
Hvis det er den første ting på listen, er det nødvendigt
at pege på NULL, fordi det er slutningen af ​​listen.
>> Så for at indsætte det, vi ser her vi tildeler den næste værdi af vores node
at være, hvad hovedet er hvilket er, hvad vi havde her.
Det er hvad vi lige gjorde.
Og så er vi tildele hoved til punkt til vores nye knudepunkt, fordi huske,
ny er nogle pointer til et knudepunkt, og det er præcis, hvad hovedet er.
Det er præcis derfor, vi har denne pil tilb.
Cool?
Mmhmm?
>> PUBLIKUM: Skal vi initialisere ny næste NULL første,
eller kan vi bare initialisere den til hovedet?
>> SPEAKER 1: Ny næste skal være NULL til at starte
fordi du ikke kender hvor det kommer til at være.
Også dette er slags ligesom et paradigme.
Du sætter det lig med NULL bare for at gøre sikker på, at alle dine baser er dækket
før du gør nogen omplacering, således at er du altid garanteret, at den vil
pege på en bestemt værdi versus ligesom en garbage værdi.
Fordi, ja, vi tildeler ny næste automatisk,
men det er mere ligesom en god praksis at initialisere det
på den måde og derefter overflytte.
>> OK, så dobbelt hægtede lister nu.
Hvad mener vi?
Hvad er anderledes med dobbelt hægtede lister?
>> Så i vores hægtede lister, vi kan kun bevæge sig i én retning, right?
Vi har kun næste.
Vi kan kun gå fremad.
>> Med en dobbelt sammenkædet liste, Vi kan også bevæge sig baglæns.
Så vi har ikke kun nummer, som vi ønsker at gemme,
vi har hvor den peger på næste og hvor vi bare kom fra.
Så det giver mulighed for nogle bedre traversal.
>> Så dobbelt forbundne knudepunkter, meget ens, right?
Eneste forskel er nu vi har en næste og foregående.
Det er den eneste forskel.
>> Så hvis vi skulle tilføjes i begyndelsen eller append-- vi ikke har nogen kode for denne op her--
men hvis du skulle prøve og indsætte det, det vigtigste
er du nødt til at gøre sikker på du tildele
både din tidligere og din næste pointer korrekt.
Så i dette tilfælde, ville du ikke kun initialisere næste,
du initialiserer tidligere.
Hvis vi er i spidsen af ​​listen, vi ville ikke kun gøre hoved lige nye,
men vores nye tidligere skulle peger på hovedet, right?
>> Det er den eneste forskel.
Og hvis du ønsker mere praksis med disse med hægtede lister, med indsættelse,
med at slette, med indsats ind i et velassorteret liste
Venligst tjek study.cs50.net.
Der er en masse store øvelser.
Jeg kan varmt anbefale dem.
Jeg ville ønske, vi havde tid til at gå igennem dem men der er en masse af datastrukturer
at komme igennem.
>> OK, så hash-tabeller.
Dette er sandsynligvis den mest nyttige bit for din pset
her, fordi du vil være gennemføre en af ​​disse, eller en prøve.
Jeg kan virkelig godt lide hash-tabeller.
De er pretty cool.
>> Så dybest set, hvad sker, er en hash tabel
er, når vi virkelig har brug for hurtig indsættelse, sletning og opslag.
Det er de ting, som vi er prioritering i en hash tabel.
De kan få temmelig store, men som vi skal se med forsøg,
Der er ting, der er meget større.
>> Men dybest set, alle en hash tabel er en hash-funktion
der fortæller dig, hvilken spand til at sætte hver af dine data, hver af dine elementer i.
En enkel måde at tænke på en hash tabel er, at det er bare spande af ting,
højre?
Så når du sorterer tingene ved ligesom det første bogstav i deres navn,
det er lidt ligesom en hash tabel.
>> Så hvis jeg var til gruppe, du fyre er i grupper af hvem navn starter
med A herovre, eller hvem har fødselsdag er i januar, februar, marts,
uanset hvad, det er effektivt skabe en hash tabel.
Det er bare at skabe spande som du sortere dine elementer i
så du kan finde dem lettere.
Så på denne måde, når jeg har brug for at finde en af ​​jer,
Jeg behøver ikke at søge gennem hver af dine navne.
Jeg kan være ligesom, åh, jeg ved, at Danielle fødselsdag er in--
PUBLIKUM: --April.
SPEAKER 1: April.
Så jeg ser i min April spand, og med lidt held,
hun vil være den eneste i der, og min tid var konstant i den forstand,
hvorimod hvis jeg nødt til at se gennem en hel masse mennesker,
det kommer til at tage meget længere tid.
Så hash tabeller er egentlig bare spande.
Nem måde at tænke på dem.
>> Så en meget vigtig ting om en hash tabel er en hash-funktion.
Så de ting, jeg lige talt om, ligesom dit første bogstav i dit fornavn
eller din fødselsdag måned, disse ideer,
virkelig korrelere til en hash-funktion.
Det er bare en måde at afgøre hvilke spand, du element går ind, OK?
Så for denne pset, kan du slå op temmelig meget enhver hash funktion, du ønsker.
>> Behøver ikke at være din egen.
Der er nogle virkelig cool dem ud der at gøre alle mulige skøre matematik.
Og hvis du ønsker at gøre dit stavekontrollen super hurtig,
Jeg ville helt sikkert se på en af ​​dem.
>> Men der er også den simple dem, ligesom beregne
summen af ​​de ord, som hvert bogstav har en række.
Beregne summen.
Der afgør spanden.
De har også de nemme dem, er ligesom alle A'er her,
alle B er her.
Enhver en af ​​dem.
>> Dybest set, det bare fortæller dig, hvilke arrayindeks dit element skal gå ind.
Bare afgøre bucket-- det hele er en hash-funktion er.
Så her har vi et eksempel, som er bare det første bogstav i strengen
at jeg bare taler om.
>> Så du har nogle hash det er bare første bogstav i din streng minus A,
som vil give dig nogle tal mellem 0 og 25.
Og hvad du ønsker at gøre, er sørge for, at dette repræsenterer
størrelsen af ​​din hash table-- hvor mange spande der er.
Med mange af disse hashfunktioner, de er
vil være tilbage værdier, der kan være langt over det antal spande
at du rent faktisk har i din hash tabel,
så du behøver at gøre sikker og MOD af dem.
Ellers går det til at sige, oh, bør det være i spand 5.000
men du har kun 30 spande i din hash tabellen.
Og selvfølgelig, vi alle ved, det er kommer til at resultere i nogle vanvittige fejl.
Så sørg for at Mod ved størrelsen på din hash tabellen.
Cool.
Så kollisioner.
Er alle godt hidtil?
Mmhmm?
>> PUBLIKUM: Hvorfor ville det returnere en sådan massiv værdi?
>> SPEAKER 1: Afhængigt af algoritmen at din hash funktion bruger.
Nogle af dem vil gøre crazy multiplikation.
Og det handler om at få en jævn fordeling,
så de gør nogle virkelig skøre ting undertiden.
Det er alt.
Noget andet?
OK.
>> Så kollisioner.
Dybest set, som jeg sagde tidligere, i bedste fald,
enhver spand jeg ser ind i, er vil have en ting,
så jeg ikke behøver at se på alle, right?
Jeg enten ved, det er der, eller det er ikke, og det er, hvad vi virkelig ønsker.
Men hvis vi har titusinder af datapunkter og mindre end dette antal
af spande, vi kommer til at have kollisioner, hvor tiden noget
er nødt til at ende i en spand, der allerede har et element.
>> Så spørgsmålet er, hvad gør vi i dette tilfælde?
Hvad gør vi?
Vi har allerede noget der?
Skal vi bare smide det ud?
>> Nej.
Vi er nødt til at holde dem begge.
Så den måde, at vi typisk gør, der er hvad?
Hvad er datastrukturen vi netop talt om?
PUBLIKUM: Linked listen.
SPEAKER 1: En linkede liste.
Så nu, i stedet for hver af disse spande bare at have et element,
det kommer til at indeholde en sammenkædet liste over de elementer, der blev hashed ind i det.
OK, er alle slags få den idé?
Fordi vi ikke kunne få et array fordi vi ikke ved, hvordan mange ting
kommer til at være der.
En linket liste giver os mulighed for har netop det nøjagtige antal, der
er hashet i den spand, right?
>> Så lineær sondering er dybest set dette idea--
det er en måde at beskæftige sig med en kollision.
Hvad du kan gøre er, hvis, i dette tilfælde, bær blev makulerede i 1
og vi har allerede noget der, du bare
holde gå ned, indtil du finde en tom slot.
Det er en måde at håndtere det.
Den anden måde at håndtere det er med det, vi lige
called-- den linkede listen kaldes chaining.
>> Så denne idé virker, hvis din hashtabel du tror
er meget større end dine data sæt, eller hvis du
ønsker at forsøge at minimere kæde indtil det er absolut nødvendigt.
Så én ting er lineær sondering betyder naturligvis
at din hash funktion er ikke helt så nyttig
fordi du vil ender med at bruge din hash-funktionen, at komme til et punkt,
du lineær sonde ned til et sted, der er til rådighed.
Men nu, selvfølgelig, noget andet, der ender der,
du er nødt til at søge endnu længere nede.
>> Og der er meget mere Søg udgift,
går i indtastning af en element i din hash tabellen nu, right?
Og nu når du gå og forsøge at finde bær igen, er du nødt til hash det,
og det kommer til at sige, åh, kigge i spand 1,
og det kommer ikke til at være i spand 1, så du er
nødt til at krydse gennem resten af ​​disse.
Så det er til tider nyttigt, men i de fleste tilfælde
vi kommer til at sige, at chaining er, hvad du ønsker at gøre.
>> Så vi talte om det tidligere.
Jeg fik lidt foran mig.
Men chaining er dybest set at hver spand i din hashtabel
er blot en linket liste.
>> Så en anden måde, eller mere teknisk måde at tænke på en hash tabel
er, at det er bare et array af hægtede lister, som
når du skriver din ordbog og du forsøger at indlæse den,
tænker på det som en vifte af hægtede lister
vil gøre det meget nemmere for dig at klargøre.
>> PUBLIKUM: Så hashtabel har en forudbestemt størrelse,
ligesom en [uhørligt] spande?
>> SPEAKER 1: Right.
Så det har et bestemt antal spande, som du determine--
som du fyre bør velkommen til at spille med.
Det kan være temmelig cool at se hvad der sker
som du ændrer din antal spande.
Men ja, det har en sæt antal spande.
Hvad giver dig mulighed for at passe så mange elementer, som du har brug for
er dette særskilt kæde, hvor du har knyttet lister i hver spand.
Det betyder, at din hash tabel vil være nøjagtig størrelse
at du har brug for det at være, ikke?
Det er hele pointen i hægtede lister.
Cool.
>> Så alle OK der?
Ok.
Ah.
Hvad skete der lige?
Virkelig nu.
Gæt nogen har at dræbe mig.
>> OK, vi kommer til at gå ind i lande, som er lidt skør.
Jeg kan lide hash-tabeller.
Jeg tror, ​​de er virkelig cool.
Lande er cool, også.
>> Så er der nogen huske, hvad en prøve er?
Du skulle have gået over det kortvarigt i forelæsning?
Kan du huske slags hvordan det virker?
PUBLIKUM: Jeg er bare nikker at vi gik over det.
SPEAKER 1: Vi går over det.
OK, vi virkelig kommer til at gå over det nu, hvad vi siger.
>> PUBLIKUM: Det er for en hentning træ.
>> SPEAKER 1: Ja.
Det er en hentning træ.
Awesome.
Så én ting at bemærke her er, at vi kigger på enkelte tegn
her, ikke?
>> Så før med vores hash-funktion, vi ledte på ord som en helhed,
og nu ser vi mere på de tegn, right?
Så vi har Maxwell herovre og Mendel.
Så dybest set en try-- en måde at tænke om dette er, at hvert niveau her
er en vifte af bogstaver.
Så dette er din root node her, right?
Det har alle de tegn i det alfabet til starten af ​​hvert ord.
>> Og hvad du ønsker at gøre, er siger, OK, vi har nogle M ord.
Vi kommer til at kigge efter Maxwell, så vi gå til M. og M peger på en hel
andet en række, hvor hver ord, så længe der
er et ord, der har en som det andet bogstav,
så længe der er et ord, har B som den anden skrivelse,
det vil have en pointer gå til nogle næste array.
>> Der er sandsynligvis ikke en ord, MP noget,
så på P position i dette array, ville det bare være NULL.
Det ville sige, OK, er der ingen ord der har M efterfulgt af en P, OK?
Så hvis vi tænker over det, hver en af ​​disse mindre ting
er faktisk en af ​​disse store arrays fra A til Z.
Så hvad kunne være en af ​​de ting det er lidt af en ulempe ved en chance?
>> PUBLIKUM: En masse hukommelse.
>> SPEAKER 1: Det er et ton af hukommelse, right?
Hver af disse blokke her repræsenterer 26 rum, 26 element array.
Så forsøger få utroligt space tung.
>> Men de er meget hurtige.
Så utroligt hurtigt, men virkelig plads ineffektiv.
Kind of nødt til at regne ud af hvilken en du ønsker.
Disse er virkelig cool for din pset, men de tager en masse hukommelse,
så du handler ud.
Ja?
>> PUBLIKUM: Vil det være muligt at oprette en prøve og derefter
Når du har alle de data i det, at du need--
Jeg ved ikke, om det ville give mening.
Jeg var at slippe af med alle de NULL tegn, men så
ville du ikke være i stand til at indeksere them--
>> SPEAKER 1: Du har stadig brug for dem.
>> AUDIENCE: - på samme måde hver gang.
SPEAKER 1: Ja.
Du skal bruge NULL tegn til at lade du vide, hvis der er ikke et ord der.
Ben havde du noget, du ønsker?
OK.
Okay, så det vil vi at gå lidt mere
ind i de tekniske detaljer bag prøve og arbejde gennem et eksempel.
>> OK, så dette er den samme ting.
Mens det i en linket liste, vores vigtigste slags of-- hvad er det ord, jeg ønsker? -
ligesom at bygge blok var en node.
I en prøve, har vi også en node, men det er defineret anderledes.
>> Så vi har nogle bool som repræsenterer, om et ord faktisk
findes på dette sted, og derefter vi har nogle matrix her-- eller rettere,
dette er en pointer til en array af 27 tegn.
Og dette er for, i dette tilfælde er 27-- Jeg er sikker på alle du er ligesom, vent,
der er 26 bogstaver i alfabetet.
Hvorfor har vi 27?
>> Så afhængigt af måde du implementerer denne,
dette er fra en pset der tilladt for apostrof.
Så det er derfor den ekstra én.
Du vil også have nogle tilfælde null-terminator
indgår som en af ​​de tegn, som det er tilladt at være,
og det er, hvordan de kontrollerer for se, om det er slutningen af ​​ordet.
Hvis du er interesseret, så tjek Kevins video på study.cs50,
samt Wikipedia har nogle gode ressourcer der.
>> Men vi kommer til at gå igennem lige slags af, hvordan du kan arbejde gennem en prøve
hvis du er givet en.
Så vi har en super enkel en her, at har ordene "bat" og "zoom" i dem.
Og som vi ser op her, denne lidt plads her
repræsenterer vores bool som siger, ja, det er et ord.
Og så har vores arrays af tegn, right?
>> Så vi kommer til at gå igennem finde "bat" i denne prøve.
Så begynder i toppen, right?
Og vi ved, at B svarer til andet indeks, det andet element
i dette array, fordi a og b.
Så omtrent den anden.
>> Og det siger, OK, cool, følge det ind næste array, fordi hvis vi husker,
det er ikke, at hver af disse faktisk indeholder elementet.
Hver enkelt af disse arrays indeholder en pointer, right?
Det er en vigtig forskel at gøre.
>> Jeg ved, at dette kommer til at være-- lande er virkelig svært at komme på den første gang,
så selvom det er den anden eller tredje gang
og det er stadig slags af tilsyneladende vanskeligt,
Jeg lover, hvis du går watch kort igen i morgen,
det vil sandsynligvis gøre en masse mere mening.
Det tager en masse at fordøje.
Jeg har stadig nogle gange er lignende, vent, hvad er en chance?
Hvordan kan jeg bruge dette?
>> Så vi har b i denne sag, som er vores andet indeks.
Hvis vi havde, siger, c eller d eller ethvert andet brev,
vi har brug for at kortlægge det tilbage til indekset vores array, der svarer til.
Så vi vil tage ligesom rchar og vi bare trække off en at kortlægge det ind fra 0 til 25.
Alle godt, hvordan vi kortlægge vores karakterer?
OK.
>> Så vi går til den anden, og vi se, at ja, det er ikke til NULL.
Vi kan gå videre til den næste array.
Så vi går videre til den næste række her.
>> Og vi siger, OK, nu vi nødt til at se, hvis en er her.
Er en null eller gør det faktisk bevæge sig fremad?
Så en egentlig bevæger sig sende i dette array.
Og vi siger, OK, t er vores sidste bogstav.
Så går vi til t ved indekset.
Og så bevæger vi os fremad fordi der er en anden.
Og denne ene siger dybest set, at ja, det siger, at der er et ord her--
at hvis du følger dette sti, har du ankom
på et ord, som vi ved er "bat".
Ja?
>> PUBLIKUM: Er det standard at have den som indeks 0 og derefter har en slags 1
eller at have i slutningen?
>> SPEAKER 1: Nej.
Så hvis vi ser tilbage på vores erklæring her, det er en bool,
så det er eget element i node.
Så det er ikke en del af array'et.
Cool.
Så når vi er færdig med vores ord, og vi er på dette array, hvad vi ønsker at gøre
er at gøre en check, er dette et ord.
Og i dette tilfælde, ville det vende tilbage ja.
>> Så på dette notat, vi ved, at "zoo" - vi kender som mennesker, at "zoo" er et ord,
højre?
Men prøv her ville sige, nej, det er ikke.
Og det vil sige, at fordi vi ikke har udpeget det som et ord her.
Selvom vi kan krydse igennem til dette array,
denne prøve vil sige, at nej, zoo er ikke i din ordbog
fordi vi ikke har udpeget det som sådan.
>> Så en måde at gøre at-- Åh, undskyld, denne ene.
Så i dette tilfælde, "zoo" er ikke et ord, men det er i vores prøve.
Men i denne ene, siger vi ønsker det indføre ordet "bad", hvad der sker
er vi følge through-- b, a, t.
Vi er i dette array, og vi gå for at søge efter h.
>> I dette tilfælde, hvor vi se på markøren på h,
det peger på NULL, OK?
Så medmindre det er udtrykkeligt peger på et andet array,
du antage, at alle de pejlemærker i denne række peger til null.
Så i dette tilfælde er h peger til null så vi kan ikke gøre noget,
så det ville også vende tilbage falsk, "bad" ikke er her.
Så nu er vi faktisk vil gå igennem
hvordan ville vi faktisk sige at "zoo" er i vores prøve.
Hvordan kan vi indsætter "zoo" ind i vores chance?
Så på samme måde, som vi startede med vores linkede liste, vi starter ved roden.
Når du er i tvivl, skal du starte på roden af ​​disse ting.
>> Og vi vil sige, OK, z.
z findes i dette, og det gør det.
Så du går videre til din næste array, OK?
Og så på den næste, vi siger, OK, går o eksisterer?
Det gør det.
Dette igen.
>> Og så på vores næste, vi har sagt, OK, der allerede eksisterer "zoo" her.
Alt, hvad vi behøver at gøre, er at sætte dette lig til sand, at der er et ord der.
Hvis du havde fulgt alt op til før dette punkt,
Det er et ord, så bare sætte den lig med sådanne.
Ja?
>> PUBLIKUM: Så gør det betyder, at "ba" er et ord også?
>> SPEAKER 1: Nej.
Så i dette tilfælde, "ba" vi ville få her, ville vi sige, er det et ord,
og det ville stadig være nej.
OK?
Mmhmm?
>> PUBLIKUM: Så når du er det en ord og du siger ja, så er det
vil indeholde for at gå til m?
>> SPEAKER 1: Så det har at gøre med-- du lægger det i.
Du siger "zoo" er et ord.
Når du går til check-- lignende, siger du ønsker at sige,
betyder "zoo" eksistere i denne ordbog?
Du kun vil søge efter "zoo" og derefter kontrollere, om det er et ord.
Du aldrig kommer til at flytte igennem til m, fordi det er ikke
hvad du leder efter.
>> Så hvis vi faktisk ønskede at tilføj "bad" i denne prøve,
vi ville gøre det samme som vi gjorde med "zoo"
bortset fra at vi ville se, at når vi prøv og få til h, betyder det ikke eksisterer.
Så du kan tænke på dette som et forsøg at tilføje en ny knude i en linket liste,
så ville vi nødt til at tilføje en anden en af ​​disse arrays, som så.
Og så hvad vi gør, er vi bare indstille h element i denne matrix peger på dette.
>> Og så hvad ville vi ønsker at gøre her?
Tilføj lig med sand fordi det er et ord.
Cool.
Jeg kender.
Lande er ikke det mest spændende.
Tro mig, jeg kender.
>> Så én ting at indse med forsøg, Jeg sagde, de er meget effektive.
Så vi har set de tage et ton af plads.
De er slags forvirrende.
Så hvorfor skulle vi nogensinde bruge disse?
Vi bruger disse, fordi de er utrolig effektiv.
>> Så hvis du nogensinde søger et ord op, er du kun
afgrænset af længden af ​​ordet.
Så hvis du leder efter en ord, der er af længde fem,
du kun nogensinde nødt til at gøre på de fleste fem sammenligninger, OK?
Så det gør det dybest set en konstant.
Ligesom indsættelse og opslag er stort set konstant tid.
>> Så hvis du nogensinde kan få noget i konstant tid,
det er så godt, som det får.
Du kan ikke få bedre end konstant tid til disse ting.
Så er en af ​​de store plusser af prøver.
>> Men det er en masse plads.
Så du slags nødt til at beslutte hvad er mere vigtigt for dig.
Og på nutidens computere, den plads, som en prøve kan tage op
måske ikke påvirker dig så meget, men måske
du har at gøre med noget der har langt, langt flere ting,
og en prøve er bare ikke rimeligt.
Ja?
>> PUBLIKUM: Vent, så du har 26 bogstaver i hver enkelt?
>> SPEAKER 1: Mmhmm.
Ja, du har 26.
Du har nogle er ord markør og derefter du har 26 pejlemærker i hver enkelt.
Og de er point--
>> PUBLIKUM: Og hver 26, har de hver især har 26?
>> SPEAKER 1: Ja.
Og det er derfor, som du kan se, udvider ganske hurtigt.
Ok.
Så vi kommer til at komme ind i træer, som Jeg har lyst er lettere og vil sandsynligvis
være en dejlig lille udsættelse fra forsøg der.
Så forhåbentlig de fleste af jer har set et træ før.
Ikke ligesom den smukke dem udenfor, som jeg
ved ikke, om nogen gik udenfor for nylig.
Jeg gik apple plukke denne weekend, og Åh min gosh, det var smukt.
Jeg vidste ikke blade kunne se, at stort.
>> Så dette er blot et træ, right?
Det er blot nogle node, og det peger på en masse andre noder.
Som du kan se her, det er slags et tilbagevendende tema.
Nodes, der peger på noder er slags essensen af ​​mange datastrukturer.
Det bare afhænger af, hvordan vi få dem pege på hinanden
og hvordan vi krydse gennem dem, og hvordan vi
indsætte ting, der bestemmer deres forskellige karakteristika.
>> Så blot nogle terminologi, som jeg har brugt før.
Så rod er, hvad der er helt i top.
det er, hvor vi altid starte.
Du kan tænke på det som også hovedet.
Men for træer, er vi tilbøjelige til at henviser til det som roden.
>> Noget ved bunden her-- på den meget, meget bottom--
betragtes blade.
Så det går sammen med den hele træet ting, right?
Blade er på kanten af ​​dit træ.
>> Og så har vi også et par vilkår for at tale om knuder i relation
til hinanden.
Så vi har forælder, børn og søskende.
Så i dette tilfælde, 3 er forælder af 5, 6 og 7.
Så forældrene er, hvad der er ét trin ovenfor hvad du er
henvise til, så bare ligesom et stamtræ.
Forhåbentlig, dette er alle lidt lidt mere intuitiv end forsøger.
>> Søskende er nogen, der har den samme forælder, right?
De er på samme niveau her.
Og så, som jeg var siger, børn er bare
hvad er et trin under den pågældende knude, OK?
Cool.
Så et binært træ.
Kan nogen gætte på en af karakteristika binært træ?
>> PUBLIKUM: Max to blade.
>> SPEAKER 1: Right.
Så max to blade.
Så i dette en før, vi havde denne ene der havde tre, men i et binært træ,
du har en max to børn per forælder, right?
Der er en anden interessant egenskab.
Er der nogen der kender det?
Binært træ.
>> Så et binært træ vil have alt på til-- denne ene ikke er sorted--
men i en sorteret binært træ, alt på højre
er større end den forælder, og alt til venstre
er mindre end forælder.
Og der har været en quiz spørgsmål før, så godt at vide.
Så den måde, vi definerer det, igen, har vi en anden node.
Dette ligner meget hvad?
Dobbelt
>> Publikum: Linked lister
>> SPEAKER 1: Et dobbelt linket liste, right?
Så hvis vi erstatte dette med forrige og næste,
dette ville være en dobbelt linket liste.
Men i dette tilfælde, vi faktisk har venstre og højre og det er det.
Ellers er det nøjagtig det samme.
Vi har stadig element du leder efter,
og du skal blot to pointers går til, hvad der bliver det næste.
Yeah, så binær søgning træ.
Hvis vi opdager, alt på lige her er større than--
eller alt straks til højre her
er større end, alt her er mindre end.
>> Så hvis vi skulle til at søge gennem det skal se meget tæt på binær søgning
her, ikke?
Undtagen i stedet for at kigge til halv array,
vi er bare at kigge på enten den venstre side eller højre side af træet.
Så det bliver lidt nemmere, tror jeg.
>> Så hvis din rod er NULL, selvfølgelig er det bare falsk.
Og hvis det er der, det er naturligvis sandt.
Hvis det er mindre end, søger vi til venstre.
Hvis det er større end, vi søger til højre.
Det er præcis ligesom binær søgning, bare en anden datastruktur
at vi bruger.
I stedet for en matrix, det er bare et binært træ.
>> OK, stakke.
Og også, det ligner vi har måske en lille smule tid.
Hvis vi gør det, er jeg glad for at gå over nogen af ​​dette igen.
OK, så stakke.
Er der nogen der kan huske hvad stacks-- eventuelle karakteristika for en stak?
>> OK, så de fleste af os, tror jeg, spise i spisesalen halls--
så meget, som vi ikke kan lide at.
Men det er klart, kan du tænke på en stak bogstavelig talt lige som en stabel af bakker
eller en stak ting.
Og hvad der er vigtigt at indse, er, at det er
something-- den karakteristiske at vi kalder det by-- er LIFO.
Er der nogen vide, hvad det står for?
Mmhmm?
>> PUBLIKUM: Sidste ind, først ud.
>> SPEAKER 1: Right, sidst ind, først ud.
Så hvis vi ved, hvis vi stable ting op, at det nemmeste grab off--
og måske det eneste, vi kan få fat i fra, hvis vores stack er stor enough--
er, at top element.
Så uanset var sat på last-- som vi ser her,
hvad blev skubbet på de fleste recently-- er
vil være den første ting, som vi pop off, OK?
>> Så hvad vi har her er andet typedef struct.
Dette er egentlig bare gerne have en lynkursus i datastruktur,
så der er en masse smidt på jer.
Jeg kender.
Så endnu en struct.
Yay for strukturer.
>> Og i dette tilfælde, det er nogle pointer til et array, der har en vis kapacitet.
Så det repræsenterer vores stack her, ligesom vores faktiske matrix
at der holder vores elementer.
Og så har vi her nogle størrelse.
>> Og typisk, du vil beholde styr på, hvor stor din stack er
fordi hvad det kommer til at tillade du skal gøre er, hvis du kender størrelsen,
det giver dig mulighed for at sige, OK, er jeg ved kapacitet?
Kan jeg tilføje noget mere?
Og det fortæller dig også hvor toppen af ​​din stack
er så du ved hvad du kan faktisk tage af.
Og der er faktisk kommer til at være lidt mere klar her.
>> Så for skub, en ting, hvis du nogensinde at gennemføre skubbe,
da jeg var bare at sige, din stakken har en begrænset størrelse, right?
Vores vifte havde nogle kapacitet.
Det er et array.
Det er en fast størrelse, så vi er nødt til sørge for, at vi ikke putter mere
ind i vores matrix, end vi faktisk har plads til.
>> Så når du opretter en push funktion, første ting du skal gøre er at sige, OK,
har jeg plads i min stak?
Fordi hvis jeg ikke gør det, undskyld, Jeg kan ikke gemme dit element.
Hvis jeg gør, så du ønsker at gemme det på toppen af ​​stakken, right?
>> Og det er derfor, vi har at holde styr på vores størrelse.
Hvis vi ikke holde styr på vores størrelse, vi ved ikke, hvor at sætte det.
Vi ved ikke, hvor mange ting er i vores matrix allerede.
Ligesom der er naturligvis måder at måske du kunne gøre det.
Du kunne initialisere alt NULL og derefter søge efter den seneste NULL,
men en meget lettere ting er lige at sige, OK, holde styr på størrelse.
Ligesom jeg ved, jeg har fire elementer i mit array, så den næste ting
at vi lægger på, er vi skal opbevares ved indeks 4.
Og så, selvfølgelig, betyder det, at du med held har skubbet noget
på din stack, du ønsker at øge størrelsen
så du ved, hvor du er så at du kan presse flere ting på.
>> Så hvis vi forsøger at pop noget fra stakken,
hvad der kunne være det første, at vi ønsker at kontrollere for?
Du forsøger at tage noget fra din stak.
Er du sikker på der er noget i din stak?
Nej.
Så hvad kunne vi ønsker at kontrollere?
>> PUBLIKUM: [uhørligt].
SPEAKER 1: Kontroller, om størrelsen?
Størrelse.
Så vi ønsker at kontrollere at se, om vores størrelse er større end 0, OK?
Og hvis det er, så ønsker vi at falde vores størrelse med 0 og returnere det.
Hvorfor?
>> I den første var vi skubbe, vi pressede det
på størrelse og opdateres derefter størrelse.
I dette tilfælde, vi dekrementering størrelse og derefter at tage det ud, plukning det
fra vores array.
Hvorfor kunne vi gøre det?
Så hvis jeg har én ting på min stak, hvad der ville være min størrelse på det tidspunkt?
1.
>> Og hvor er element 1 opbevares?
På hvilket indeks?
PUBLIKUM: 0.
SPEAKER 1: 0.
Så i dette tilfælde, vi altid nødt til at gøre sure--
stedet for at returnere størrelse minus 1, fordi vi
ved, at vores element er skal oplagres på en mindre
uanset vores størrelse er, at dette bare tager sig af det.
Det er en lidt mere elegant måde.
Og vi bare formindske vores størrelse og derefter vende tilbage størrelse.
Mmhmm?
>> PUBLIKUM: Jeg gætter bare i almindelighed, hvorfor skulle denne datastruktur
være gavnligt?
>> SPEAKER 1: Det afhænger af din kontekst.
Så for nogle af de teorier, hvis du arbejder med-- OK,
Lad mig se, om der er en gavnlig én som er gavnlig for mere end uden
CS.
Med stakke, når som helst du har brug for at holde styr på noget,
er den mest nylig tilføjet er, når du vil ønsker at bruge en stak.
>> Og jeg kan ikke tænke på en god eksempel på det lige nu.
Men når den seneste ting er vigtigst for dig,
det er, når en stak vil være nyttig.
Jeg forsøger at tænke, hvis der er et godt for dette.
Hvis jeg tænker på et godt eksempel i den næste 20 minutter vil jeg helt sikkert fortælle dig.
>> Men samlet, hvis der er noget, ligesom jeg sagde de fleste, hvor seneste
er vigtigst, der er hvor en stabel kommer i spil.
Ud fra følgende betragtninger køer er slags det modsatte.
Og alle de små hunde.
Er dette ikke det store, right?
Jeg føler, at jeg skulle bare have en kanin video
lige i midten af sektion for jer
fordi det er en intens sektion.
>> Så en kø.
Dybest set en kø er ligesom en linje.
Du fyre jeg er sikker på, brug denne hverdag, ligesom i vore spisesale.
Så vi nødt til at gå i og få vores bakker, jeg er
sikker på at du er nødt til at vente i linje stryge eller få din mad.
>> Så forskellen her er, at dette er FIFO.
Så hvis LIFO sidst var i første ud, FIFO er først ind, først ud.
Så det er her, hvad du lægger på første er din vigtigste.
Så hvis du ventede i en line-- kan du
tænk hvis du gik til gå få den nye iPhone
og det var en stak, hvor sidste person på linje fik det første,
folk ville dræbe hinanden.
>> Så FIFO, vi er alle meget velkendte med i den virkelige verden her,
og det hele har at gøre med faktisk slags genskabe hele denne linje
og kø struktur.
Så der med stakken, vi har push og pop.
Med en kø, har vi enqueue og dequeue.
Så enqueue dybest set betyder sætte det på ryggen,
og dequeue midler tage off forfra.
Så vores datastruktur er en lidt mere kompliceret.
Vi har en anden ting at holde styr på.
>> Så uden hoved, dette er netop en stak, right?
Dette er den samme struktur som en stak.
Det eneste anderledes nu er vi har denne hovedet, som hvad tror du
kommer til at holde styr på?
>> PUBLIKUM: Den første.
>> SPEAKER 1: Right, den første ting, vi sætter i.
Lederen af ​​vores kø.
Hvem er først i køen.
Okay, så hvis vi gør enqueue.
Igen med nogen af disse datastrukturer,
da vi har at gøre med et array, vi nødt til at tjekke, om vi har plads.
>> Det er lidt ligesom mig fortælle du fyre, hvis du åbner en fil,
du nødt til at tjekke for null.
Med nogen af ​​disse stakke og køer, du har brug for
at se, om der er plads, fordi vi er beskæftiger sig med en fast størrelse array,
som vi ser her-- 0, 1 alt op til 5.
Så hvad vi gør i dette tilfælde er kontrol at se, om vi stadig har plads.
Er vores størrelse mindre end kapaciteten?
>> Hvis det er tilfældet, er vi nødt til at gemme det på halen og vi opdaterer vores størrelse.
Så hvad kunne halen være i dette tilfælde?
Det er ikke udtrykkeligt skrevet ud.
Hvordan ville vi gemme det?
Hvad ville halen være?
>> Så lad os gå gennem dette eksempel.
Så dette er en vifte af størrelse 6, right?
Og vi har lige nu, vores størrelse er 5.
Og når vi sætter det i, går det at gå ind i femte indeks, right?
Så opbevares ved halen.
>> En anden måde at skrive hale vil blot være vores udvalg på indeks af størrelse, right?
Dette er størrelse 5.
Næste ting kommer til at gå ind i 5.
Cool?
OK.
Det bliver lidt mere kompliceret når vi begynder at rode med hovedet.
Ja?
>> PUBLIKUM: Betyder det, at vi ville have erklæret en array,
var fem elementer lang og så vi tilføjer på det?
>> SPEAKER 1: Nej.
Så i dette tilfælde, er dette en stak.
Dette ville blive erklæret som en vifte af størrelse 6.
Og i dette tilfælde, vi bare har én plads til venstre.
>> OK, så én ting er i denne tilfælde, hvis vores hoved er på 0,
så vi bare kan tilføje den på størrelse.
Men det bliver lidt tricky fordi faktisk, de
ikke har en slide for dette, så jeg har tænkt mig
at tegne en, fordi det ikke er helt så enkel, når du
begynde at slippe af med ting.
Så der med en stak du kun nogensinde har
at bekymre sig om, hvad størrelse er når du tilføjer noget på,
med en kø, du også nødt til at gøre sikker på, at dit hoved er tegnede sig for,
fordi en cool ting om køer er, at hvis du ikke er på kapacitet,
du kan faktisk gøre det wrap around.
>> OK, så man thing-- åh, dette er forfærdeligt kridt.
Én ting at overveje, er tilfældet.
Vi vil bare gøre fem.
OK, så vi kommer til at siger hovedet er her.
Dette er 0, 1, 2, 3, 4.
>> Hovedet er der, og skal du have ting i dem.
Og vi ønsker at tilføje noget i, right?
Så de ting, vi er nødt til at ved er, at hovedet er altid
kommer til at flytte denne måde og derefter løkke tilbage omkring, OK?
>> Så denne kø har et areal, right?
Det har plads i begyndelsen, form for det modsatte af dette.
Så hvad vi skal gøre, er vi nødt til at beregne halen.
Hvis du ved, at din hoved har ikke flyttet, hale
er bare dit array på indekset af størrelse.
>> Men i virkeligheden, hvis du bruger en kø, dit hoved er sandsynligvis at blive opdateret.
Så hvad du behøver at gøre er faktisk beregne halen.
Så hvad vi gør, er denne formel her, som jeg har tænkt mig at lade dig
fyre tænker over, og så vil vi tale om det.
Så dette er kapacitet.
>> Så dette vil faktisk give dig en måde at gøre det.
Fordi der i dette tilfælde, hvad?
Vores hoved er på 1, vores størrelse er 4.
Hvis vi mod, der med 5, får vi 0, som er, hvor vi skal skrive den.
>> Så i den næste sag, hvis vi skulle gøre det,
vi siger, OK, lad os dequeue noget.
Vi dequeue dette.
Vi tager ud dette element, right?
>> Og nu er vores hoved peger her, og vi ønsker at tilføje i en anden ting.
Dette er dybest set den bagsiden af ​​vores linje, right?
Køer kan wrap omkring opstillingen.
Det er en af ​​de væsentligste forskelle.
Stakke, kan du ikke gøre dette.
>> Med køer, kan du fordi alt, der betyder noget
er, at du ved, hvad blev senest tilføjede.
Da alt vil blive tilføjet i denne mod venstre retning, i dette tilfælde,
og derefter wrap rundt, kan du fortsætte sætte i nye elementer
på forsiden af ​​grupperingen fordi det ikke er virkelig
forsiden af ​​grupperingen længere.
Du kan tænke på begyndelsen af array som hvor dit hoved rent faktisk er.
>> Så denne formel er, hvordan du beregne din hale.
Giver det mening?
OK.
OK, dequeue, og derefter du fyre har 10 minutter
til at stille mig opklarende spørgsmål du ønsker, fordi jeg ved, det er vanvittigt.
>> Okay, så i samme way-- Jeg ved ikke, hvis du fyre har bemærket,
men CS handler om mønstre.
Ting er temmelig samme, bare med små tweaks.
Så samme ting her.
Vi er nødt til at tjekke for at se, om vi rent faktisk har noget i vores kø, right?
Sige, OK, er vores størrelse større end 0?
Cool.
>> Hvis vi gør, så vi flytter vores hoved, som er, hvad jeg lige demonstreret her.
Vi opdaterer vores hoved til at være en mere.
Og så har vi formindske vores størrelse og returnere elementet.
>> Der er meget mere konkret kode på study.cs50.net,
og jeg anbefaler stærkt går igennem det, hvis du har tid,
selvom det er bare en pseudo-kode.
Og hvis du fyre ønsker at tale igennem at med mig en på én, så lad mig venligst
vide.
Jeg ville være glad for.
Datastrukturer, hvis du tager CS 124, vil du
ved, at datastrukturer få meget sjov og dette er netop begyndt.
>> Så jeg ved, det er svært.
Det er OK.
Vi kæmper.
Jeg gør det stadig.
Så du skal ikke bekymre dig for meget om det.
>> Men det er dybest set din lynkursus i datastrukturer.
Jeg ved, det er en masse.
Er der noget, vi vil gerne gå igen?
Noget vi ønsker at tale igennem?
Ja?
>> PUBLIKUM: For dette eksempel, så den nye hale er på 0 over det?
SPEAKER 1: Ja.
PUBLIKUM: OK.
Så går igennem, du ville have 1 plus 4 eller--
>> SPEAKER 1: Så du sagde, når vi ønsker at gå gøre det igen?
PUBLIKUM: Ja.
Så hvis du var at regne out-- hvor er du beregne halen fra i det?
>> SPEAKER 1: Så halen var in-- Jeg har ændret dette.
Så i dette eksempel her, det var array vi kigger på, OK?
Så vi har ting i 1, 2, 3 og 4.
Så vi har vores hoved er lig med 1 på dette punkt, og vores størrelse er lig med 4
på dette tidspunkt, right?
>> Du er alle enige om at det er tilfældet?
Så vi gør hovedet plus størrelse, som giver os 5 og derefter vi mod ved 5.
Vi får 0, hvilket fortæller os, at 0 er hvor er vores hale, hvor vi har plads.
>> PUBLIKUM: Hvad er en cap?
>> SPEAKER 1: kapacitet.
Undskyld.
Så det er størrelsen af ​​din array.
Ja?
>> PUBLIKUM: [uhørligt] før vi returnere element?
>> SPEAKER 1: Så vi flytter hoved eller returnere det øjeblik?
Så hvis vi flytter en, formindske størrelsen?
Hold på.
Jeg helt sikkert har glemt en anden.
Pyt.
Der er ikke en anden formel.
Yeah, ville du ønsker at vende tilbage hovedet og derefter flytte det tilbage.
>> PUBLIKUM: OK, fordi der på dette punkt, lederen var på 0,
og du derefter ønsker at vende tilbage indeks 0 og derefter foretage head 1?
>> SPEAKER 1: Right.
Jeg tror, ​​der er en anden formel slags som denne.
Jeg har ikke det på toppen mit hoved som Jeg ønsker ikke at give dig den forkerte.
Men jeg tror, ​​det er helt i orden at sige, OK, gemme denne element-- uanset
hovedets element is-- formindske din størrelse, flytte dit hoved over, og returnering
uanset det element er.
Det er helt gyldig.
OK.
Jeg mener ligesom dette ikke er ligesom most-- du ikke er
kommer til at gå ud af her ligesom, ja, jeg ved forsøg.
Jeg fik det hele.
Det er OK.
Jeg lover.
Men datastrukturer er noget, det tager en masse tid til at vænne sig til.
Sandsynligvis en af ​​de hårdest ting, tror jeg, i løbet.
>> Så det absolut tager repetition og leder at-- jeg
vidste virkelig hægtede lister indtil jeg gjorde alt for meget med dem,
på samme måde, som jeg gjorde ikke rigtig forstå pointers
indtil jeg har haft til at undervise i det for to år og gøre mine egne psets med det.
Det tager en masse af gentagelse og tid.
Og i sidste ende, vil den slags klik.
>> Men i mellemtiden, hvis du har slags et højt niveau forståelse af, hvad
disse gør, deres fordele og cons-- hvilket er hvad
vi virkelig har en tendens til at understrege, især i intro kursus.
Ligesom, hvorfor skulle vi bruge en prøve over et array?
Ligesom, hvad er de positive og negativer af hver af disse?
>> Og forstå trade-offs mellem hver af disse strukturer
er, hvad der er meget mere vigtigt lige nu.
Der kan være en skør spørgsmål eller to, der er
vil bede dig om at implementere skubbe eller implementere pop eller enqueue og dequeue.
Men for det meste, der har det højere forståelse niveau og mere
af en intuitiv forståelse er vigtigere end faktisk
være i stand til at gennemføre den.
>> Det ville være virkelig fedt, hvis alle jer kunne gå ud og gå gennemføre en prøve,
men vi forstår, det er ikke nødvendigvis den mest fornuftige ting lige nu.
Men du kan i din pset, hvis du ønsker til, og så får du praksis,
og så måske vil du rigtig forstå det.
Ja?
>> PUBLIKUM: OK, så, hvilke der er vi betød at bruge i pset?
Behøver jeg at bruge en af ​​dem?
SPEAKER 1: Ja.
Så har du dit valg.
Jeg gætter i dette tilfælde, kan vi tale om pset en lille smule
fordi jeg kørte gennem disse.
Så i din pset, har du din valg af lande eller hash-tabeller.
Nogle mennesker vil forsøge og bruge bloom filtre,
men dem, der teknisk ikke er korrekte.
På grund af deres sandsynlighedstekniske, de giver falske positiver tider.
De er cool look ind, selv om.
Kan varmt anbefale at kigge på dem mindst.
Men du har dit valg mellem en hash tabel og en prøve.
Og det kommer til at være der, hvor du lægger i din ordbog.
>> Og du bliver nødt til at vælge din hash-funktionen,
du bliver nødt til at vælge, hvor mange skovle du har, og den vil variere.
Ligesom hvis du har flere spande, måske det vil køre hurtigere.
Men måske du spilder en masser af plads på den måde, selv om.
Du er nødt til at regne det ud.
Mmhmm?
>> PUBLIKUM: Du sagde før, at vi kan bruge andre hashfunktioner,
at vi ikke behøver at skabe en hash-funktion?
>> SPEAKER 1: Ja, til højre.
Så bogstaveligt til din hash funktion, ligesom google "hash-funktion"
og kigge efter nogle seje dem.
Du er ikke forventes at bygge dine egne hashfunktioner.
Folk bruger deres Teser om disse ting.
>> Så du skal ikke bekymre dig om at bygge din egen.
Find et online til at begynde med.
Nogle af dem er du nødt til manipulere en lille smule
for at sikre tilbagevenden typer matche op og whatnot, så i begyndelsen,
Jeg vil anbefale at bruge noget virkelig nemt at måske bare
hashes på det første bogstav.
Og så når du har at arbejde, inkorporerer en køler hash-funktionen.
Mmhmm?
>> PUBLIKUM: Ville en prøve være eller effektiv, men blot sværere at, like--
>> SPEAKER 1: Så en prøve, tror jeg, er intuitivt svært at gennemføre
men er meget hurtig.
Dog fylder mere.
Igen, kan du optimere både af dem i forskellige måder og der er måder at--
PUBLIKUM: Hvordan skal vi gradueres på dette?
Er det matter--
>> SPEAKER 1: Så du gradueret normal måde.
Du kommer til at blive gradueret på design.
Uanset hvordan du gør det, du ønsker at sørg for at det er så elegant, som det kan være
og så effektivt som det kan være.
Men hvis du vælger en prøve eller hash bord, så længe det fungerer,
vi er tilfreds med at.
Og hvis du bruger noget, der hashes på det første bogstav, det er fint,
som måske lignende design-wise.
Vi er også at nå punkt i denne semester--
Jeg ved ikke, om du fyre noticed-- hvis du er
pset kvaliteter falde en lille smule på grund af design og whatnot,
det er helt fint.
Det bliver til et punkt, hvor din programmer bliver mere kompliceret.
Der er flere steder du kan forbedre på.
>> Så det er helt normalt.
Det er ikke, at du er klarer sig dårligere på din pset.
Det er bare vi bliver hårdere på dig nu.
Så alles føler det.
Jeg har lige gradueret alle dine psets.
Jeg kender alle føler det.
>> Så du skal ikke være bekymret over det.
Og hvis du har spørgsmål om forudgående psets eller måder, du kan forbedre,
Jeg prøver og kommentere den specifikke steder, men nogle gange er det for sent
og jeg bliver træt.
Er der andre ting om datastrukturer?
Jeg er sikker på, du fyre ikke rigtig ønsker at tale om dem længere,
men hvis der er, er jeg glad for at gå over dem, samt noget
fra forelæsning denne fortid uge eller sidste uge.
>> Jeg kender i sidste uge var alle gennemgang, så vi kan have sprunget over nogle anmeldelse
fra forelæsning.
Alle andre spørgsmål kan jeg svare?
OK, okay.
Nå, jer komme ud 15 minutter tidligt.
>> Jeg håber, dette var semi-nyttige mindste og jeg vil se jer i næste uge,
eller torsdag kontortid.
Er der anmodninger om snacks til næste uge, det er de ting?
Fordi jeg glemte slik i dag.
Og jeg bragte slik sidste uge, men det var Columbus Day,
så der var ligesom seks personer, der havde fire sække med slik til sig selv.
Jeg kan bringe starbursts igen, hvis du kan lide.
Starbursts?
OK, lyder godt.
Hav en god dag, gutter.