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. 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 -