[Muziek] 

ANDI Peng: Welkom in week 6 van de sectie. We afgeweken van onze standaard sectie tijd van dinsdag middag om deze mooie zondagochtend. Dank u voor iedereen die toegetreden mij vandaag, maar serieus, een applaus. 

Dat is een vrij grote inspanning. Ik bijna niet maken het zelfs in de tijd, maar het was ok. Dus ik weet dat jullie allemaal hebben het gewoon aan de quiz. Allereerst van harte welkom om de keerzijde van dat. 

Ten tweede, zullen we over praten. We praten over de quiz. We zullen praten over hoe je doet in de klas. Je zult wel goed. Ik heb je quizzen voor u eind hier dus als jullie willen nemen een naar kijken, helemaal prima. 

Zo snel voordat we beginnen, de agenda voor vandaag als volgt. Zoals u kunt zien, zijn we in principe een snelle afvuren door middel van een hele hoop van datastructuren echt, echt, echt snel. Dus als zodanig, zal het niet worden super interactief vandaag. Het zal aan mij liggen soort schreeuwen dingen die je, en als ik verwarren, als ik ga te snel, laat het me weten. Ze zijn gewoon verschillende data structuren en kader van PSET deze komende week, zult u worden gevraagd om een ​​van hen uit te voeren, misschien twee them-- beiden in uw PSET. OK, dus ik ga gewoon beginnen met een aantal aankondigingen. We zullen gaan over stacks en wachtrijen meer in diepte dan wat we voor de quiz deden. We zullen gaan over gekoppelde lijst opnieuw, nogmaals, meer in de diepte dan wat we hadden voor de quiz. En dan zullen we praten over hash tafels, bomen en probeert die zijn allemaal erg nodig zijn voor uw PSET. En dan gaan we over een aantal handige tips voor pset5. 

OK, dus quiz 0. Het gemiddelde was 58%. Het was erg laag, en dus jullie allemaal deed zeer, zeer goed in overeenstemming met dat. 

Vrij veel, vuistregel is als je binnen een standaarddeviatie van het gemiddelde vooral omdat we in een minder comfortabele sectie, je bent helemaal prima. Je bent op het juiste spoor. Het leven is goed. 

Ik weet dat het eng om te denken dat Ik heb als een 40% op deze quiz. Ik ga deze klasse mislukken. Ik beloof je, je bent niet naar de klasse mislukken. Je bent helemaal prima. 

Voor degenen onder u die dan kreeg het gemiddelde, indrukwekkend, indrukwekkend, als, serieus goed gedaan. Ik heb ze bij me. Voel je vrij om te komen hen aan het eind van de sectie. Laat me weten als je hebt problemen, vragen hen. Als we uw score verkeerd, laat het ons weten. 

OK, dus pset5, dit is echt een rare week voor Yale in de zin dat onze PSET is te wijten Woensdag op de middag met inbegrip het einde van de dag, dus het is eigenlijk theoretisch verschuldigde dinsdag op de middag. Waarschijnlijk niemand klaar op dinsdag op de middag. Dat is helemaal prima. We gaan kantooruren vanavond evenals maandagavond. En alle van de secties deze week daadwerkelijk worden omgezet in workshops, dus voel je vrij om pop in elke sectie die u wilt, en ze zullen soort mini-PSET zijn workshops voor hulp op dat. Dus als zodanig, dit is de enige sectie waar we lesmateriaal. Alle andere afdelingen zal worden gericht uitsluitend op de hulp van de PSET. Ja? 

Publiek: Waar zijn de kantooruren? 

ANDI Peng: Spreekuur tonight-- oh, goede vraag. Ik denk dat de kantooruren vanavond zijn in Wintertaling of Commons. Als u online CS50 controleren en ga je naar de kantooruren, Er moet een schema dat vertelt u waar ze allemaal zijn. 

Ik weet ook vanavond of morgen is wintertaling, en ik denk dat we hebben commons voor de andere nacht. Ik weet het niet zeker. Goede vraag. Controleer op CS50. 

Koele, vragen over de schema voor de komende als drie dagen? Ik beloof jullie als David zei, dit is de top van de heuvel. Jullie zijn er bijna. Slechts drie dagen. Krijgen daar, en dan gaan we allemaal naar beneden komen. We zullen een mooie CS-vrije pauze. Welkom terug. We zullen een duik nemen in het web programmering en ontwikkeling, dingen die zijn erg leuk in vergelijking een aantal van de andere psets. En het zal chill, en We zullen veel plezier hebben. We zullen meer snoep te hebben. Sorry voor snoep. Ik vergat snoep. Het was een ruwe ochtend. Dus jullie zijn er bijna, en ik ben echt trots op jullie. 

OK, dus stapelt. Die hield de vraag over Jack en zijn kleding op de quiz? Niemand? Oke dat is goed. 

Dus in wezen als je kunt foto Jack, deze man hier, houdt om de kleding te nemen uit de bovenkant van de stapel, en hij zet het terug op de stapel nadat hij heeft gedaan. Dus op deze manier, hij nooit lijkt te zijn om aan de onderkant van de stapelen in zijn kleding. Dus dit soort beschrijft de basisgegevens structuur hoe een stack is geïmplementeerd. 

Wezen, denk aan een stack eventuele stapel voorwerpen waar je dingen op de top, en ze dan pop je uit de top. Dus LIFO is de afkorting we graag om use-- Last In, First Out. En zo lang op de top van de stack is de eerste die naar buiten komt. En zo de twee termen we willen associëren met die push en pop genoemd. Als je iets op het duwen stapelen, en je pop een back-up. 

En dus ik denk dat dit soort van een abstract concept voor degenen onder u die willen zien als een daadwerkelijke uitvoering van deze in de echte wereld. Hoeveel van jullie hebben een essay geschreven misschien als een uur voordat het te wijten was, en je per ongeluk verwijderd een enorme deel van het, zoals per ongeluk? En wat aanvangen we gebruiken om het terug te zetten? Controle-Z, ja? Controle-Z, dus het aantal keren dat Controle-Z mijn leven heeft gered, heeft mijn kont opgeslagen, elke keer dat is uitgevoerd door middel van een stapel. 

In wezen alle informatie dat is op uw Word-document, het wordt geduwd en dook op wil. En dus in wezen wanneer u alles verwijderen, je pop een back-up. En dan, als je het nodig hebt weer op, u duw het, dat is wat de Control-C doet. En zo echte wereld functie hoe eenvoudige datastructuur kan helpen met uw dagelijks leven. 

Dus een structuur is de manier waarop we eigenlijk creëren een stapel. We typen definiëren structuur, en vervolgens we noemen het stapelen op de bodem. En binnen de stack, hebben we twee parameters welke wij in essentie manipuleren dus we hebben char ster strijkers capaciteit. 

Alles wat zij doet creëert een array dat we kunnen opslaan wat je wilt waarbij we de capaciteit kan bepalen. Capaciteit is gewoon de max hoeveelheid artikelen die wij in deze serie kan zetten. int grootte is de teller die blijft bijhouden hoeveel items zijn in de stack. Dus dan kunnen we bijhouden, A, zowel hoe groot de werkelijke stapel, en, B, hoeveel van die stapel we gevuld omdat wij niet willen over te overstromen wat onze capaciteit. 

Dus bijvoorbeeld, deze mooie vraag was op de quiz. In wezen hoe kunnen we duwen op de bovenkant van een stapel. Vrij eenvoudig. Als je er naar kijkt, we lopen door dit. Als [onverstaanbaar] omvang-- vergeet niet, wanneer u wilt een toegang parameter binnen een structuur, je doet de naam van de struct.parameter. 

In dit geval, s de naam van onze stack. Wij willen toegang tot de grootte van het, dus we doen s.size. Dus zolang de grootte is niet gelijk aan de capaciteit of zolang want het is minder dan de capaciteit, ofwel zou hier werken. 

U wilt toegang tot de binnenkant van je stack, zo s.strings, en je gaat naar dat nieuwe nummer gezet dat u wilt invoegen in daar. Laten we zeggen dat we willen Steek int n op de stapel, we konden s.strings doen, beugels, s.size gelijk aan n. Omdat de grootte is waar we Momenteel zijn er in de stapel als we gaan om te duwen het op, wij slechts toegang waar de grootte, de huidige volheid van de stack, en duwen we de int n op het. En dan willen we ervoor zorgen dat We zijn ook het verhogen van de grootte van de n, dus we kunnen bijhouden we hebben Een extra ding toegevoegd aan de stack. Nu hebben we een grotere omvang. Betekent dit hier te maken zin om iedereen, hoe logisch het werkt? Het was een beetje snel. PUBLIEK: Kunt u gaan over de s.stringss.strings [s.size] weer? ANDI Peng: Tuurlijk, dus wat doet s.size ons momenteel te geven? Publiek: Het is de huidige omvang. ANDI Peng: Precies, dus het huidige index die onze omvang is, en dus willen we de nieuwe integer zetten die we willen invoegen in s.size. Slaat dat ergens op? Omdat s.strings, dat alles is de naam van de array. Al is het is de toegang tot serie in onze structuur, en dus als we willen plaatsen n in die index, kunnen we gewoon toegang toe met behulp van beugels s.size. Koel. 

