DAVID Malan: Oke. Welkom terug bij CS50. Dit is het begin van week 8. En herinner dat probleem set 5 eindigde met een beetje een uitdaging. Dus de veronderstelling dat u hersteld van al uw onderwijs Fellows en CA's foto's in het card.raw bestand, komt u in aanmerking om nu al die mensen vinden, en een gelukkige winnaar zal naar huis lopen met een van deze dingen, de sprong beweging apparaat dat u kunt gebruiken voor de definitieve projecten, bijvoorbeeld. 

Dit, elk jaar, leidt tot een beetje creepiness. En dus wat ik dacht dat ik zou doen is het aandeel met u enkele van de noten die moeten gegaan heen en weer over de lijst met medewerkers van laat. Bijvoorbeeld, gisteravond, citaat unquote, van een van de medewerkers leden, "ik een student klop had net op mijn deur om een ​​foto met mij nemen. Stalkers, zeg ik je. "Begon vrij beschrijvende en dan zijn we verhuisd op, een uur of wat later, "ik had een student op me te wachten na sectie en hij had al onze namen en foto's op een aantal vellen papier. 'Oke. Zo georganiseerd, maar niet al die griezelige nog. 

Dan: "Ik was buiten de stad dit weekend, en toen ik terug kwam, was er een in mijn slaapkamer. "[LACH] DAVID Malan: Volgend citaat uit een staf lid, "een student kwam naar mijn huis op Somerville op 4:00 vanochtend. "Next personeel, "Ik moet mijn hotel in San Francisco en een student stond te wachten me in de lobby met drie DSLR's. " Type camera. "Ik ben niet eens op het personeel dit semester, maar een student in mijn huis ingebroken deze ochtend en nam de hele zaak met Google Glass. "En dan tot slot, "Ten minste 12 mensen gretig waren wachten voor mij toen ik uit mijn limo, en toen ik wakker. 'Oke. Dus onder de foto's, zoals u wellicht herinneren, zijn hier deze kerel, die je misschien kennen als Milo Banana, die leeft met Lauren Carvalho, ons hoofd lesgeven Fellow. Milo, Milo, kom hier jongen. Milo. Milo. Let wel, hij draagt ​​Google Glass, dus we zullen jullie dit allemaal zien na. Dus dit is Milo als je wilt neem een ​​foto met hem daarna. Als je wilt om uit te kijken naar het publiek daar. OK. Dat is goed beeldmateriaal. Nou, Milo Banana. Oh, doe dat niet. 

[Lachen] 

OK. Dus een woord dan op wat ons te wachten, want als we beginnen om de overgang, deze week bijzonder vanaf een command line omgeving om PHP en JavaScript en SQL en HTML en CSS in een web-based omgeving, zullen we uitrusten u met alle meer kennis voor mogelijke afstudeeropdrachten. Tegen dat eind, de cursus heeft een traditie van het houden van seminars, die zijn op tangentiële onderwerpen aan de cursus. Zeer nauw samen met de programmering en app ontwikkeling enzovoort, maar niet noodzakelijkerwijs onderzocht door eigen syllabus van de cursus. 

Dus als u misschien wel interesse zou hebben in een of meer van dit jaar de seminars, registreren op cs50.net/seminar. Er zijn oudere seminars bij cs50.net/seminars. En op het rooster tot nu toe voor dit jaar zijn schitterende Web Apps met Ruby on Rails, die een alternatief taal PHP. Computational Linguistics. Inleiding IOS, dat de platform dat wordt gebruikt voor de iPhone en iPad ontwikkeling. JavaScript voor Web Apps, zullen we betrekking hebben dat, maar in dit seminar, ga je in meer detail. 

Leap Motion, dus we eigenlijk hebben enkele van onze vrienden van Leap Motion, het bedrijf zelf, samen met ons. Morgen, in feite beoogd een hands-on seminar, indien voor u van belang. Meteor.js, een alternatieve techniek voor met behulp van JavaScript niet in een browser, maar op een server. Node.js, dat is heel erg in die geest ook. Slanke Android Design. Android is een zeer populaire alternatief naar iOS en Windows Phone en andere mobiele platforms. En Web Security actieve verdediging. 

Dus in feite, als je zou willen om deel te nemen in deze, laat me noteer deze. We zijn erg blij om te zeggen dat onze vrienden bij Leap Beweging, dat is een startup - dit apparaat eigenlijk alleen maar kwam een paar maanden geleden - heeft gedoneerd 30 dergelijke apparaten de klasse voor zoveel studenten als u wilt de hardware lenen naar het einde van semester en gebruiken voor een feitelijke afstudeerproject. Ze ondersteunen een aantal talen. Geen van hen C, geen van PHP, zodat realiseren van een of meer van deze seminars zou kunnen blijken van belangstelling. En alle van hen zal worden gefilmd in het geval dat u niet in staat bent bij te wonen in persoon. Het schema via aangekondigd worden e-mail als we stollen kamers. 

En tot slot, als je naar projects.cs.50.net, is een website We houden elk jaar dat we uitnodigen mensen uit de gemeenschap, faculteit, afdelingen, medewerkers, en beide in een buiten de CS50 aan voorstellen projectideeën. Dingen van belang om groepen studenten. Dingen van belang om afdelingen. Dus wees draaien er als je moeite hebt met onzekerheid over wat je zelf zou willen aanpakken. 

Dus laatste keer dat we een aantoonbaar geïntroduceerd meer complexe datastructuur dan wij hadden gezien in weken verleden. We hadden gebruik gemaakt van arrays vrij gelukkig als nuttig als simplistisch datastructuur. Vervolgens introduceerden we deze die Natuurlijk zijn verbonden lijsten. En wat was een van de motivaties voor invoering van deze datastructuur? Yeah? Wat is dat? 

PUBLIEK: Dynamische grootte. 

DAVID Malan: Dynamische grootte. Dus terwijl in array, moet je weet de grootte van tevoren bij toewijzen u het. In gelinkte lijst, doe je niet moeten weten dat. Je kunt gewoon malloc, of meer in het algemeen, toewijzen van een extra knooppunt, om zo te zeggen, elke keer dat je meer data wilt invoegen. En knooppunt heeft geen vooraf bepaalde betekenis. Het is gewoon een algemene term beschrijft een soort container die we gebruikt in onze datastructuur te slaan sommige post plaats, in dit geval toevallig gehele getallen. 

Maar er is altijd een afweging. Dus krijgen we dynamische afmetingen van de data structuur, maar welke prijs moeten we betalen? Wat is het nadeel van gelinkte lijsten? Yeah? 

PUBLIEK: Vereist meer geheugen. 

DAVID Malan: Het vergt meer geheugen, hoe precies? 

PUBLIEK: [onverstaanbaar]. 

DAVID Malan: Precies. Dus nu hebben we pointers toegang tot extra geheugen dat we eerder niet nodig, omdat het voordeel , array is natuurlijk dat alles is aaneengesloten, terug aan rug aan rug, waarin geeft je random access. Want alleen door het gebruik vierkante haken notatie, of meer technisch aanwijzer rekenkunde, zeer eenvoudige toevoeging, hebt u toegang tot alle elementen in constante tijd. En in feite, dat is een soort van zinspeelde op een andere prijs die we betalen met een gelinkte lijst. 

