DAVID MALAN: All right. Velkommen tilbake til CS50. Dette er starten på uke 8. Og husker at oppgavesettet fem endte med litt av en utfordring. Så forutsatt at du gjenopprettet alle dine undervisning Fellows og CAs fotografier i card.raw fil, er du kvalifisert til nå finne alle disse menneskene, og en heldig vinner vil gå hjem med en av disse tingene, spranget bevegelse enhet som du kan bruke for endelig prosjekter, for eksempel. 

Dette, hvert år, fører til litt av creepiness. Og så det jeg trodde jeg ville gjøre er å dele med deg noen av notatene som har gått frem og tilbake over de ansatte liste over sent. For eksempel, bare i går kveld, sitat unquote, fra en av de ansatte medlemmer, "Jeg hadde bare en student knock på døren min for å ta et bilde med meg. Stalkers, sier jeg deg. "Begynte ganske beskrivende og da vi flyttet på, en time eller så senere: «Jeg hadde en student venter på meg etter avsnitt og han hadde alle våre navn og bilder på noen ark. "All right. Så organisert, men ikke alt det skumle ennå. 

Da, "jeg var ute av byen denne helgen, og da jeg kom tilbake, var det en i min soverom. "[Latter] DAVID MALAN: Neste sitat fra en stab medlem ", en student kom til huset mitt på Somerville på 4 AM i morges. "Next ansatte, "Jeg kom til hotellet mitt i San Francisco og en student var ventet på meg i lobbyen med tre speilreflekskameraer. " Type kamera. "Jeg er ikke engang i staben dette semesteret, men en student brøt seg inn i huset mitt denne morgen og spilte inn hele greia med Google Glass. "Og så til slutt, "Minst 12 mennesker var ivrig venter for meg da jeg kom ut av min limo, og da jeg våknet. "All right. Så blant bildene, som du kan husker, er denne karen her, som du kanskje kjenner som Milo Banana, som bor med Lauren Carvalho, vårt hode undervisning Fellow. Milo, Milo, kom hit gutt. Milo. Milo. Mind du, han iført Google Glass, så Vi skal vise deg alt dette etter. Så dette er Milo hvis du ønsker å ta et bilde med ham etterpå. Hvis du ønsker å se ut på publikum der. OK. Det er bra opptakene. Vel, Milo Banana. Oh, ikke gjør det. 

[Latter] 

OK. Så et ord da på hva som ligger foran, fordi når vi begynner å gå over, denne uke spesifikt, fra C i en kommandolinje miljø til PHP og JavaScript og SQL og HTML og CSS i en web-basert miljø, vil vi være utstyre deg med all den mer kunnskap for potensielle endelige prosjekter. Mot dette målet, har banen et tradisjon for å holde seminarer som er på tangentiale emner til kurset. Veldig mye relatert til programmering og til app utvikling og så videre, men ikke nødvendigvis utforsket av kursets egen pensum. 

Så hvis du kan være interessert i en eller flere av årets seminarer, registrer deg på cs50.net/seminar. Det er eldre seminarer på cs50.net/seminars. Og på vaktliste så langt i år er Amazing Web Apps med Ruby on Rails, som er et alternativ språk til PHP. Datalingvistikk. Innføring i iOS, som er plattform som brukes for iPhone og iPad utvikling. JavaScript for Web Apps, vil vi dekke det, men i dette seminaret vil du gå i mer detalj. 

Leap Motion, så vi vil faktisk ha noen av våre venner fra Leap Motion, selskapet selv, bli med oss. I morgen, faktisk, for å gi en hands-on seminar, hvis av interesse for deg. Meteor.js, en alternativ teknikk for bruker JavaScript ikke i en nettleser, men på en server. Node.js, som er veldig mye Av den grunn også. Slank Android Design. Android er et svært populært alternativ til iOS og Windows Phone og andre mobile plattformer. Og Web Security Active Defense. 

Så faktisk, hvis du ønsker å engasjere seg i dette, la meg gjøre oppmerksom på dette. Vi er veldig glad for å si at våre venner på Leap Motion, som er en oppstart - denne enheten egentlig bare kom ut for noen måneder siden - har velvillig donert 30 slike enheter til klassen for så mange studenter, hvis du ønsker å låne maskinvaren mot semesters slutt og bruke den til en faktisk endelige prosjektet. De støtter en rekke språk. Ingen av dem C, ingen av dem PHP, så realisere ett eller flere av disse seminarene kan vise interesse. Og alle av dem vil bli filmet i tilfelle at du ikke er i stand å møte personlig. Planen bli annonsert via e-post som vi stivne rom. 

Og til slutt, hvis du går til projects.cs.50.net, er dette en nettside vi opprettholder hvert år at vi inviterer folk fra lokalsamfunnet, fakultet, avdelinger, ansatte og begge i en utenfor av CS50 til foreslå prosjektideer. Ting av interesse for studentgrupper. Ting av interesse for avdelinger. Så snur det hvis du sliter med usikkerhet med hensyn til hva du selv ønsker å takle. 

Så sist gang vi innførte en kanskje mer kompleks datastruktur enn vi hadde sett i uker tidligere. Vi hadde brukt matriser pen lykkelig som en nyttig hvis forenklede datastruktur. Da vi innførte disse, som selvfølgelig er knyttet lister. Og hva var en av motivasjonene for innføre dette datastruktur? Yeah? Hva er det? 

PUBLIKUM: Dynamisk størrelse. 

DAVID MALAN: Dynamisk størrelse. Så mens i array, må du vet størrelsen på forhånd når du fordele den. I lenket liste, trenger du ikke må vite det. Du kan bare malloc, eller mer generelt, bevilge ytterligere node, så å si, når du vil sette inn flere data. Og node har ingen forhåndsbestemt mening. Det er bare en fellesbetegnelse som beskriver en slags beholder som vi er ved hjelp av i vår datastruktur for å lagre enkelte element av interesse, som i denne tilfelle skje for å være heltall. 

Men det er alltid en avveining. Så vi får dynamiske størrelser av data struktur, men hvilken pris vi betaler? Hva er ulempen med koblede lister? Yeah? 

PUBLIKUM: Krever mer minne. 

DAVID MALAN: Det krever mer minne, hvordan akkurat? 

PUBLIKUM: [uhørlig]. 

DAVID MALAN: Nettopp. Så nå har vi pekere tar opp ekstra minne som vi tidligere trenger ikke, fordi den fordel av en matrise, er selvfølgelig at alt er sammenhengende, tilbake til tilbake til ryggen, som gir deg direkte tilgang. Fordi bare ved å bruke hakeparentes notasjon, eller mer teknisk pekeren aritmetikk, veldig enkel addisjon, kan du få tilgang til alle elementer i konstant tid. Og faktisk, er den slags antyde en annen pris som vi betaler med en lenket liste. 