Oké, pop, ik pseudocode het uit voor jullie, maar vergelijkbaar concept. Slaat dat ergens op? Als de grootte groter dan nul, dan heb je weet dat je iets wilt nemen omdat als het formaat is niet groter dan nul, dan heb je hebben niets in de stapel. 

Zodat u alleen wilt uitvoeren Deze code, het kan alleen maar pop als er iets te knallen. Dus als de grootte is groter dan 0, we min de grootte. We verlagen de grootte en dan terug wat is de binnenkant van het omdat door knallen, we willen toegang welke wordt opgeslagen de index van de top van de stack. Alles zinvol? Als ik jullie dit schrijf uit, zouden jullie in staat zijn om het uit te schrijven? Oké, jullie kunnen rond spelen. Geen zorgen als je niet krijgen. We hebben geen tijd om code het vandaag, want we hebben kreeg veel van deze structuren om door te gaan, maar in wezen pseudocode, zeer, zeer vergelijkbaar te duwen. Volg gewoon langs de logica. Zorg ervoor dat je toegang tot alle functies van uw structuur correct. Ja? 

PUBLIEK: Zal ​​deze dia's en deze hele zaak vandaag-ish? ANDI Peng: Altijd, yep. Ik ga proberen om te zetten dit op als een uur na. Ik zal e-mail David, zal David proberen zet het op als een uur na dit. 

OK, dus dan gaan we naar deze andere mooie gegevensstructuur genaamd een wachtrij. Zoals jullie hier kunt zien, een wachtrij, voor de Britten onder ons, al is het een lijn. Dus in tegenstelling tot wat je denkt dat een stapel, een wachtrij is precies wat logisch je denkt dat het is. Het is in het bezit van de regels van FIFO, dat is First In, First Out. Als je de eerste één op de lijn, je bent de eerste die komt uit de lijn. 

Dus wat we willen noemen dit wordt dequeueing en enqueueing. Als we iets willen toevoegen onze wachtrij, we enqueue. Als we willen dequeue, of neem iets weg, we dequeue. 

Zodat hetzelfde gevoel dat we soort creëren van vaste grootte elementen die we kunnen bepaalde opslaan dingen, maar we kunnen ook veranderen waar we plaatsen parameters binnenkant van hen gebaseerd op wat voor soort functionaliteit die we willen. Dus stacks, wilden we de laatste een, N de eerste buiten te zijn. Wachtrij is willen we het eerste ding in om het eerste ding uit zijn. 

Zodat de structuur-type definiëren, zoals u kunt zien, het is een beetje anders van wat de stack was omdat we niet alleen moeten blijven spoor van waar de grootte van dit moment is, we willen ook spoor van het hoofd houden evenals waar we nu zijn. Dus ik denk dat het makkelijker als ik trek deze omhoog. Dus laten we denken dat we een wachtrij gekregen, dus laten we zeggen dat het hoofd is hier. Het hoofd van de lijn, laat gewoon zeggen dat er op dit moment, en we willen invoegen iets in de wachtrij. Ik ga op maat wezen bellen is hetzelfde als de staart, het einde van waar uw wachtrij. Laten we zeggen dat de grootte is hier. 

Dus hoe werkt een haalbare Steek iets in een wachtrij? Wat index willen we plaatsen waar we willen invoegen in. Als dit het begin van wachtrij en dit is het einde ervan of de grootte van het, waar doen we wil naar het volgende object toe te voegen? 

PUBLIEK: [onverstaanbaar] ANDI Peng: Precies, je wilt toevoegen is afhankelijk heb je het geschreven. Of deze leeg is of dat is leeg. Dus je wilt het waarschijnlijk toe te voegen hier, want als de grootte is-- als deze zijn allemaal vol, je wilt om het hier toe, toch? 

En dat is dus, terwijl het heel erg eenvoudige, niet helemaal altijd correct omdat de belangrijkste verschil tussen een wachtrij en een stapel dat de wachtrij kan daadwerkelijk gemanipuleerd zodat de kop verandert afhankelijk van waar u wilt het begin van uw cue om te beginnen. En als gevolg, je staart Ook gaat veranderen. En zo een kijkje nemen op deze code nu. Zoals jullie ook gevraagd schrijf op de quiz, enqueue. Misschien zullen we door waarom praten het antwoord was wat het was. 

Ik kon niet helemaal fit deze lijn op een, maar in wezen dit stukje code moet op één lijn. Breng als 30 seconden. Neem een ​​kijkje en zie waarom Dit is de manier waarop het is. 

Zeer, zeer vergelijkbare structuur, zeer, zeer gelijkaardige structuur als de vorige stack behalve misschien een regel code. En dat een regel code bepaalt de functionaliteit. En het is echt onderscheidt een wachtrij van een stapel. 

Iedereen wil een gooi te nemen uit te leggen waarom je hebt kreeg deze ingewikkelde ding hier? We zien de terugkeer van onze prachtige vriend modulus. Zoals jullie binnenkort zullen komen te herkennen in de programmering, bijna elke keer als u iets nodig hebt te wikkelen rond iets, modulus gaat om de manier te doen. Dus weten dat doet iedereen wil om te proberen uit te leggen dat de regel code? Ja, alle antwoorden zijn geaccepteerde en welkom. Publiek: Heb je het tegen mij? ANDI PENG: Ja. PUBLIEK: Oh, nee sorry. ANDI Peng: OK, dus laten we lopen door deze code. Dus als je probeert om iets toe te voegen aan een wachtrij, in de mooie geval dat het hoofd gebeurt om hier te zijn, het is erg makkelijk voor ons om gewoon naar het einde Steek iets, toch? Maar het hele punt van een wachtrij is dat het hoofd daadwerkelijk kan dynamisch veranderen afhankelijk van waar we wil het begin van onze q te zijn, en als zodanig, de staart Ook gaat veranderen. 

En dus stellen dat dit niet was wachtrij, maar dit was de wachtrij. Laten we zeggen dat het hoofd is hier. Laten we zeggen dat onze wachtrij leek dit. Als we wilden verplaatsen, waar het begin van de lijn is, laten we zeggen dat we verschoven hoofd op deze manier en maten hier. 

Nu willen we iets aan toe te voegen deze wachtrij, maar zoals jullie kunnen zien, het is niet zo simpel als gewoon toevoegen wat is na de grootte want dan uit lopen we grenzen van onze huidige array. Waar we willen echt toe is hier. Dat is het mooie van een wachtrij is dat voor ons, visueel is lijkt alsof de lijn gaat als volgt, maar wanneer opgeslagen in een gegevensstructuur, ze geven het als als een cyclus. Het wraps soort rond aan de achterkant dezelfde manier dat een lijn kan ook wrap rond, afhankelijk van waar u willen begin van de regel te zijn. En dus als we een kijk hier naar beneden, laten we zeggen dat we wilde een te creëren functie genaamd enqueue. We wilden int n toe te voegen in die q. Als q.size q-- we noemen dat onze gegevens structure-- als onze queue.size niet gelijk aan de capaciteit of het is minder dan de capaciteit, q.strings is de matrix in onze q. We gaan om te stellen dat gelijk is aan q.heads, dat is hier, plus q.size modulus van de capaciteit, die wrap ons terug hier in de buurt. 

In dit voorbeeld, index van het hoofd is 1, toch? De index van grootte 0, 1, 2, 3, 4. Dus we kunnen 1 plus 4 modulus doen door onze capaciteit dat is 5. Wat betekent dat ons? Wat is de index die komt uit deze? 

Publiek: 0. 

ANDI Peng: 0, die gebeurt om hier te zijn, en dus willen we in staat zijn te voegen in hier. En dus deze vergelijking hier soort van alleen werkt met alle nummers afhankelijk van waar je hoofd en uw maat zijn. Als je weet wat die dingen zijn, weet je precies waar u wilt invoegen wat is na uw wachtrij. Heeft dat zin om iedereen? 

Ik weet dat soort van een brein teaser vooral omdat dit kwam in de nasleep van uw quiz. Maar hopelijk iedereen nu kan begrijpen waarom deze oplossing of dit functie is de manier waarop het is. Iedereen die een beetje onduidelijk over dat? OK. 

En nu, als je wilde dequeue deze is waar ons hoofd zou verschuiven want als we dequeue, we niet opstijgen het einde van de q. We willen het hoofd af te nemen, toch? Dus als gevolg, is het hoofd gaat veranderen, en dat is de reden waarom als je enqueue, je hebt om bij te houden waar uw hoofd en uw maat zijn te kunnen voegen in de juiste positie. 