Wat gebeurt er met de looptijd van zoiets als zoeken, als ik wil vindt u enkele waarde en de binnenkant van een gekoppelde lijst? Wat doet mijn rijtijd worden? Big O van n. Als het wordt gesorteerd op? Wat als de datastructuur is gesorteerd? Kan ik beter dan grote doen O van n voor zoeken? Nee, want in het ergste geval zou zeer goed gesorteerd, maar het aantal u zoekt groot zou kunnen zijn. Het kan het nummer 100, die zijn kan gebeuren met allemaal helemaal aan het einde. En omdat je kunt alleen toegang krijgen tot een gekoppelde lijst in deze uitvoering door manier van zijn eerste knooppunt, je bent nog een beetje pech. Je moet de hele zaak doorkruisen van eerste tot de laatste om te weten die grote waarde, zoals 100. Of om te bepalen of het er niet eens. 

Dus we kunnen niet doen wat algoritme in een data structuur die er als volgt uitziet? We kunnen binary search niet doen, want binary search vereist dat we hadden random access. We konden gewoon springen van plaats tot locatie zonder te volgen deze broodkruimels in de vorm al deze pointers. 

Nu, hoe hebben we dit implementeren? Nou, als we naar het scherm hier, indien kunnen we snel deze gegevens herimplementeren structuur - Mijn handschrift is niet zo hier geweldig, maar we zullen proberen. Dus typedef struct, en wat deed ik wil dit ding hier roepen? Node. Dus ik zal ons begonnen. En nu, wat moet de binnenkant van de gegevensstructuur die afzonderlijk gelinkte lijst? Hoeveel velden? 

Dus twee. Men is vrij eenvoudig. Dus int n. En we konden n wat we willen noemen, maar het moet een int zijn als we uitvoering van een gekoppelde lijst voor ints. En nu, wat doet de tweede veld zijn? Struct knoop *. Dus als ik het doe struct knoop *, en dan heb ik kan dit ook wat ik wil noemen, maar gewoon om duidelijk te zijn Ik bel het volgende, zoals we hebben gedaan. En dan zal ik mijn accolades sluiten. 

En nu, als de vorige keer, Ik zet knooppunt hier beneden. Maar als ik dit te verklaren is als een knooppunt, waarom heb ik moeite zo verbose hier in het verklaren struct * volgende knooppunt, in tegenstelling om gewoon knooppunt * next? Yeah? 

PUBLIEK: [onverstaanbaar]. 

DAVID Malan: Precies. Precies. Omdat C neemt je echt letterlijk en ziet alleen de definitie van knooppunt weg hier beneden, kun je niet verwijzen naar het hier. Dus hebben we dit soort preventieve verklaring hier, die weliswaar is meer verbose. Struct knooppunt, dat betekent kunnen we nu toegang tot het binnenzijde van de gegevensstructuur. 

En als een terzijde, want dit is steeds een beetje meer subjectieve nu, de ster kan hier technisch gaan, het kan hier gaan, het kan gaan zelfs in het midden. We hebben aangenomen, in de stijl gids voor de cursus, de conventie van zetten de ster naast de gegevens type, die in dit geval, zou struct node. Maar realiseren in veel leerboeken en keer gevonden, zou je inderdaad zien het aan de andere kant. Maar gewoon beseffen dat beide ook daadwerkelijk werken en je moet gewoon consistent. 

Oke. Dus dat was onze verklaring van struct knoop. Maar toen begonnen we meer doen verfijnde dingen. Bijvoorbeeld, hebben we besloten in te voeren iets als een hash table. Dus hier is een hash-tabel van grootte n, geïndexeerd vanaf 0 in de linkerbovenhoek te n minus 1 linksonder. Dit kan een hash tafel voor iets. Maar wat voor soort dingen hebben we praten over het gebruik van een hash-tabel voor? Het opslaan van wat? 

Namen. We konden namen doen zoals we deden vorige keer. En echt, kunt u iets op te slaan. En we zullen ook dit zien in PHP en JavaScript. Een hash table is een mooi soort van Zwitserse Zakmes die u toelaat om op te slaan vrijwel alles wat je wilt binnenkant van het associëren van sleutels waarden. Toetsen met waarden. 

Nu in dit eenvoudige geval, onze toetsen zijn gewoon nummers. We implementeren van een hash tabel als een array. En zo de toetsen zijn 0, 1, 2, enzovoort. En zo zijn wij, als mens, besloot vorig week dat je weet wat, als we gaat winkel namen, laten we gewoon arbitrair, maar vrij redelijk, veronderstellen dat Alice, een met naam, zal alleen worden geïndexeerd in 0. En Bob, een B naam, zal worden geïndexeerd in 1, enzovoort. Dus we hadden een mapping tussen de ingangen, die zijn snaren, en de hash plaatsen, welke getallen. 

Zodat proces is algemeen bekend als een hash-functie, en je kan echt implementeren in code. Als ik wilde een hash-functie te implementeren dat is precies wat we wel zojuist beschreven van de vorige keer, ik zou verklaren een functie die neemt, als ingang voor bijvoorbeeld - en laten we dit doen op deze scherm over hier. Als ik wilde implementeren van een hash functie, zou ik zeggen zoiets als dit. 

Het gaat om een ​​int terug. Het gaat hash genoemd te worden, en het is gaan als argument een om te accepteren snaar, of we kunnen nu meer goede, en zeggen: char *, we noemen het s. En dan al deze functie te maken heeft, uiteindelijk, wordt terug een int. Nu, hoe het doet dat misschien niet zo duidelijk. Ik ga dit uitvoeren zonder vormen van foutcontrole nu. Ik ga gewoon blindelings zeggen, terug wat is op s beugel 0, minus, laten we zeggen, de hoofdstad Een puntkomma. 

Helemaal kapot. Het is niet perfect omdat men, wat als s null is? Slechte dingen gaan gebeuren. Twee, wat als de eerste letter in dit naam is niet een hoofdletter? Dat gaat niet draaien goed uit ook. Het is misschien een kleine letter worden of geen brief helemaal. Zo totaal ruimte voor verbetering hier, maar dit is het basisidee. 

Wat we vorige week beschreven mondeling als gewoon een proces van het in kaart brengen Alice aan 0 en Bob 1 kan worden uitgedrukt zeker meer formulaically als C functioneren hier. Riep opnieuw hash, neemt een string als ingang, en dan een of andere manier iets doet met die ingang met een uitgang produceren. Niet in tegenstelling tot onze black box beschrijving dat we lang hebben gedaan. Ik weet niet hoe dit zou kunnen zijn werken onder de motorkap. 

Voor probleem set 6, een van de uitdagingen is voor u om te beslissen welke zal uw hash-functie zijn? Wat gaat de binnenkant van die zwart zijn doos, en vermoedelijk, het zal een wat interessanter dan deze, en zeker meer gevoelig voor fouten controle dan dit implementatie. 

Maar er kunnen problemen ontstaan, toch? Als we een datastructuur, zoals deze men, wat is een van de problemen je kan lopen in de tijd als je plaatst meer namen in de hash table? Je krijgt botsingen, toch? Wat als je Alice en Aäron, twee mensen van wie de namen gebeurd te beginnen A? Dat roept de vraag op, waar u zet de tweede dergelijke Een naam? 