Hva skjer med kjøretiden noe som Søk, hvis jeg vil finne noen verdi og inne av en lenket liste? Hva min kjøretid bli? Big O n. Hvis det er sortert til? Hva om datastruktur er sortert? Kan jeg gjøre det bedre enn store O av n for å søke? Nei, fordi i verste fall kan det meget vel være sortert, men antallet du leter etter kan være stor. Det kan være det nummer 100, hvilken kan skje for å være alt den måte på slutten. Og fordi du bare kan få tilgang til en koblet listen i denne implementeringen ved måte av sin første noden, er du fortsatt slags ute av lykken. Du må bla gjennom hele greia fra først til sist for å finne den store verdien som 100. Eller for å fastslå om det er ikke engang der. 

Så vi kan ikke gjøre hva algoritmen i en data struktur som ser ut som dette? Vi kan ikke gjøre binære søk, fordi binære søk krevde at vi hadde random access. Vi kunne bare hoppe fra sted til sted uten å måtte følge disse brødsmuler i form av alle disse pekerne. 

Nå, hvordan vi gjennomføre dette? Vel, hvis vi går til skjermen her, hvis Vi kan raskt reimplement disse dataene struktur - min håndskrift er ikke alle som flott her, men vi skal prøve. Så typedef struct, og hva gjorde jeg ønsker å kalle denne tingen her oppe? Node. Så jeg skal få oss i gang. Og nå, hva må være inne i datastrukturen for det enkeltvis lenket liste? Hvor mange felt? 

Så to. Er ganske enkelt. Så int n. Og vi kan kalle n noe vi ønsker, men det bør være en int hvis vi er implementere en lenket liste for ints. Og nå hva gjør andre Feltet må være? Struct node *. Så hvis jeg gjør struct node *, og da jeg kan kalle dette også hva jeg vil, men bare for å være klart jeg ringer det neste, som vi har gjort. Og så skal jeg lukke mine klammeparentes. 

Og nå, som sist, Jeg satte node ned her. Men hvis jeg erklære dette er som en node, hvorfor jeg gidder å være så ordrik her i å erklære struct node * ved siden av, i motsetning å bare node * neste? Yeah? 

PUBLIKUM: [uhørlig]. 

DAVID MALAN: Nettopp. Nettopp. Fordi C virkelig tar deg bokstavelig og bare ser definisjonen av node helt ned her, kan du ikke referere til det her oppe. Så vi har denne typen preemptive erklæring her, som er riktignok mer ordrik. Struct node, som betyr Vi kan nå få tilgang til det innsiden av datastrukturen. 

Og som en side, fordi dette er bli litt mer subjektiv nå, stjernen kan teknisk gå her, det kan gå her, kan det selv gå i midten. Vi har vedtatt, i stilen guide for kurset, konvensjonen om å sette stjernen rett ved siden av data type, som i dette tilfellet ville være struct node. Men innser i en rekke lærebøker og online referanser, kanskje du faktisk ser det på den andre siden. Men bare innse at begge faktisk vil fungere, og du bør rett og slett være konsekvent. 

OK. Så det var vår erklæring av struct node. Men da vi begynte å gjøre mer sofistikerte ting. For eksempel, har vi besluttet å innføre noe som en hash table. Så her er en hash table av størrelse n, indeksert fra 0 øverst til venstre for å n minus 1 på bunnen igjen. Dette kan være en hash tabell for noe. Men hva slags ting vi snakke om å bruke en hash tabell for? Lagring av hva? 

Navn. Vi kunne gjøre navn som vi gjorde forrige gang. Og egentlig, kan du lagre noe. Og vi vil se dette igjen i PHP og JavaScript. En hash table er en fin form for Swiss Army kniv som lar deg lagre ganske mye hva du vil innsiden av det ved å knytte taster med verdier. Taster med verdier. 

Nå i denne enkle saken, vår tastene er bare tall. Vi implementere en hash tabell som en matrise. Og så tastene er 0, 1, 2 og så videre. Og så vi, som mennesker, besluttet sist uke at du vet hva, hvis vi er kommer til å lagre navn, la oss bare vilkårlig, men ganske rimelig, anta at Alice, en A navn, vil bare bli indeksert i 0. Og Bob, en B navn, vil bli indeksert inn i en, og så videre. Så vi hadde en mapping mellom innganger, som er strenger, og hash steder, som er tall. 

For at prosessen er generelt kjent som en hash-funksjon, og du kan virkelig implementere det i koden. Hvis jeg ønsket å gjennomføre en hash-funksjon som gjør akkurat det vi bare beskrevet fra forrige gang, kanskje jeg erklære en funksjon som tar, som inngang for eksempel - og la oss gjøre dette på denne skjermen over her. Hvis jeg ønsket å gjennomføre en hash funksjon, kan jeg si noe sånt som dette. 

Det kommer til å returnere en int. Det kommer til å bli kalt hasj, og det er kommer til å godta som et argument en string, eller vi kan være mer riktig nå, og si char *, vi kaller det er. Og så all denne funksjonen har å gjøre, slutt, er returnere en int. Nå, hvordan det som kanskje ikke være så tydelige. Jeg kommer til å gjennomføre dette uten form for feilsjekking akkurat nå. Jeg skal bare blindt si, tilbake hva er på s brakett 0, minus, la oss si, kapital semikolon. 

Helt ødelagt. Det er ikke perfekt fordi en, hva hvis s er null? Dårlige ting kommer til å skje. To, hva om den første bokstaven i dette Navnet er ikke en stor bokstav? Som ikke kommer til å snu godt ut heller. Det kan være en liten bokstav eller ikke en bokstav i det hele tatt. Så helt rom for forbedring her, men dette er den grunnleggende ideen. 

Hva vi beskrev i forrige uke verbalt som bare en prosess for å kartlegge Alice til 0 til 1 og Bob kan uttrykkes sikkert mer formulaically som en C fungere her. Ringte igjen hasj, tar en streng som input, og deretter gjør liksom noe med den inngang for å produsere en utgang. Ikke ulikt vår black box beskrivelse at vi har lenge gjort. Jeg vet ikke hvordan dette kan være arbeider under panseret. 

For oppgavesettet 6, en av utfordringene er for deg å bestemme hva vil hash-funksjon være? Hva kommer til å være inne i det svarte boks, og antagelig vil det være en litt mer interessant enn dette, og definitivt mer utsatt for feil sjekker enn dette gjennomføring. 

Men problemer kan oppstå, ikke sant? Hvis vi har en datastruktur slik som denne en, hva som er et av problemene du kan kjøre inn over tid som du setter inn flere og flere navnene inn i hash table? Du får kollisjoner, ikke sant? Hva hvis du har Alice og Aron, to personer som har navn som skjedde å starte med A? Det må da spørre hvor du sette den andre et slikt navn? 