En dus als je dequeue, Ik Pseudocode het ook uit. Voel je vrij om als je wilt om te proberen codering dit uit. U wilt het hoofd te bewegen, toch? Als ik wilde dequeue, I zou het hoofd bewegen over. Dit zou het hoofd zijn. 

En onze huidige omvang zou aftrekken omdat we niet langer vier elementen in de array. We hebben slechts drie, en dan willen we terug welke binnen opgeslagen van het hoofd omdat we willen deze nemen waarde uit dus sterk op de stack. Gewoon je neemt vanuit een andere plaats, en je moet je wijzer toewijzen verschillende plaats als gevolg. Logisch, iedereen volgen? Grote. 

OK, dus we gaan een beetje praten meer in de diepte over gelinkte lijsten omdat ze zeer, zeer waardevol zal zijn voor u in de loop van deze week psets. Gelinkte lijsten, zoals jullie kan herinneren, alles wat ze zijn knooppunten knooppunten die bepaalde waarden van zowel een waarde en een pointer die met elkaar zijn verbonden door die pointers. En zo de structuur van hoe creëren we een knooppunt hier is dat we hebben int n, die ongeacht de waarde in een winkel of tekenreeks n of wat je wilt noemen, de char ster n. Struct knooppunt ster, die de wijzer dat u wilt hebben in elk knooppunt, je gaat die moeten wijzer punt in de richting van de volgende. Je zult het hoofd hebben van een gekoppelde lijst die is zal wijzen op de rest van de waarden enzovoorts enzovoorts totdat je uiteindelijk het einde bereikt. En dit laatste knooppunt is gewoon naar een pointer hebben. Het gaat om te wijzen op null, en dat is wanneer je weet dat je hebt geraakt het einde van uw gelinkte lijst is wanneer uw laatste pointer niet wijzen op iets. 

Dus gaan we een beetje meer in te gaan diepgaande over hoe men zou eventueel zoek een gekoppelde lijst. Onthoud wat zijn enkele van de nadelen van de gekoppelde lijsten verzen een serie over zoekopdrachten. Een array kun je binair zoeken, maar waarom kan je niet doen in een gekoppelde lijst? 

Publiek: Omdat ze allemaal zijn aangesloten, maar je weet niet precies weten waar [ONHOORBAAR]. 

ANDI Peng: Ja, precies zo onthouden dat de schittering van een array was het feit dat we hadden willekeurig toegankelijk geheugen waarin als ik wilde de waarde van de index zes, ik kon alleen maar zeggen index zes, geef mij die waarde. En dat komt omdat arrays zijn gesorteerd in een aaneengesloten ruimte van het geheugen op één plek, terwijl soort gekoppelde lijsten willekeurig afgewisseld rondom, en de enige manier waarop je kunt er een te vinden is door middel van een pointer die je vertelt het adres van de plaats waar die volgende knooppunt. 

Dus als gevolg dat de enige manier om door middel van een gekoppelde lijst is lineair zoeken. Omdat ik niet precies weet waar 12 waarde in de gekoppelde lijst, Ik moet het geheel doorkruisen van die gelinkte lijst één één van de kop met het eerste knooppunt, het tweede knooppunt aan het derde knooppunt helemaal naar beneden totdat ik eindelijk waar dat knooppunt Ik ben op zoek naar is. En dus in die zin, zoeken op een gekoppelde lijst is altijd n. Het is altijd n. Het is altijd in lineaire tijd. 

En dus is de code in die implementeren we dit, en dit is een beetje nieuw voor jullie, omdat je jongens hebben niet echt over gesproken of ooit gezien wijzers in hoe zoeken door middel van pointers, dus we zullen doorkruisen dit zeer, zeer langzaam. Dus bool zoeken, rechts, Laten we veronderstellen we willen een functie genaamd creëren search dat true retourneert als u een waarde in de gekoppelde gevonden lijst, en keert anders false. Knooppunt ster lijst momenteel alleen de pointer naar het eerste item in de gekoppelde lijst. int n is de waarde die je zoekt in die lijst. 

Dus knooppunt ster pointer gelijk lijst. Dat betekent dat we het instellen bent en creëren van een pointer om die eerste knooppunt in de lijst. Iedereen met mij? Dus als we waren te gaan hier terug, zou ik geïnitialiseerd een pointer die naar het hoofd van welke die lijst is. 

En dan als je hier beneden, terwijl de pointer is niet gelijk aan nul, dus dat is de lus waarin we zal vervolgens worden doorkruisen de rest van onze lijst omdat wat gebeurt er als aanwijzer gelijk aan nul? We weten dat we have-- 

PUBLIEK: [onverstaanbaar] 

ANDI Peng: Precies, dus we weten dat we hebben het einde van de lijst bereikt, toch? Als je hier terug te gaan, elk knooppunt moeten wijzen naar een ander knooppunt enzovoort totdat je uiteindelijk hit de staart van uw gelinkte lijst, waarbij een pointer heeft die net niet ergens anders dan geen wijzen. En dus je eigenlijk weet dat de lijst is er nog steeds totdat wijzer is niet gelijk null, want zodra het is gelijk aan nul, je weet dat er geen spullen meer. 

Dus dat is de lus waarin we gaan naar de werkelijke zoeken hebben. En als de pointer-- zie je dat soort pijl functie daar? Dus als wijzer punten n, indien de pointer aan n gelijk gelijk is aan n, dat betekent dat als de aanwijzer dat je zoekt op het einde van elke node feite gelijk aan de waarde je zoekt, dan is u wilt echte terugkeren. Dus eigenlijk, als je op een knooppunt dat heeft de waarde die u zoekt, weet je dat je bent geweest in staat om succesvol te zoeken. 

Anders, u wilt instellen aanwijzer naar het volgende knooppunt. Dat is wat die lijn hier doet. Wijzer gelijk wijzer naast. Iedereen zien hoe dat werkt? 

En in wezen je gaat gewoon doorkruisen het geheel van de lijst, resetten van uw wijzer telkens tot je uiteindelijk raakte het einde van de lijst. En je weet dat er geen meer knooppunten te zoeken door, en dan kun je return false omdat je weet dat, oh, nou ja, Als ik in staat om te zoeken geweest door het geheel van de lijst. Als in dit voorbeeld, als ik wilde te kijken naar de waarde van 10, en ik begin aan het hoofd, en Ik zoek helemaal naar beneden, en ik kreeg uiteindelijk tot dit, dat een pointer die wijst op null, Ik weet dat, onzin, ik denk dat 10 is niet in deze lijst want ik kon het niet vinden. En ik ben aan het eind van de lijst. En in dat geval weet je Ik ga return false. 

Laat dat weken in voor een klein beetje. Dit zal vrij zijn belangrijk voor uw PSET. De logica is zeer eenvoudig, misschien syntactisch gewoon de uitvoering ervan. Jullie willen maken zeker van zijn dat je het begrijpt. Koel. 

OK, dus hoe zouden we invoegen van knooppunten, rechts, in een lijst, omdat onthouden wat zijn de wat van de voordelen van het hebben van een gekoppelde lijst versus een reeks in termen van opslag? 

Publiek: Het is dynamisch, zodat het makkelijker to-- 

ANDI Peng: Precies, dus het is dynamisch, die betekent dat het kan uitzetten en krimpen afhankelijk van de behoeften van de gebruiker. En ja, in deze zin, we hoeven niet onnodige geheugen te verspillen, omdat ik als ik weet niet hoeveel waarden Ik wil op te slaan, heeft het geen zin voor mij om een ​​array te creëren, omdat als ik wil 10 waarden op te slaan en ik maak een serie van 1000, dat is een hoop verspilde geheugen toegewezen. Daarom willen we gebruik maken van een gekoppelde lijst kunnen dynamisch wijzigen of te krimpen onze omvang. 

En dus dat maakt het inbrengen een beetje meer ingewikkeld. Aangezien wij kunnen niet willekeurig toegang elementen de manier waarop we een array zou van. Als ik wil een element in te voegen in de zevende index Ik kan het gewoon invoegen in de zevende index. Op een gekoppelde lijst, het niet vrij werk zo gemakkelijk, en dus als we wilden voegen het hier in de gekoppelde lijst, visueel, het is heel gemakkelijk om te zien. We willen alleen maar om het daar in te voegen, aan het begin van de lijst, direct na het hoofd. 

Maar de manier waarop we moeten toewijzen de wijzers is een beetje ingewikkeld of, logischerwijs, is het zinvol, maar wilt u ervoor zorgen dat je het hebt helemaal naar beneden, omdat het laatste wat je wilt is een pointer het toewijzen manier dat we hier doen. Als u de dereferentie pointer van kop tot 1, dan ineens de rest van uw gelinkte lijst is verloren omdat je eigenlijk niet creëerde een tijdelijk iets. Dat wees naar de 2. Als u de aanwijzer, dan is het toewijzen rest van de lijst is totaal verloren. Dus je wilt zijn heel, heel voorzichtig hier naar de eerste wijzen de wijzer uit wat je wilt invoegen in waar je wilt, en dan moet je kan dereference de rest van de lijst. 