Nou, je zou naïef zet ze gewoon waar Bob hoort, maar dan Bob is soort geschroefd als je probeert te plaatst zijn naam naast en er is geen plaats voor hem. Dus je zou Bob waar Charlie is, zet en je kunt voorstellen dat dit zeer snel delegeren naar een beetje een puinhoop. Iets lineair in het einde, waar u gewoon de hele zaak zoeken op zoek naar Alice of Bob of Aaron of Charlie. 

Dus in plaats daarvan hebben we voorgesteld, in plaats van alleen lineair peilen naar open ruimten en plopping de namen daar, we voorgesteld een liefhebber aanpak. Een hash table nog steeds uitgevoerd met een reeks van indices, maar de data type deze indices waren nu pointers. Pointers naar wat? Pointers naar gelinkte lijsten. 

Omdat herinneren dat een gelinkte lijst is eigenlijk gewoon een pointer naar een knooppunt, en het knooppunt een volgend veld, en dat knooppunt een volgende veld, enzovoort. Dus je kunt nu denken van deze array op de linkerkant van een hash tabel leidt tot een gekoppelde lijst. Het voordeel daarvan is als je een botsing tussen Alice en Aäron, wat doe je dan met de tweede dergelijke persoon? Sluit je er gewoon hem of haar naar de end of zelfs het begin van die gelinkte lijst. 

En eigenlijk, laten we gewoon noodle door dat voor slechts een seconde. Waar zou het meest logisch? Als ik Alice voegen en ze eindigt bij de eerste plaats, dan probeer ik neem de naam van Aaron, en er is uiteraard een aanrijding, moet ik hem in het begin van de gelinkte lijst? Dat is op die eerste locatie, of aan het einde? 

PUBLIEK: [onverstaanbaar]. 

DAVID Malan: OK. Ik hoorde begin. Waarom bij het begin? 

PUBLIEK: [onverstaanbaar]. 

DAVID Malan: OK. Het is alfabetisch, dus dat is leuk. Dat is een goede eigenschap. Het zal me wat tijd besparen potentieel. Het zal me niet laten doen binair zoeken, maar ik zou ten minste in staat om uit te breken van een lus als ik realiseer, nou, ik ben weg Vroeger waren Aaron zou in deze zijn gesorteerd gelinkte lijst. Ik heb niet om mijn tijd te verspillen op zoek helemaal tot het einde. Dus dat is redelijk. Waarom anders zou u wilt invoegen de botsende naam bij de het begin van de lijst? Wat is dat? 

PUBLIEK: [onverstaanbaar]. 

DAVID Malan: Het kan lang duren om naar het einde van de lijst. En inderdaad, langer en langer. Hoe meer namen je plaatst dat beginnen met A, hoe langer dat keten gaat krijgen. Hoe langer gekoppeld lijst gaat krijgen. Dus je bent eigenlijk gewoon verspillen van uw tijd. Misschien bent u beter af handhaven constante invoegtijd, big O van 1, door altijd de botsende naam bij zetten het begin van de gekoppelde lijst en niet verontrustend zoveel over het sorteren. 

Wat is het beste antwoord? Het is onduidelijk. Het soort is afhankelijk van wat de distributie, wat de patroon is van de namen die u invoegt. Het is niet per se een duidelijk antwoord. Maar hier, nogmaals, is een ontwerp gelegenheid. 

Dus we bekeken toen dit ding, dat is echt de andere grote kans voor p-set 6. En beseffen, als je nog niet hebt, Zamyla duikt in deze beide, hash tabellen en probeert, in meer detail. En de video walkthrough is ingebed in p-set spec. Dit was een Trie - T-R-I-E. En wat interessant was hiervoor was dat de looptijd van het zoeken naar een naam, zoals Maxwell vorige keer, was groot O van wat? Wat is dat? 

PUBLIEK: Het aantal letters. 

DAVID Malan: Aantal letters. Ik hoorde twee dingen. Aantal letters en constante tijd. Dus laten we gaan met die eerste. Het aantal letters. Nou, deze datastructuur, recall, is als een boom, een stamboom, elk van waarvan de knopen bestaan ​​uit arrays. En die arrays zijn verwijzingen naar andere dergelijke knooppunten of soortgelijke arrays in de boom. 

Dus als we wilden dan bepalen of Maxwell is in hier, zou ik gaan naar de eerste matrix, op de top van de boom, de zogenaamde wortel, bovenop de Trie, en volg de m aanwijzer, dan is het een pointer, dan x, w, e, l, l. En dan als ik zie wat speciaal symbool, hier aangeduid als een driehoek. In code ziet u stellen wij voor dat u geïmplementeerd als een bool, gewoon zeggen ja of nee, een woord stopt hier. 

Nou, zodra we weg naar M-A-X-W-E-L-L, voelt als zeven, misschien acht als we gaan nog een verleden, acht stappen om Maxwell vinden. Of laten we het noemen K. Maar herinner laatste tijd, ik betoogd dat als er realistisch een maximum lengte van de woord, zoals 40-sommige-oneven tekens, een maximumlengte impliceert een constante waarde. Dus echt, ja, het is technisch big O van 8 of 7, of echt grote O van K. Maar als er een eindige pet op wat K zou kunnen zijn, het is een constante. En dus is het grote O van 1 op het einde van de dag. 

Niet in de echte wereld. Niet wanneer u daadwerkelijk beginnen met kijken uw klok als uw programma's lopen. Het is absoluut gaat een beetje te zijn langzamer dan echt constant tijd met een stap. Het gaat om zeven of acht stappen, maar dat is veel, veel beter dan een algoritme zoals grote O van n die afhankelijk van de grootte van wat in de gegevensstructuur. 

Let op de kop is hier dat we kunnen invoegen een miljoen meer namen in deze datastructuur, maar hoeveel meer stappen gaat het om ons te vinden Maxwell in dat geval? Geen. Hij is onaangetast. En tot nu toe, ik denk niet dat we hebben gezien een voorbeeld van een datastructuur of een algoritme dat volledig was beïnvloed door externe gedrag zoals dat. Maar dit kan niet verbazingwekkend. Dit kan niet de enige oplossing zijn de p-set 

En het is niet. Dit is niet noodzakelijkerwijs de gegevens structuur moet je aangetrokken tot, want zoals hash tabellen, afweging. Wat is de prijs die u betaalt hier? Geheugen. Ik bedoel, dit is een gruwelijke hoeveelheid geheugen. En je kunt niet helemaal zien hier omdat de auteur van deze foto uiteraard afgeknotte Alle matrices, en wij niet ziet veel A's en B en C en Q's en Y's en Z in deze arrays. Maar ze zijn er. 

Elk van deze knooppunten een hele reeks van ongeveer 26 of meer bytes, elk waarin een letter staat. 27 in ons geval, zodat we kunnen ondersteunen apostrof in het probleem set. Dus dit datastructuur is echt, echt dicht en breed. En dat alleen al zou kunnen eindigen vertragen dingen neer, of in ieder geval kost je een veel meer ruimte. Maar nogmaals, kunnen we trekken vergelijkingen hier. 

Herinneren een tijdje terug, we veel bereikt meer spannende lopende tijd in het sorteren wanneer we gebruik merge sort, maar de prijs We betaalden te bereiken n log n voor samenvoegen sorteer vereist dat we uitgeven meer welke bron? Meer ruimte. We hadden behoefte aan een secundaire array kopiëren mensen in, net als we hebben hier op het podium. Dus nogmaals, geen duidelijke winnaars, maar enkel subjectieve ontwerp beslissingen worden gemaakt. 

