>> DAVID MALAN: Okej.
Välkommen tillbaka till CS50.
Detta är början på vecka 8.
Och minns att problemet set 5 slutade med lite av en utmaning.
Så antar att du återhämtat alla dina Undervisning Fellows och CA: s fotografier
i card.raw filen, har du rätt att nu hitta alla dessa människor, och
en lycklig vinnare kommer att gå hem med en av dessa saker, språnget rörelse
enhet som du kan använda för final projekt, till exempel.
>> Detta, varje år, leder till en bit av creepiness.
Och så vad jag trodde jag skulle göra är att dela med dig några av de anmärkningar som har
gått fram och tillbaka över personalen listan över sent.
Till exempel, bara i går kväll, citat unquote, från en av personalen
medlemmar, "Jag hade bara en elev knock på min dörr för att ta ett foto med mig.
Stalkers, säger jag. "Började ganska beskrivande och sedan vi flyttade
till, en timme eller så senare, "Jag hade en studenten väntar på mig efter avsnitt
och han hade alla våra namn och foton på några pappersark. "Okej.
Så organiseras, men inte allt som obehagligt ännu.
>> Sedan, "jag var ute på stan i helgen, och när jag kom tillbaka, det var en i
min
sovrummet. "[SKRATT]
DAVID MALAN: Nästa citat från en personal ledamot, "en elev kom till mitt hus på
Somerville klockan 4 i morse. "Next personal, "jag fick till mitt hotell i San
Francisco och en student väntade mig i lobbyn med tre digitala systemkameror. "
Typ av kamera.
"Jag är inte ens på personal här terminen, men en student bröt sig in i mitt hus här
morgon och spelade in alltihop med Google Glass. "Och sedan sist,
"Minst 12 människor var ivrigt väntar på mig när jag kom ut ur min
limo, och sedan jag
vaknade. "Okej.
Så bland fotografierna, som ni kanske minns, är denna karl här, vem du
kanske vet så Milo Banana, som bor med Lauren Carvalho, vårt huvud
undervisning Fellow.
Milo, Milo, kom hit pojken.
Milo.
Märk väl, han bär Google Glass, så Vi ska visa dig allt detta efter.
Så det här är Milo om du vill ta ett foto med honom efteråt.
Om du vill titta ut på publiken där.
OK.
Det är bra tagning.
Tja, Milo Banana.
Åh, gör inte det.
>> [SKRATT]
>> OK.
Så ett ord och sedan på vad som väntar, för som vi börjar övergången,
denna vecka specifikt, från C i en kommandoraden miljö till PHP och
JavaScript och SQL och HTML och CSS i en webbaserad miljö, vi ska vara
utrusta dig med all mer kunskap för
potentiella slutliga projekt.
Mot detta har naturligtvis en traditionen att hålla seminarier som
är på tangentiella ämnen till kursen.
Mycket relaterade till programmering och applikationsutveckling och så vidare, men
inte nödvändigtvis utforskas genom kursens egen kursplan.
>> Så om du kan vara intresserad av en eller mer av årets seminarier,
registrera dig på cs50.net/seminar.
Det finns äldre seminarier vid cs50.net/seminars.
Och på deltagarlistan hittills i år är fantastiska Web Apps med Ruby on
Skenor, som är ett alternativ språk till PHP.
Datorlingvistik.
Introduktion till iOS, som är den plattform som används för iPhone och
iPad utveckling.
JavaScript för Web Apps kommer vi att täcka det, men i detta seminarium kommer du att gå
in mer i detalj.
>> Leap Motion, så vi ska faktiskt ha lite av våra vänner från Leap Motion,
företaget självt, ansluta sig till oss.
I morgon, i själva verket, för att ge en hands-on seminarium om
av intresse för dig.
Meteor.js, en alternativ teknik för med hjälp av JavaScript inte i en webbläsare,
men på en server.
Node.js, som är mycket i samma anda som väl.
Sleek Android Design.
Android är ett mycket populärt alternativ till iOS och Windows Phone
och andra mobila plattformar.
Och Web Security Active Defense.
>> Så i själva verket, om du vill att engagera sig i detta, låt mig
anteckna detta.
Vi är mycket glada att kunna säga att våra vänner på Leap
Motion, vilket är en start -
denna enhet egentligen bara kom ut för några månader sedan -
har artigt donerat 30 sådana anordningar till klassen för så många studenter, om
du vill låna hårdvaran mot terminen slut och använda den för
en verklig slutprojekt.
De stöder ett antal olika språk.
Ingen av dem C, ingen av dem PHP, så förverkliga ett eller flera av dessa seminarier
kan visa sig intressant.
Och alla av dem kommer att filmas i Om du inte kan
att närvara personligen.
Schemat meddelas via e-post som vi stelna rum.
>> Och slutligen, om du går till projects.cs.50.net, detta är en webbplats
vi underhåller varje år som vi inbjuder folk från gemenskapen, fakultet,
avdelningar, personal och båda i en utsida av CS50 till
föreslå projektidéer.
Saker av intresse för studentgrupper.
Saker av intresse för avdelningar.
Så vänder det om du kämpar med osäkerhet om vad du
själv skulle vilja angripa.
>> Så förra gången vi införde en tvekan mer komplex datastruktur än vi skulle
ses i veckor tidigare.
Vi hade använt arrayer ganska glatt som ett användbart om
simplistic datastruktur.
Sedan vi införde dessa, vilket givetvis är länkade listor.
Och vad som var ett av motiven för införa denna datastruktur?
Yeah?
Vad är det?
>> Publik: Dynamisk storlek.
>> DAVID MALAN: Dynamisk storlek.
Så medan array, måste du vet dess storlek i förväg när
du fördela det.
I länkad lista, gör du inte måste veta det.
Du kan bara malloc, eller mer generellt, allokera ytterligare
nod, så att säga, varje gång du vill infoga mer data.
Och noden har ingen förutbestämd mening.
Det är bara en allmän term som beskriver någon form av behållare som vi är
användning i vår datastruktur för att lagra vissa objekt av intresse, vilket i detta
fall råkar vara heltal.
>> Men det finns alltid en avvägning.
Så vi får dynamiska storlekar av data struktur, men vilket pris ska vi betala?
Vad är nackdelen med länkade listor?
Yeah?
>> Publik: Kräver mer minne.
>> DAVID MALAN: Det krävs mer minne, exakt hur?
>> Publik: [OHÖRBAR].
>> DAVID MALAN: Exakt.
Så nu har vi pekare tar upp extra minne som vi tidigare
inte behöver, eftersom fördelen av en matris, naturligtvis, är att
allt är sammanhängande, rygg att rygg mot rygg, vilket
ger dig direktåtkomst.
Eftersom bara genom att använda klammer notation, eller mer tekniskt pekare
aritmetik, mycket enkel addition, kan du komma åt alla
element i konstant tid.
Och i själva verket är den sortens antyda annat pris som vi betalar med en
länkad lista.
>> Vad händer med gångtiden något liknande Search, om jag vill
hitta något värde och inne av en länkad lista?
Vad min gångtid bli?
Big O n.
Om det sorteras?
Vad händer om den datastruktur är sorterade?
Kan jag göra bättre än stora O n för att söka?
Nej, eftersom det i värsta fall kan det mycket väl ska sorteras, men antalet
du letar efter kan vara stort.
Det kan vara numret 100, vilket kanske råkar vara alla
vägen i slutet.
Och eftersom du kan bara få en länkad Listan i denna implementering av
vägen för dess första noden, du fortfarande lite av lycka.
Du måste korsa hela från första till sista för att finna
det stora värde som 100.
Eller för att avgöra om det är inte ens där.
>> Så vi kan inte göra vad algoritmen i en data struktur som ser ut så här?
Vi kan inte göra binär sökning, eftersom binär sökning krävs att vi hade
random access.
Vi kunde bara hoppa från plats till plats utan att behöva följa
dessa brödsmulor i form av alla dessa tips.
>> Nu, hur vi genomför detta?
Tja, om vi går till skärmen här, om Vi kan snabbt reimplement dessa data
struktur -
min handstil är inte så stor här, men vi ska försöka.
Så typedef struct, och vad gjorde jag vill kalla den här saken här uppe?
Nod.
Så jag ska komma igång.
Och nu, vad som behöver vara inne i datastrukturen för att var för sig
länkad lista?
Hur många områden?
>> Så två.
Man är ganska lätt.
Så int n.
Och vi kan kalla n vad vi vill, men det bör vara en int om vi
genomföra en länkad lista för ints.
Och nu vad gör den andra fältet måste vara?
Struct nod *.
Så om jag gör struct node *, och sedan jag kan kalla detta också vad jag vill,
men bara för att vara tydlig jag ringer det nästa, som vi har gjort.
Och sedan ska jag stänga mina klammerparenteser.
>> Och nu, som förra gången, Jag satte nod här nere.
Men om jag förklara detta är som en nod, varför jag bry vara så
verbose här förklara struct nod * nästa, i motsats
att bara nod * nästa?
Yeah?
>> Publik: [OHÖRBAR].
>> DAVID MALAN: Exakt.
Exakt.
Eftersom C tar verkligen du bokstavligen och bara ser definitionen av noden
vägen ner hit, kan du inte hänvisa till det här uppe.
Så vi har denna typ av förebyggande förklaring här, vilket är visserligen
mer mångordig.
Struct nod, det betyder Vi kan nu komma åt det
insidan av datastruktur.
>> Och som en parentes, eftersom detta är blir lite mer subjektiv nu,
stjärnan kan tekniskt gå hit, det kan gå här, kan det
ens gå i mitten.
Vi har antagit, i stil guide för kursen, konventionen för att sätta
stjärnan bredvid datan typ, som i detta fall,
skulle vara struct nod.
Men inser i många läroböcker och online referenser, kanske du faktiskt
se det på den andra sidan.
Men bara att inse att båda kommer faktiskt arbete och du bör helt enkelt vara
konsekvent.
>> Okej.
Så det var vår deklaration av struct nod.
Men sedan vi började göra mer sofistikerade saker.
Till exempel, beslutade vi att införa något som liknar en hash-tabell.
Så här är en hash tabell av storlek n, indexeras från 0 uppe till vänster till n
minus 1 längst ned till vänster.
Detta kan vara en hash bord för någonting.
Men vilka typer av saker vi pratar om att använda en hash-tabell för?
Lagra vad?
>> Names.
Vi kunde göra namn som vi gjorde förra gången.
Och egentligen, kan du lagra något.
Och vi får se detta igen PHP och JavaScript.
En hash-tabell är en trevlig slags schweiziska Armékniv som låter dig lagra
ganska mycket vad du vill inne i det genom att associera tangenter med värden.
Nycklar med värden.
>> Nu i detta enkla fall, vår nycklar är bara siffror.
Vi genomför en hash bord som en matris.
Och så är tangenterna 0, 1, 2, och så vidare.
Och så vi, som människor, beslutade förra vecka som ni vet vad, om vi är
går att lagra namn, låt oss bara godtyckligt, men ganska rimligt,
anta att Alice, en Ett namn, kommer bara att indexeras i 0.
Och Bob, ett B-namn, kommer att indexeras till 1, och så vidare.
Så vi hade en mappning mellan ingångar, som är strängar, och hash
platser, vilket är siffror.
>> Så att processen är allmänt känd som en hashfunktion, och du kan verkligen
genomföra det i koden.
Om jag ville genomföra en hashfunktion som gör exakt vad vi
just beskrivits från förra gången, kan jag deklarera en funktion som tar, som
ingång till exempel -
och låt oss göra detta på detta Skärmen hit.
Om jag ville genomföra en hash funktion, kan jag säga
ungefär så här.
>> Det kommer att returnera en int.
Det kommer att kallas hash, och det är kommer att acceptera som argument en
sträng, eller vi kan vara mer rätt nu, och säger char *, ska vi kalla det är.
Och så all denna funktion har att göra, Ytterst är tillbaka en int.
Nu, hur det skulle kunna inte vara så tydlig.
Jag kommer att genomföra detta utan form av felkontroll just nu.
Jag kommer bara att blint säga, tillbaka vad är er konsol 0, minus,
låt oss säga, huvudstad semikolon.
>> Helt trasig.
Det är inte perfekt eftersom en, tänk om s är null?
Dåliga saker kommer att hända.
Två, vad händer om den första bokstaven i det här Namnet är inte stor bokstav?
Det kommer inte att vända väl ut heller.
Det kan vara en liten bokstav eller inte en bokstav alls.
Så helt utrymme för förbättringar, men detta är den grundläggande idén.
>> Vad vi beskrivit förra veckan muntligt som bara en process för att kartlägga Alice till
0 och Bob till 1 kan uttryckas säkert mer formulaically som en C
fungera här.
Ringde igen hash, tar en sträng som ingång, och sedan på något sätt gör något
med den ingången för att producera en utsignal.
Inte olikt vårt svarta lådan beskrivning att vi har länge gjort.
Jag vet inte hur detta kan vara arbetar under huven.
>> För problem 6 set, en av utmaningarna är för dig att bestämma vad
kommer din hashfunktion vara?
Vad kommer att vara inne i det svarta box, och förmodligen kommer det att bli en
lite mer intressant än detta, och definitivt mer benägna att fel
kontroll än detta genomförande.
>> Men problem kan uppstå, eller hur?
Om vi ​​har en datastruktur som denna en, vad är ett av de problem som
du kan stöta på under tiden som du sätter fler och fler namn till
hash table?
Du får kollisioner, rätt?
Vad händer om du har Alice och Aron, två personer vars namn hände
att börja med A?
Detta väcker frågan, där du sätta den andra ett sådant namn?
>> Tja, kanske du naivt bara lägga den där Bob hör hemma, men då Bob är
sorts skruvas om du försöker sätta sitt namn bredvid och
det finns ingen plats för honom.
Så du kan sätta Bob där Charlie är, och ni kan föreställa er detta mycket snabbt
delegera till en bit av en enda röra.
Något linjär i slutet, där du bara att söka på hela
letar efter Alice eller Bob eller Aaron eller Charlie.
>> Så istället vi föreslog, i stället för bara linjärt sondering för öppna ytor
och plopping namnen där, vi föreslagit ett snyggare tillvägagångssätt.
En hash table genomförs fortfarande med en samling av index, men datatypen för
dessa index var nu pekare.
Pekare till vad?
Pekare till länkade listor.
>> Därför minns att en länkad lista är egentligen bara en pekare till en nod, och
noden har en nästa fält, och den noden har en nästa fält, och så vidare.
Så du kan nu tänka på denna array på den vänstra sidan av en hash-tabell som
vilket leder till en länkad lista.
Den fördelen är om du får ett kollision mellan Alice och Aron,
vad gör du med den andra personen?
Du fäster bara honom eller henne till ände eller ens början
av den länkade listan.
>> Och faktiskt, låt oss bara nudel genom som för bara en sekund.
Vart skulle göra det bästa bemärkelse?
Om jag sätter Alice och hon hamnar på den första platsen, så jag försöker
infoga Arons namn, och det finns uppenbarligen en kollision, ska jag sätta
honom i början av den länkade listan?
Det är på den första platsen, eller i slutet?
>> Publik: [OHÖRBAR].
>> DAVID MALAN: OK.
Jag hörde början.
Varför i början?
>> Publik: [OHÖRBAR].
>> DAVID MALAN: OK.
Det är alfabetiskt, så det är trevligt.
Det är en bra egenskap.
Det kommer att spara mig lite tid potentiellt.
Det kommer inte låta mig göra binär sökning, men jag skulle åtminstone kunna bryta ut
av en loop om jag inser, ja, jag är långt Tidigare var Aaron skulle vara i detta
sorterade länkad lista.
Jag behöver inte slösa min tid på att leta hela vägen till slutet.
Så det är rimligt.
Varför annars kanske du vill infoga det krockande namnet på
början av listan?
Vad är det?
>> Publik: [OHÖRBAR].
>> DAVID MALAN: Det kan ta lång tid att komma till slutet av listan.
Och i själva verket, längre och längre.
Ju fler namn som du infogar att börja med A, ju längre
kedjan kommer att få.
Ju längre det länkade Listan kommer att få.
Så du är egentligen bara slösar bort din tid.
Kanske är du bättre bevara konstant isättning tid, big O 1,
genom att alltid sätta kolliderande namn på början av den länkade listan,
och inte oroa så mycket om sortering.
>> Vad är det bästa svaret?
Det är oklart.
Den typ av beror på vad distributionen är, vad mönstret är
av de namn du sätter.
Det är inte nödvändigtvis ett självklart svar.
Men här, igen, är en design tillfälle.
>> Så vi sedan tittade på den här saken, som är egentligen den andra stora chans
för p-set 6.
Och inse, om du inte redan har gjort, Zamyla dyker ner i båda dessa, hash
bord och försöker, i mer detalj.
Och video genomgång är inbäddade i p-set spec.
Detta var en trie -
T-R-I-E. Och vad var intressant detta var att gångtid
att söka efter ett namn, som Maxwell förra gången, var stort O vad?
Vad är det?
>> Målgrupp: Antalet bokstäver.
>> DAVID MALAN: Antal bokstäver.
Jag hörde två saker.
Antal bokstäver och konstant tid.
Så låt oss gå med det första.
Antalet bokstäver.
Nåväl, detta är datastruktur, återkallelse, som ett träd, ett släktträd, vart och ett av
vars noder består av matriser.
Och dessa matriser är pekare till andra sådana noder, eller andra sådana
arrayer i trädet.
>> Så om vi ville sedan bestämma om Maxwell är här, kan jag gå
till den första gruppen, högst upp på trädet, den så kallade roten, toppen av
den trie och följ sedan m pekaren, sedan en pekare, då x,
w, e, l, l.
Och sen när jag ser någon speciell symbol, betecknas här som en triangel.
I koden ser du föreslår vi att du implementeras som en bool, bara säga ja
eller nej, stannar ett ord här.
>> Nåväl, när vi har gått till M-A-X-W-E-L-L, känns som sju, kanske
åtta om vi går en förbi, åtta åtgärder för att hitta Maxwell.
Eller låt oss kalla det K. Men minns förra tid, hävdade jag att om det finns
realistiskt en maximal längd på en ord, liksom 40-del-udda karaktärer, en
maximala längden innebär ett konstant värde.
Så egentligen, ja, det är tekniskt Big O av 8 7 eller, eller riktigt stora O K. Men
om det finns en ändlig tak för vad K kan vara, det är en konstant.
Och så det är stor O av 1 vid slutet av dagen.
>> Inte i den verkliga världen.
Inte när du börjar faktiskt titta din klocka som ditt program körs.
Det kommer absolut att bli lite långsammare än verkligt konstant
tid med ett steg.
Det kommer att bli sju eller åtta steg, men ändå det är mycket, mycket bättre
än en algoritm som Big O n som beror på storleken på vad som finns i
datastruktur.
>> Lägg märke till upp här är att vi kan sätta in en miljon fler namn i detta
datastruktur, men hur många fler steg det kommer att ta oss att hitta
Maxwell i så fall?
Inga.
Han är opåverkad.
Och hittills, jag tror inte vi har sett ett exempel på en datastruktur eller
algoritm som var helt opåverkad av externa
beteenden som.
Men detta kan inte vara fantastiskt.
Detta kan inte vara den enda lösningen för p-set
>> Och det är inte.
Detta är inte nödvändigtvis de uppgifter struktur bör du dras till,
eftersom som hashtabeller, avvägning.
Vad är det pris du betalar här?
Minne.
Jag menar, är detta en avskyvärd mängd minne.
Och du kan inte riktigt se det här eftersom författare till den här bilden
uppenbarligen stympad alla matriser, och vi inte ser massor av A: s och
B: s och C: s och Q: s och Y: s och Z är i dessa matriser.
Men de är där.
>> Var och en av dessa noder är en hel rad vissa 26 eller fler bytes, vilka
som representerar en bokstav.
27 i vårt fall, så att vi kan stödja apostrofer i problembild.
Så här datastruktur är riktigt, riktigt tät och bred.
Och det ensamt kan sluta att sakta ner saker, eller åtminstone kostar dig en
mycket mer utrymme.
Men återigen, kan vi dra jämförelser här.
>> Minns en tid tillbaka har vi uppnått mycket mer spännande drifttid i sortering
när vi använder merge sort, men priset Vi betalade för att uppnå n log n för sammanfogningen
Sortera krävs att vi spenderar mer vilken resurs?
Mer utrymme.
Vi behövde en sekundär array till kopiera folk in, precis som
vi gjorde här på scenen.
Så återigen, inga tydliga vinnare, men bara subjektiv utformning
beslut som ska fattas.
>> Okej.
Så vad sägs om det här?
Någon känner igen som D-Hall?
OK.
Så tre av oss gör.
Mather House.
Så det här är för Mather s matsal.
Jag slår vad alla matsalarna har högar av brickor som denna.
Och detta är verkligen representativt av något vi har
uppenbarligen redan sett.
Vi kallade det bokstavligen en stapel.
Och stapeln, i termer av din datorns minne, är där data går
medan funktioner som anropas.
>> Till exempel vilka typer av saker går på stacken med avseende på den
minne layout vi har diskuterat i veckor tidigare?
Vad är det?
>> Målgrupp: Samtal till funktioner.
>> DAVID MALAN: Jag är ledsen.
>> Målgrupp: Samtal till funktioner.
>> DAVID MALAN: Samtal till funktioner, men specifikt, vad som finns inuti var och en av
dessa ramar?
Vilka typer av saker?
Yeah.
Så lokala variabler.
När som helst vi behövde någon lokal lagring, som ett argument, eller int jag, eller int
temp, eller vad den lokala variabeln, vi har varit
sätta det på stacken.
Och vi kallar det en bunt eftersom av denna skiktning idé.
Bara typ av matcher med verkligheten, konceptet därav.
>> Men det visar sig att en stapel kan också ses som en datastruktur, en
alternativ till en matris, ett alternativ till en länkad lista.
Något begreppsmässigt mer intressant som fortfarande kan vara
genomföras med hjälp av någon av de saker, men det är en annan typ av
datastruktur stödjande, verkligen, endast två operationer.
Men du kan lägga på snyggare funktioner än dessa.
Men dessa är grunderna -
driva och pop.
>> Och idén med en stack är att om jag har här, med eller utan Annenberg
vetskap, en bricka från nästa dörr med nummer 9 på den.
Så bara en int.
Och jag vill driva detta på uppgifterna struktur, som för närvarande är tom.
Tänk på detta i botten av stapeln.
Jag skulle driva detta nummer 9 på stapla, och nu är det rätt där.
>> Men det intressanta med en stack är att om jag nu vill driva
något annat värde, 17 gillar, och jag trycker detta på stacken, kommer jag att göra
det enda intuitiva sak, jag ska bara att sätta det rätt där vi människor
skulle vara benägna att lägga den på toppen.
Men vad som är intressant nu är, hur får jag vid 9?
Du vet, det gör jag inte utan viss ansträngning.
>> Så vad är intressant en skorsten är att genom design,
det är en LIFO datastruktur.
Silly sätt att beskriva sist in, först ut.
Så det sista numret i vid denna tid var 17.
Så om jag vill smälla något utanför av stapeln, kan det bara 17.
Så det finns en obligatorisk ordning Operationerna här, där den sista posten
i måste vara först ut.
Därav förkortningen, LIFO.
>> Så varför skulle detta vara användbart?
Är deras sammanhang där du vill vill ha en datastruktur som denna?
Tja, är det verkligen varit till nytta insidan av en dator.
Så operativsystem använder tydligt detta typ av datastruktur för stackar.
Vi ser också samma idé när det gäller webbsidor.
Så den här veckan och nästa vecka och utanför, och när du börjar genomföra webben
sidor på ett språk som kallas HTML, kan du faktiskt använda en datastruktur som
detta för att avgöra om sidan är korrekt formaterad.
Eftersom vi ser alla webbsidor följer ett slags hierarki, en fördjupning
som kommer i slutet av dagen, vara en trädstruktur under huven.
Så mer om att på bara en bit.
>> Men för nu, låt oss föreslå ett ögonblick, hur skulle vi gå om
representerar vad en stapel är?
Låt mig föreslå att vi genomför en bunt med koden så här.
Så en stapel kommer att ha inne i det två saker, en array, som kallas brickor,
bara för att vara förenligt med demo.
Och var och en av punkterna i denna matris kommer att bli en typ int.
Och kapaciteten är förmodligen vad?
Eftersom jag inte har skrivit fullständig definition här.
>> Det är förmodligen den största storleken på matrisen.
Och det är förmodligen förklaras som en skarp definiera på toppen av filen, vissa
slags konstant underförstådda som genom enbart versaler.
Så någonstans kapaciteten definieras som i största möjliga storlek.
Samtidigt, inne i datastrukturen känd som en stapel kommer det
vara ett heltal bara kända helt enkelt som storlek.
>> Så om jag skulle representera detta nu bildmässigt, låt oss anta att detta
Hela svarta lådan representerar min stack.
Inuti är det två variabler.
Så jag kommer att dra första som storlek.
Och den andra ska jag att dra som en matris.
>> Men bara för att hålla saker ordnad, Normalt skulle jag rita en array som
detta, men det är typ av trevligt Om vi ​​matchar verkligheten, eller
matcha den mentala modellen.
Så låt mig istället dra array vertikalt, är som just, återigen,
konstnärs tolkning.
Spelar egentligen ingen roll vad det är under huven.
Och vi säger att, som standard, kapacitet kommer att bli tre.
Så detta kommer att vara platsen 0, detta kommer att vara plats 1, detta
kommer att vara plats 2.
>> Om jag muta med en stress boll, skulle någon vilja komma upp och köra
styrelsen här för bara en stund?
OK, såg din hand först.
Kom upp.
Okej.
Så jag tror att det är Steven.
Kom upp.
Okej.
>> Men antag nu vi spola tillbaka till den ursprungliga tillståndet i världen där jag
har precis förklarat en stapel, och det är kommer att vara av kapaciteten tre.
Men storleken har ännu inte bestämts.
Brickor har ännu inte fastställts.
Så ett par frågor först.
Och låt mig ge dig mikrofonen så att du kan delta mer aktivt i detta.
>> Så vad är inne i storlek i denna stund i tid om allt jag har gjort är
förklarade en bunt med en rad kod?
>> STEVEN: Inte mycket.
>> DAVID MALAN: OK, inte mycket.
Vet vi vad som finns inne i storlek, vet vi vad som finns inuti
av denna array här?
>> STEVEN: Bara slumpvis kod, eller hur?
Just -
>> DAVID MALAN: Ja, jag ska kalla det kod, men random -
>> STEVEN: Saker.
>> DAVID MALAN: Saker som slumpvis
>> STEVEN: Bits.
>> DAVID MALAN: Bits, rätt?
Så sopor värden, rätt?
Så permutationer av 0 s och 1 s.
Rester av tidigare användningar av detta minne.
Och vi vet inte riktigt vad de värden är, så vi drar oftast dem
som frågetecken.
>> Så det första vi förmodligen kommer att vilja göra här -
och låt mig ge detta fält inuti av det ett namn - brickor.
Vad ska vi initiera förmodligen storlek att om vi vill
börja använda denna stack?
>> STEVEN: Tray är sub 3.
>> DAVID MALAN: Så, OK.
För att vara tydlig, är kapaciteten förklaras håll som tre.
Och det är vad jag har använt att allokera arrayen.
Storlek kommer att hänvisa till hur många brickor finns för närvarande på stacken.
>> STEVEN: Zero.
>> DAVID MALAN: Så det borde vara noll.
Så sätt igång, och varje finger, rita en nolla i storlek.
Okej.
Så nu, vad som finns inuti denna här, vet vi inte.
Dessa är egentligen bara skräp värden.
Så kunde vi rita frågetecken, men Låt oss hålla styrelsen ren för nu
eftersom det inte spelar någon roll vad som finns där.
Vi behöver inte initiera arrayen till någonting, för om vi vet att
storleken på stapeln är noll, väl, vi bör inte titta på någonting i
denna array ändå på denna tidpunkt.
>> Så nu antar att jag trycker på nummer 9 på stacken.
Hur ska vi uppdaterar datastrukturen insidan av denna svarta låda?
Vilka värden behöver ändra?
>> STEVEN: Inom -
storleken?
>> DAVID MALAN: OK.
Storleken ska bli vad?
>> STEVEN: Storlek skulle vara en.
>> DAVID MALAN: OK.
Så storlek ska bli en.
Så du kan göra detta på ett par olika sätt.
Låt mig ge er, nu din fingret är ett radergummi.
Okej.
Då nu fingret är en borste.
Okej.
Och nu vad måste förändras, självklart, i datastrukturen?
>> STEVEN: Vi kommer från botten upp till 9.
>> DAVID MALAN: 9.
OK, bra.
Så fortfarande ingen roll vad som finns på plats en eller två eftersom de är
sopor värden, men vi ska inte bry ser det eftersom storleken är
säger oss att bara det första elementet är faktiskt legitimt.
Så nu jag skjuta 17 på listan.
Vad händer med den här bilden?
>> STEVEN: Så storlek kommer att gå till två.
>> DAVID MALAN: OK.
Du är suddgummi -
oops.
Du är ett suddgummi.
>> STEVEN: Eraser.
>> DAVID MALAN: Du är en borste.
>> STEVEN: Brush.
>> DAVID MALAN: OK.
Och vad mer?
>> STEVEN: Och sedan vi -
>> DAVID MALAN: Vi sköt 17.
>> STEVEN: Vi håller 17 på topp, så -
>> DAVID MALAN: OK, bra.
>> STEVEN: - släpp ner den.
>> DAVID MALAN: Okej.
Det blir lätt.
Jag tänker inte hjälpa dig den här gången.
Push 22.
>> STEVEN: Klar.
Att bli ett suddgummi.
Jag blir en borste.
Och då är jag sätta 22.
>> DAVID MALAN: 22.
Utmärkt.
Så en gång till.
Jag kommer nu att driva på stacken 26.
>> STEVEN: Ooh.
Oh gosh.
Du fångade mig verkligen off guard.
>> DAVID MALAN: Du gjorde inte se detta komma?
>> STEVEN: Jag såg inte detta komma.
Kan vi åter initial kapacitet?
>> DAVID MALAN: Det är en bra fråga.
Så vi har typ av målat oss i ett hörn här.
Det finns egentligen inget bra ut för Steven eftersom vi har tilldelats denna array
statiskt, så att säga, inuti av datastruktur.
Och vi har väsentligen hårdkodade att det är av storlek tre.
Så vi kan inte riktigt omfördela dem.
>> Vi kunde om vi gick tillbaka, vi omdefinierade facken att vara en pekare som
Vi använder sedan malloc till hands minne.
För om vi fick minnet från högen via malloc, vi
kunde därefter frigöra den.
Men innan befria det, kan vi omfördela en större bit av minnet,
uppdatera pekaren, och så vidare.
Men för nu, är detta verkligen det bästa vi kan göra.
Push och pop är förmodligen kommer att behöva signalera något fel.
>> Så till exempel, vårt genomförande push kunde återvända en bool som
tidigare returneras true, true, true.
Men den fjärde gången, det kommer att ha att returnera false, till exempel.
Okej.
Mycket bra gjort.
Grattis.
Du har förtjänat din stress boll idag.
>> [Applåder]
>> STEVEN: Tack.
>> DAVID MALAN: Tack.
OK, så detta verkar vara inte mycket ett steg framåt, eller hur?
Vi beskrev denna datastruktur.
Det har varit spännande, eller hur?
Operativsystem gillar det.
Tydligen webben kan utnyttja detta, och andra program fortfarande.
Men vad en dum begränsning som vi är tillbaka till typ av vecka två gränser
där vi har fast storlek matriser.
>> Så det finns faktiskt ett par hur vi skulle kunna lösa detta.
Vi kunde dynamiskt allokera arrayen, inte genom hårt kodning det som jag har
gjort här, utan i stället på nytt förklara detta, att bara vara tydlig, eftersom
ungefär så här.
Int * brickor, inte besluta på en kapacitet än.
Men när jag förklarar stapeln på annat håll i min kod, kan jag ringa då malloc,
få adressen till en bit av minne, och jag kunde ge
den adressen till brickor.
>> Och sedan, eftersom det är bara en bit av minne, skulle jag fortsätta att använda torget
hakparenteser på vanligt sätt.
Eftersom igen, det är typ av detta funktionell ekvivalent av matriser och
bitar av minne som kommer tillbaka från malloc.
Vi kan behandla en som de andra hjälp pekararitmetik eller
klammer notation.
Så det är en strategi.
>> Men hur annars kan vi genomföra detta samma datastruktur, potentiellt?
Rätt?
Jag tycker vi just löst detta problem som för en vecka sedan.
Vad var lösningen på detta problem att Steven sprang in?
Så länkade listor, höger.
>> Om problemet är att vi målar in oss i ett hörn genom att allokera
i förväg för lite minne som vi därefter har att på något sätt ta itu med, väl,
varför inte bara undvika att emittera sammanlagt?
Varför inte bara förklara brickor för att vara en pekare till en nod, ergo en länkad lista,
och sedan helt enkelt tilldela nya noder varje gång Steven behövs för att passa en
nummer i datastrukturen.
>> Så bilden måste förändras.
Det kommer inte att vara så rena och som enkelt som att bara en samling av tre ints.
Nu kommer det att vara en pekare till en struct, och att struct kommer att
har en int och en nästa pekare.
Det kommer att leda via denna pekare till en annan sådan struct till
en annan sådan strukt.
Så bilden skulle faktiskt få lite stökigare.
Och vi skulle ha pilar knyta allt tillsammans.
>> Men det är bra, rätt, eftersom Vi har sett hur man gör detta.
Och när du får bekväm genomföra något som en länkad
listan, vilket du måste göra om du välja att genomföra en hash-tabell med
separat kedja för p-set 6, kan du använda den som en byggsten, eller
ingrediens, eller i Scratch tala, en förfarande, något som du lägger, du
skapat en egen pusselbit som du sedan kan återanvända.
Så kompromisser, men potentiella lösningar att vi har faktiskt sett förut.
>> Så ganska ofta, ser du detta varje år eller två när Apple släpper
något nytt, och alla galna människor line up utanför Apple
butik för att köpa deras marginella uppgradera på hårdvara.
Jag säger detta, det är OK, eftersom Jag är en av dem.
Så vilken typ av datastruktur kan representera denna verklighet?
>> Nåväl, låt oss kalla det en kö, en linje.
Så britterna skulle kalla det normalt en kö ändå, så det är ett fint namn.
Och de två operationer som en kö ska stödja vi kallar en enqueue
drift och en dequeue operation, som är liknande i
ande att driva och pop.
Det är bara typ av annorlunda i konvention, vad vi kallar dem.
Men att köa något sätt att lägga eller sätt den till datastruktur.
Att avköa innebär att ta bort den.
Men medan en stapel var en LIFO uppgifter struktur, är en kö en först in-
först ut-datastruktur.
>> Om du är den första personen i raden, du kommer att vara den första personen att få
ut ur linjen och köpa din nya enhet.
Föreställ dig hur upprörd dessa människor skulle vara Om Apple istället använde en stapel för
Exempelvis, för att genomföra plockning upp på din nya leksak.
Så köer vettigt, förvisso, och Vi kan tänka på alla möjliga
applikationer, förmodligen, för köer, speciellt när du vill ha rättvisa.
Så hur kan vi genomföra dessa som en datastruktur?
>> Tja, föreslår jag att vi kanske behöver göra det här sättet.
Så jag ska nu ha siffror.
Så vi ska hålla det enkelt och inte nödvändigtvis tala i termer av brickor.
Bara siffror som folk fått.
Kapaciteten kommer att, återigen, fixera totala antalet personer som kan vara i
denna linje, som tre eller vad annat värde.
>> Men jag föreslår att jag måste hålla koll inte bara av storleken på
kö, hur många saker är i det.
Så storleken är den nuvarande storlek, kapacitet är den maximala storleken.
Bara igen, nomenklatur enligt praxis.
Varför behöver jag en extra int inne av en kö för att hålla reda på vem som är i
framsidan av linjen?
Varför behöver jag göra det i det här fallet?
>> Nå, hur är detta bilden kommer att förändras?
Jag kan nog återanvända mest av denna bild.
Låt mig gå vidare och radera det som finns här.
Vi ska ge detta en något annat namn här uppe.
Låt oss bli av med 17, låt oss bli av 9, låt oss bli av med 3.
Och låt oss lägga en annan sak.
Jag föreslår att jag måste hålla reda på framsidan av listan, som just
kommer att vara en int liksom.
Och vi kommer att hålla det enkelt.
Ingen länkad lista för nu.
>> Vi ska erkänna att vi ska stöta upp mot denna gräns.
Men vad jag vill se hända den här gången?
Så antar jag gå vidare och den första personen kommer upp i linje, och
det är nummer 9.
Vi har stress bollar.
Kan jag stjäla, säg, två eller tre personer?
Ett, två, tre?
Kom upp.
Höger framifrån, eftersom Vi ska göra det här snabbt.
>> Var och en av er kommer nu att vara en fläkt pojke i rad vid Apple.
Du kommer inte att ta emot Apple-maskinvara i slutet av detta dock.
Okej.
Så du är nummer 9, är du nummer 17, nummer 22.
Dessa är godtyckliga tal, liksom student-ID eller whatnot.
Och på bara ett ögonblick, låt oss börja att börja lägga till saker.
Och jag ska köra styrelsen här den här gången.
>> Så i det här fallet har jag initieras fronten för att vara -
Jag faktiskt inte riktigt bryr sig om vad front är, eftersom storleken är noll.
Så det här kan lika gärna vara ett frågetecken.
Dessa är alla frågetecken.
Så nu ska vi börja att faktiskt se några folk köar i butiken.
>> Så om nummer 9, är du den första där kl 5, gå vidare och rada upp,
eller kvällen innan.
OK.
Så nu 9 är här.
Så 9 är på framsidan av listan.
Så jag kommer att gå vidare och uppdatera storleken på denna aktuella data
struktur för att inte vara 0 anymore, men för att vara 1.
Jag kommer att sätta 9 vid framsidan av listan.
Låt mig gå vidare och växla skärmen så att vi kan se förbi oss här.
>> Och nu vad vill jag att sätta på framsidan?
Jag kommer att hålla koll på att fram i kön just nu
är i position 0.
För vad är nästa kommer att hända?
Tja, antar jag nu köa 17 liksom.
Så hoppa i linje där.
Och vidare den typ av dörren till Butiken kommer att vara här.
Så nu har jag lagt 17.
Och även om dessa killar blockerar skärmen, det är OK,
eftersom vi kan se det här uppe.
Ursäkta.
>> Publik: Vi kan flytta -
>> DAVID MALAN: Nej, det är OK.
Det är enormt där uppe.
Så 17 är nu inne i kön.
Jag behöver uppdatera vilka fält nu dock?
OK, definitivt storlek.
Och vad sägs om fronten?
OK, ingen.
Fram bör inte förändras, eftersom till skillnad från en stapel, vi
vill upprätthålla rättvisa.
Så om 9 kom i första, vill vi 9 att vara den första av linjen
och in i affären.
>> I själva verket, låt oss se det.
Innan vi sätter 22, låt oss gå vidare och dequeue 9.
Vad är ditt namn igen?
>> Publiken: Jake.
>> DAVID MALAN: Jake går att ur kön nu.
Så du får gå in i butiken.
Och låtsas att butiken är borta.
Så nu vad som behöver - dit-dit-dit!
Vad måste hända nu?
Design beslut.
Så inte en dålig instinkt, men - vad heter du nu igen?
>> Publiken: David.
>> DAVID MALAN: David.
Så vad gjorde David göra?
Han försökte att sortera fastställa vilka uppgifter struktur och flytta från sin plats
i Jakes tidigare platsen.
Och det är bra om vi är villiga att acceptera det som en
implementeringsdetalj.
Men först, låt oss uppdatera data struktur innan vi gör det.
Eftersom jag inte gillar tanken på allt folket skiftar i denna linje.
>> Det är ingen stor sak om David gör det med ett steg, men igen, tänker tillbaka på
när vi har haft åtta volontärer på skede och vi har gjort liknande insättning
Sortera, där vi var tvungna att börja flytta alla runt omkring.
Det blev dyrt, eller hur?
Det gör mig hukar om Big O n, kvadrat stort O n igen.
Det är inte känslan som ett perfekt resultat.
>> Så låt oss bara uppdatera denna.
Så storleken på kön är inte längre två.
Det är nu bara 1.
Men jag kan nu uppdatera något Jag har inte uppdaterat tidigare,
framsidan av listan.
Jag kunde bara säga, är den platsen 1?
Så nu har vi skräp värde här, Garbage värde här, och David i
mitten av detta skräp.
Men den datastruktur är fortfarande intakt.
>> Och i själva verket har jag inte ens behöver ändra Jake tidigare nummer
9, för vem bryr sig.
Jag har tillräckligt med information nu i storlek som jag vet att det finns en person i
denna kö.
Och jag vet att den personen är på plats 1, inte 0.
Jag räknar inte.
Så 1 liksom.
Så den datastruktur är fortfarande OK.
>> Tja, vad händer härnäst?
Låt oss enqueue -
vad är ditt namn?
>> Publiken: Callen.
>> DAVID MALAN: Callen.
Låt oss köa en Callen, och 22 är nu i kön.
Så nu vad som måste förändras här?
Fram kommer inte att ändra, uppenbarligen.
Storlek kommer att förändras för att vara 2 igen.
Och 22 slutar här, är 9 kvar, men det är effektivt en
Garbage värde nu.
Det är bara en kvarleva av Jake förflutna.
>> Så nu vad som händer om Jag avköa David?
En sista operationen, dequeue David.
Vi kunde skifta, men jag föreslår låt oss göra så lite arbete som möjligt.
Nu är min datastruktur går bak i storlek från 2 till 1.
Men fram i kön nu blir 2.
Jag behöver inte ändra dessa siffror ännu, eftersom de är
bara skräp värden.
>> Men nu vad händer?
Anta att jag köa mig själv, 26?
Jag känner att jag hör hemma här.
Så jag blir kö.
Så jag slags hör hemma här.
Och även om du inte riktigt uppskatta detta visuellt på scenen,
eftersom vi har gott om utrymme, skulle jag inte stå här, varför?
>> Publik: Du är out of bounds.
>> DAVID MALAN: Höger.
Jag är out of bounds.
Jag har indexerat bortom gränserna för denna grupp.
Jag borde verkligen vara i en av de tre möjliga lägen.
Nu, var är mest naturligt att gå?
Jag föreslår att vi belånade en vecka ett trick.
Det mod operatör, procent.
Eftersom jag tekniskt står vid Plats 3, men jag gör 3 mod kapacitet,
så 3, ett procenttecken, 3 -
kapacitet är 3.
Vad är det?
Vad är resten då du dela upp 3 av 3?
0.
>> Så det sätter mig var Jake var, som är faktiskt bra.
Så nu genomförandet av denna sak kommer att
vara lite av en huvudvärk.
Det är egentligen bara en rad av huvudvärk, av koden.
Men åtminstone nu finns sopor värde här, men det finns två
legitima ints här.
Och jag hävdar att vi nu har gjort precis vad vi behöver göra, så länge
vi ändrar vad Jakes Värdet var att vara 26.
>> Vi har nu tillräckligt med information fortfarande att bibehålla integriteten
av denna datastruktur.
Vi är fortfarande lite av lycka när vi vill infoga fyra eller fler totalt
element, men jag kan åtminstone göra ganska effektiv användning av denna konstant
tid, faktiskt.
Jag behöver inte oroa sig för att flytta alla, som Davids lutning var.
>> Eventuella frågor om stackar, eller denna kö?
>> Publik: Är anledningen du behöver storlek så att du vet
var att ha en person?
>> DAVID MALAN: Exakt.
Jag behöver veta storleken på arrayen eftersom jag vill veta exakt hur
många av dessa värden är legitima, och så att jag kan hitta var att sätta
nästa person.
Exakt.
Storleken är -
faktiskt, vi uppdaterar inte här ännu.
Jag la mig vid 26.
Storleken är nu, inte en, utan två.
Så nu detta hjälper faktiskt mig att hitta av listan, vilket inte är 0, inte
1, men är 2.
Framsidan av listan är verkligen nummer 22.
Eftersom han kom in först, så han borde släppas in i butiken innan mig,
trots att visuellt står jag närmare till butiken.
>> Okej?
En applåd för killarna och vi låter dem därifrån.
>> [Applåder]
>> DAVID MALAN: jag kunde låta du håller facket.
Vi kunde se vad som händer om du vill, men kanske inte.
Okej.
Så vad händer nu lämnar det oss?
Nåväl, låt mig föreslå att det finns en några andra datastrukturer vi kunde
börja lägga till vår verktygslåda som kommer faktiskt vara ganska, ganska relevant som
Vi dyker in web grejer.
Som återigen, har någon form av anslutning till träd i form av
något som kallas DOM, dokument objektmodellen.
Men vi får se mer av att innan lång.
>> Låt mig föreslå definitionally att vi ringa träd nu vad ni kanske vet så
mer av ett släktträd, där du har någon förfader på
rötterna på trädet.
En patriarkalisk eller en matriark på högst upp i trädet.
Utan sin make, i det här fallet.
Men vi har nu vad vi kallar barn, vilka är noder som hänger
utanför den vänstra underordnade eller högra underordnade behandlingselementet, pilar som avbildas här.
>> Med andra ord, i en träddatastruktur i datorn, har ett träd noll
eller fler noder.
Om den har åtminstone en nod, som kallas roten.
Det är de saker visuellt att vi drar på toppen.
Och den noden, som alla andra noder, kan ha noll, en eller två, eller tre,
eller hur många barn de datastruktur stöder.
I detta fall, roten, lagra värdet ett, har två barn, 2 och 3,
så vi kallar generellt 2 vänster barn och 3 rätt barnet.
>> Och sedan när vi kommer ner till 5, 6, och 7, 6 skulle kunna kallas mitt barn.
Om du har fyra barn, det blir förvirrande.
Så vi slutar använda denna typ av genvägen verbalt.
Men det är egentligen bara ett släktträd.
Och bladen här är de noder som själva har inga barn.
De hänger ut längst ned i trädet.
>> Så hur kan vi implementera ett träd som har bara två barn maximalt?
Vi kallar det ett binärt träd.
Bi betyder återigen två, i detta fall, som med binär.
Och så den kan ha noll, en, eller två barn maximalt.
>> Jag föreslår att vi genomför noden för denna struktur med en int n,
och därefter två pekare, som kallas en vänster, en som heter rätt.
Men de är bara trevligt godtyckliga konventioner.
Och vad är bra nu, speciellt om du slags kämpade konceptuellt med
rekursion, eller trodde att det inte var verkligen en lösning på någonting,
speciellt om du kunde slut på minne.
Nu när vi pratar om uppgifter strukturer och algoritmer som gör det möjligt
oss att korsa och manipulera dem, visar sig att rekursion kommer tillbaka i
en mycket mer övertygande om inte vackert sätt.
>> Så här jag föreslår är att genomföra av en sökfunktion.
Givet två ingångar -
så se det som en svart låda.
Givet två ingångar, n, en int, och en pekare till ett träd, en pekare till en
nod, eller egentligen roten av ett träd, jag hävdar att denna funktion kan återvända
sant eller falskt, det värde n är inne i det här trädet.
>> Vad finns inuti denna svarta låda?
Tja, fyra grenar.
Den första bara kollar.
Om trädet är null, bara returnera false.
Om det inte finns någon nod, det finns ingen n, det finns inget nummer, bara returnera false.
Om dock, n, värdet du söker för, är mindre än träd arrow N, och
bara för att vara tydlig, vad betyder det när Jag skriver trädet och sedan pilen
notation, n?
Exakt.
Det betyder avreferera att pekare kallas träd.
Gå dit, och sedan komma in i det nod och få sitt område kallas n.
Och sedan jämföra den faktiska n som var passerat in Sök mot den.
>> Så om n är mindre än, värdet n i trädet noden själv, ja,
vad betyder det?
Det betyder ingenting vid första anblicken.
Rätt?
Precis som när du har en samling av värden, kanske du vill använda binära
söka som en form av klyftan och erövra.
Men vad antagandet behövde vi göra för binär sökning till fungerar alls
i telefonboken och tidigare exempel?
>> Hur ska sorteras.
Så låt oss förfina definitionen av trädet här inte bara vara ett träd, vilket kan
ha valfritt antal barn.
Inte bara ett binärt träd, vilket kan har 0, 1, eller 2 maximalt.
Men som ett binärt sökträd, eller BST, vilket är bara ett finare sätt att säga en
binärt träd, så att varje nods vänstra barnet, om sådan finns, är
mindre än noden.
Och varje nods högra barn, om den är närvarande, är större
än själva noden.
>> Så med andra ord, om du skulle rita trädet ut, alla nummer är
omsorgsfullt balanseras så här så att om du har 55 som root, kan 33 gå
till vänster eftersom det är mindre än 55.
77 kan gå till sin rätt eftersom det är större än 55.
Men nu märker, samma definition, det är en rekursiv definition verbalt,
måste ansöka om 33.
33 vänstra barnet måste vara mindre än det, och 33 rätt barn, 44, måste vara
större än den.
>> Så detta är ett binärt sökträd, och Jag föreslår, med hjälp av en liten bit av
rekursion, kan vi nu hitta n.
Så om n är mindre än värdet n som är aktuella noden, jag ska gå
framåt och punt, så att säga, och bara tillbaka vad svaret är på
söka för n på trädets vänstra barn.
Lägg märke igen, denna funktion bara förväntar sig en nod stjärna, en
pekare till en nod.
Så väl jag bara kan göra träd pil vänster, vilket kommer att leda
mig till en annan nod.
Men vad är denna nod?
>> Tja, enligt denna förklaring, vänster är bara en pekare, så att bara
betyder att jag går till sökfunktionen en annan pekare, nämligen
den som representerar min vänstra barns träd.
Så i detta fall, pekaren till 33, om Detta är vårt urval ingång tiden, om
n är större än värdet n vid aktuella noden i trädet, då är jag
kommer att gå vidare och punt i andra riktning och bara säga, gör jag inte
vet om detta värde n är i trädet, men jag vet om det är, det är ner min
högra grenen, så att säga.
Så låt mig rekursivt ringa Sök, passerar en n igen, men passerar i en
pekare till min högra barn.
>> Med andra ord, om jag är närvarande vid 55 och jag letar efter 99, jag vet att 99
är större än 55, så precis som jag slet telefonboksinställningar veckor sedan och vi
gick rätt, på samma sätt är vi kommer att gå här.
Och jag vet inte om det är på min högra barn, och det är inte, är 77 där, men
Jag vet att det är i den riktningen.
Så jag kallar sökning på min högra barn, 77, och låt sökning figur ut från
där om 99 i denna godtyckliga exempel är faktiskt där.
>> Else, vad är det slutliga målet?
Om trädet är null är ett fall.
Om n är mindre än den aktuella nodens värde är ett annat fall.
Om n är större än den aktuella nodens värde är ett tredje fall.
Vad är den fjärde och sista målet?
Jag tror att vi är ute på ärenden, eller hur?
Det måste vara att n är i nuvarande nod som jag är på.
>> Så om jag söker efter 55 på denna punkt i berättelsen, den gren av
träd skulle återvända sant.
Så vad är intressant här är att vi faktiskt, till skillnad veckor tidigare, typ vi
av har två basfallen.
Och de behöver inte vara allt på toppen.
Toppen är ett basfall för om träd är null, det finns inget att göra.
Bara returnera en hård kodad värdet false.
>> Den nedersta grenen är typ av standard, vilket om vi har kontrollerat för
null, har vi kontrollerat om det skulle vara kvar, men det borde inte vara, har vi
kontrolleras om det skulle vara rätt, men det inte bör vara, tydligt att det måste vara
precis där vi är.
Det är ett basfall.
Så det finns två rekursiva fall inklämt där i mitten.
Men jag kunde ha skrivit detta i valfri ordning.
Jag tyckte bara det kändes slags naturlig att först kontrollera om ett eventuellt fel,
så kolla vänster, så kolla till höger, sedan antar att du är på noden
du är faktiskt ute efter.
>> Så varför skulle detta vara användbart?
Så visar det sig -
och låt mig hoppa till en teaser här som är i nätet.
Vi kommer att börja använda inte en programmeringsspråk vid första, men en
märkningsspråk.
Ett märkspråk är en som är i samma anda som programmering
språk, men det ger inte dig förmåga att uttrycka dig logiskt.
Det ger bara dig möjlighet att uttrycka dig strukturellt.
>> Vart vill du sätta något på sidan, på webbsidan?
Vilken färg vill du göra det?
Vilken textstorlek vill du göra det?
Vilka ord vill du verkligen vill på webbsidan?
Så det är ett märkspråk.
Men sedan kommer vi mycket snabbt införa JavaScript, vilket är en fullfjädrad
programmeringsspråk.
Mycket lik syntaktiskt i utseende till C, men det tar lite
trevligt, mer kraftfull, mer användarvänliga funktioner.
>> Och en av de frustrationer på detta punkt i terminen är att vi ska
snart genomföra speller i betydligt färre rader kod som använder andra språk
än C själv medger, men för förnuftets Vi kommer snart att förstå.
Detta kommer att bli den första webbsidan.
Det kommer att vara helt underwhelming, det första vi gör.
Det kommer helt enkelt att säga, hej världen.
Men om du aldrig har sett den tidigare, är denna HTML,
HyperText Markup Language.
>> Om du går till en viss menyalternativ i mest alla webbläsare, på en webbsida på
Internet, kan du se HTML att vissa människor skrev till
skapa den webbsidan.
Och det är förmodligen inte ser så kort eller så snyggt som det här.
Men det kommer att följa mönstret i dessa öppna fästen och snedstreck och
bokstäver och potentiellt siffror.
>> Jag trodde jag skulle ge dig en teaser av vad du kommer att kunna göra
efter att ha tagit CS50.
Låt mig gå till cs.harvard.edu / rob, vår egen Rob Bowden hemsida.
Han gjorde detta för oss.
Så du kommer snart att kunna göra det.
Och dessutom, vad du hört i morse -
vad du hörde i morse -
>> [HAMSTER Dansmusik]
>> - Du ska kunna göra detta.
Som väntar oss på onsdag.
Vi kommer att se dig då.
>> [HAMSTER Dansmusik]
DAVID MALAN: Vid nästa CS50 -