Dus dit geldt voor overal je probeert in te voegen in. Als u wilt invoegen op de hoofd, als je hier wilt beantwoorden, Als u wilt invoegen op het einde, goed, het einde I denk dat je zou gewoon hebben geen wijzer, maar u willen ervoor zorgen dat je niet verliest de rest van de lijst. Je wilt altijd om ervoor te zorgen uw nieuwe knooppunt wijst in de richting van wat je wilt invoegen in, en dan kun je voeg de chaining op. Iedereen duidelijk? 

Dit gaat worden een van de echte problemen. Een van de meest belangrijke kwesties je gaat op je PSET is dat je gaat proberen te creëren een gelinkte lijst en insert dingen maar dan gewoon verliest de rest van uw gekoppelde lijst. En je gaat te zijn zoals ik weet niet waarom dit gebeurt? En het is een pijn om te gaan door en doorzoeken van uw pointers. 

En ik garandeer je op deze PSET, schrijven en tekenen deze knooppunten uit zal zeer, zeer behulpzaam. Dus je kunt helemaal bijhouden van waar al je pointers zijn, wat er fout gaat, waarbij alle knopen, wat je moet doen om toegang te krijgen of invoegen of verwijderen of een van hen. Iedereen goed met dat? Koel. 

Dus als we wilden kijken naar de code? Oh, ik weet niet of we kan the-- OK zien, dus aan de top al is het een functie genoemd insert waar we willen int n om in te voegen in de gekoppelde lijst. We gaan lopen door dit. Het is een stuk van de code, een heleboel nieuwe syntaxis. We zullen OK. 

Dus op naar boven, wanneer we willen iets maken wat hebben we nodig om te doen, vooral als je wil het niet worden opgeslagen op de stapel maar in de heap? We gaan naar een malloc, toch? Dus we gaan naar een pointer te creëren. Knoop, wijzer, nieuwe gelijken malloc het formaat van een knooppunt want we willen dat knooppunt te worden gemaakt. We willen dat de hoeveelheid geheugen dat een knooppunt neemt toe te wijzen voor de creatie van het nieuwe knooppunt. 

En dan gaan we controleren zien of er nieuwe gelijken gelijk aan nul. Weet je nog wat we zeiden? Wat je malloc, Wat moet je altijd doen? Je moet altijd controleren om te zien ongeacht of dat is nul. 

Bijvoorbeeld, als uw besturingssysteem systeem was helemaal vol, als je had geen meer geheugen aan allen en je probeert te malloc, het zou null voor u terug. En dus als je probeert om het te gebruiken toen het wees op null, je bent niet van plan om in staat toegang tot die informatie. Dus als zodanig, wilden we ervoor zeker van dat wanneer je mallocing, je bent altijd te controleren om te zien of die herinnering aan u gegeven is null. En als het niet, dan kunnen we verhuizen op met de rest van onze code. 

Dus we gaan initialiseren van het nieuwe knooppunt. We gaan doen nieuwe n gelijk is aan n. En dan gaan we doen set nieuwe de aanwijzer op nieuwe null want nu doen we niet wil iets voor het te wijzen. We hebben geen idee waar het gaat om u, en dan als we willen plaatst u deze aan het hoofd, dan kunnen we toewijzen de aanwijzer naar het hoofd. Heeft iedereen volgt de logica waar dat gebeurt? 

Alles wat we doen is het creëren van een nieuw knooppunt, het instellen van de wijzer op null, en dan opnieuw toewijzen het aan de kop als we weten we willen voegen aan het hoofd. En dan de kop gaat wijzen naar die nieuwe knooppunt. Iedereen OK met dat? 

Dus het is een proces van twee stappen. Je moet eerst toewijzen wat u maakt. Stel dat aanwijzer naar de referentie, en dan moet je kan soort dereferentie de eerste pointer en richt deze naar het nieuwe knooppunt. Waar u het wilt invoegen, die logica gaat om waar te houden. 

Het is net zoiets als het toekennen tijdelijke variabelen. Vergeet niet, je hebt om ervoor te zorgen dat u niet bijhouden als je ruilt niet verliezen. Wilt u ervoor zorgen dat u een tijdelijke variabele die soort houdt spoor waar dat ding wordt opgeslagen, zodat u geen waarde te verliezen in de loop van zoals knoeien met het. 

OK, dus code zal hier zijn. Jullie een kijkje nemen na sectie. Het zal er zijn. 

Dus ik denk dat hoe werkt deze verschillen als we wilden in te voegen in het midden of het einde? Heeft iemand een idee van wat de pseudocode als logische referentie dat we zouden nemen als we wilden om deze te plaatsen in het midden? Dus als we wilden het te voegen bij de hoofd, alles wat we doen is het creëren van een nieuw knooppunt. We zetten de wijzer van dat nieuw knooppunt aan wat het hoofd, en dan zetten we het hoofd naar het nieuwe knooppunt, toch? Als we wilden om deze te plaatsen in het midden van de lijst, wat zouden we moeten doen? 

PUBLIEK: het zou nog steeds zijn een soortgelijk proces zoals het toekennen van pointer en het toewijzen die pointer, maar we zouden hebben om er te vinden. 

ANDI Peng: Precies, dus precies hetzelfde proces behalve dat je moeten waar precies lokaliseren u wil dat de nieuwe aanwijzer in te gaan, dus als ik wil invoegen in het midden van gekoppelde list-- OK, laten we zeggen dat is onze gelinkte lijst. Als we willen het hier in te voegen, we gaan naar een nieuw knooppunt te maken. We gaan malloc. We gaan naar een nieuw knooppunt te maken. We gaan naar het toewijzen wijzer van dit knooppunt hier. 

Maar het probleem dat afwijkt waar het hoofd is is dat we precies wisten waarbij het hoofd is. Het was vlak bij het eerste, toch? Maar hier hebben we te houden van waar we deze in. Als we het plaatsen van onze knooppunt hier, we hebben om ervoor te zorgen dat de men vóór dit knooppunt is degene die de wijzer opnieuw toewijst. Dus dan moet je soort bijhouden van twee dingen. Als je bijhouden waar dit houden knooppunt momenteel invoegen in. Je moet ook bijhouden waar houden de vorige knooppunt dat u zoekt op was er ook. Iedereen goed met dat? OK. 

Hoe zit het invoegen in het einde? Als ik wilde het toevoegen hier-- als ik wilde een nieuw knooppunt toe te voegen aan het eind van een lijst, hoe zou ik over dat doen? Publiek: Dus op dit moment, de laatste's wees op null. ANDI PENG: Ja. Precies, dus dit momenteel is gericht weten, en zo denk ik, in deze zin, het is zeer eenvoudig toe te voegen aan het einde van de lijst. Alles wat je hoeft te doen is het instellen gelijk aan nul en dan boom. Daar, zeer eenvoudig. Erg makkelijk. 

Zeer vergelijkbaar met de hoofd, maar logischerwijs u willen ervoor zorgen dat de stappen neemt u in de richting van een van dit te doen, je volgt samen. Het is heel gemakkelijk om, in het midden van je code, verstrikt raken op, oh, ik heb zo veel pointers. Ik weet niet waar niets wijst. Ik weet niet eens weten welke knoop ik ben op. Wat is er aan de hand? 

Ontspannen, te kalmeren, haal diep adem. Trek uw gekoppelde lijst. Als je zegt, ik weet waar precies Ik moet dit in te voegen in en ik weet precies hoe mijn toewijzen pointers, veel, veel gemakkelijker om foto out-- veel, veel makkelijker om niet verdwalen in de bugs van uw code. Iedereen OK met dat? OK. 

Dus ik denk dat een concept dat we niet echt over gesproken vóór nu, en ik denk dat je waarschijnlijk zal niet tegenkomen veel yet-- het is een soort van een geavanceerde concept-- is dat we eigenlijk een data structuur heet een dubbel gelinkte lijst. Dus zoals jullie kunnen zien, alles wat we doen is het creëren van een werkelijke waarde, een extra aanwijzer op elk van onze knooppunten die wijst ook naar het vorige knooppunt. Dus niet alleen hebben we onze nodes verwijzen naar de volgende. Ze wijzen ook op de vorige. Ik ga om te negeren deze twee nu. 

Dus dan heb je een keten dat kan in beide richtingen bewegen, en dan is het een stuk makkelijker logisch volgen langs. Zoals hier, in plaats van het bijhouden van, oh, ik moet weten dat dit knooppunt degene die ik moet toewijzen, Ik kan gewoon gaan hier en trek gewoon de vorige. Dan weet ik precies waar dat is, en dan moet je hoeft de traverse onderdelen van de gekoppelde lijst. Het is een beetje makkelijker. 