Oke. Dus hoe zit dit? Herkent iemand die D-Hall? OK. Dus drie van ons doen. Mather House. Dus dit is voor Mather's dineren. Ik wed dat alle eetzalen hebben stapels trays als deze. En dit is eigenlijk representatief van iets wat we hebben natuurlijk al gezien. We noemden het letterlijk een stapel. En de stack, in termen van uw geheugen van de computer, is de plaats waar de gegevens gaat terwijl functies worden genoemd. 

Bijvoorbeeld, wat voor soort dingen gaan op de stapel ten opzichte van de geheugen layout die we hebben besproken in weken verleden? Wat is dat? 

PUBLIEK: Oproepen naar functies. 

DAVID Malan: Het spijt me. 

PUBLIEK: Oproepen naar functies. 

DAVID Malan: Gesprekken naar functies, maar specifiek, wat er in elk van die frames? Wat voor dingen? Yeah. Zodat lokale variabelen. Wanneer we nodig hadden een aantal lokale opslag, als een argument, of int I, of int temp, of wat dan ook de lokale variabel is, waar we zijn geweest zetten dat op de stapel. En we noemen het een stapel omdat van die gelaagdheid idee. Gewoon een soort overeenkomsten met de werkelijkheid, het begrip daarvan. 

Maar het blijkt dat een stapel kan ook worden beschouwd als een gegevensstructuur, een alternatief voor een matrix, een alternatief een gekoppelde lijst. Iets conceptueel interessanter dat nog kan worden uitgevoerd met behulp van beide dingen, maar het is een ander soort datastructuur ondersteunen, echt, maar twee operaties. Maar u kunt toevoegen aan liefhebber functies dan deze. Maar dit zijn de basics - push en pop. 

Het idee van een stack is dat als ik hebben hier, met of zonder Annenberg wetende, een lade van naast de deur met het nummer 9 op. Dus gewoon een int. En ik wil dit duwen op de data structuur, die nog leeg is. Beschouw dit de bodem van de stapel. Ik zou dit nummer 9 te duwen op de stapelen, en nu is het daar. 

Maar het interessante ding over een stapel is dat als ik nu wil duwen een andere waarde, zoals 17, en ik duw deze op de stapel, ik ga doen het enige intuïtieve ding, ik ben gewoon gaan om het recht te zetten, waar wij mensen zou geneigd om het te zetten, op de top. Maar wat is interessant nu is, hoe krijg ik om 9? Weet je, ik doe niet zonder enige moeite. 

Dus wat is er interessant aan een stack is dat door het ontwerp, het is een LIFO datastructuur. Domme manier van het beschrijven last in, first out. Dus het laatste nummer in op dit moment was 17. Dus als ik iets wil knallen van de stack, het kan alleen worden 17. Dus er is een verplichte volgorde van activiteiten hier, waar het laatste item moet in de eerste buiten. Vandaar het acroniem, LIFO. 

Dus waarom zou dit nuttig zijn? Zijn hun contexten waarin je zou wil een datastructuur als deze? Nou, het is zeker nuttig geweest binnenkant van een computer. Dus besturingssystemen dit duidelijk te gebruiken soort datastructuur stacks. We zullen ook zien hetzelfde idee als het gaat om webpagina's. Dus deze week en volgende week en daarbuiten, en als je beginnen met de uitvoering web pagina's in een taal genaamd HTML, kunt u gebruikt, namelijk gegevensstructuur zoals Dit om te bepalen of de pagina is correct geformatteerd. Want we zullen zien alle webpagina's volgen een soort van hiërarchie, een inkeping die aan het eind van de dag, een boomstructuur onder de motorkap. Dus meer op dat in slechts een beetje. 

Maar voor nu, laten we voorstellen voor een ogenblik, hoe zouden we gaan over wat neerkomt op wat een stack is? Laat ik stel voor dat we de uitvoering van een stapel met code zoals deze. Dus een stapel gaat erin om twee dingen, een array, genaamd trays, alleen in overeenstemming te zijn met de demo. En elk van de items in die array gaat om een ​​type int zijn. En de capaciteit is vermoedelijk wat? Want ik heb niet geschreven de volledige definitie hier. 

Het is waarschijnlijk de maximale grootte van de matrix. En het is waarschijnlijk verklaard als een scherpe voorschriften op het begin van het bestand, sommige soort van constante zoals gesuggereerd door de loutere kapitalisatie. Dus ergens capaciteit wordt gedefinieerd zoals de maximale grootte. Ondertussen, in de datastructuur bekend als een stapel zal er een geheel getal alleen bekend gewoon als maat. 

Dus als ik deze vertegenwoordigen nu pictorially, laten we veronderstellen dat deze hele zwarte doos vertegenwoordigt mijn stack. Binnenkant van het is twee variabelen. Dus ik ga naar de loting eerste de grootte. En de tweede ik ga op te stellen als een array. 

Maar gewoon om dingen ordelijk te houden, normaal zou ik een array tekenen als dit, maar het is wel leuk als we overeenkomen met de werkelijkheid, of overeenkomen met het mentale model. Dus laat me in plaats trekken de array verticaal, dat is gewoon, weer, vertolking kunstenaar. Maakt niet echt uit wat het is onder de motorkap. En we zullen zeggen dat, bij verstek, capaciteit gaat worden drie. Dus dit zal zijn locatie 0, dit zal plaats 1, dit zijn zal zijn plaats 2. 

Als ik omkopen met een stressbal, zou iemand willen komen en uitvoeren van de boord hier voor slechts een moment? OK, eerst zag je hand. Kom maar naar boven. Oke. Dus ik denk dat het Steven. Kom maar naar boven. Oke. 

Maar stel nu dat we terugspoelen naar de oorspronkelijke toestand van de wereld waar ik hebben net uitgeroepen tot een stapel, en het is gaat worden van de capaciteit drie. Maar omvang is nog niet bepaald. Trays is nog niet bepaald. Dus eerst een paar vragen. En laat me je een microfoon, zodat u kunt deelnemen actiever in deze. 

Dus wat is de binnenkant van omvang op dit moment in de tijd als alles wat ik heb gedaan is verklaarde een stapel met een regel code? 

STEVEN: Niet veel. 

DAVID MALAN: OK, niet veel. Weten we wat er binnen in omvang, weten we wat er in zit van deze array hier? 

STEVEN: Gewoon willekeurige code, toch? Net - 

DAVID MALAN: Ja, ik ga noem het code, maar willekeurig - 

STEVEN: Things. 

DAVID Malan: Dingen als willekeurig 

STEVEN: Bits. 

DAVID MALAN: Bits, toch? Dus vuilnis waarden, toch? Dus permutaties van 0 en 1's. Restanten van vorige gebruiksmogelijkheden van dit geheugen. En we weten niet echt wat de waarden zijn, zodat we ze meestal trekken als vraagtekens. 

Dus het eerste wat we vermoedelijk gaat te willen doen hier - en laat me dit gebied binnen van er een naam - trays. Wat moeten we vermoedelijk initialiseren omvang om als we willen begint met deze stack? 

STEVEN: Tray is sub 3. 