Vel, kanskje du naivt bare sette den hvor Bob hører hjemme, men da Bob er slags skrudd hvis du prøver å sette navnet hans neste og det er ikke rom for ham. Så du kan sette Bob der Charlie er, og du kan forestille deg dette svært raskt devolving inn litt av et rot. Noe lineær i slutten, hvor du bare å søke på hele greia på jakt etter Alice eller Bob eller Aaron eller Charlie. 

Så i stedet vi foreslo, i stedet for bare lineært sondering for åpne plasser og plopping navnene der, vi foreslått en mer avansert tilnærming. En hash table implementert fortsatt med en rekke indekser, men dataene type disse indeksene nå var pekere. Pekere til hva? Pekere til lenkede lister. 

Fordi huske at en lenket liste er egentlig bare en peker til en node, og noden har en neste felt, og at noden har en neste felt, og så videre. Så du kan nå tenke på dette array på den venstre side av en hash tabell som fører til en lenket liste. Fordelen med noe som er hvis du får en kollisjon mellom Alice og Aron, hva gjør du med andre slik person? Du må bare legge ham eller henne til slutten av eller til og med begynnelsen av at lenket liste. 

Og faktisk, la oss bare noodle gjennom at bare et sekund. Hvor ville gjøre det mest fornuftig? Hvis jeg setter Alice og hun ender opp på den første plasseringen, så jeg prøver å sette Aaron navn, og det er åpenbart en kollisjon, skal jeg sette seg ved begynnelsen av lenket liste? Det er på den første plasseringen, eller på slutten? 

PUBLIKUM: [uhørlig]. 

DAVID MALAN: OK. Jeg hørte begynnelsen. Hvorfor i begynnelsen? 

PUBLIKUM: [uhørlig]. 

DAVID MALAN: OK. Det er alfabetisk, så det er fint. Det er en god egenskap. Det vil spare meg litt tid potensielt. Det vil ikke la meg gjøre binære søk, men jeg kan i det minste være i stand til å bryte ut av en loop hvis jeg skjønner, vel, jeg er måten fortiden var Aaron ville være i denne sortert lenket liste. Jeg trenger ikke å kaste bort min tid på å lete hele veien til enden. Så det er rimelig. Hvorfor ellers vil du kanskje sette inn den kolliderer navnet på begynnelsen av listen? Hva er det? 

PUBLIKUM: [uhørlig]. 

DAVID MALAN: Det kan ta lang tid for å komme til enden av listen. Og faktisk, lengre og lengre. Jo flere navn du setter det starter med A, jo lenger at kjeden kommer til å få. Jo lenger som knyttet Listen kommer til å få. Så du er egentlig bare kaste bort tiden din. Kanskje du er bedre å opprettholde konstant tidspunktet for innsetting, av en stor O, ved alltid å sette kollidere navnet på begynnelsen av lenket liste, og ikke bekymre seg så mye om sortering. 

Hva er det beste svaret? Det er uklart. Den slags avhenger av hva fordelingen er, hva mønsteret er av navnene du setter inn. Det er ikke nødvendigvis et opplagt svar. Men her, igjen, er et design anledning. 

Så vi deretter så på denne tingen, som er egentlig den andre store mulighet for p-set seks. Og skjønner, hvis du ikke allerede har gjort, Zamyla dykk inn begge disse, hash bord og prøver, i mer detalj. Og videogjennomgang er innebygd i p-set spec. Dette var en trie - T-R-I-E. Og det interessante dette var at kjøretiden å søke etter et navn, som Maxwell siste gang, var stor O av hva? Hva er det? 

PUBLIKUM: Antall bokstaver. 

DAVID MALAN: Antall brev. Jeg hørte to ting. Antall bokstaver og konstant tid. Så la oss gå med det første. Det antall bokstaver. Vel, dette er data struktur, husker, liker et tre, et familietre, hver av som noder består av arrays. Og disse arrays er pekere til andre slike noder, eller andre slike arrays i treet. 

Så hvis vi ønsket å deretter bestemme enten Maxwell er her, kan jeg gå til den første array, helt på toppen av treet, den såkalte rot, oppå den trie, og følg deretter m pekeren, deretter en peker, deretter x, w, e, l, l. Og så når jeg ser noen spesiell symbol, betegnes her som en trekant. I koden ser du foreslår vi at du implementert som en bool, bare si ja eller nei, stopper et ord her. 

Vel, når vi har gått til M-A-X-W-E-L-L, føles som sju, kanskje åtte hvis vi går en forbi den, åtte fremgangsmåten for å finne Maxwell. Eller la oss kalle det K. Men husker sist tid, hevdet jeg at hvis det er realistisk en maksimal lengde på en ord, som 40-some-odd tegn, en Maksimal lengde innebærer en konstant verdi. Så egentlig, ja, det er teknisk big O 8 eller 7, eller virkelig store O av K. Men hvis det er et endelig tak på hva K kan være, er det en konstant. Og så det er big O av en på slutten av dagen. 

Ikke i den virkelige verden. Ikke når du faktisk begynne å se din klokke som programmet kjører. Det er absolutt kommer til å være litt tregere enn virkelig konstant tid med ett trinn. Det kommer til å være syv eller åtte trinn, men likevel det er mye, mye bedre enn en algoritme som big O n som avhenger av størrelsen på hva som er i datastruktur. 

Legg merke oppsiden her er at vi kan sette inn en million flere navn i denne datastruktur, men hvor mange flere trinn går det å ta oss til å finne Maxwell i så fall? Ingen. Han er upåvirket. Og til dags dato, tror jeg ikke vi har sett et eksempel på en datastruktur eller et algoritme som var helt upåvirket av ytre atferd sånn. Men dette kan ikke være fantastisk. Dette kan ikke være den eneste løsningen for P-set 

Og det er ikke. Dette er ikke nødvendigvis de data struktur bør du bevege til, fordi som hash tabeller, byttehandel. Hva er prisen du betaler her? Minne. Jeg mener, dette er en fryktelig mye minne. Og du kan ikke helt se det her fordi forfatteren av dette bildet åpenbart avkortet alle matriser og vi ikke ser mye av A og B og C-er og Q og Y og Z er i disse arrays. Men de er der. 

Hver av disse noder er en hel rekke av enkelte 26 eller flere byte, hver av som representerer en bokstav. 27 i vårt tilfelle, slik at vi kan støtte apostrofer i oppgavesettet. Så dette datastruktur er virkelig, virkelig tett og bred. Og det alene kan ende opp med å bremse ting ned, eller i det minste koste deg mye mer plass. Men igjen, kan vi trekke sammenligninger her. 

Huske en stund tilbake, har vi oppnådd mye mer spennende kjøretid i sortering når vi bruker merge slag, men prisen vi betalte for å oppnå n log n for flettingen sortere nødvendig at vi bruker mer hva ressurs? Mer plass. Vi trengte en sekundær array til kopiere folk inn, akkurat som vi gjorde her på scenen. Så igjen, ingen klare vinnere, men bare subjektive utforming beslutninger skal gjøres. 