Maar als zodanig, dubbel u de hoeveelheid pointers, Dat is het dubbele van de hoeveelheid geheugen. Het is een stuk van de aanwijzingen bij te houden. Het is een beetje ingewikkelder, maar het is een beetje gebruiksvriendelijker afhankelijk van wat je probeert te bereiken. 

Dus dit soort gegevens structuur volledig bestaat, de structuur is het heel erg eenvoudige behalve alles wat je hebt met is, in plaats van alleen een pointer naar de volgende, je moet ook een verwijzing naar de vorige. Dat is alles wat het verschil was. Iedereen goed met dat? Koel. 

Oke, dus nu ben ik echt waarschijnlijk te besteden zoals 15 tot 20 minuten of bulk van de rest van de tijd in sectie over hash tabellen. Hoeveel van jullie pset5 spec hebben gelezen? Oké, goed. Dat is hoger dan de 50% van normaal. Het is ok. 

Dus zoals jullie zullen zien, je uitdaging in pset5 zal een woordenboek implementeren waar je laadt meer dan 140.000 woorden dat wij u en spellingcontrole tegen alle tekst. Wij geven u willekeurige stukken literatuur. Wij geven je de Odyssee. Wij geven je de Ilias. Wij geven je Austin Powers. 

En uw uitdaging zal zijn om controle te spellen elk woord in alle van deze woordenboeken wezen met onze spellingcontrole. En dus is er een paar onderdelen van het creëren van deze PSET, eerst je wilt zijn in staat om daadwerkelijk te laden alle woorden in uw woordenboek, en dan moet je willen in staat zijn om spellingcontrole allemaal. En dus als zodanig, je gaat te eisen een gegevensstructuur die deze snel kan doen en efficiënt en dynamisch. 

Dus ik veronderstel dat de makkelijkste manier om dit te doen, moet je zou waarschijnlijk een array, toch? De eenvoudigste manier van opslag is u kan een reeks van 140.000 woorden te creëren en ze gewoon alle plaatsen daar en Vervolgens doorkruisen ze door binaire zoekopdracht of door selecties of niet-- jammer dat is het sorteren. Je kunt ze sorteren en dan doorkruisen ze door binaire zoeken of gewoon lineair zoeken en net laatste woorden, maar dat neemt een enorme hoeveelheid geheugen, en het is niet erg efficiënt. 

En dus gaan we om te beginnen over manieren om onze lopende tijd efficiënter. En ons doel is om constante tijd waar het is bijna alsof arrays, waarbij je hebt onmiddellijke toegang. Als ik op zoek naar iets, Ik wil in staat zijn om gewoon, boom, vind het precies, en trek hem uit. Zo een structuur waarin zullen we steeds zeer dicht in staat zijn om toegang te krijgen tot een constante tijd, deze heilige graal in de programmering van de constante tijd wordt een hash tabel. En dus David eerder vermeld de [Onverstaanbaar] een beetje in collegezaal, maar we gaan echt duiken in diep deze week op een stuk dat is over hoe een hash-tabel werkt. 

Dus de wijze waarop een hash tafel werken, bijvoorbeeld, als ik wilde een bos van woorden op te slaan, een bos van woorden in het Engels, Ik kon in theorie zetten banaan, appel, kiwi, mango, paar, en meloen allemaal op slechts een array. Ze konden allemaal passen en te vinden. Het zou een soort van pijn aan doorzoeken en toegang, maar eenvoudiger manier hiervoor is dat we eigenlijk kunnen creëren een structuur riep een hash tafel waar we hash. We lopen al onze sleutels door middel van een hashfunctie, een vergelijking, dat maakt ze allemaal in een soort van een waarde die vervolgens kan slaan we op in wezen een reeks van gekoppelde lijst. 

En dus even, als we wilden naar Engels woorden op te slaan, we konden potentieel gewoon, ik niet weet, zet al de eerste letters in een soort van een getal. En zo, bijvoorbeeld, als ik wilde Een synoniem zijn met apple-- of met de index van 0, en B synoniem met 1 te zijn, kunnen we 26 inzendingen dat kan gewoon opslaan alle letters van het alfabet dat we zullen beginnen. En dan kunnen we appel op de index van 0. We kunnen banaan hebben bij de index van 1, cantaloupe de index van 2, enzovoort. En zo als ik wilde om te zoeken mijn hash tafel en toegang appel, Ik weet dat Apple begint met een A, en ik weet precies dat het moet de hash tafel bij index 0, omdat van de functie eerder toegewezen. 

Dus ik weet het niet, we zijn een gebruiker programma waarin u zult worden belast met arbitrarily-- niet willekeurig, met het proberen om bedachtzaam denk aan goede vergelijkingen kunnen verspreiden al je waarden op een manier die ze gemakkelijk toegang zij later met als een vergelijking dat u zelf weten. Dus in die zin als ik wilde naar mango, ik weet het, oh, het begint met m. Het moet de index van 12. Ik hoef niet te zoeken door iets. Ik weet exactly-- ik kon naar de index van 12 en trek dat uit. 

Iedereen duidelijk over hoe een functie hash tafel werkt? Het is een soort van slechts een meer complexe reeks. Dat is alles wat het is. OK. 

Dus ik denk dat we tegenkomen deze kwestie van wat gebeurt als je meerdere dingen dat geeft je dezelfde index? Dus zeggen dat onze functie al deed was dat de eerste letter en zet die in een respectievelijk 0 tot 25 index. Dat is helemaal prima als je hebt slechts één van elk. Maar de tweede u begint met meer, je bent gaat te hebben wat een botsing genoemd. 

Dus als ik probeer in te voegen te begraven in een hash tabel die al heeft banaan op het, wat er gaat gebeuren als je probeert in te voegen dat? Slechte dingen omdat banaan reeds binnen de index bestaat dat u wilt opslaan in. Berry soort is als, ah, wat moet ik doen? Ik weet niet waar te gaan. Hoe kan ik dit oplossen? 

En dus je jongens zullen soort zien we dit lastige zaak waar we kunnen soort eigenlijk creëren gekoppelde lijst in onze arrays. En dus is de makkelijkste manier om na te denken over dit, alle hash tabel is een reeks van gekoppelde lijsten. En ja, in die zin, je hebt dit prachtige array van pointers, en vervolgens elke aanwijzer in die waarde in die index, daadwerkelijk kan verwijzen naar andere dingen. En dus moet je al deze afzonderlijke kettingen komende uit van een grote reeks. 

En dus even, als ik wilde bessen voegen, Ik weet het, OK, ik ga ingang het door mijn hash-functie. Ik ga om te eindigen met de index van 1, en dan ga ik om te kunnen hebben slechts een kleine subset van deze giant 140.000 woord woordenboek. En dan kan ik alleen kijken door middel van 1/26 van dat. 

En dus dan kan ik gewoon te voegen bessen voor of na banaan in dit geval? Na, toch? En dus je gaat te willen Steek dit knooppunt na banaan, en dus je gaat voegen aan de staart van die gelinkte lijst. Ik ga terug te gaan deze vorige dia, zodat jullie kunnen zien hoe hash-functie werkt. 

Dus hash-functie is deze vergelijking dat je draait soort uw input door middel van te krijgen wat index wilt u het naar toe te wijzen. Dus, in dit voorbeeld alle we wilden te doen was de eerste letter, Zet dat in een index, dan zijn we kan slaan dat in onze hash-functie. Alles wat we hier doen is dat we omzetten van de eerste letter. Dus KeyKey [0] is slechts de eerste letter van welke snaar we hebben, we passeren in. We omzetten die aan de bovenste en we trekken door hoofdletters A, dus alles wat doet geeft ons een aantal waarin we onze waarden hash op. 

En dan gaan we terug hash modulus SIZE. Heel, heel voorzichtig omdat theoretisch, here je hash-waarde zou kunnen zijn oneindig. Het zou gewoon gaan op en op en op. Het zou echt een aantal, echt grote waarde, maar omdat je hash tafel u hebt gemaakt, heeft slechts 26 indexen, wilt u ervoor zorgen dat uw modulusing zodat u niet run-- het is hetzelfde zoiets als je queue-- zodat je niet lopen van de onderkant van de hash-functie. 

U wilt het rond wikkelen terug Op dezelfde manier in [onverstaanbaar] bij je had als een zeer, zeer grote brief, u niet dat dat net vandoor het einde. Hetzelfde hier, wilt u ervoor zorgen Het loopt niet uit het einde van wikkelen rond de bovenkant van de tabel. Dus dit is slechts een zeer eenvoudige hash-functie. Al dat deed was de eerste letter van wat onze inbreng was en zet die in een index die we konden in onze hash tafel. 

Ja, en dus zoals ik al zei, de manier waarop we conflicten op te lossen in onze hash tabellen hebben, wat wij noemen, chaining. Dus als u probeert meerdere invoegen woorden die beginnen met het zelfde ding, je gaat om een ​​hash-waarde hebben. Avocado en appel, als je hebt lopen via onze hash-functie, gaat u op te geven hetzelfde nummer, het aantal 0. En dus is de manier waarop we op te lossen dat is dat we kunnen eigenlijk wel te koppelen elkaar via gelinkte lijsten. 