DAVID MALAN: Dus, OK. Om duidelijk te zijn, wordt de capaciteit verklaard elders drie. En dat is wat ik heb gebruikt de matrix wijzen. Size gaat verwijzen naar hoeveel trays zijn op de stack. 

STEVEN: Zero. 

DAVID Malan: Dus het moet nul zijn. Ga zo door, en bij elke vinger, trek een nul in grootte. Oke. Dus nu, wat er in deze hier, weten we niet. Dit zijn eigenlijk gewoon vuilnis waarden. Dus we konden vraagtekens te tekenen, maar laten we het bord schoon voor nu omdat het niet uit wat er staat. We hoeven niet aan de array te initialiseren om het even wat, want als we weten dat de grootte van de stapel nul is, goed, we moet niet op zoek naar iets in deze array toch op dit punt in de tijd. 

Dus nu stel dat ik op de nummer 9 op de stack. Hoe moeten we de data structuur updaten binnenkant van deze zwarte doos? Welke waarden moeten veranderen? 

STEVEN: Binnen - de grootte? 

DAVID Malan: OK. Maat zal wat worden? 

STEVEN: Maat zou een te zijn. 

DAVID Malan: OK. Dus maat zal worden een. Dus je kunt dit doen op een paar manieren. Laat ik u, nu uw vinger is een gum. Oke. Dan is nu je vinger is een borstel. Oke. En nu wat er moet veranderen, uiteraard, in de datastructuur? 

STEVEN: We gaan uit bottom tot 9. 

DAVID Malan: 9. OK, Good. Dus nog steeds niet uit wat er op het locatie een of twee omdat ze vuilnis waarden, maar we moeten niet de moeite zoek er omdat de grootte is ons te vertellen dat alleen het eerste element is eigenlijk legitiem. Dus nu heb ik duw 17 op de lijst. Wat gebeurt er met deze foto? 

STEVEN: Dus grootte zal gaan naar twee. 

DAVID Malan: OK. Je bent gum - oops. Je bent een gum. 

STEVEN: Eraser. 

DAVID Malan: Je bent een borstel. 

STEVEN: Brush. 

DAVID Malan: OK. En wat nog meer? 

STEVEN: En dan hebben we - 

DAVID Malan: We geduwd 17. 

STEVEN: Wij houden 17 op de top, dus - 

DAVID MALAN: OK, goed. 

STEVEN: - zet het neer. 

DAVID Malan: Oke. Het wordt steeds gemakkelijk. Ik ben niet van plan om u te helpen deze keer. Duwen 22. 

STEVEN: Gedaan. Becoming een gum. Ik ben steeds een borstel. En dan zet ik 22. 

DAVID Malan: 22. Excellent. Dus nog een keer. Ik ga nu duwen op de stapel 26. 

STEVEN: Ooh. Oh gosh. Je bent echt gevangen me off guard. 

DAVID Malan: Je deed het niet zien aankomen? 

STEVEN: Ik heb niet zien aankomen. Konden we opnieuw initiële capaciteit? 

DAVID Malan: Dat is een goede vraag. Dus we hebben soort van geschilderde onszelf in een hoek hier. Er is echt geen goed uit voor Steven omdat we deze array hebben toegewezen statisch, zo te zeggen, binnen van de gegevensstructuur. En we hebben in wezen hard gecodeerd het van grootte van drie. Dus we kunnen niet echt herverdelen het. 

We konden als we gingen terug in, we geherdefinieerd trays met een pointer die zijn we vervolgens gebruiken malloc om de hand geheugen om. Want als we het geheugen van de hoop via malloc, we kan dan bevrijden. Maar voordat het vrijmaken, konden we herverdelen van een groter stuk van het geheugen, bijwerken van de wijzer, enzovoort. Maar voor nu, dit is echt het beste kunnen we doen. Push en pop zijn vermoedelijk gaan te hebben om een ​​fout signaal. 

Dus bijvoorbeeld onze implementatie van push een bool konden terugkeren die eerder teruggekeerd true, true, true. Maar de vierde keer, het gaat hebben valse keren, bijvoorbeeld. Oke. Zeer goed gedaan. Gefeliciteerd. Je hebt vandaag verdiend uw stress bal. 

[Applaus] 

STEVEN: Dank je wel. 

DAVID Malan: Dank je wel. OK, dus dit lijkt niet veel van een stap voorwaarts, toch? We beschreven deze datastructuur. Het is al overtuigend, toch? Besturingssystemen bevalt. Blijkbaar het web kan gebruik van maken, en andere toepassingen nog. Maar wat een domme beperking dat we terug naar soort van week twee limieten waar we hebben vaste afmetingen arrays. 

Dus er zijn inderdaad een paar manieren waarop we kunnen dit oplossen. We konden dynamisch toewijzen van de array, niet door harde codering als ik heb hier gedaan, maar in plaats daarvan opnieuw te verklaren dit, gewoon om duidelijk te zijn, zoals zoiets als dit. Int * trays, niet beslissen Op nog een capaciteit. Maar toen ik verklaar de stapel elders in mijn code, kon ik dan bellen malloc, krijgen het adres van een brok van geheugen, en ik kon toewijzen dat adres te laden. 

En dan, want het is gewoon een brok van geheugen, kon ik blijven vierkant gebruiken haakjesnotering op de gebruikelijke manier. Want nogmaals, er is een soort van deze functionele equivalent arrays en delen van het geheugen die komen terug van malloc. We kunnen een behandelen als de andere met behulp van pointers of square bracket notatie. Dus dat is een benadering. 

Maar hoe anders zouden we dit implementeren dezelfde datastructuur, mogelijk? Rechts? Ik heb het gevoel dat we gewoon dit opgelost probleem als een week geleden. Wat was de oplossing voor dit probleem dat Steven tegenkwam? Dus gelinkte lijsten, rechts. 

Als het probleem is dat we schilderen onszelf in een hoek door het toewijzen vooraf te weinig geheugen we dan hebben om een ​​of andere manier omgaan met, goed, waarom niet gewoon vermijden dat helemaal af te geven? Waarom niet gewoon verklaren trays te zijn van een pointer naar een knooppunt, ergo een gelinkte lijst, en dan gewoon nieuwe knooppunten toe te wijzen elke keer dat Steven nodig is om een ​​fit nummer in de gegevensstructuur. 

Zodat het beeld zou moeten veranderen. Het gaat niet zo schoon en zo simpel als gewoon een array van drie ints. Nu het gaat om een ​​pointer naar een te zijn struct, en dat struct gaat hebben een int en een volgende pointer. Het zal leiden via die pointer aan een andere struct nog zo'n struct. Zodat het beeld zou eigenlijk een beetje Messier. En we zouden hebben pijlen koppelverkoop alles samen. 

Maar dat is prima, rechts, want we hebben gezien hoe dit te doen. En als je eenmaal wennen uitvoering van iets als een gekoppelde lijst, die je moet doen als je kiezen om een ​​hash table implementeren met aparte chaining voor p-set 6, kunt u gebruiken als een bouwsteen, of een ingrediënt, of in Scratch spreken, een procedure, iets dat je, je gemaakt uw eigen puzzelstukje die u vervolgens kunt hergebruiken. Dus afwegingen, maar mogelijke oplossingen dat we eigenlijk eerder gezien. 