OK. Så hva med denne? Noen som gjenkjenner som D-Hall? OK. Så tre av oss gjør. Mather House. Så dette er for Mather spisesalen. Jeg vedder alle spisesaler har stabler av skuffer som dette. Og dette er faktisk representative av noe vi har åpenbart sett allerede. Vi kalte det bokstavelig talt en stabel. Og bunken, i form av din datamaskinens minne, er hvor data går mens funksjoner blir kalt. 

For eksempel, hva slags ting går på stabelen med hensyn til minne layout vi har diskutert i uker tidligere? Hva er det? 

PUBLIKUM: Samtaler til funksjoner. 

DAVID MALAN: Jeg beklager. 

PUBLIKUM: Samtaler til funksjoner. 

DAVID MALAN: Anrop til funksjoner, men spesifikt, hva som er inni hver av disse rammer? Hva slags ting? Yeah. Så lokale variabler. Når som helst vi trengte litt lokal lagring, som et argument, eller int jeg, eller int temp, eller hva det lokale variabelen, har vi vært sette det på stakken. Og vi kaller det en stabel fordi av at lagdeling idé. Bare slags kamper opp med virkeligheten, begrepet derav. 

Men det viser seg at en stabel kan også bli sett på som en datastruktur, en alternativ til en matrise, et alternativ til en lenket liste. Noe konseptuelt mer interessant som fortsatt kan være implementert ved hjelp av noen av disse ting, men det er en annen type datastruktur støtte, egentlig, bare to operasjoner. Men du kan legge på mer avansert funksjoner enn disse. Men disse er det grunnleggende - presse og pop. 

Og ideen med en stabel er at hvis jeg har her, med eller uten Annenberg vite, et brett fra naboen med tallet 9 på den. Så bare en int. Og jeg ønsker å presse dette på dataene struktur, som for tiden er tom. Betrakt dette nederst i stabelen. Jeg ville presse dette tallet 9 på stable, og nå er det akkurat det. 

Men det interessante ting om en stabel er at hvis jeg nå ønsker å presse en annen verdi, 17, ut og jeg presse dette på stakken, jeg kommer til å gjøre den eneste intuitive ting, jeg bare kommer å sette den akkurat der vi mennesker ville være tilbøyelig til å si det, på toppen. Men det som er interessant nå er, hvordan får jeg på 9? Vet du, jeg tror ikke uten litt innsats. 

Så hva er interessant om en stabel er at ved design, det er en LIFO datastruktur. Silly måte å beskrive sist inn, først ut. Så det siste nummeret i på dette tidspunktet var 17 år. Så hvis jeg ønsker å komme noe av av stabelen, kan det bare være 17. Så det er en obligatorisk rekkefølge operasjoner her, hvor det siste elementet i må være den første ut. Derav forkortelsen, LIFO. 

Så hvorfor kan dette være nyttig? Er deres sammenhenger der du hadde vil ha en datastruktur som dette? Vel, det er sikkert vært nyttig innsiden av en datamaskin. Så operativsystemer klart bruke dette type datastruktur for stabler. Vi vil også se den samme ideen når det kommer til web-sider. Så denne uken og neste uke og utover, og som du begynner å implementere web sider i et språk som heter HTML, kan du faktisk bruke en datastruktur som dette for å bestemme om siden er riktig formatert. Fordi vi vil se alle websider følger et slags hierarki, et innrykk som vil, ved slutten av dagen, være en trestruktur under panseret. Så mer om det i bare litt. 

Men for nå, la oss foreslå for en øyeblikk, hvordan kunne vi gå om representerer hva en stabel er? La meg foreslå at vi implementerer en stabel med kode som dette. Så en stabel kommer til å ha på innsiden av det to ting, en rekke, kalt skuffer, bare for å være i samsvar med demoen. Og hvert av elementene i denne matrisen kommer til å være en type int. Og kapasitet er formodentlig hva? Fordi jeg ikke har skrevet fullstendig definisjon her. 

Det er trolig det maksimale størrelsen på matrisen. Og det er sannsynligvis erklært som en skarp definere på toppen av filen, noen slags konstant som følger av den bare store bokstaver. Så et sted kapasitet er definert som maksimal mulig størrelse. I mellomtiden innsiden av datastrukturen kjent som en stabel vil det være et heltall bare kjent bare som størrelse. 

Så hvis jeg skulle representere dette nå pictorially, la oss anta at dette Hele svart boks representerer min stack. Innsiden av det er to variabler. Så jeg kommer til å trekke første som størrelse. Og den andre jeg kommer å trekke som en matrise. 

Men bare for å holde ting ryddig, normalt ville jeg trekke en matrise som dette, men det er litt fint hvis vi samsvarer med virkeligheten, eller matche den mentale modellen. Så la meg i stedet trekke matrisen vertikalt, er der bare igjen, kunstnerens gjengivelse. Spiller egentlig ingen rolle hva det er under panseret. Og vi vil si at, som standard, kapasitet kommer til å bli tre. Så dette vil være 0 beliggenhet, dette vil være plassering 1, dette vil være plassering to. 

Hvis jeg bestikke med en stress ball, ville noen liker å komme opp og kjøre borde her for bare et øyeblikk? OK, så hånden først. Kom opp. OK. Så jeg tror det er Steven. Kom opp. OK. 

Men anta nå vi spole tilbake til den opprinnelige tilstanden i verden hvor jeg har nettopp erklært en stabel, og det er kommer til å være av kapasiteten tre. Men størrelse er ennå ikke bestemt. Skuffer er ennå ikke bestemt. Så et par spørsmål først. Og la meg gi deg mic slik at du kan delta mer aktivt i dette. 

Så hva er inne i størrelse i dette øyeblikk i tid hvis alt jeg har gjort er erklærte en stabel med en linje med kode? 

STEVEN: Ikke mye. 

DAVID MALAN: OK, ikke mye. Vet vi hva som er inne i størrelse, vet vi hva som er inni i denne tabellen her? 

STEVEN: Bare tilfeldig kode, ikke sant? Just - 

DAVID MALAN: Ja, jeg kommer til å kaller det koden, men tilfeldig - 

STEVEN: Things. 

DAVID MALAN: Ting som tilfeldig 

STEVEN: Bits. 

DAVID MALAN: Bits, ikke sant? Så søppel verdier, ikke sant? Så permutasjoner av 0 og 1-ere. Rester av tidligere bruksområder av denne hukommelse. Og vi vet egentlig ikke hva verdiene er, slik vi vanligvis trekke dem som spørsmålstegn. 

Så det første vi er formodentlig kommer til å ønske å gjøre her - og la meg gi dette feltet inne av det et navn - skuffer. Hva bør vi antagelig starte størrelse til hvis vi ønsker å begynne å bruke denne bunken? 

STEVEN: Skuff er sub 3. 