Dus in die zin, kunnen jullie soort te zien hoe data structuren die we zijn het instellen van eerder als een rozijn gelinkte lijst soort van elkaar kunnen komen tot één. En dan kan je ver creëren efficiëntere datastructuren die kunnen grotere hoeveelheden te behandelen data, die dynamisch vergroten of verkleinen, afhankelijk op uw behoeften. Iedereen duidelijk? Iedereen soort duidelijke wat hier gebeurt? 

Als ik wilde insert-- wat is een fruit dat begint met, ik weet het niet, B, met uitzondering van bessen, banaan. 

Publiek: Blackberry. 

ANDI Peng: Blackberry, blackberry. Waar gaat blackberry gaan hier? Nou, we hebben eigenlijk niet gesorteerd dit nog niet, maar in theorie als we wilden dit hebben in alfabetische volgorde, waar moet blackberry gaan? 

PUBLIEK: [onverstaanbaar] 

ANDI PENG: Precies, na hier, toch? Maar omdat het is erg moeilijk om reorder-- Ik denk dat het is aan jullie. Jullie kunnen helemaal implementeren wat je wilt. De efficiëntere wijze dit misschien doen zou zijn om te sorteren uw gekoppelde een lijst in alfabetische volgorde, en dus als je invoegen van dingen, je wilt om zeker te zijn om ze te voegen in alfabetische volgorde zodat dan wanneer je bent proberen om ze te zoeken, je hoeft niet alles te doorkruisen. Je weet precies waar het is, en het is makkelijker. 

Maar als je het soort hebt dingen willekeurig afgewisseld, je bent nog steeds te hebben om het anyways doorkruisen. En dus als ik wilde gewoon Steek blackberry hier en ik wilde om te zoeken naar het, ik weet het, oh, blackberry moet beginnen met de index van 1, dus ik weet ogenblikkelijk gewoon zoeken op 1. En dan kan ik soort doorkruisen de gelinkte lijst totdat ik op Blackberry, en then-- ja? 

Publiek: Als je probeert te create-- Ik denk dat als dit is een zeer eenvoudige hash functie. En als we wilden doen meerdere lagen zoals die, OK, we willen scheiden in net als alle alfabetische letters en dan weer naar een andere set graag van alfabetische brieven binnen die, we zetten als een hash tabel in een hash-tabel, of als een functie binnen een functie? Of is dat-- 

ANDI PENG: Dus je hash function-- uw hash table kan zo groot zijn als u dat wilt. Dus in die zin, dacht ik Het was erg makkelijk, erg eenvoudig voor mij om gewoon soort gebaseerde op brieven van het eerste woord. En dus is er slechts 26 opties. Ik kan alleen maar 26 opties 0-25 omdat zij alleen kunnen start van A tot Z. Maar als je wilde toevoegen, misschien meer complexiteit of sneller lopen tijd om uw hash table, u absoluut kunnen allerlei dingen doen. U kunt uw eigen te maken vergelijking die je geeft meer spreiding in uw woorden, dan wanneer u zoekt, het gaat sneller. 

Het is helemaal aan jullie hoe je wilt implementeren dat. Zie het als gewoon emmers. Als ik wilde hebben 26 emmers, ik ga om dingen in die emmers afstand. Maar ik ga een heleboel hebben dingen in elke emmer, dus als je wilt om het te maken sneller en efficiënter laat me honderd emmers. 

Maar dan moet je uitzoeken een manier om dingen te sorteren, zodat zij in de juiste bak ze zouden moeten zijn in. Maar dan als je daadwerkelijk willen kijken naar die emmer, het is een stuk sneller omdat er minder spullen in elke emmer. En zo ja, dat is eigenlijk de truc voor jullie in pset5 is dat je in uitgedaagd om gewoon te creëren wat is de meest efficiënte functie die je kunt bedenken zijn in staat om op te slaan en laat deze waarden. 

Helemaal aan jullie maar u wilt doen, maar dat is een heel goed punt. Dat de aard van de logica u willen gaan nadenken over is, nou ja, waarom niet ik meer emmers. En dan moet ik zoeken minder dingen, en dan misschien I een andere hashfunctie. 

Ja, er is een heleboel manieren om dit te doen PSET, sommige zijn sneller dan anderen. Ik ben helemaal ga gewoon zien hoe snel was de snelste je jongens zullen in staat zijn om hun functies te werken. Oké, iedereen goed op chaining en hash tabellen? Het is eigenlijk net als een zeer eenvoudige Het concept als je erover nadenkt. Al is het is het scheiden van wat uw ingangen zijn in emmers, ze te sorteren, en dan zoeken op het geeft dat er is gekoppeld. 

Koel. Oké, nu hebben we een ander soort data structuur die heet een boom. Laten we verder gaan en praten over pogingen die duidelijk verschillend, maar in dezelfde categorie. Wezen, al een boom is in plaats organiseren data op de lineair dat een hash tafel does-- u weet, het heeft een top en een bodem en dan heb je soort koppelen off van het-- een De boom heeft een top die je de wortel noemen, en dan heeft het blad rondom. 

En dus alles wat je hier is slechts de top knooppunt die naar andere knooppunten, die punten meer nodes, enzovoort, enzovoort. En dus moet je gewoon splitsen takken. Het is gewoon een andere manier van organiseren data, en omdat we noemen het een boom, jullie gewoon-- het is gewoon gemodelleerd naar uitzien als een boom. Dat is waarom we noemen het bomen. 

Hash tafel lijkt op een tafel. Een boom ziet eruit als een boom. Alle het is is een aparte manier van organiseren knooppunten afhankelijk van wat uw wensen zijn. 

Dus je hebt een wortel en dan heb je bladeren. De manier waarop we kunnen met name denken over het is een binaire boom, een binaire boom is slechts een bepaald type boom waarbij elk knooppunt alleen punten tot op max, twee andere knooppunten. En dus even je duidelijk hebt symmetrie in uw boom dat maakt het makkelijker om soort kijken op welke waarden je bent, want dan heb je hebben altijd een links of rechts. Er is nooit als een linker derde van links of een vierde van links. Het is gewoon je een linker en een rechter en u kunt zoeken een van deze twee. En dus waarom is dit nuttig? De manier waarop dit handig is als u op zoek bent om door middel van waarden, toch? In plaats van uitvoering binaire zoeken in een fout array, als je wilde om te kunnen knopen voegen en neem knooppunten weg op wil en ook het behoud van de zoekopdracht capaciteiten van binaire zoeken. Dus op deze manier, we zijn soort tricking-- herinneren wanneer we zei gekoppelde lijsten kan niet binary search? We soort van het creëren van een datastructuur dat de trucs die in het beroepsleven. 

En omdat gelinkte lijsten zijn lineair, zij slechts verbinden na elkaar. We kunnen soort hebben ander soort pointers dat punt naar verschillende knooppunten die ons kunnen helpen met zoeken. En dus even, als ik wilde hebben een binaire zoekboom, Ik weet dat mijn middelvinger als 55. Ik ga gewoon te creëren dat zoals mijn midden, zoals mijn wortel, en dan ga ik heb waarden spin-off van het. 

Dus hier, als ik ga op zoek naar de waarde van 66, kan ik beginnen bij 55. Het is 66 groter dan 55? Ja het is, dus ik weet dat ik mus zoeken i n de juiste wijzer van deze boom. Ik ga naar 77. OK, is 66 kleiner of groter dan 77? Het is minder dan, zodat u weet, oh, dat bij de linker node. 

En dus even we soort van het behoud alle van de grote dingen over arrays, dus als dynamisch vergroten of verkleinen voorwerpen, die in staat om in te voegen en te verwijderen op wil, zonder zich zorgen te maken over de vaste hoeveelheid ruimte. We hebben nog steeds alles te behouden die prachtige dingen terwijl ook in staat om het te behouden log en zoek de tijd van binaire zoekopdracht die we eerder waren slechts in staat om een ​​zin te krijgen. 

Koele datastructuur, soort moeilijk uitvoerbaar, het knooppunt. Zoals u kunt zien, al is de structuur van het knooppunt is dat u een links en rechteraanwijzer. Dat is alles wat het is. Dus in plaats van alleen met een X of een eerdere. Je hebt een links of rechts, en dan u kunt soort koppelen ze samen Maar je daarvoor kiezen. 

OK, we eigenlijk gaan slechts een paar minuten duren. Dus we gaan om hier terug te gaan. Zoals ik al eerder zei, Ik soort uitgelegd de logica achter hoe we zou zoeken door middel van deze. We gaan proberen pseudocoding dit uit te zien als we soort kunnen toepassen Dezelfde logica van binaire zoekopdracht een ander type gegevensstructuur. Als jullie willen nemen als een paar minuten om gewoon na te denken over dit. OK. Oké, ik ga eigenlijk alleen maar geef je geen the--, we over de pseudocode praten eerste. Dus doet iedereen wil een steek op te geven wat het eerste wat je wilt doen als je begint uit te zoeken is? Als we op zoek naar de waarde van 66, wat is het eerste wat we willen doen als we willen binary search deze boom? 