Dus heel vaak, dit zie je elke jaar of twee toen Apple releases iets nieuws, en alle gekke mensen line-up buiten de Apple slaan om hun marginale kopen upgraden van hardware. Ik zeg dit, het is OK, omdat Ik ben een van die mensen. Dus wat voor soort data structuur zou dit werkelijkheid te representeren? 

Nou, laten we noemen het een wachtrij, een lijn. So British zou het meestal een bel wachtrij toch, dus het is een mooie naam. En de twee operaties die een wachtrij zullen steunen we een enqueue bellen werking en een dequeue operatie, die vergelijkbaar zijn geest te duwen en te knallen. Het is gewoon soort van verschillende in conventie, wat we roepen deze. Maar om iets enqueue betekent om toe te voegen of steek hem in de datastructuur. Om dequeue betekent om het te verwijderen. Maar terwijl een stapel was een LIFO data structuur, een wachtrij is een eerste in, first out datastructuur. 

Als u bent de eerste persoon in de rij, je zal de eerste persoon om te krijgen uit lijn en koop uw nieuwe apparaat. Stel je voor hoe overstuur deze mensen zouden zijn als Apple gebruikt in plaats van een stapel voor bijvoorbeeld de uitvoering picking up van uw nieuwe speeltje. Dus wachtrijen zinvol, zeker, en kunnen we denken aan allerlei toepassingen, vermoedelijk voor wachtrijen vooral als je wilt eerlijkheid. Dus hoe kunnen we de uitvoering van deze als een datastructuur? 

Nou, ik stel voor dat we misschien moet het op deze manier doen. Dus ik ga nu nummers. Dus zullen we het simpel en niet te houden se spreken in termen van trays. Gewoon nummers die mensen van gekregen. Capaciteit gaat, nogmaals, bevestig de totaal aantal mensen dat kan worden in deze lijn, als drie of welke andere waarde. 

Maar ik stel voor dat ik nodig heb om bij te houden niet alleen de grootte van de wachtrij, hoeveel dingen zijn in het. Dus grootte is de huidige omvang, capaciteit is de maximale grootte. Gewoon weer, nomenclatuur volgens afspraak. Waarom moet ik een extra int binnen van een wachtrij bij te houden van wie er in te houden voorkant van de lijn? Waarom moet ik dat doen in dit geval? 

Nou ja, hoe is deze foto gaat veranderen? Ik kan waarschijnlijk het meest hergebruiken van deze foto. Laat me gaan en wist wat hier is. We zullen dit een iets te geven andere naam hier. Laten we te ontdoen van de 17, laten we ontdoen van de 9, laten zich te ontdoen van de 3. En voegen we een ander ding. Ik stel voor dat ik nodig heb om bij te houden de voorkant van de lijst, dat is gewoon gaat een int als goed. En we gaan het simpel te houden. Geen gekoppelde lijst voor nu. 

We zullen toegeven dat we gaan bump up tegen deze limiet. Maar wat wil ik zien gebeuren deze keer? Dus stel ik ga je gang en de eerste persoon komt in de rij, en het is het getal 9. We hebben stress ballen. Kan ik steel, zeg, twee of drie personen? Een, twee, drie? Kom maar naar boven. Recht van voren, omdat we maken dit een snelle. 

Ieder van jullie is nu gaat worden een fan jongen in de rij bij Apple. Je zal niet worden ontvangen van Apple-hardware aan het einde van deze wel. Oke. Dus je nummer 9 bent, ben je nummer 17, nummer 22. Dit zijn willekeurige getallen, zoals student-id's of zo. En in slechts een moment, laten we beginnen om te beginnen met het toevoegen van dingen. En ik zal het bestuur hier deze keer draaien. 

Dus in dit geval, heb ik geïnitialiseerd de voorzijde zijn - Ik heb eigenlijk niet echt schelen wat de voorkant is, omdat de grootte nul. Dus dit kan net zo goed gewoon wel een vraagteken. Dit zijn allemaal vraagtekens. Dus nu gaan we beginnen om daadwerkelijk wat te zien mensen in de rij bij de winkel. 

Dus als nummer 9, je bent de eerste er op 5:00, ga je gang en line-up, of de avond ervoor. OK. Dus nu 9 is hier. Dus 9 is aan de voorzijde van de lijst. Dus ik ga om verder te gaan en bij te werken de grootte van deze stroom data structuur niet meer zijn 0, maar om 1. Ik ga 9 zetten op de voorzijde van de lijst. Laat me ga je gang en schakelen het scherm dus kunnen we aan ons voorbij zien hier. 

En nu wat wil ik te zetten op de voorkant? Ik ga om bij te houden dat de vooraan in de wachtrij nu is op locatie 0. Want wat is de volgende gaat gebeuren? Nou, stel dat ik nu enqueue 17 ook. Dus hop in de rij daar. En nogmaals, het soort deur naar de winkel gaat om hier te zijn. Zo nu heb ik toegevoegd 17. En hoewel deze jongens blokkeren het scherm, dat is OK, omdat we het hier kunnen zien up. Sorry. 

PUBLIEK: We kunnen bewegen - 

DAVID MALAN: Nee, dat is OK. Het is enorm daarboven. Dus 17 is nu de binnenkant van de wachtrij. Ik moet werken die velden nu al? OK, zeker grootte. En hoe zit het voor? OK, nee. Voorzijde moet niet veranderen, omdat in tegenstelling tot een stapel, we willen eerlijkheid te behouden. Dus als 9 kwam in de eerste, willen we 9 de eerste uit de lijn zijn en in de winkel. 

In feite, laten we zien dat. Voordat we 22 voegen, laten we ga je gang en dequeue 9. Hoe heet je ook alweer? 

PUBLIEK: Jake. 

DAVID Malan: Jake gaat nu worden gedequeued. Zo krijg je te lopen in de winkel. En alsof dat de winkel is daar. Dus wat nu nodig heeft - dit-dit-zegt! Wat moet er nu gebeuren? Beslissing ontwerp. Dus geen slechte instinct, maar - hoe heet je ook alweer? 

PUBLIEK: David. 

DAVID Malan: David. Dus wat deed David? Hij probeerde te sorteren van de gegevens vast structuur en beweging van zijn locatie in de voormalige locatie Jake's. En dat is prima als we bereid zijn om dat te accepteren als een implementatie detail. Maar laten we eerst het actualiseren van de gegevens structuur voordat we dat doen. Want ik ben niet aardig vinden het idee van alle de mensen verschuiving in deze lijn. 

Het is geen big deal als David doet het met een stap, maar nogmaals, denk terug aan toen we acht vrijwilligers op het hebt gehad podium en we hebben gedaan, zoals het inbrengen sorteren, waar we moesten beginnen bewegen iedereen. Dat zette duur, toch? Dat maakt me ineenkrimpen over grote O van n, grote O van n kwadraat weer. Het is het gevoel niet meer een ideale uitkomst. 

Dus laten we gewoon dit updaten. Zodat de grootte van de wachtrij niet meer 2. Het is nu gewoon 1. Maar ik kan nu iets updaten Ik heb niet eerder updaten, de voorzijde van de lijst. Ik kon alleen maar zeggen, is dat de locatie 1? Dus nu hebben we vuilnis waarde hier, garbage waarde hier, en David in de midden van deze rotzooi. Maar de gegevensstructuur nog intact. 