DAVID MALAN: Så, OK. Å være klar, er kapasiteten erklært andre steder som tre. Og det er det jeg har brukt å fordele array. Størrelse kommer til å referere til hvor mange skuffer er for tiden på stakken. 

STEVEN: Zero. 

DAVID MALAN: Så det burde være null. Så gå videre, og med noen finger, tegner en null i størrelse. OK. Så nå, hva som er inni denne her, vet vi ikke. Dette er egentlig bare søppel verdier. Slik at vi kunne trekke spørsmålstegn, men la oss holde styret ren for nå fordi det spiller ingen rolle hva som er der. Vi trenger ikke å initialisere tabellen til noe, fordi hvis vi vet at størrelsen av stabelen er null, vel, vi bør ikke være å se på noe i denne matrisen allikevel på dette tidspunktet. 

Så nå anta at jeg skyver nummer 9 på bunken. Hvordan skal vi oppdatere datastruktur innsiden av denne svarte boksen? Hvilke verdier må endre? 

STEVEN: Innen - størrelsen? 

DAVID MALAN: OK. Størrelse bør bli det? 

STEVEN: Størrelse skulle være ett. 

DAVID MALAN: OK. Så størrelse bør bli ett. Så du kan gjøre dette i et par måter. La meg gi deg, nå er din finger er et viskelær. OK. Så nå fingeren er en pensel. OK. Og nå hva andre har å endre, Selvfølgelig, i datastrukturen? 

STEVEN: Vi går fra bunnen opp til ni. 

DAVID MALAN: 9. OK, Bra. Så fortsatt ingen rolle hva som står på beliggenhet én eller to fordi de er søppel verdier, men vi bør ikke bry ser det fordi størrelsen er forteller oss at bare det første elementet er faktisk legitimt. Så nå skal jeg presse 17 på listen. Hva skjer med dette bildet? 

STEVEN: Så størrelsen kommer til å gå til to. 

DAVID MALAN: OK. Du er viskelær - oops. Du er et viskelær. 

STEVEN: Eraser. 

DAVID MALAN: Du er en børste. 

STEVEN: Brush. 

DAVID MALAN: OK. Og hva annet? 

STEVEN: Og da er vi - 

DAVID MALAN: Vi presset 17. 

STEVEN: Vi holder 17 på topp, så - 

DAVID MALAN: OK, bra. 

STEVEN: - slippe den ned. 

DAVID MALAN: All right. Det begynner å bli lett. Jeg kommer ikke til å hjelpe deg denne gangen. Push 22. 

STEVEN: Ferdig. Å bli et viskelær. Jeg blir en børste. Og så jeg setter 22. 

DAVID MALAN: 22. Utmerket. Så en gang til. Jeg er nå kommer til å presse på stabelen 26.. 

STEVEN: Ooh. Oh gosh. Du virkelig fanget meg av vakt. 

DAVID MALAN: Du gjorde ikke se dette komme? 

STEVEN: Jeg så ikke dette komme. Kunne vi re-initial kapasitet? 

DAVID MALAN: Det er et godt spørsmål. Så vi har litt malt oss selv i et hjørne her. Det er egentlig ingen god ut for Steven fordi vi har tildelt denne tabellen statisk, så å si, inni av datastrukturen. Og vi har egentlig hardkodet det å være av størrelsen tre. Så vi kan ikke egentlig omfordele det. 

Vi kunne hvis vi gikk inn igjen, vi omdefinert skuffer å være en peker som vi da bruke malloc for hånden minne til. Fordi hvis vi fikk minnet fra haugen via malloc, vi kan da frigjøre den. Men før frigjør det, kunne vi omdisponere en større mengde minne, oppdatere pekeren, og så videre. Men for nå, er dette virkelig det beste vi kan gjøre. Presse og pop er antagelig kommer til å signalisere noen feil. 

Så for eksempel, vår gjennomføring av presse kunne returnere en bool som tidligere returnert true, true, true. Men fjerde gang, det kommer til å ha for return false, for eksempel. OK. Veldig godt gjort. Gratulerer. Du har fortjent stress ball i dag. 

[APPLAUSE] 

STEVEN: Takk. 

DAVID MALAN: Takk. OK, så dette synes å være ikke mye av et skritt fremover, ikke sant? Vi beskrev dette datastruktur. Det har vært overbevisende, ikke sant? Operativsystemer liker det. Angivelig nettet kan gjøre bruk av dette, og andre programmer fremdeles. Men hva en dum begrensning som vi er tilbake til slags uke to grenser der vi har fast størrelse arrays. 

Så det er faktisk et par måter vi kan løse dette. Vi kunne dynamisk allokere array, ikke ved hardt koding det som jeg har gjort her, men i stedet re-erklærte dette, å bare være klart, som noe sånt som dette. Int * skuffer ikke bestemme på en kapasitet ennå. Men når jeg erklærer stabelen andre steder i koden min, kan jeg da kalle malloc, få adressen til en del av minne, og jeg kunne tildele den adressen til skuffene. 

Og så, fordi det er bare en del av minne, kan jeg fortsette å bruke plassen brakett notasjon på vanlig måte. Fordi igjen, det er liksom dette funksjonell ekvivalent av matriser og biter av minne som kommer tilbake fra malloc. Vi kan behandle en som de andre bruke pekeren aritmetisk eller hakeparentes notasjon. Så det er en tilnærming. 

Men hvordan ellers kan vi gjennomføre dette samme datastruktur, potensielt? Høyre? Jeg føler at vi bare løst dette problem som for en uke siden. Hva var løsningen på dette problemet at Steven kjørte inn? Så lenkede lister, høyre. 

Hvis problemet er at vi male oss selv inn i et hjørne ved å allokere på forhånd for lite minne som vi deretter har å liksom forholde seg til, vel, hvorfor ikke bare unngå at utstede helt? Hvorfor ikke bare erklære skuffer å være en peker til en node, ergo en lenket liste, og så bare tildele nye noder hver gang Steven nødvendig for å passe til en nummer i datastruktur. 

Slik at bildet måtte endre. Det kommer ikke til å være så ren og som enkelt som bare et utvalg av tre ints. Nå det kommer til å være en peker til en struct, og at struct kommer til å har en int og en neste pekeren. Det kommer til å lede via denne pekeren til en annen slik struct til en annen slik struct. Slik at bildet ville faktisk få litt Messier. Og vi ville ha piler binde alt sammen. 

Men det er greit, ikke sant, fordi Vi har sett hvordan du gjør dette. Og når du blir komfortabel gjennomføre noe sånt som en koblet liste, som du må gjøre hvis du velger å gjennomføre en hash tabell med separat kjeding for p-set 6, kan du bruke den som en byggekloss, eller en ingrediens, eller i Scratch snakke, en prosedyre, noe som du putter, du opprettet din egen puslespill brikke som du deretter kan bruke. Så avveininger, men mulige løsninger at vi faktisk har sett før. 