PUBLIEK: U wilt naar rechts kijken en kijk links en zie [onverstaanbaar] groter aantal. 

ANDI Peng: Ja, precies. Dus je gaat kijken naar uw wortel. Er zijn veel manieren waarop u kunt bellen het, je ouders knooppunt mensen zeggen. Ik wil wortel zeggen, want dat is net als de wortel van de boom. Je gaat kijken naar je root-knooppunt, en je bent gaan zien is 66 groter of kleiner dan 55. En als het groter is dan, nou ja, het is groter dan, waar willen we naar kijken? Waar willen we zoeken nu, toch? Wij willen het zoeken rechter helft van deze boom. 

Dus we hebben, gunstig, een pointer die wijst naar rechts. En dus dan kunnen we stellen onze nieuwe root te zijn 77. We kunnen gewoon gaan naar waar de wijzer wijst. Nou, oh, hier zijn we beginnen op 77, en we kunnen alleen maar Dit doen recursief opnieuw en opnieuw. Op deze manier, je soort van een functie. Je hebt een manier van zoeken die je kan gewoon herhalen over en over en over, afhankelijk van waar u wilt kijken totdat je uiteindelijk de waarde die u zoekt. Zin? 

Ik sta op het punt om te laten zien van de werkelijke code, en het is een veel code. Geen behoefte om freak out. We praten er doorheen. 

Eigenlijk niet. Dat was gewoon pseudocode. OK, dat was gewoon de pseudocode, dat is een beetje ingewikkeld, maar het is helemaal prima. Iedereen volgt samen hier? Als de wortel is null, rendement valse want dat betekent je hoeft niet eens iets hebben daar. 

Als wortel n is de waarde, dus als het gebeurt er met degene die je zoekt op zijn, dan zul je ware terug omdat je weet dat je het gevonden. Maar als de waarde minder dan wortel van n, je bent gaat naar de linkerzijde kind of de linker blad, wat je ook wilt noemen. Als deze waarde groter is dan wortel, je gaat naar de juiste boom zoeken, dan gewoon de functie run door middel van zoeken weer. 

En als wortel is null, dat betekent dat je het einde hebt bereikt? Dat betekent dat je geen meer meer bladeren om te zoeken, dan weet je, oh, ik denk dat het niet hier want nadat ik keek door de hele zaak en het is niet hier, het misschien gewoon niet hier. 

Heeft dat zin om iedereen? Dus het is net als binary search behoud de mogelijkheden van gekoppelde lijsten. Cool, en dus het tweede type van datastructuur jullie kunt implementeren op uw PSET, je hoeft maar één te kiezen. Maar misschien een alternatieve methode om de hash-tabel is wat wij een trie noemen. 

Allemaal een trie is een specifieke boomsoort die heeft waarden die naar andere waarden. Dus in plaats van een binaire structuur in die zin dat enige wat kan wijzen op twee, kunt u een ding punt aan vele, vele dingen. Je hebt in wezen arrays de binnenkant van die u opslaat pointers die naar andere arrays. 

Dus het knooppunt van de manier waarop we zou trie definiëren is dat we willen hebben Boolean, c woord, toch? Zodat de node Boolean als waar of onwaar, allereerst aan het hoofd van die array, is dit een woord? Ten tweede, wil je pointers hebben naar wat de rest van hen zijn. Een beetje ingewikkeld, een beetje abstract, maar Ik zal wat dat alle middelen uit te leggen. 

Dus hier bovenaan, als je hebben een scala verklaarde al, een knooppunt waar u een Boole opgeslagen waarde aan de voorzijde dat vertelt u is dit een woord? Is dit niet een woord? En dan heb je de rest van uw array die eigenlijk slaat alle mogelijkheden wat het kan zijn. Dus, bijvoorbeeld, als aan de top heb je het eerste ding dat waar of zegt onwaar, ja of nee, dit is een woord. 

En dan heb je 0 tot en met 26 van de letters die u kunt opslaan. Als ik hier wilde zoeken voor bat, ga ik naar de top en ik kijk naar B. Ik vind B in mijn array, en zo weet ik, OK, is B een woord? B is geen woord, zodat daarmee Ik moet blijven zoeken. Ik ga van B, en ik kijk naar de pointer die wijst naar B en ik zie een andere array van informatie, dezelfde structuur die we eerder hadden. 

En hier-- oh, de volgende brief in [onverstaanbaar] A. Dus we kijken in die array. Wij vinden de achtste waarde, en dan kijken we om te zien, oh, hey, is dat een woord, is B-A een woord? Het is geen woord. We moeten blijven kijken. 

En dus dan kijken we naar de plaats waar de wijzer van A punten en het wijst op een andere manier die we hebben meer waarde opgeslagen. En uiteindelijk komen we bij B-A-T, dat een woord. En dus de volgende keer je kijkt, je gaat dat controle van, ja hebben, deze Boolean functie is waar. En zo in de zin dat we soort van een boom met arrays. 

Dus dan kun je soort zoeken naar beneden. In plaats van een hashing-functie en toekennen van waarden door gelinkte lijst, je kunt gewoon uitvoeren van een trie dat downwords zoekt. Echt, echt ingewikkeld spul. Niet gemakkelijk om te denken, want ik ben net als spugen zoveel datastructuren uit op je af, maar doet iedereen soort begrijpen hoe de logica van dit werkt? 

OK, cool. Dus B-A-T, en dan je gaat zoeken. De volgende keer dat je gaat te zien, oh, hey, het is waar, dus ik weet dat dit moet een woord zijn. 

Hetzelfde voor de dierentuin. Dus hier is het ding nu, als we wilde om te zoeken naar de dierentuin, op dit moment, momenteel dierentuin is niet een woord in ons woordenboek omdat, zoals jullie kunnen zien, de eerste plaats dat we een Boolean return true is aan het eind van de zoom. We hebben Z-O-O-M. 

En dus even, we eigenlijk niet hebben het woord, dierentuin, in ons woordenboek omdat dit selectievakje is niet aangevinkt. Zodat de computer niet weten dat de dierentuin is een woord omdat de manier waarop we hebben opgeslagen het, alleen een zoom hier heeft eigenlijk een Booleaanse waarde die is gedraaid waar. Dus als we willen het invoegen woord, dierentuin, in ons woordenboek, hoe zouden we gaan dat doen? Wat moeten we doen om ervoor te zorgen dat onze computer weet dat Z-O-O is een woord en niet het eerste woord is Z-O-O-M? 

PUBLIEK: [onverstaanbaar] 

ANDI Peng: Precies, we willen ervoor zorgen dat deze Hier, dat Booleaanse waarde afgevinkt dat het waar is. Z-O-O, dan gaan we controleren of, zodat we precies weten, he, dierentuin is een woord. Ik ga het vertellen computer dat het een woord zo dat wanneer de computer controleert, het weet dat de dierentuin is een woord. 

Want vergeet niet al deze gegevens structuren, het is erg makkelijk voor ons te zeggen, oh, vleermuis is een woord. Zoo is een woord. Zoom is een woord. Maar als je bouwen, de computer heeft geen idee. 

Dus je moet het precies vertellen op welk punt is dat een woord? Op welk punt is het niet een woord? En op welk moment moet ik nodig hebt om dingen te zoeken, en op welk moment moet ik naast gaan? Iedereen duidelijk dat? Koel. 

En dus dan komt het probleem hoe zouden we gaan over het plaatsen van iets dat is eigenlijk niet? Dus laten we gewoon zeggen dat we willen invoegen het woord, bad, in onze trie. Zoals jullie kunnen zien, zoals momenteel alles wat we nu hebben, is B-A-T, en deze nieuwe datastructuur er had een pint die wees op null omdat we aannemen dat, oh, er is geen woorden na de B-A-T, waarom hebben we nodig om te blijven die dingen na die T. 

Maar het probleem ontstaat als we u doen willen een woord dat komt na hebben de T's. Als je bad, je bent gaan naar een H rechts wilt. En dus is de manier waarop we dat doen is we gaan een apart knooppunt te maken. We zijn niet toe te wijzen wat voor bedrag geheugen voor deze nieuwe array, en we gaan pointers toewijzen. 

We gaan naar het toewijzen H, allereerst dit null, we gaan om zich te ontdoen van. We gaan te hebben het H-punt naar beneden. Als we een H, we willen het om te gaan naar ergens anders. 

Hier kunnen we dan controleren ja uit. Als we een H hit na de T, oh, dan weten we dat dit een woord. De Booleaanse gaat om waar te keren. Iedereen duidelijk over de manier waarop dat gebeurde? OK. 