En in feite, ik weet niet eens nodig om veranderen voormalig nummer Jake's 9, want who cares. Ik heb genoeg informatie nu in de formaat dat ik weet dat er een persoon in deze wachtrij. En ik weet dat die persoon is op locatie 1, niet 0. Ik ben niet te tellen. Dus 1 ook. Zodat de data structuur is nog steeds OK. 

Nou, wat gebeurt er nu? Let's enqueue - wat is je naam? 

PUBLIEK: Callen. 

DAVID Malan: Callen. Laten we enqueue een Callen, en 22 is nu in de wachtrij. Dus nu wat er moet hier veranderen? Voorzijde is niet van plan om veranderen, natuurlijk. Grootte gaat veranderen om weer 2. En 22 eindigt hier, 9 is nog steeds aanwezig, maar het is in feite een garbage waarde nu. Het is gewoon een overblijfsel van Jake verleden. 

Dus nu wat gebeurt er als Ik dequeue David? Een laatste operatie, dequeue David. We kunnen verschuiven, maar ik stel voor laten we doe zo weinig mogelijk werk. Nu is mijn datastructuur gaat terug in grootte van 2 naar 1. Maar de voorkant van de wachtrij Nu wordt 2. Ik hoef niet naar deze nummers te veranderen gewoon nog niet, omdat ze gewoon huisvuil waarden. 

Maar nu wat gebeurt er? Stel dat ik enqueue mezelf, 26? Ik voel me alsof ik behoor dan hier. Dus ik word enqueued. Dus ik soort behoor hier. En ook al heb je niet helemaal waardeer dit visueel op het podium, want we hebben genoeg ruimte, zou ik hier niet staan, waarom? 

PUBLIEK: Je bent out of bounds. 

DAVID Malan: Right. Ik ben out of bounds. Ik heb geïndexeerd buiten de grenzen van deze array. Ik moet echt in een van de drie mogelijke locaties. Nu, waar is het meest natuurlijke om te gaan? Ik stel voor dat we leveraged een week een truc. De mod operator, percentage. Want ik ben technisch staan ​​aan locatie 3, maar ik doe 3 mod capaciteit, dus 3, een procent teken, 3 - capaciteit is 3. Wat is dat? Wat is de rest als verdeel je 3 bij 3? 0. 

Zodat ik zet waren Jake was, dat is eigenlijk goed. Dus nu de uitvoering van dit ding gaat wel een beetje hoofdpijn. Het is eigenlijk gewoon een regel van hoofdpijn, van de code. Maar in ieder geval nu is er vuilnis waarde hier, maar er is twee legitieme ints hier. En ik beweer dat nu hebben we gedaan precies wat we nodig hebben om zo lang doen we veranderen wat Jake's waarde moest worden 26. 

We hebben nu voldoende informatie nog de integriteit deze gegevensstructuur. We zijn nog steeds soort van geluk toen we willen vier of meer totale voegen elementen, maar ik kan in ieder geval mooi te maken efficiënt gebruik van deze constante tijd, in feite. Ik heb geen zorgen te maken over het verschuiven iedereen, zoals neiging Davids was. 

Heeft u vragen over stapels, of deze wachtrij? 

PUBLIEK: Is de reden waarom je nodig hebt grootte, zodat u weet waar om een ​​persoon te hebben? 

DAVID Malan: Precies. Ik moet de grootte van de matrix weten want ik moet precies weten hoe veel van deze waarden zijn legitiem, en zodat ik kan vinden waar te zetten de volgende persoon. Precies. De grootte is - eigenlijk, we hebben dit nog niet updaten. Ikzelf toegevoegd op 26. De grootte is nu niet 1 maar 2. Dus nu dit inderdaad helpt mij vinden de van de lijst, die niet 0 is, niet 1, maar 2. De voorzijde van de lijst inderdaad nummer 22. Want hij kwam in de eerste, dus hij moet in de winkel worden toegestaan ​​voor mij, hoewel visueel sta ik dichter naar de winkel. 

Oke? Een applaus voor deze jongens en we zullen ze laten uit daar. 

[Applaus] 

DAVID Malan: ik kon laten u de lade te houden. We konden zien wat er gebeurt als je wilt, maar misschien ook niet. Oke. Dus wat nu betekent dat ons verlaten? Nou, laat me voorstellen dat er een enkele andere datastructuren we konden beginnen met het toevoegen aan onze tool kit die zal eigenlijk heel, heel relevant als We duiken in web-dingen. Die opnieuw, heeft een soort verbinding om bomen in de vorm van iets genaamd DOM, document object model. Maar we zullen meer van zien dat duurde niet lang. 

Laat me definitionally stel voor dat we nu wat je zou kunnen kennen als noemen boom meer van een stamboom, waar u wat voorouder op wortels van de boom. Een patriarchale of een matriarch op de top van de boom. Zonder hun echtgenoot, in dit geval. Maar we hebben nu wat we noemen kinderen, die knooppunten die hangen uit de linker kind of rechts kind, pijlen zoals hier afgebeeld. 

Met andere woorden, in een boom datastructuur in computer, een boom zero of meer knooppunten. Indien ten minste een knooppunt dat heet de wortel. Het zijn de dingen die visueel trekken we aan de top. En dat knooppunt, net als elk ander knooppunt, kan hebben nul, een, of twee, of drie, of hoeveel kinderen de gegevensstructuur ondersteunt. In dit geval, de wortel, de opslag waarde een, twee kinderen, 2 en 3, zodat we over het algemeen noemen 2 links kind en 3 het juiste kind. 

En toen we naar beneden naar 5, 6, en 7, 6 kan de middelste kind genoemd. Als je vier kinderen, het wordt verwarrend. Dus we stoppen met dat soort van snelkoppeling verbaal. Maar het is eigenlijk gewoon een stamboom. En de bladeren hier zijn de knooppunten die hebben zelf geen kinderen. Ze hangen af ​​van de onderkant van de boom. 

Dus hoe kunnen we de uitvoering van een boom die heeft slechts twee kinderen maximaal? We noemen het een binaire boom. Bi opnieuw betekenis twee, in dit geval, net als met binaire. En dus het kan hebben nul, een, of twee kinderen maximaal. 

Ik stel voor dat we de uitvoering van het knooppunt voor die structuur met een int n, en dan twee wijzers, een zogenaamde links, een zogenaamde rechts. Maar die zijn gewoon leuk willekeurige conventies. En wat is er nu leuk, vooral als u soort worstelde conceptueel met recursie, of dacht dat het niet was echt een oplossing voor alles, vooral als je kon opraken van het geheugen. Nu praten we over gegevens structuren en algoritmen die het mogelijk maken ons te doorkruisen en te manipuleren, blijkt dat recursie komt terug in een veel meer dwingende zoniet mooie manier. 

Dus dit stel ik voor de implementatie van een Search-functie. Gegeven twee ingangen - dus denk aan dit als een zwarte doos. Gegeven twee ingangen, n, int, en pointer naar een boom, een pointer naar een knooppunt, of eigenlijk de wortel van een boom, ik bewering dat deze functie kan terugkeren waar of onwaar, dat waarde n is de binnenkant van deze boom. 