Så ganske ofte, ser du dette hver år eller to når Apple utgivelser noe nytt, og alle de gale menneskene linje opp utenfor Apple butikken for å kjøpe deres marginale oppgradere på maskinvare. Jeg sier dette, er det OK, fordi Jeg er en av dem. Så hva slags datastruktur kan representere denne virkeligheten? 

Vel, la oss kalle det en kø, en linje. Så britisk vil kalle det vanligvis en køen uansett, så det er et fint navn. Og de to operasjonene som en kø skal støtte vi kaller en enqueue drift og en dequeue drift, som er like i ånd å presse og pop. Det er bare en slags annerledes i konvensjon, hva vi kaller disse. Men for å Enqueue noe betyr å legge eller sette den til datastruktur. Å dequeue betyr å fjerne det. Men mens en stabel var en LIFO data struktur, er en kø et først inn, først ut datastruktur. 

Hvis du er den første personen i kø, vil du være den første personen til å få ut av linjen og kjøpe den nye enheten. Tenk deg hvor opprørt disse menneskene ville være hvis Apple i stedet brukt en stabel, for eksempel, å gjennomføre plukking opp av din nye leketøy. Så køer fornuftig, i hvert fall, og vi kan tenke på alle slags applikasjoner, antagelig, for køer, spesielt når du ønsker rettferdighet. Så hvordan kan vi gjennomføre disse som en datastruktur? 

Vel, foreslår jeg at vi kan trenger å gjøre det på denne måten. Så jeg kommer til å nå ha tall. Så vi vil holde det enkelt og ikke nødvendigvis snakker i form av skuffer. Bare tall som folk har fått. Kapasiteten skal, igjen, fikse totale antall personer som kan være i denne linjen, som tre eller hva andre verdi. 

Men jeg foreslår at jeg trenger å holde styr ikke bare av størrelsen på den kø, hvor mange ting er i den. Så størrelsen er den nåværende størrelse, kapasitet er den maksimale størrelse. Bare igjen, nomenklatur etter konvensjonen. Hvorfor trenger jeg en ekstra int inne av en kø for å holde styr på hvem som er i foran linjen? Hvorfor trenger jeg å gjøre det i dette tilfellet? 

Vel, hvordan er dette bildet kommer til å forandre seg? Jeg kan sikkert bruke mest av dette bildet. La meg gå videre og slette innholdet her. Vi gir dette en litt annet navn her oppe. La oss bli kvitt den 17, la oss bli kvitt av ni, la oss bli kvitt den 3. Og la oss legge til en annen ting. Jeg foreslår at jeg trenger å holde styr på forsiden av listen, i hvilken bare kommer til å være en int også. Og vi kommer til å holde det enkelt. Ingen lenket liste for nå. 

Vi skal innrømme at vi kommer til å bump opp mot denne grensen. Men hva ønsker jeg å se skje denne gangen? Så antar jeg gå videre og den første person kommer opp i kø, og det er nummer ni. Vi har stress baller. Kan jeg stjele, sier, to eller tre personer? En, to, tre? Kom opp. Rett forfra, fordi vi vil gjøre dette til en rask. 

Hver av dere nå kommer til å være en fan gutt i kø på Apple. Du vil ikke motta Apple-maskinvare på slutten av dette selv. OK. Så du er nummer 9, er du nummer 17, nummer 22. Dette er vilkårlige tall, som student-ID eller whatnot. Og om en liten stund, la oss begynne å begynne å legge ting. Og jeg skal kjøre brettet her denne gangen. 

Så i dette tilfellet, har jeg initialisert foran å være - Jeg faktisk ikke egentlig bryr seg hva foran er, fordi størrelsen er null. Så dette kan like godt bare være et spørsmålstegn. Disse er alle spørsmålstegn. Så nå skal vi begynne å faktisk se noen folk i kø i butikken. 

Så hvis nummer 9, er du den første der på 5 AM, gå videre og stille opp, eller kvelden før. OK. Så nå ni er her. Så 9 er på forsiden av listen. Så jeg kommer til å gå videre og oppdatere Størrelsen på denne aktuelle data struktur for å ikke være 0 lenger, men for å være en. Jeg kommer til å sette 9 på forsiden av listen. La meg gå videre og slå på skjermen slik at vi kan se forbi oss her. 

Og nå hva jeg vil å sette på forsiden? Jeg kommer til å holde styr på at foran i køen akkurat nå er på stedet 0. Fordi hva er neste kommer til å skje? Vel, vel nå jeg Enqueue 17 i tillegg. Så hoppe på linje der. Og igjen, den slags døren til butikken kommer til å være her. Så nå har jeg lagt 17. Og selv om disse gutta blokkerer skjermen, det er OK, fordi vi kan se det her oppe. Unnskyld. 

PUBLIKUM: Vi kan flytte - 

DAVID MALAN: Nei, det er OK. Det er stor der oppe. Så 17 er nå inne i køen. Jeg trenger å oppdatere som felt nå skjønt? OK, absolutt størrelse. Og hva med fronten? OK, nei. Foran bør ikke endre, fordi i motsetning til en stabel, vi ønsker å opprettholde rettferdighet. Så hvis 9 kom i første, vil vi 9 å være den første ut av linjen og inn i butikken. 

Faktisk, la oss se det. Før vi setter 22, la oss gå videre og dequeue ni. Hva er navnet ditt igjen? 

PUBLIKUM: Jake. 

DAVID MALAN: Jake kommer å bli dequeued nå. Så du kommer til å gå inn i butikken. Og late som at butikken er der borte. Så nå hva trenger - dit-dit-dit! Hva må skje nå? Design beslutning. Så ikke en dårlig instinkt, men - hva heter du igjen? 

PUBLIKUM: David. 

DAVID MALAN: David. Så hva gjorde David? Han prøvde å liksom fikse data struktur og flytte fra stedet hans til Jakes tidligere plassering. Og det er fint hvis vi er villige å akseptere at som en implementering detaljer. Men først, la oss oppdatere dataene strukturen før vi gjør det. Fordi jeg ikke er fornøyd med tanken på alt folk skiftende i denne linjen. 

Det er ingen big deal om David gjør det med ett trinn, men igjen, tenker tilbake til når vi har hatt åtte frivillige på scenen og vi har gjort som innsetting sortere, hvor vi måtte starte flytte alle rundt. Som fikk dyrt, ikke sant? Det gjør meg flau om big O av N, kvadrerte stor O for n på nytt. Det er ikke følelsen som en ideell utfall. 

Så la oss bare oppdatere denne. Slik at størrelsen av køen ikke lenger er to. Det er nå bare en. Men jeg kan nå oppdatere noe Jeg fikk ikke oppdatere før, den forsiden av listen. Jeg kunne bare si, er at stedet en? Så nå har vi søppel verdi her, søppel verdi her, og David i Midt i dette søppel. Men datastrukturen er fortsatt intakt. 