Dus in wezen allemaal Deze gegevensstructuren dat we dan vandaag de dag zijn gegaan, ik heb echt, echt snel gegaan over hen en niet te veel detail, en dat is OK. Zodra u begint knoeien met het, zult u het bijhouden van de plaats waar alle pointers zijn, wat er gaande is in uw gegevensstructuren, et cetera. Ze zullen zeer nuttig zijn, en het is aan jou jongens om volledig uit te zoeken hoe je dingen wilt implementeren. 

En zo pset4, van 5-- oh, dat is verkeerd. Pset5 is spelfouten. Zoals ik al eerder zei, je gaat, zodra weer, downloaden broncode van ons. Er gaat drie zijn dingen die je zult downloaden. Je zult woordenboeken downloaden kers, en teksten. 

Al die dingen zijn zijn ofwel woordenboeken woorden dat we willen dat je om te controleren of het testen van gegevens dat we willen dat je check spellen. En zo de woordenboeken Wij geven je gaat je werkelijke woorden die we willen geven om ergens slaan op een manier die efficiënter dan een array. En dan de teksten gaat worden wat we vraag je om de spelling controleren om er zeker alle woorden zijn er echte woorden. 

En zo de drie blokken van programma's die we je geven dictionary.c worden genoemd, dictionary.h en speller.c. En zo alle dictionary.c doet is wat je gevraagd wordt te implementeren. Het laadt woorden. Het te spellen controles hen, en het zorgt ervoor dat dat alles goed geplaatst. 

diction.h is gewoon een bibliotheek bestand dat verklaart al die functies. En speller.c, we gaan u. U hoeft niet een van te wijzigen. Alle speller.c doet is te nemen dat, laadt, controleert de snelheid ervan, test de benchmark van als hoe snel ben je in staat om dingen te doen. 

Het is een speller. Gewoon niet knoeien met het, maar maak ervoor dat je begrijpt wat het doet. We maken gebruik van een functie genaamd getrusage dat test de prestaties van uw spell checker. Alles wat het doet is eigenlijk het testen van de de tijd van alles in je woordenboek, dus zorg ervoor dat je het begrijpt. Wees voorzichtig om niet knoeien met het of anders dingen niet goed lopen. 

En het grootste deel van deze uitdaging is voor jullie echt dictionary.c wijzigen. We gaan u 140.000 woorden in een woordenboek. We gaan u een tekst te geven bestand dat die woorden heeft, en we willen dat je in staat zijn om te organiseren ze in een hash tabel of een trie want als wij vragen u te spellen check-- stel als je spell zoals het controleren van de Odyssee van Homerus. Het is als deze enorme, enorme beproeving. 

Stel je voor dat elke word je moest kijken door middel van een reeks van 140.000 waarden. Dat zou een eeuwigheid duren voor uw machine te draaien. Daarom willen we onze organisatie data naar efficiëntere datastructuren zoals een hash tafel of een trie. En dan kunnen jullie soort wanneer je toegang zoeken dingen makkelijker en sneller. 

En dus wees voorzichtig om botsingen te lossen. Je gaat om een ​​bos te krijgen van woorden die beginnen met A. Je gaat naar een bos woorden krijgen die beginnen met B. Tot u jongens hoe je wilt het op te lossen. Misschien is er meer efficiënte hash-functie dan alleen de eerste letter van iets, en dat is aan jou jongens soort doen wat je wilt. 

Misschien dat u wilt toevoegen alle letters bij elkaar. Misschien wil je graag doen rare dingen het aantal letters account, boeiend. Tot jullie hoe je wilt doen. Als u wilt een hash tafel te doen, als je willen een trie proberen, helemaal aan jou. Ik zal je op voorhand te waarschuwen voor de tijd dat de trie is meestal een beetje moeilijker gewoon omdat er veel Meer tips om bij te houden. Maar helemaal aan jullie. Het is veel efficiënter in de meeste gevallen. Je wilt echt te kunnen blijven spoor al uw pointers. Net hetzelfde doen dat ik hier aan het doen. Wanneer je probeert in te voegen waarden in een hash tabel of te verwijderen, zorg ervoor dat je bent echt bijhouden van waar alles is omdat het is echt makkelijk voor als ik proberen in te voegen als het woord, andy. Laten we zeggen dat het een echt woord, het woord, andy, in een gigantische lijst van A woorden. 

Als ik toevallig toewijzen een pointer fout, oops, daar gaat het geheel van de rest van mijn gekoppelde lijst. Nu is het enige woord dat ik hebben is andy, en nu alle andere woorden woordenboek zijn verloren gegaan. En dus wilt u ervoor zorgen dat u bijhouden van al uw pointers of anders je gaat krijgen grote problemen in uw code. Trekken dingen zorgvuldig stap voor stap. Het maakt het een stuk makkelijker om te bedenken. 

En tot slot, wil je in staat zijn om test uw prestaties van uw programma op het grote bord. Als jullie nemen kijk naar CS50 nu, wij hebben wat heet de groot bord. Het is het scoreblad van de snelste spellingscontrole keer in al CS50 nu, ik denk dat de top, zoals 10 keren dat ik denk dat acht van hen zijn medewerkers. We willen dat jullie ons verslaan. 

Ieder van ons probeerden uit te voeren de snelste code mogelijk. We willen dat jullie proberen aan te vechten ons en implementeren sneller dan ons allemaal kan. En dus dit is echt de eerste keer dat we vragen jullie om een ​​PSET doen kan je echt doen in welke methode jij wil. 

Ik zeg altijd, dit is meer verwant een echte oplossing, toch? Ik zeg, hey, ik heb je nodig om dit te doen. Bouwen van een programma dat dit doet voor mij. Doe het zoals u dat wilt. Ik weet alleen dat ik wil vasten. Dat is jouw uitdaging voor deze week. Jongens, we gaan om u een taak. We gaan om u een uitdaging te geven. En dan is het aan jullie volledig gewoon uitzoeken wat is de snelste en meest efficiënte manier om dit te implementeren. Ja? 

Publiek: Mogen we als wilde snellere manieren onderzoeken om hash tabellen online doen, kunnen we doen en dat noemen de code van iemand anders? ANDI Peng: Ja, helemaal prima. Dus als lezen jullie de spec, is er een lijn in de spec dat jullie zegt zijn volledig vrij om hash onderzoek functies op wat zijn sommige van de snellere hash functies om dingen te lopen door als Zolang je die code noemen. Dus sommige mensen al hebben bedacht snelle manieren van het doen van spellingcontrole, van snelle manieren opslaan van informatie. Helemaal aan jullie als je willen gewoon dat, toch? Zorg ervoor dat je citeert. De uitdaging hier echt dat we proberen om te testen is ervoor te zorgen dat je weet je weg pointers. Voor zover u de uitvoering de werkelijke hashfunctie en komen met als de wiskunde om dat te doen, jullie kunnen onderzoeken wat methoden online jullie willen. Ja? 

Publiek: Kunnen we citeren net met behulp van de [onverstaanbaar]? 

ANDI PENG: Ja. Je kunt gewoon in uw commentaar, U kunt noemen zoals, oh, genomen van yada, yada, yada, hash-functie. Iemand nog vragen? We eigenlijk breezed door middel van sectie vandaag. Ik zal hier zijn om vragen te beantwoorden als goed. 

Ook, zoals ik al zei, kantoor uur vanavond en morgen. De specificatie van deze week is eigenlijk super makkelijk en super kort te lezen. Ik stel het nemen van een kijkje, net Lees de onderdelen ervan. 

En Zamyla eigenlijk loopt u door elk van de functies je nodig hebt om te implementeren, en dus is het heel, heel duidelijk hoe om alles te doen. Gewoon om ervoor te zorgen dat u bent het bijhouden van pointers. Dit is een zeer uitdagende PSET. 

Het is niet uitdagend want zoals, oh, de begrippen zijn zo veel meer moeilijk, of je moet leren zo veel nieuwe syntaxis de weg dat je deed voor de laatste PSET. Dit PSET is moeilijk, omdat er zijn zo veel pointers, en dan is het heel, heel gemakkelijk om een ​​keer je hebt een fout in uw code niet kunnen te vinden waar dat fout is. 

En zo volslagen vertrouwen in u jongens in staat zijn om onze [onverstaanbaar] verslaan spellingen. Ik heb eigenlijk geen schriftelijke mijne nog niet, maar ik ben op het punt om de mijne te schrijven. Dus terwijl je schrijft van jou, zal ik schrijven de mijne. Ik ga proberen te maken mijne sneller dan de jouwe. We zullen zien wie de snelste is. 

En ja, ik zal alles zien jullie hier op dinsdag. Ik zal een soort als een PSET workshop draaien. Alle secties deze week zijn PSET workshops, Dus jullie hebben veel kansen voor hulp, kantooruren zoals altijd, en ik kijk uit naar het lezen van al uw jongens 'code. Ik heb quizzen hier als u jongens willen komen halen die. Dat is alles.