>> DAVID MALAN: Okay.
Velkommen tilbage til CS50.
Dette er starten på uge 8.
Og huske, at problemet sæt 5 sluttede med en lille smule af en udfordring.
Så antager du genvundet alle dine undervisning Fellows og CA'ens fotografier
i card.raw filen, er du berettiget nu finde alle de mennesker, og
en heldig vinder vil gå hjem med én af disse ting, springet bevægelse
enhed, som du kan bruge til endelig projekter, for eksempel.
>> Dette hvert år, fører til en smule creepiness.
Og så hvad jeg tænkte jeg ville gøre, er andelen med dig nogle af de noter, der har
gået frem og tilbage over de ansatte over sent.
For eksempel, bare aftes, citat citat slut, fra en af ​​de ansatte
medlemmer, "Jeg har lige haft en elev knock på min dør for at tage et billede med mig.
Stalkers, jeg fortælle dig. "Startede temmelig beskrivende og vi flyttede derefter
på, en time eller så senere "Jeg havde en student venter på mig efter sektion
og han havde alle vores navne og fotos på nogle ark papir. "Okay.
Så organiseret, men ikke alt, utryg endnu.
>> Så "Jeg var ude af byen denne weekend, og da jeg kom tilbage, var der en i
min
soveværelse. "[Latter]
DAVID MALAN: Next citat fra et personale medlem ", en elev kom til mit hus på
Somerville 4 kl morges. "Next personale, "Jeg fik til mit hotel i San
Francisco og en studerende ventede på mig i lobbyen med tre DSLR. "
Type kamera.
"Jeg er ikke engang på personale dette semester men en studerende brød ind i mit hus, det
morgen og indspillet det hele med Google Glass ". Og så endelig
"Mindst 12 mennesker var ivrigt afventer for mig, når jeg fik ud af min
limo, og så er jeg
vågnede. "Okay.
Så blandt de fotografier, som du kan husker, er dette fyr her, hvem du
måske kender som Milo Banana, der bor med Lauren Carvalho, vores hoved
undervisning Fellow.
Milo, Milo, kom her dreng.
Milo.
Mind dig, han iført Google Glass, så vi vil vise dig alt dette efter.
Så dette er Milo, hvis du gerne vil tage et fotografi med ham bagefter.
Hvis du gerne vil se ud på publikum der.
OK.
Det er godt optagelser.
Nå, Milo Banana.
Åh, ikke gør det.
>> [Latter]
>> OK.
Så et ord og derefter på, hvad der ligger forude, fordi som vi begynder at overgangen
denne uge specifikt fra C i en kommandolinje miljø til PHP og
JavaScript og SQL og HTML og CSS i et web-baseret miljø, vil vi være
udstyre dig med alle de mere viden om
potentielle endelige projekter.
Henimod herpå, har naturligvis en tradition for at holde seminarer,
er på tangentielle emner til kurset.
Meget meget relateret til programmering og app udvikling og så videre, men
ikke nødvendigvis udforsket af kursets egen pensum.
>> Så hvis du kunne være interesseret i én eller flere af dette års seminarer,
registrere på cs50.net/seminar.
Der er ældre seminarer på cs50.net/seminars.
Og på den vagtplan hidtil for dette år er Amazing Web Apps med Ruby on
Skinner, som er et alternativ sprog PHP.
Datalingvistik.
Introduktion til iOS, som er platform, der bruges til iPhone og
IPAD udvikling.
JavaScript for Web Apps, vil vi dække der, men i dette seminar, vil du gå
mere i detaljer.
>> Leap Motion, så vi rent faktisk har nogle af vores venner fra Leap Motion,
virksomheden selv, slutte sig til os.
Morgen, i virkeligheden, give en hands-on seminar, hvis
af interesse for dig.
Meteor.js en alternativ teknik til ved hjælp af JavaScript ikke i en browser,
men på en server.
Node.js, som er meget i denne ånd samt.
Sleek Android Design.
Android er et meget populært alternativ til iOS og Windows Phone
og andre mobile platforme.
Og Web Security Active Defense.
>> Så i virkeligheden, hvis du gerne vil at engagere sig i dette, så lad mig
gøre opmærksom på dette.
Vi er meget glade for at sige, at vores venner på Leap
Motion, hvilket er en start -
denne enhed virkelig bare kom ud et par måneder siden -
har allernådigst doneret 30 sådanne anordninger til klassen for så mange studerende, hvis
du gerne vil låne den hardware mod semesters ende og bruge det til
en egentlig afsluttende projekt.
De støtter en række sprog.
Ingen af ​​dem C, ingen af ​​dem PHP, så nå et eller flere af disse seminarer
kan vise sig af interesse.
Og alle af dem vil blive filmet i tilfælde af at du ikke er i stand
til at møde personligt.
Tidsplanen blive annonceret via e-mail som vi størkne værelser.
>> Og endelig, hvis du går til projects.cs.50.net, dette er en hjemmeside
fastholder vi hvert år, at vi invitere folk fra lokalsamfundet, fakultet,
afdelinger, personale og både i et udenfor CS50 til
foreslå projektideer.
Ting af interesse for grupper af studerende.
Ting af interesse for afdelinger.
Så du slå der hvis du kæmper med usikkerhed om, hvad du
selv ønsker at tackle.
>> Så sidste gang vi indført et velsagtens mere kompleks datastruktur, end vi havde
set i uger tidligere.
Vi havde brugt arrays pretty lykkeligt som et nyttigt, hvis
simplistisk datastruktur.
Derefter introducerede vi disse, som naturligvis er forbundet lister.
Og hvad var en af ​​årsagerne til indføre denne datastruktur?
Ja?
Hvad er det?
>> PUBLIKUM: Dynamisk størrelse.
>> DAVID MALAN: Dynamisk størrelse.
Så mens der i array, skal du kender sin størrelse på forhånd, når
du tildele det.
I linket liste, behøver du ikke nødt til at vide det.
Du kan bare malloc eller mere generelt, afsætte yderligere
node, så at sige, hver gang du ønsker at indsætte flere data.
Og node har ingen forudbestemt mening.
Det er bare en generisk betegnelse, der beskriver en slags container, at vi er
hjælp i vores datastruktur til at lagre nogle emne af interesse, som i dette
tilfælde tilfældigvis være heltal.
>> Men der er altid en afvejning.
Så vi får dynamiske størrelser af data struktur, men hvilken pris skal vi betale?
Hvad er ulempen ved sammenkædede lister?
Ja?
>> PUBLIKUM: Kræver mere hukommelse.
>> DAVID MALAN: Det kræver mere hukommelse, præcis hvordan?
>> PUBLIKUM: [uhørlig].
>> DAVID MALAN: Præcis.
Så nu har vi pointere at optage ekstra hukommelse, som vi tidligere
behøvede ikke, fordi fordelen af en matrix, er naturligvis, at
alt er op til hinanden, ryg til tilbage til tilbage, som
giver dig random access.
Fordi blot ved hjælp af firkantede beslag notation, eller mere teknisk pointer
aritmetik, meget simpel addition, kan du få adgang til alle
elementer i konstant tid.
Og faktisk er den slags antyde anden pris, vi betaler med en
linkede liste.
>> Hvad sker der med køretiden for noget som Search, hvis jeg ønsker at
finde nogle værdi og inde af en sammenkædet liste?
Hvad betyder min køretid blevet?
Big O n.
Hvis det er ordnet på?
Hvad hvis datastrukturen er ordnet?
Kan jeg gøre det bedre end store O n til at søge?
Nej, fordi det i værste fald kan det meget vel blive sorteret, men antallet
du leder efter kunne være stort.
Det kan være nummer 100, som kan ske at være alt
måde ved udgangen.
Og fordi du kun kan få adgang til en sammenkædet listen i denne implementering af
måde sin første node, er du stadig slags ude af lykke.
Du er nødt til at krydse det hele fra først til sidst for at finde
at store værdi som 100.
Eller at afgøre, om det er ikke engang der.
>> Så vi kan ikke gøre, hvad algoritme i en data struktur, der ligner dette?
Vi kan ikke gøre binær søgning, fordi binær søgning kræves, at vi havde
random access.
Vi kunne bare springe fra sted til placering uden at følge
disse brødkrummer i form af alle disse pejlemærker.
>> Nu, hvordan kom vi gennemfører dette?
Tja, hvis vi går til skærmen her, hvis kan vi hurtigt reimplement disse data
struktur -
min håndskrift er ikke alt, stor her, men vi vil forsøge.
Så typedef struct, og hvad gjorde jeg ønsker at kalde denne ting op her?
Node.
Så jeg vil få os i gang.
Og nu, hvad der skal være inde i datastrukturen for denne enkeltvis
linkede liste?
Hvor mange felter?
>> Så to.
Den ene er temmelig let.
Så int n.
Og vi kunne kalde n noget, vi ønsker, men det skal være en int, hvis vi er
gennemføre en linket liste til int'er.
Og nu, hvad gør den anden felt skal være?
Struct node *.
Så hvis jeg gør struct node *, og så er jeg kan kalde dette også, hvad jeg vil,
men bare for at være klar, jeg ringer Det næste, som vi har gjort.
Og så vil jeg lukke mine krøllede parenteser.
>> Og nu, som sidste gang, Jeg sætter node hernede.
Men hvis jeg erklære dette er så en node, hvorfor jeg gider at være så
verbose her erklære struct node * næste, i modsætning
til lige node * næste?
Ja?
>> PUBLIKUM: [uhørlig].
>> DAVID MALAN: Præcis.
Præcis.
Fordi C virkelig tager dig bogstaveligt og kun ser definitionen af ​​node
vej herned, du kan ikke henvise til det heroppe.
Så vi har denne form for forebyggende erklæringen her, hvilket er ganske vist
mere detaljeret.
Struct knude, der betyder kan vi nu få adgang til det
indersiden af ​​datastruktur.
>> Og som en sidebemærkning, fordi dette er bliver lidt mere subjektive nu,
stjernen kan teknisk gå her, det kan gå her, det kan
endda gå i midten.
Vi har vedtaget, i stil guide for kurset, konventionen om at sætte
stjernen lige ved siden af ​​de data, typen, som i dette tilfælde,
ville være struct node.
Men indse i en masse lærebøger og online referencer, du måske faktisk
se det på den anden side.
Men bare indse, at begge vil faktisk arbejde, og du bør simpelthen være
konsekvent.
>> Ok.
Så det var vores erklæring af struct node.
Men så begyndte vi at gøre mere sofistikerede ting.
For eksempel har vi besluttet at indføre noget som en hash tabel.
Så her er en hash tabel med n, indekseret fra 0 på øverste venstre hjørne til n
minus 1 nederst til venstre.
Dette kunne være en hash tabel for noget.
Men hvad slags ting gjorde vi taler om at bruge en hash tabel for?
Lagring hvad?
>> Navne.
Vi kunne gøre navne som vi gjorde sidste gang.
Og virkelig, du kan gemme noget.
Og vi vil se det igen i PHP og JavaScript.
En hash tabel er en dejlig slags schweizisk Army kniv, der giver dig mulighed for at gemme
temmelig meget, hvad du ønsker inde i det ved at knytte nøgler med værdier.
Nøgler med værdier.
>> Nu i denne simple tilfælde vores nøgler er bare tal.
Vi gennemføre en hash tabel som en matrix.
Og så tasterne er 0, 1, 2, og så videre.
Og så vi, som mennesker, besluttede sidste uge, at du ved, hvad, hvis vi er
kommer til at gemme navne, lad os bare vilkårligt, men temmelig rimeligt,
antage, at Alice, en Et navn, vil bare blive indekseret i 0.
Og Bob, en B navn, vil blive indekseret i 1, og så videre.
Så vi havde en mapping mellem indgange, der er strenge, og hash
steder, der er tal.
>> Således at processen er generelt kendt som en hash-funktion, og du kan virkelig
gennemføre den i koden.
Hvis jeg ønskede at gennemføre en hash-funktion der gør præcis, hvad vi
netop beskrevet fra sidste gang, jeg måske erklære en funktion, der tager som
indgang for eksempel -
og lad os gøre det på denne skærmen herovre.
Hvis jeg ønskede at gennemføre en hash funktion, kan jeg sige
noget som dette.
>> Det kommer til at returnere en int.
Det kommer til at blive kaldt hash, og det er kommer til at acceptere som et argument et
streng, eller vi kan være mere korrekt nu og sige char *, vi kalder det er.
Og så har denne funktion at gøre, i sidste ende, er returnere en int.
Nu, hvor det gør det måske ikke være så klar.
Jeg har tænkt mig at gennemføre dette uden form for fejlkontrol lige nu.
Jeg skal bare blindt sige, tilbage hvad der er på s beslag 0, minus,
lad os sige, hovedstad Et semikolon.
>> Fuldstændig brudt.
Det er ikke perfekt, fordi én, hvad nu hvis s er ugyldig?
Dårlige ting kommer til at ske.
To, hvad nu hvis det første bogstav i denne navn er ikke et stort bogstav?
Det kommer ikke til at slå godt ud enten.
Det kan være et lille bogstav eller ikke et bogstav overhovedet.
Så helt plads til forbedringer her, men dette er den grundlæggende idé.
>> Hvad vi beskrev i sidste uge verbalt som blot en proces kortlægning Alice til
0 og Bob til 1. kan udtrykkes sikkert mere formulaically som en C
fungere her.
Kaldes igen hash, tager en streng som input, og så en eller anden måde gør noget
med dette input til at producere et output.
Ikke ulig vores sorte box beskrivelse , som vi længe har gjort.
Jeg ved ikke, hvordan dette kan være arbejder under hætten.
>> For problemet sæt 6, en af ​​udfordringerne er for dig at beslutte, hvad
vil dit hash-funktionen være?
Hvad kommer til at være inde i den sorte box, og formentlig vil det være en
lidt mere interessant end dette, og klart mere tilbøjelige til fejl
kontrol end netop dette gennemførelse.
>> Men problemer kan opstå, right?
Hvis vi har en datastruktur som denne én, hvad er et af de problemer
du kan løbe ind i, efterhånden som du indsætter flere og flere navne i den
hash tabellen?
Du får kollisioner, right?
Hvad hvis du har Alice og Aron, to personer, hvis navne er sket
til at starte med A?
Det rejser spørgsmålet, hvor du sætte den anden sådan et navn?
>> Nå, du måske naivt bare sætte det hvor Bob tilhører, men så Bob er
slags skruet hvis du forsøger at indsætte hans navn næste og
der er ikke plads til ham.
Så du kan sætte Bob, hvor Charlie er, og du kan forestille sig dette meget hurtigt
uddelegere til lidt af en rod.
Noget lineær i sidste ende, hvor du bare nødt til at søge det hele
søger Alice eller Bob eller Aaron eller Charlie.
>> Så i stedet har vi foreslået, i stedet for bare lineært sondering for åbne rum
og plopping navne der, vi foreslået en amatør tilgang.
En hash tabel implementeret stadig med et vifte af indeks, men datatype
disse indekser nu var pointere.
Pointere til hvad?
Henvisninger til hægtede lister.
>> Fordi tilbagekaldelse, at en sammenkædet liste egentlig bare en pointer til en knude, og
knudepunktet har en næste felt, og denne node har en næste felt, og så videre.
Så kan du nu tænke på dette array på den venstre side af en hash tabel som
fører til en sammenkædet liste.
Den fordel, som er, hvis du får en kollision mellem Alice og Aron,
hvad gør du med det anden sådanne person?
Du skal bare vedhæfte ham eller hende til ende, eller endog begyndelsen
af den linkede liste.
>> Og faktisk, lad os bare noodle gennem at for bare et sekund.
Hvor ville give mest mening?
Hvis jeg indsætter Alice og hun ender på det første sted, så jeg prøver at
indsæt Aaron navn, og der er naturligvis en kollision, skal jeg sætte
ham i begyndelsen den linkede liste?
Det er på det første sted, eller i slutningen?
>> PUBLIKUM: [uhørlig].
>> DAVID MALAN: OK.
Jeg hørte begyndt.
Hvorfor i starten?
>> PUBLIKUM: [uhørlig].
>> DAVID MALAN: OK.
Det er alfabetisk, så det er rart.
Det er en god egenskab.
Det vil spare mig noget tid potentielt.
Det vil ikke lade mig gøre binær søgning, men jeg kunne i det mindste være i stand til at bryde ud
af en løkke, hvis jeg indser, ja, jeg er vejen fortiden var Aaron ville være i denne
sorteret forbundet liste.
Jeg behøver ikke at spilde min tid på at kigge hele vejen til enden.
Så det er rimeligt.
Hvorfor ellers kan du indsætte det kolliderende navn i
begyndelse af listen?
Hvad er det?
>> PUBLIKUM: [uhørlig].
>> DAVID MALAN: Det kan tage lang tid for at komme til slutningen af ​​listen.
Og i virkeligheden,. Længere og længere
Jo flere navne, du indsætter, at starter med A, jo længere at
kæden kommer til at få.
Jo længere der er forbundet liste vil få.
Så du er virkelig bare spilder din tid.
Måske er du bedre stillet opretholdelse konstant indsættelse tid, store O i 1,
ved altid at sætte kolliderende navnet på begyndelsen af ​​den linkede liste,
og ikke bekymre sig så meget om sortering.
>> Hvad er det bedste svar?
Det er uklart.
Den slags afhænger af, hvad fordelingen er, hvad det mønster er
af de navne, du indsætter.
Det er ikke nødvendigvis et indlysende svar.
Men her til, igen, er et design muligheder.
>> Så vi så på denne ting, som er virkelig den anden store mulighed
for p-set 6..
Og indse, hvis du ikke allerede har, Zamyla dykker ned begge disse, hash
tabeller og forsøger, mere detaljeret.
Og videogennemgang er indlejret i p-set spec.
Dette var en trie -
T-R-I-E. Og hvad var interessant ved dette var, at køretiden
for at søge efter et navn, ligesom Maxwell sidste gang, var store O af hvad?
Hvad er det?
>> PUBLIKUM: Antallet af bogstaver.
>> DAVID MALAN: Antallet af bogstaver.
Jeg hørte to ting.
Antallet af breve og konstant tid.
Så lad os gå med det første.
Antallet af bogstaver.
Nå, dette datastruktur, tilbagekaldelse, er som et træ, et stamtræ, som hver
hvis knudepunkter består af arrays.
Og de arrays er henvisninger til andre sådanne knudepunkter eller andre sådanne
arrays i træet.
>> Så hvis vi ønskede at derefter afgøre hvorvidt Maxwell er her, kan jeg gå
til den første array, på toppen af træet, den såkaldte rod, top
den trie, og følg derefter m pointer, derefter en pegepind, så X,
w, e, l, l.
Og så når jeg ser nogle særlige symbol, betegnes her som en trekant.
I koden vil du se foreslår vi, at du implementeret som en bool, bare at sige ja
eller nej, et ord stopper her.
>> Nå, når vi har gået til M-A-X-W-E-L-L, føles som syv, måske
otte hvis vi går en forbi den, otte trin for at finde Maxwell.
Eller lad os kalde det K. Men husker sidste gang, jeg fremførte, at hvis der er
realistisk en maksimal længde på en word, ligesom 40-nogle-ulige antal tegn, en
maksimale længde indebærer en konstant værdi.
Så virkelig, ja, det er teknisk set stort O på 8 eller 7, eller virkelig store O i K. Men
hvis der er en udtømmelig cap på, hvad K kunne være, er det en konstant.
Og så det er big O i 1 ved slutningen af ​​dagen.
>> Ikke i den virkelige verden.
Ikke når du rent faktisk begynde at se dit ur som dit program kører.
Det er absolut kommer til at være en smule langsommere end virkelig konstant
tid med et trin.
Det kommer til at være syv eller otte trin, men stadig det er meget, meget bedre
end en algoritme som store O n at afhænger af størrelsen af ​​hvad der er i
datastruktur.
>> Bemærk opadrettede her er at vi kan indsætte en million flere navne i denne
datastruktur, men hvor mange flere trin det kommer til at tage os med at finde
Maxwell i denne sag?
Ingen.
Han er upåvirket.
Og til dato, tror jeg ikke, vi har set et eksempel på en datastruktur eller et
algoritme, der var helt upåvirket af ydre
adfærd som det.
Men det kan ikke være fantastisk.
Dette kan ikke være den eneste løsning for p-sæt
>> Og det er ikke.
Dette er ikke nødvendigvis de data, struktur, du skal drages til,
fordi ligesom hash tabeller, tradeoff.
Hvad er den pris, du betaler her?
Hukommelse.
Jeg mener, dette er en grusomme mængde hukommelse.
Og du kan ikke helt se det her, fordi forfatteren af ​​dette billede
naturligvis afkortet alle arrays, og vi er ikke at se masser af A s og
B og C s og Q og Y'er og Z er i disse arrays.
Men de er der.
>> Hver af disse knudepunkter er en hel række af omkring 26 eller flere byte, som hver
som repræsenterer et brev.
27 i vores tilfælde, så vi kan understøtte apostroffer i problemet sættet.
Så dette datastruktur er rigtig, virkelig tæt og bredt.
Og det alene kan ende langsommere ting ned, eller i det mindste koster dig en
meget mere plads.
Men igen, kan vi drage sammenligninger her.
>> Recall et stykke tid tilbage, vi opnået meget mere spændende køretid i sortering
når vi bruger merge slags, men prisen Vi betalte for at opnå n log n for sammenfletningen
sortere krævede, at vi bruger mere, hvad ressource?
Mere plads.
Vi havde brug for en sekundær array til kopiere folk ind, ligesom
vi gjorde her på scenen.
Så igen ingen klare vindere, men blot subjektive design
beslutninger, der skal foretages.
>> Ok.
Så hvordan omkring dette?
Nogen genkender som D-Hall?
OK.
Så tre af os gør.
Mather House.
Så dette er for Mathers spisning.
Jeg vil vædde alle de spisesale har stakke af bakker som denne.
Og det er faktisk repræsentativ af noget, vi har
naturligvis set allerede.
Vi kaldte det bogstaveligt talt en stabel.
Og stakken, i form af din computerens hukommelse, er, hvor data går
mens funktioner bliver kaldt.
>> For eksempel går, hvad slags ting på stakken med hensyn til
memory layout vi har diskuteret i uger tidligere?
Hvad er det?
>> PUBLIKUM: Opkald til funktioner.
>> DAVID MALAN: Undskyld.
>> PUBLIKUM: Opkald til funktioner.
>> DAVID MALAN: Opkald til funktioner, men specifikt hvad der er inde i hver af
disse rammer?
Hvilke ting?
Ja.
Så lokale variable.
Når som helst vi havde brug for nogle lokale lagring, som en argument eller int I eller int
temp, eller hvad den lokale variabel, vi har været
sætte det på stakken.
Og vi kalder det en stak, fordi af denne lagdeling idé.
Bare slags kampe op med virkeligheden, begrebet deraf.
>> Men det viser sig, at en stabel kan også ses som en datastruktur, en
alternativ til en matrix, en alternativ til en sammenkædet liste.
Noget begrebsmæssigt mere interessant der kan stadig være
gennemføres ved hjælp af en af ​​disse ting, men det er en anden type
datastruktur der understøtter, virkelig, kun to operationer.
Men du kan tilføje mere avanceret funktioner end disse.
Men disse er grundlæggende -
skubbe og pop.
>> Og ideen med en stak er, at hvis jeg har her, med eller uden Annenberg
vel vidende, en bakke fra næste dør med nummeret 9 på det.
Så bare en int.
Og jeg ønsker at skubbe dette på de data, struktur, som i øjeblikket er tom.
Betragt dette bunden af ​​stakken.
Jeg vil skubbe denne nummer 9 på stak, og nu er det lige der.
>> Men det interessante ved en stak er, at hvis jeg nu ønsker at presse
en anden værdi, ligesom 17, og jeg skubbe dette på stakken, vil jeg gøre
det eneste intuitive ting, jeg bare at sige det lige der, hvor vi mennesker
ville være tilbøjelig til at sætte det på toppen.
Men hvad er interessant nu er, hvordan får jeg ved 9?
Du ved, det gør jeg ikke uden en vis indsats.
>> Så hvad er interessant ved en stak er, at ved design,
det er en LIFO datastruktur.
Silly måde at beskrive sidste ind, først ud.
Så det sidste nummer i på dette tidspunkt var 17.
Så hvis jeg ønsker at pop noget fra af stakken, kan det kun være 17..
Så der er en obligatorisk rækkefølge operationer her, hvor det sidste punkt
i har at være den første ud.
Derfor akronym, LIFO.
>> Så hvorfor kan det være nyttigt?
Er deres sammenhænge, ​​hvor du ville ønsker en datastruktur som dette?
Nå, det helt sikkert været nyttigt indersiden af ​​en computer.
Så operativsystemer klart bruge dette type datastruktur stakke.
Vi vil også se den samme idé når det kommer til websider.
Så denne uge og næste uge, og ud over, og som du begynder at gennemføre web
sider i et sprog kaldet HTML, kan du faktisk bruger en datastruktur som
dette at afgøre, om side er korrekt formateret.
Fordi vi vil se alle websider følger en slags hierarki, en indskæring
der vil ved slutningen af ​​dagen, være en træstruktur under hætten.
Så mere om det i bare en smule.
>> Men for nu, lad os foreslå en øjeblik, hvordan kunne vi gå om
repræsenterer, hvad en stak er?
Lad mig foreslå, at vi gennemfører en stak med kode som dette.
Så en stak kommer til at have inde i det to ting, en vifte, kaldet bakker,
bare for at være i overensstemmelse med demo.
Og hver af punkterne i denne matrix vil være en type int.
Og kapaciteten er formentlig hvad?
Fordi jeg ikke har skrevet fulde definition her.
>> Det er nok det maksimale størrelse af matrixen.
Og det er nok erklæret som en skarp defineres på toppen af ​​filen, nogle
slags konstant som antydes af den blotte kapitalisering.
Så sted kapacitet er defineret som den maksimale mulige størrelse.
I mellemtiden, indersiden af ​​datastruktur kendt som en stak vil der
være et heltal bare kendt blot som størrelse.
>> Så hvis jeg skulle repræsentere det nu billedligt, lad os antage, at dette
Hele sorte boks repræsenterer mit stack.
Inde i det er to variable.
Så jeg har tænkt mig at tegne første som størrelse.
Og det andet, jeg har tænkt mig at tegne som en matrix.
>> Men bare for at holde tingene ordnet, normalt ville jeg trække et array som
dette, men det er slags nice hvis vi matche virkeligheden, eller
matche den mentale model.
Så lad mig i stedet trække array lodret, hvilket er lige, igen,
kunstners gengivelse.
Er faktisk ligegyldigt, hvad det er under hætten.
Og vi vil sige, at som standard kapaciteten vil være tre.
Så dette vil være placering 0, dette vil være location 1, dette
vil være location 2..
>> Hvis jeg bestikke med en stress bold, ville nogen kan lide at komme op og køre
bord her for blot et øjeblik?
OK, så din hånd først.
Kom op.
Ok.
Så jeg tror, ​​det er Steven.
Kom op.
Ok.
>> Men forestil vi nu tilbage til den oprindelige tilstand i verden, hvor jeg
har netop erklæret en stak, og det er vil være kapacitet tre.
Men størrelse er endnu ikke fastlagt.
Bakker er endnu ikke fastlagt.
Så et par spørgsmål først.
Og lad mig give dig mic, så du kan deltage mere aktivt i dette.
>> Så hvad er inde i størrelse i dette øjeblik i tide, hvis alt hvad jeg har gjort, er
erklæret en stak med én linje kode?
>> STEVEN: Ikke meget.
>> DAVID MALAN: OK, ikke meget.
Ved vi, hvad der er inde i størrelse, ved vi, hvad der er indeni
af dette array her?
>> STEVEN: Just tilfældig kode, right?
Just -
>> DAVID MALAN: Ja, jeg går til kalder det kode, men random -
>> STEVEN: Ting.
>> DAVID MALAN: Ting som tilfældig
>> STEVEN: Bits.
>> DAVID MALAN: Bits, right?
Så skrald værdier? Ret
Så permutationer af 0'er og 1'er.
Rester af tidligere kutymer af denne hukommelse.
Og vi ved ikke rigtig, hvad de værdier er, så vi typisk trække dem
som spørgsmålstegn.
>> Så den første ting, vi er formentlig lyst til at gøre her -
og lad mig give dette felt inde af der et navn - bakker.
Hvad skal vi formentlig initialisere størrelse til, hvis vi ønsker at
begynde at bruge denne stak?
>> STEVEN: Bakke er sub 3..
>> DAVID MALAN: Så OK.
For at være klar, er kapaciteten erklæret andre steder som tre.
Og det er hvad jeg har brugt at tildele array.
Størrelse vil henvise til, hvor mange bakker er i øjeblikket på stakken.
>> STEVEN: Zero.
>> DAVID MALAN: Så det skal være nul.
Så gå videre og med alle finger, tegne en nul i størrelse.
Ok.
Så nu, hvad der er inde i dette her ved vi ikke.
Disse er egentlig bare skrald værdier.
Så vi kunne trække spørgsmålstegn, men lad os holde bestyrelsen rent for nu
fordi det ikke betyder noget hvad der er.
Vi behøver ikke at initialisere array til noget, for hvis vi ved, at
størrelsen af ​​stakken er nul, godt, vi bør ikke se på noget i
dette array alligevel på dette tidspunkt.
>> Så nu antage, at jeg skubber nummer 9 på stakken.
Hvordan skal vi opdaterer datastruktur inde i denne sorte boks?
Hvilke værdier skal ændre?
>> STEVEN: Indenfor -
størrelsen?
>> DAVID MALAN: OK.
Størrelse bør blive det?
>> STEVEN: Size ville være én.
>> DAVID MALAN: OK.
Så størrelse bør blive en.
Så du kan gøre dette på et par måder.
Lad mig give dig, nu er din finger er et viskelæder.
Ok.
Så nu er din finger er en pensel.
Ok.
Og nu, hvad andre har at ændre, naturligvis i datastrukturen?
>> STEVEN: Vi går fra bottom up til 9.
>> DAVID MALAN: 9..
OK, Good.
Så stadig ikke ligegyldigt, hvad der er på placering en eller to, fordi de er
skrald værdier, men vi skal ikke genere ser der, fordi størrelse er
fortæller os, at kun det første element er faktisk legitimt.
Så nu jeg skubbe 17 på listen.
Hvad sker der med billedet?
>> STEVEN: So størrelse kommer til at gå til to.
>> DAVID MALAN: OK.
Du er viskelæder -
oops.
Du er et viskelæder.
>> STEVEN: Eraser.
>> DAVID MALAN: Du er en pensel.
>> STEVEN: Brush.
>> DAVID MALAN: OK.
Og hvad ellers?
>> STEVEN: Og så har vi -
>> DAVID MALAN: Vi pressede 17..
>> STEVEN: Vi holder 17 på toppen, så -
>> DAVID MALAN: OK, godt.
>> STEVEN: - drop det ned.
>> DAVID MALAN: Okay.
Det bliver let.
Jeg har ikke tænkt til at hjælpe dig denne gang.
Push 22..
>> STEVEN: Udført.
At blive et viskelæder.
Jeg bliver en pensel.
Og så jeg lægger 22.
>> DAVID MALAN: 22..
Excellent.
Så en gang mere.
Jeg vil nu til at skubbe på stakken 26.
>> STEVEN: Ooh.
Oh gosh.
Du har virkelig fangede mig ud vagt.
>> DAVID MALAN: Du gjorde det ikke se det komme?
>> STEVEN: Jeg kunne ikke se det komme.
Kunne vi re-oprindelige kapacitet?
>> DAVID MALAN: Det er et godt spørgsmål.
Så vi har slags malet os i et hjørne her.
Der er virkelig ingen god ud for Steven fordi vi har afsat dette array
statisk, så at sige, inde over den datastruktur.
Og vi har stort set hårdt kodet det er af størrelse tre.
Så vi kan ikke rigtig omfordele det.
>> Vi kunne, hvis vi gik igen, vi omdefineret bakker at være en pointer,
vi så bruge malloc ved hånden hukommelse til.
Fordi hvis vi fik den hukommelse, den bunke via malloc, vi
kunne derefter frigøre det.
Men før at frigøre det, kunne vi omfordele en større bid af hukommelse,
opdatere markøren, og så videre.
Men for nu, er det virkelig det bedste, vi kan gøre.
Skubbe og pop er formentlig gå nødt til at signalere nogle fejl.
>> Så for eksempel, implementering vores push kunne returnere en bool, der
tidligere returnerede sandt, sandt, sandt.
Men fjerde gang, det kommer til at have at returnere falsk, f.eks.
Ok.
Meget godt klaret.
Tillykke.
Du har fortjent din stress bold i dag.
>> [Applaus]
>> STEVEN: Tak.
>> DAVID MALAN: Tak.
OK, så dette synes ikke at være meget et skridt fremad, right?
Vi beskrev denne datastruktur.
Det har været overbevisende, right?
Operativsystemer lide det.
Tilsyneladende nettet kan gøre brug af denne, og andre applikationer stille.
Men hvad en dum begrænsning, at vi er tilbage til slags uge to grænser
hvor vi har fast størrelse arrays.
>> Så der er faktisk et par måder, hvorpå vi kan løse dette.
Vi kunne dynamisk tildele array, ikke ved hårdt kodning det som jeg har
gjort her, men i stedet re-erklære dette, bare for at være klar, da
noget som dette.
Int * bakker ikke beslutte på en kapacitet endnu.
Men når jeg erklærer stakken andetsteds i min kode, jeg kunne derefter kalde malloc,
få adressen på en luns af hukommelse, og jeg kunne tildele
denne adresse til bakker.
>> Og så, fordi det er bare en luns af hukommelse, kunne jeg fortsætte med at bruge firkantede
beslag notation på den sædvanlige måde.
Fordi igen, er der er en slags dette funktionel ækvivalent af arrays og
bidder af hukommelse, der kommer tilbage fra malloc.
Vi kan behandle ene som det andet hjælp pointer aritmetik eller
firkantede beslag notation.
Så det er en tilgang.
>> Men hvordan man ellers kunne vi gennemføre denne samme datastruktur, potentielt?
Right?
Jeg føler, at vi bare løst dette problem som for en uge siden.
Hvad var løsningen på dette problem at Steven løb ind?
Så hægtede lister, til højre.
>> Hvis problemet er, at vi maler os op i et hjørne ved at afsætte
i forvejen for lidt hukommelse, vi så have en eller anden måde at beskæftige sig med, ja,
hvorfor ikke bare undgå, udstede i alt?
Hvorfor ikke bare erklære bakker at være en pointer til en node, ergo en sammenkædet liste
og så bare tildele nye noder hver gang Steven nødvendig for at passe en
nummer i datastrukturen.
>> Så ville billedet have at ændre.
Det kommer ikke til at være så ren og som simpelt som bare en vifte af tre ints.
Nu er det kommer til at være en pegepind til en struct, og at struct vil
har en int og en næste pointer.
Det kommer til at lede via denne pointer til en anden sådan struct til
en anden sådan struct.
Så ville billedet faktisk få en smule Messier.
Og vi ville have pile binde det hele sammen.
>> Men det er fint, til højre, fordi Vi har set, hvordan du gør dette.
Og når du får komfortabel gennemføre noget som en sammenkædet
liste, som du bliver nødt til at gøre, hvis du vælger at gennemføre en hash tabel med
separate chaining for p-sæt 6, kan du bruge det som en byggesten, eller
ingrediens, eller i Scratch tale, en procedure, noget, som du sætter, dig
oprettet din egen brik som du derefter kan genbruge.
Så tradeoffs, men potentielle løsninger at vi faktisk har set før.
>> Så ganske ofte, kan du se det hver år eller to, når Apple frigiver
noget nyt, og alle de skøre mennesker line up uden for Apple
lagre til at købe deres marginale opgradere på hardware.
Jeg siger dette, er det OK, fordi Jeg er en af ​​disse mennesker.
Så hvad slags datastruktur kan repræsentere denne virkelighed?
>> Nå, lad os kalde det en kø, en linje.
Så briterne ville kalde det typisk en kø alligevel, så det er en nice navn.
Og de to operationer, at en kø støtter vi vil kalde en enqueue
drift og en dequeue drift, som er ens i
ånd at skubbe og pop.
Det er bare slags anderledes i konvention, hvad vi kalder dem.
Men at enqueue noget betyder at tilføje eller sæt den til datastruktur.
At dequeue betyder at fjerne det.
Men hvor en stak var en LIFO data struktur, en kø er en først ind,
først ud datastruktur.
>> Hvis du er den første person i rækken, du vil være den første person til at få
ude af trit og købe din nye enhed.
Forestil dig, hvor ked af disse mennesker ville være hvis Apple i stedet brugt en stak, for
Eksempelvis at gennemføre plukning up af dit nye legetøj.
Så køer mening, i hvert fald, og Vi kan tænke på alle mulige
applikationer, formentlig for køer, især når du ønsker retfærdighed.
Så hvordan kan vi implementere disse som en datastruktur?
>> Nå, jeg foreslår, at vi måske nødt til at gøre det på denne måde.
Så jeg har tænkt mig at nu har numre.
Så vi vil holde det simpelt og ikke nødvendigvis tale i form af bakker.
Bare tal, at folk i fået.
Kapacitet vil, igen, fastsætte samlede antal personer, der kan være i
denne linje, da tre eller enhver anden værdi.
>> Men jeg foreslår, at jeg har brug for at holde styr ikke blot af størrelsen af
kø, hvor mange ting er i det.
Så størrelse er den aktuelle størrelse, kapacitet er den maksimale størrelse.
Lige igen, nomenklatur efter sædvane.
Hvorfor har jeg brug for en ekstra int inde af en kø for at holde styr på, hvem der er i
forsiden af ​​den linje?
Hvorfor skal jeg nødt til at gøre det i dette tilfælde?
>> Nå, hvordan er dette billede kommer til at ændre sig?
Jeg kan sandsynligvis genbruge mest af dette billede.
Lad mig gå videre og slette, hvad der er her.
Vi vil give det en anelse andet navn heroppe.
Lad os slippe af de 17, lad os slippe af 9, lad os slippe af med den 3..
Og lad os tilføje en anden ting.
Jeg foreslår, at jeg har brug for at holde styr på den forreste del af listen, hvilket er lige
vil være en int så godt.
Og vi kommer til at holde det simpelt.
Ingen linkede liste for nu.
>> Vi vil indrømme, at vi kommer til at bump op mod denne grænse.
Men hvad jeg ønsker at se ske denne gang?
Så formoder jeg gå videre og den første person kommer op på linje, og
det er nummer 9.
Vi har stress bolde.
Kan jeg stjæle, siger, to eller tre personer?
En, to, tre?
Kom op.
Lige forfra, fordi vil vi gøre dette til en hurtig.
>> Hver af jer er nu kommer til at være en fan dreng i kø ved Apple.
Du vil ikke modtage Apple-hardware i slutningen af ​​dette selv.
Ok.
Så du er nummer 9, er du nummer 17, nummer 22..
Disse er vilkårlige numre, ligesom studerende id'er eller whatnot.
Og på bare et øjeblik, så lad os begynde at begynde at tilføje ting.
Og jeg vil køre i bestyrelsen her i denne tid.
>> Så i dette tilfælde, har jeg initialiseret fronten for at være -
Jeg faktisk ikke rigtig pleje hvad front er, fordi størrelsen er nul.
Så dette kan lige så godt bare være et spørgsmålstegn.
Disse er alle spørgsmålstegn.
Så nu vil vi begynde at rent faktisk se nogle mennesker foring op i butikken.
>> Så hvis nummer 9, er du den første der på 5:00, gå videre og stille op,
eller natten før.
OK.
Så nu 9 er her.
Så 9 er i den forreste del af listen.
Så jeg har tænkt mig at gå videre og opdatere størrelsen af ​​denne aktuelle data
struktur ikke være 0 længere, men at være 1.
Jeg har tænkt mig at sætte 9 ved foran listen.
Lad mig gå videre og skifte skærmen så vi kan se forbi os her.
>> Og nu, hvad vil jeg have til at sætte foran?
Jeg har tænkt mig at holde styr at forrest i køen lige nu
er ved placeringen 0.
Fordi det næste kommer til at ske?
Nå, formoder jeg nu enqueue 17 så godt.
Så hop på linje der.
Og igen, den slags dør til butik kommer til at være her.
Så nu har jeg tilføjet 17.
Og selv om disse fyre blokerer skærmen, det er OK,
fordi vi kan se det heroppe.
Undskyld.
>> PUBLIKUM: Vi kan flytte -
>> DAVID MALAN: Nej, det er OK.
Det er enorme deroppe.
Så 17 er nu inde i køen.
Jeg har brug for at opdatere hvilke felter nu selv?
OK, absolut størrelse.
Og hvad med fronten?
OK, nej.
Foran bør ikke ændre, fordi i modsætning til en stak, vi
ønsker at opretholde retfærdighed.
Så hvis 9 kom i første omgang ønsker vi 9 at være den første ud af linjen
og ind i butikken.
>> Faktisk, lad os se.
Før vi indsætter 22, lad os gå videre og dequeue 9..
Hvad er dit navn igen?
>> PUBLIKUM: Jake.
>> DAVID MALAN: Jake går skal dequeued nu.
Så får du at gå ind i butikken.
Og foregive, at butikken er derovre.
Så nu, hvad har brug for - dit-dit-dit!
Hvad skal der ske nu?
Design beslutning.
Så ikke en dårlig instinkt, men - hvad er dit navn igen?
>> PUBLIKUM: David.
>> DAVID MALAN: David.
Så hvad gjorde David gøre?
Han prøvede at sortere i fastsætte data struktur og flytte fra sin placering
i Jakes tidligere placering.
Og det er fint, hvis vi er villige at acceptere, at som en
gennemførelse detalje.
Men først, lad os opdatere data struktur, før vi gør det.
Fordi jeg ikke kunne lide tanken om alle de mennesker, flytte i denne linje.
>> Det er ikke nogen big deal, hvis David gør det med et skridt, men igen, tænke tilbage på
når vi har haft otte frivillige på fase, og vi har gjort ligesom indsættelse
sortere, hvor vi havde til at starte flytte alle omkring.
Det fik dyrt, right?
Det gør mig krybe om store O n, kvadreret store O n igen.
Det er ikke at føle sig som en ideel resultat.
>> Så lad os bare opdatere denne.
Så størrelsen af ​​køen er ikke længere 2..
Det er nu blot 1.
Men jeg kan nu opdatere noget Jeg har ikke opdateret før,
foran listen.
Jeg kunne bare sige, er, at location 1?
Så nu har vi skrald værdi her, skrald værdi her, og David i
midten af ​​dette affald.
Men datastrukturen er stadig intakt.
>> Og i virkeligheden, behøver jeg ikke engang behøver at ændre Jakes tidligere nummer
9, fordi der bekymrer.
Jeg har nok information nu er i størrelse, som jeg ved, der er én person i
denne kø.
Og jeg ved, at denne person er location 1, ikke 0.
Jeg er ikke tælle.
Så 1 samt.
Så datastrukturen er stadig OK.
>> Nå, hvad sker der nu?
Lad os enqueue -
hvad er dit navn?
>> PUBLIKUM: Callen.
>> DAVID MALAN: Callen.
Lad os enqueue en Callen, og 22 er nu i køen.
Så nu, hvad skal ændres her?
Front ikke kommer til at ændre, naturligvis.
Størrelse kommer til at ændre til at være 2 igen.
Og 22 ender her, 9 er stadig til stede, men det er effektivt en
skrald værdi nu.
Det er bare en rest af Jake fortid.
>> Så nu, hvad sker der, hvis Jeg dequeue David?
En sidste operation, dequeue David.
Vi kunne flytte, men jeg foreslår lad os gøre så lidt arbejde som muligt.
Nu er min datastruktur går tilbage i størrelse 2-1.
Men forrest i køen bliver nu 2..
Jeg har ikke brug for at ændre disse numre bare endnu, fordi de er
bare skrald værdier.
>> Men nu hvad sker der?
Antag jeg enqueue mig selv, 26?
Jeg føler, at jeg hører herovre.
Så jeg bliver enqueued.
Så jeg slags hører til her.
Og selvom du ikke helt værdsætte denne visuelt på scenen,
fordi vi har masser af plads, jeg skulle ikke stå her, hvorfor?
>> PUBLIKUM: Du er out of bounds.
>> DAVID MALAN: Right.
Jeg er ude af bounds.
Jeg har indekseret over det grænserne for dette array.
Jeg burde være i en af ​​de tre mulige placeringer.
Nu hvor der er mest naturligt at gå?
Jeg foreslår, vi gearede en uge en trick.
The Mod operatør procentdel.
Fordi jeg teknisk set er stående på location 3, men jeg gør 3 mod kapacitet,
så 3 et procenttegn, 3 -
kapacitet er 3..
Hvad er det?
Hvad er resten, når du opdele 3 af 3?
0.
>> Så det sætter mig var Jake var, der er faktisk godt.
Så nu gennemførelsen af denne ting kommer til at
være lidt af en hovedpine.
Det er egentlig bare en linje hovedpine, kode.
Men i det mindste nu er der skrald værdi her, men der er to
legitime ints her.
Og jeg hævder, at nu har vi gjort præcis, hvad vi skal gøre, så længe
vi ændre, hvad Jakes værdi var at være 26.
>> Vi har nu oplysninger nok stadig at opretholde integriteten
af denne datastruktur.
Vi er stadig slags ude af lykke, når vi ønsker at indsætte fire eller flere samlede
elementer, men jeg kan i det mindste gøre pretty effektiv udnyttelse af denne konstante
tid, i virkeligheden.
Jeg behøver ikke at bekymre dig om at flytte alle, da Davids hældning var.
>> Eventuelle spørgsmål vedrørende stakke, eller denne kø?
>> TILHØRERNE: Er grunden du har brug for størrelse, så du kender
hvor at have en person?
>> DAVID MALAN: Præcis.
Jeg har brug for at kende størrelsen af ​​array fordi jeg har brug for at vide præcis, hvordan
mange af disse værdier er legitime, og så jeg kan finde, hvor at sætte
den næste person.
Præcis.
Størrelsen er -
faktisk, vi ikke opdatere denne endnu.
Jeg tilføjede mig på 26..
Størrelsen er nu, ikke 1, men 2.
Så nu er dette faktisk hjælper mig med at finde leder af listen, der ikke er 0, ikke
1, men er 2.
Den forreste del af listen er faktisk nummer 22.
Fordi han kom i først, så bør han være tilladt ind i butikken før mig,
selvom visuelt jeg står tættere til butikken.
>> Okay?
En runde af bifald for disse fyre og vi vil lade dem ud derfra.
>> [Applaus]
>> DAVID MALAN: jeg kunne lade du holder bakken.
Vi kunne se, hvad der sker, hvis du vil, men måske ikke.
Ok.
Så hvad nu, står vi?
Nå, lad mig foreslå, at der er en få andre datastrukturer, vi kunne
begynde at tilføje til vores værktøjskasse, der vil faktisk være helt, helt relevant som
vi dykke ned i web stuff.
Hvilket igen har en vis form for forbindelse til træer i form af
noget, der hedder DOM, dokument objekt model.
Men vi vil se mere af at inden længe.
>> Lad mig foreslå definitionally at vi kalde træet nu, hvad du måske kender som
mere af en familie træ, hvor man har nogle forfader ved
rødder af træet.
En patriarkalsk eller matriark på toppen af ​​træet.
Uden deres ægtefælle. I dette tilfælde
Men nu har vi, hvad vi vil kalde børn, som er knuder, der hænger
off venstre barn eller højre barn, pile, som afbildet her.
>> Med andre ord, i et træ datastruktur i computer har et træ nul
eller flere knuder.
Hvis det har mindst en knude, der hedder root.
Det er de ting, visuelt at vi trækker på toppen.
Og denne node, som enhver anden knude, kan have nul, én eller to, eller tre,
eller hvor mange børn de datastruktur understøtter.
I dette tilfælde, roden opbevaring af værdi en, har to børn, 2 og 3,
så vi generelt kalder 2 venstre barn og 3 højre barn.
>> Og så når vi kommer ned til 5, 6 og 7, 6 kunne kaldes den midterste barn.
Hvis du har fire børn, det bliver forvirrende.
Så vi stoppe med at bruge den slags genvej verbalt.
Men det er egentlig bare et stamtræ.
Og bladene her er de noder, selv har ingen børn.
De hænger ned fra bunden af ​​træet.
>> Så hvordan kan vi implementere et træ, har kun to børn maximalt?
Vi kalder det et binært træ.
Bi igen betyder to, i dette tilfælde gerne med binær.
Og så kan det have nul, et, eller to børn maksimalt.
>> Jeg vil foreslå, at vi gennemfører node for denne struktur med en int n,
og derefter to pointere, den ene kaldte venstre, der hedder rigtigt.
Men de er bare nice vilkårlige konventioner.
Og hvad er rart nu, især hvis du slags kæmpet konceptuelt med
rekursion eller troede, at det ikke var virkelig en løsning på noget som helst,
især hvis du kunne løber tør for hukommelse.
Nu, hvor vi taler om data strukturer og algoritmer, der tillader
os at krydse og manipulere dem, viser sig, at rekursion kommer tilbage i
en langt mere overbevisende hvis ikke smuk måde.
>> Så dette jeg foreslår, er gennemførelsen en søgefunktion.
Da to indgange -
så tænk på det som en sort boks.
Da to indgange, n, en int og en pointer til et træ, en pointer til en
node, eller virkelig roden af ​​et træ, jeg påstand om, at denne funktion kan returnere
sandt eller falsk, at værdien n er inde i dette træ.
>> Hvad er inde i denne sorte boks?
Nå, fire filialer.
Den første lige tjekker.
Hvis træet er null, bare returnere falsk.
Hvis der ikke er nogen node, er der ingen n, der er ingen tal, bare returnere falsk.
Hvis selv, n, den værdi, du leder efter til mindre end træ pil n er, og
bare for at være klar, hvad betyder det, når Jeg skriver træet og derefter pilen
notation, n?
Præcis.
Det betyder dereference at pointer kaldet træ.
Derned, og derefter komme ind i denne node og få sit felt kaldet n.
Og derefter sammenligne den faktiske n, der var gået ind Søg imod det.
>> Så hvis n er mindre end værdien n i træet node selv, godt
hvad betyder det?
Det betyder ikke noget ved første øjekast.
Right?
Ligesom når du har en bred vifte af værdier, kan du lide at anvende binære
søge som en form for kløft og erobre.
Men hvad antagelse vi nødt til at gøre for binær søgning for at arbejde på alle
i telefonbogen og tidligere eksempler?
>> Hvordan skal sorteres.
Så lad os forfine definitionen af ​​træet her ikke at være bare et træ, der kan
have et vilkårligt antal børn.
Ikke bare et binært træ, som kan har 0, 1 eller 2 maksimalt.
Men som en binær søgning træ eller BST, der er bare en fancy måde at sige en
binært træ, således at hver node venstre barn, hvis det nuværende er
mindre end knudepunktet.
Og hver node ret barn, hvis tilstede, er større
end knudepunktet selv.
>> Så med andre ord, hvis du skulle tegne træet ud, alle numrene er
omhyggeligt afbalanceret som dette, så hvis du har 55 som roden, kan 33 gå
til venstre, fordi det er mindre end 55 år.
77 kan gå til sin ret, fordi den er større end 55 år.
Men nu mærke, samme definition, Det er en rekursiv definition verbalt,
skal ansøge om 33.
33 venstre barn skal være mindre end det, og 33 ret barn, 44, skal være
større end det.
>> Så dette er en binær søgning træ, og Jeg foreslår, at bruge en lille smule af
rekursion, kan vi nu finde n..
Så hvis n er mindre end den værdi, n, der er nuværende node, jeg kommer til at gå
fremad og punt, så at sige, og bare tilbage uanset svar er
søger efter n på tree venstre barn.
Bemærk igen, denne funktion bare forventer en node stjerne, en
pointer til et knudepunkt.
Så vel kan jeg bare gøre træet pil venstre, som vil føre
mig til en anden node.
Men hvad er det node?
>> Tja, ifølge denne erklæring venstre er blot en pegepind, så bare
betyder jeg passerer til søgefunktionen en anden pointer, nemlig
den, som repræsenterer min venstre barns træ.
Så i dette tilfælde, at markøren 33, hvis dette er vores prøve input mellemtiden, hvis
n er større end værdien N ved nuværende node i træet, så er jeg
kommer til at gå videre og punt i det andet retning og bare sige, jeg ikke
vide, om denne værdi n er i træet, men jeg ved, om det er, det er ned af min
højre gren, så at sige.
Så lad mig kalde rekursivt søge, passerer en n igen, men passerer i en
pointer til min højre barn.
>> Med andre ord, ved hvis jeg er i øjeblikket 55 og jeg leder for 99, jeg ved, at 99
er større end 55, så ligesom jeg rev i telefonbogen uger siden, og vi
gik ret, på samme måde er vi kommer til at gå lige her.
Og jeg ved ikke, om det er ved min højre barn, og det er ikke, 77 er der, men
Jeg ved, det er i den retning.
Så jeg kalder søgning på min højre barn, 77 og lad søgningen tal ud fra
der, hvis 99 i denne vilkårlige eksempel er faktisk der.
>> Else, hvad er det sidste tilfældet?
Hvis træet er null er én sag.
Hvis n er mindre end den aktuelle node værdien er en anden sag.
Hvis n er større end den aktuelle node værdi er et tredje tilfælde.
Hvad er den fjerde og sidste sag?
Jeg tror, ​​vi er ude af sager, right?
Det må være n er i aktuelle node at jeg er på.
>> Så hvis jeg søger efter 55 på dette punkt i historien, gren, den
træ ville returnere sandt.
Så hvad er interessant her, er, at vi faktisk, i modsætning uger tidligere, vi slags
af har to base tilfælde.
Og de behøver ikke at være alle på toppen.
Den øverste er en base tilfældet, fordi hvis træ er null, er der intet at gøre.
Bare returnere en hård kodet værdi af falsk.
>> Den nederste gren er en slags standard, hvor hvis vi har kontrolleret for
null, vi har tjekket om det skulle være venstre, men det bør ikke være, vi har
kontrolleres, hvis det skulle være rigtigt, men det bør ikke være det helt klart må være
lige der, hvor vi er.
Det er en base case.
Så der er to rekursive tilfælde klemt der i midten.
Men jeg kunne have skrevet dette i vilkårlig rækkefølge.
Jeg syntes bare det følte slags naturlig først kontrollere, om en eventuel fejl,
så tjek venstre, så tjek lige, så antage, at du er på node
du faktisk leder efter.
>> Så hvorfor kan det være nyttigt?
Så det viser sig -
og lad mig springe til en teaser her, at der er i nettet.
Vi kommer til at begynde at bruge ikke programmeringssprog i starten, men en
kodesprog.
Et markup sprog er en, der er samme ånd til programmering
sprog, men det gør ikke give dig den evne til at udtrykke dig logisk.
Det giver dig kun mulighed for at udtrykke dig strukturelt.
>> Hvor vil du sætte noget på siden,? websiden
Hvilken farve vil du gøre det?
Hvilken skriftstørrelse vil du gøre det?
Hvilke ord vil du faktisk ønsker på websiden?
Så det er et kodesprog.
Men så vil vi meget hurtigt indfører JavaScript, som er et fuldgyldigt
programmeringssprog.
Meget lig syntaktisk i udseende til C, men det vil have nogle
nice, mere kraftfuld, mere brugervenlige funktioner.
>> Og en af ​​de frustrationer på dette punkt i semesteret er, at vi vil
snart gennemføre speller i langt færre linjer kode ved hjælp af andre sprog
end C selv tillader det, men for fornuftens Vi vil snart forstå.
Dette vil være den første webside.
Det vil være helt underwhelming, det første vi gør.
Det vil blot sige, hej verden.
Men hvis du aldrig har set det før, det er HTML,
HyperText Markup Language.
>> Hvis du går til en bestemt menupunkt i de fleste enhver browser på enhver webside på
internettet, kan du se HTML at nogle mennesker skrev til
skabe den webside.
Og det sandsynligvis ikke ser ud som kortfattet eller så pæn som dette.
Men det vil følge det mønster af disse åbne parenteser og skråstreger og
bogstaver og potentielt tal.
>> Jeg troede, jeg ville give dig en teaser af, hvad du vil være i stand til at gøre
efter at have taget CS50.
Lad mig gå til cs.harvard.edu / Rob, vores egen Rob Bowden hjemmeside.
Han gjorde dette for os.
Så du vil snart være i stand til at gøre det.
Og også, hvad du har hørt morges -
hvad du hørte i morges -
>> [HAMSTER DANCE MUSIC]
>> - Du kunne gøre dette.
Der venter os på onsdag.
Vi vil se dig derefter.
>> [HAMSTER DANCE MUSIC]
DAVID MALAN: På det næste CS50 -