Og faktisk, jeg trenger ikke engang å endre Jakes tidligere nummer 9, fordi hvem bryr seg. Jeg har nok informasjon nå i størrelse som jeg vet det er én person i denne køen. Og jeg vet at den personen er på en plassering, ikke 0. Jeg er ikke telle. So 1 tillegg. Så datastrukturen er fortsatt OK. 

Vel, hva skjer videre? La oss enqueue - hva heter du? 

PUBLIKUM: Callen. 

DAVID MALAN: Callen. La oss Enqueue en Callen, og 22 er nå i køen. Så hva nå må endre her? Foran er ikke til å endre, selvsagt. Størrelse kommer til å endre til å være to igjen. Og 22 ender opp her, er ni fortsatt er til stede, men det er effektivt en søppel verdi nå. Det er bare en rest av Jake fortiden. 

Så nå hva skjer hvis Jeg dequeue David? En siste operasjon, dequeue David. Vi kunne skifte, men jeg foreslår la oss gjøre så lite arbeid som mulig. Nå er min datastruktur går tilbake i størrelse 2-1. Men den foran i køen nå blir to. Jeg trenger ikke å endre disse tallene ennå, fordi de er bare søppel verdier. 

Men nå hva skjer? Antar jeg Enqueue meg selv, 26? Jeg føler at jeg hører hjemme her borte. Så jeg blir enqueued. Så jeg slags hører hjemme her. Og selv om du ikke helt setter pris på dette visuelt på scenen, fordi vi har god plass, skulle jeg ikke bli stående her, hvorfor? 

PUBLIKUM: Du er utenfor banen. 

DAVID MALAN: Høyre. Jeg er utenfor banen. Jeg har indeksert utover rammene av denne tabellen. Jeg burde virkelig være i en av de tre mulige steder. Nå, hvor er mest naturlig å gå? Jeg foreslår vi leveraged en uke ett triks. Mod operatør, prosent. Fordi jeg er teknisk sett stående på 3 plassering, men jeg gjør 3 mod kapasitet, så 3, en prosent tegn, 3 - kapasitet er tre. Hva er det? Hva er resten når du dele tre av tre? 0. 

Så det setter meg var Jake var, som faktisk er bra. Så nå gjennomføringen av denne saken kommer til å være litt av en hodepine. Det er egentlig bare én linje hodepine, med kode. Men i det minste nå er det søppel verdi her, men det er to legitime ints her. Og jeg hevder at vi nå har gjort akkurat hva vi trenger å gjøre så lenge vi endre hva Jake Verdien var å være 26.. 

Vi har nå nok informasjon fortsatt for å opprettholde integriteten av dette datastruktur. Vi er fortsatt litt ute av lykken når vi vil sette inn fire eller flere total elementer, men jeg kan i det minste gjøre ganske effektiv bruk av denne konstante tid, faktisk. Jeg trenger ikke å bekymre deg for å skifte alle, som Davids tilbøyelighet var. 

Eventuelle spørsmål om stabler, eller denne køen? 

PUBLIKUM: Er grunnen du trenger størrelse slik at du vet hvor du skal ha en person? 

DAVID MALAN: Nettopp. Jeg trenger å vite størrelsen på array fordi jeg trenger å vite nøyaktig hvordan mange av disse verdiene er legitime, og slik at jeg kan finne hvor du skal sette neste person. Nettopp. Størrelsen er - faktisk, det gjorde vi ikke oppdatere dette ennå. Jeg har lagt meg selv på 26.. Størrelsen er nå, ikke en, men to. Så nå dette hjelper faktisk meg å finne begynnelsen av listen, som ikke er 0, ikke 1, men er 2.. Fronten av listen er faktisk nummer 22. Fordi han kom i første, så han burde tillates inn i butikken før meg, selv om visuelt jeg står nærmere til butikken. 

Greit? En runde med applaus for disse gutta og vi vil la dem ut av det. 

[APPLAUSE] 

DAVID MALAN: jeg kunne la du holder skuffen. Vi kunne se hva som skjer hvis du vil, men kanskje ikke. OK. Så hva nå etterlater det oss? Vel, la meg foreslå at det er en få andre datastrukturer vi kunne begynne å legge til vår verktøykasse som vil faktisk være ganske, ganske relevant som vi dykke inn i web ting. Som igjen har en eller annen tilknytning til trær i form av noe som kalles DOM, dokument objekt-modellen. Men vi får se mer av som før lenge. 

La meg foreslå definitionally at vi kaller treet nå hva du kanskje kjenner som mer av et familietre, der du har noen stamfar på røttene til treet. En patriarkalsk eller en matriark på toppen av treet. Uten sin ektefelle, i dette tilfellet. Men nå har vi det vi kaller barn, som er noder som henger av venstre barn eller høyre barn, piler som avbildet her. 

Med andre ord, i et tre datastruktur i maskinen, har et tre null eller flere noder. Hvis den har minst en node, Det kalles roten. Det er de tingene visuelt at vi trekke på toppen. Og at node, som enhver annen node, kan har null, én eller to, eller tre, eller imidlertid mange barn datastruktur støtter. I dette tilfellet, roten, lagrer verdi en, har to barn, to og tre, så vi vanligvis kaller to til venstre barn og 3 den rette barnet. 

Og så når vi kommer ned til 5, 6, og 7, 6 som kan kalles den mellomste barnet. Hvis du har fire barn, det blir forvirrende. Så vi slutte å bruke den slags av snarvei verbalt. Men det er egentlig bare et familietre. Og bladene her er nodene som seg selv har ingen barn. De henger av bunnen av treet. 

Så hvordan kan vi gjennomføre et tre som har bare to barn maksimalt? Vi kaller det et binært tre. Bi igjen betyr to, i denne tilfelle, som med binær. Og så det kan ha null, én, eller to barn maksimalt. 

Jeg vil foreslå at vi implementere node for at strukturen med et int n, og deretter to pekere, kalt en igjen, en som heter rett. Men de er bare hyggelig vilkårlige konvensjoner. Og hva er fint nå, spesielt hvis du slags slet konseptuelt med rekursjon, eller trodde at det ikke var virkelig en løsning på noe, spesielt hvis du kunne går tom for minne. Nå som vi snakker om data strukturer og algoritmer som gjør at oss å traversere og manipulere dem, viser seg at rekursjon kommer tilbake i en mye mer overbevisende hvis ikke vakker måte. 

Så dette jeg foreslår er gjennomføringen av en søkefunksjon. Gitt to innganger - så tenk på dette som en svart boks. Gitt to innganger, n, en int, og en pekeren til et tre, en peker til en node, eller egentlig roten av et tre, jeg hevder at denne funksjonen kan returnere sant eller usant, at verdien n er inne i dette treet. 