Wat is de binnenkant van deze zwarte doos? Nou ja, vier vestigingen. Het eerste net controleert. Als boom is null, net return false. Als er geen knooppunt, is er geen n, er is geen nummer, maar return false. Indien wel, n, de waarde die u op zoek bent voor, minder dan boom arrow n en alleen maar om duidelijk te zijn, wat betekent het als Ik schrijf boom en vervolgens op de pijl notatie, n? Precies. Het betekent dat dereferentie pointer genaamd boom. Ga daar heen, en dan krijg binnenkant van die knooppunt en krijg zijn gebied genaamd n. En dan vergelijken met de werkelijke n dat was overgegaan in Zoeken tegen. 

Als n kleiner is dan de waarde n in de boom node zelf, goed, Wat betekent dat? Dat betekent dat er niets op het eerste gezicht. Rechts? Net als wanneer je een array van waarden, zou u willen binaire toepassing zoeken als een vorm van verdeel en heers. Maar wat aanname hebben we moeten ervoor voor binaire zoeken om te werken op alle in het telefoonboek en eerdere voorbeelden? 

Hoe te sorteren. Dus laten we het verfijnen van de definitie van de boom hier niet om gewoon een boom, die kan worden hebben een aantal van de kinderen. Niet alleen een binaire boom, dat kan hebben 0, 1, of 2 maximaal. Maar als een binaire zoekboom, of BST, dat is gewoon een mooie manier om te zeggen een binaire boom zodat elk knooppunt linker kind, indien aanwezig, is minder dan het knooppunt. En elke knoop heeft gelijk kind, indien aanwezig, groter dan het knooppunt zelf. 

Dus met andere woorden, als je om te tekenen de boom uit, alle getallen zorgvuldig afgewogen als deze, zodat als heb je 55 als de wortel, kan 33 gaan links daarvan omdat hij minder dan 55. 77 kan naar haar recht, omdat is groter dan 55. Maar let nu op, dezelfde definitie, het is een recursieve definitie verbaal, heeft te gelden voor 33. 33's linker kind moet lager zijn dan het zijn, en 33's rechts kind, 44, moet zijn groter dan. 

Dus dit is een binaire zoekboom, en Ik stel voor, met behulp van een beetje recursie, kunnen we nu vinden n. Als n kleiner is dan de waarde die n huidige knooppunt, ik ga om te gaan gang en trap, om zo te zeggen, en gewoon terug wat het antwoord is van zoeken naar de n linker kind boom. Let nog eens op, deze functie alleen verwacht een knooppunt ster, een pointer naar een knooppunt. Dus zeker kan ik gewoon doen boom pijl naar links, wat zal leiden me naar een ander knooppunt. Maar wat is dat knooppunt? 

Nou, volgens deze verklaring, links is slechts een pointer, zodat alleen betekent dat ik overgaan naar de zoekfunctie een andere aanwijzer, namelijk degene die vertegenwoordigt boom mijn linker kind. Dus in dit geval de aanwijzer 33, indien dit is onze steekproef ingang Ondertussen, als n is groter dan de waarde n aan de huidige knooppunt in de boom, dan ben ik ga je gang en de trap te gaan in de andere richting en gewoon zeggen, ik doe niet weten of deze waarde n in de structuur, maar ik weet dat als het is, het is in mijn rechts tak, zo te zeggen. Dus laat me call recursief zoeken, het passeren van een n weer, maar passeren in een pointer naar mijn rechter kind. 

Met andere woorden, als ik op dit moment op 55 en ik ben op zoek naar 99, ik weet dat 99 groter is dan 55, dus net als ik scheurde het telefoonboek weken geleden en we ging rechts, eveneens zijn wij ga hier gaan. En ik weet niet of het aan mijn rechter kind, en het is niet, 77 is er, maar Ik weet dat het in die richting. Dus bel ik zoek op mijn rechter kind, 77, en laat zoeken figuur uit daar als 99 in deze arbitraire Zo is er eigenlijk. 

Anders, wat is het laatste geval is? Als boom is null is een geval. Als n kleiner is dan het huidige knooppunt waarde ander geval. Als n groter is dan de huidige node waarde is een derde geval. Wat is de vierde en laatste geval? Ik denk dat we uit gevallen, toch? Het moet dat n in de huidige knooppunt dat ik op. 

Dus als ik ben op zoek naar 55 op dit punt in het verhaal, die tak van de boom zou return true. Dus wat is interessant hier is dat we eigenlijk, in tegenstelling tot de weken voorbij, we soort van twee base gevallen. En ze hoeven niet te worden alle aan de top. De top is een referentiemodel want als de boom is null, er is niets te doen. Net terug van een hard gecodeerde waarde false. 

De onderste tak is een soort van de standaard, waarbij als wij hebben gecontroleerd null, hebben we gekeken of het zou moeten zijn vertrokken, maar het moet niet, we hebben gecontroleerd of het recht mag, maar moet niet duidelijk het moet precies waar we zijn. Dat is een base case. Dus er is twee recursieve gevallen daar ingeklemd in het midden. Maar ik zou hebben geschreven dit in willekeurige volgorde. Ik dacht dat het soort voelde natuurlijke eerst controleren voor een mogelijke fout, controleer dan linksaf, check dan rechts, dan gaan ervan uit dat je op het knooppunt je bent eigenlijk op zoek naar. 

Dus waarom zou dit nuttig zijn? Zo blijkt het - en laat me springen naar een teaser hier is dat in het web. We gaan aan de slag met geen programmeertaal op het eerste, maar een opmaaktaal. Een opmaaktaal zijnde een die in dezelfde geest te programmeren taal, maar het niet geven u de vermogen om jezelf te uiten logisch. Het geeft alleen de mogelijkheid om structureel te uiten jezelf. 

Waar wil je iets zetten op de pagina, de webpagina? Welke kleur wil je het maken? Welke lettergrootte wil je het maken? Welke woorden heb je eigenlijk wil op de webpagina? Dus dat is een opmaaktaal. Maar dan zullen we heel snel invoeren JavaScript, dat is een volwaardige programmeertaal. Zeer vergelijkbaar syntactisch in uiterlijk naar C, maar het zal wat hebben nice, krachtiger, gebruiksvriendelijke functies. 

En een van de frustraties bij deze punt in het semester is dat we zullen snel te implementeren speller in veel minder coderegels gebruik van andere talen dan C zelf maakt, maar voor de rede's we zullen snel begrijpen. Dit zal de eerste dergelijke webpagina. Het zal volledig underwhelming, de eerste die we maken. Het wil alleen maar zeggen, hello wereld. Maar als je nog nooit hebt gezien eerder is HTML, HyperText Markup Language. 

Als je naar een bepaalde menu-optie in vrijwel elke browser, op een webpagina op het internet, kunt u de HTML- dat sommige mensen schreven aan creëren die webpagina. En het waarschijnlijk niet uitzien als korte of zo netjes als dit. Maar het zal het patroon van deze te volgen geopend beugels en schuine strepen en letters en cijfers mogelijk. 

Ik dacht, ik geef je een teaser van wat je zult kunnen doen na het nemen van CS50. Laat me gaan naar cs.harvard.edu / rob, onze eigen Rob Bowden's homepage. Hij maakte deze voor ons. Dus je zult snel in staat om dat te doen. En ook, wat je gehoord vanmorgen - wat je hoorde vanmorgen - 

[HAMSTER DANCE MUSIC] 

- U zult in staat zijn om dit te maken. Dat wacht ons op woensdag. Wij zullen u dan zien. 

[HAMSTER DANCE MUSIC] DAVID Malan: Bij de volgende CS50 -