Hva er inni denne svarte boksen? Vel, fire grener. Den første bare sjekker. Hvis treet er null, bare return false. Hvis det er ingen node, er det ingen n, det er ingen tall, bare return false. Hvis skjønt, n, verdien du leter for, er mindre enn tre pilen n, og bare for å være klar, hva betyr det når Jeg skriver treet og deretter pilen notasjon, n? Nettopp. Det betyr dereference at pekeren kalt treet. Gå dit, og deretter få innsiden av det node og få sitt felt kalt n. Og deretter sammenligne den faktiske n som var gått inn Søk mot den. 

Så hvis n er mindre enn verdien n i treet node selv, vel, hva betyr det? Det betyr ingenting ved første øyekast. Høyre? Akkurat som når du har en rekke verdier, kan du liker å bruke binær søke på som en form for splitt og hersk. Men hva antagelsen vi må gjøre for binære søk for å jobbe i det hele tatt i telefonboken og tidligere eksempler? 

Hvordan skal sorteres. Så la oss avgrense definisjonen av treet her ikke å være bare et tre, som kan ha en rekke barn. Ikke bare et binært tre, noe som kan har 0, 1 eller 2 maksimalt. Men som et binært søketre, eller BST, som er bare en fancy måte å si en binært tre slik at hver node venstre barn, hvis de finnes, er mindre enn noden. Og hver node rett barn, hvis de finnes, er større enn noden selv. 

Så med andre ord, om du skulle tegne ut treet, alle tall er nøye balansert som dette slik at hvis du har 55 som root, kan 33 gå til venstre for den fordi det er mindre enn 55 år. 77 kan gå til sin rett fordi den er større enn 55. Men nå legger merke til, den samme definisjonen, det er en rekursiv definisjon verbalt, må søke om 33. 33 venstre barnet må være mindre enn det, og 33 er rette barnet, 44, må være større enn den. 

Så dette er et binært søketre, og Jeg foreslår, ved hjelp av en liten bit av rekursjon, kan vi nå finne n. Så hvis n er mindre enn den verdi som er n gjeldende node, jeg kommer til å gå fremover og punt, så å si, og bare returnere det Svaret er søker etter n på treets venstre barn. Legg merke til igjen, denne funksjonen bare forventer en node stjerne, en peker til en node. Så sikkert jeg bare kan gjøre tre pil venstre, noe som vil føre meg til en annen node. Men hva er det node? 

Vel, i henhold til denne erklæringen, venstre er bare en peker, slik at bare betyr at jeg har bestått til søkefunksjonen en annen peker, nemlig den som representerer min venstre barns treet. Så i dette tilfellet pekeren til 33, hvis Dette er vårt utvalg innspill mellomtiden, hvis n er større enn verdien n i gjeldende node i treet, da er jeg kommer til å gå videre og punt i den andre retning og bare si, vet jeg ikke vite om denne verdien n er i treet, men jeg vet ikke om det er, er det ned min høyre gren, så å si. Så la meg kalle rekursivt søke, passerer en n igjen, men går i en pekeren til høyre for meg barn. 

Med andre ord, hvis jeg er for tiden på 55 og jeg ser for 99, vet jeg at 99 er større enn 55, så akkurat som jeg rev telefonboken uker siden, og vi gikk rett, på samme måte er vi kommer til å gå her. Og jeg vet ikke om det er ved min høyre barn, og det er ikke, er 77 der, men Jeg vet det er i den retningen. Så jeg kaller søk på min høyre barn, 77, og la søk figur ut fra der hvis 99 i denne vilkårlig eksempel er faktisk der. 

Else, hva er den siste saken? Hvis treet er null er én sak. Hvis n er mindre enn den gjeldende nodens verdien er en annen sak. Hvis n er større enn dagens node verdi er et tredje tilfelle. Hva er den fjerde og siste saken? Jeg tror vi er ute av tilfellene, ikke sant? Det må være at n er i gjeldende node at jeg er på. 

Så hvis jeg søker etter 55 på dette punktet i historien, den grenen av treet ville returnere true. Så hva er interessant her er at vi faktisk, i motsetning til uker tidligere, typen vi av har to basen tilfeller. Og de trenger ikke å alle være på toppen. Toppen er en base tilfelle fordi dersom treet er null, det er ingenting å gjøre. Bare returnere en hard kodet Verdien av falsk. 

Den nederste grenen er liksom den standard, der hvis vi har sjekket for null, har vi sjekket om det bør være igjen, men det bør ikke være, har vi sjekket om det skulle være riktig, men det bør ikke være, klart at det må være akkurat der vi er. Det er en base case. Så det er to rekursive tilfeller klemt der i midten. Men jeg kunne ha skrevet dette i hvilken som helst rekkefølge. Jeg tenkte bare at det føltes slags naturlig å først se etter en mulig feil, så sjekk igjen, så sjekk høyre, deretter anta at du er på noden du faktisk leter etter. 

Så hvorfor kan dette være nyttig? Så det viser seg - og la meg hoppe til en teaser her som er i nettet. Vi kommer til å begynne å bruke ikke en programmeringsspråk i starten, men en kodespråk. Et kodespråk være en som er ligner i ånden til programmering språk, men det gir deg ikke den evne til å uttrykke deg logisk. Det gir deg bare muligheten til å uttrykke deg strukturelt. 

Hvor vil du sette noe på siden, nettsiden? Hvilken farge ønsker du å gjøre det? Hva skriftstørrelsen ønsker du å gjøre det? Hvilke ord har du faktisk ønsker på nettsiden? Så det er et kodespråk. Men så får vi svært raskt introdusere JavaScript, som er en fullverdig programmeringsspråk. Svært lik syntaktisk i utseende til C, men det vil ha noen nice, kraftigere, mer brukervennlige funksjoner. 

Og en av de frustrasjoner på dette punkt i semesteret er at vi vil snart gjennomføre stavekontroll i langt færre linjer med kode som bruker andre språk enn C i seg selv gjør, men på grunn av for oss vi vil snart forstå. Dette vil være den første slike nettside. Det vil være helt underwhelming, det første vi gjør. Det vil rett og slett si, hallo verden. Men hvis du aldri har sett det før, er dette HTML, HyperText Markup Language. 

Hvis du går til en viss menyvalg i mest alle nettlesere, på en nettside på internett, kan du se HTML at noen mennesker skrev til lage denne websiden. Og det sannsynligvis ikke se ut som kort eller så godt som dette. Men det vil følge mønsteret av disse åpne braketter og flenger og bokstaver og potensielt tall. 

Jeg tenkte jeg skulle gi dere en teaser av hva du vil være i stand til å gjøre etter å ha tatt CS50. La meg gå til cs.harvard.edu / rane, vår egen Rob Bowden hjemmeside. Han gjorde dette for oss. Så du vil snart være i stand til å gjøre det. Og også, hva du har hørt denne morgenen - hva du har hørt denne morgenen - 

[HAMSTER DANCE MUSIC] 

- Vil du være i stand til å gjøre dette. Som venter oss på onsdag. Vi vil se deg da. 

[HAMSTER DANCE MUSIC] DAVID MALAN: Ved neste CS50 -