DAVID J. Malan: Oke. Dus welkom om de allereerste CS50 postmortem voor een quiz. We dachten dat we zouden huldigen deze traditie dit jaar. En dit zal een gelegenheid zijn te lopen door de oplossingen voor de quiz. En we zullen versnellen of vertragen gebaseerd op de rente van deze hier. 

Zodat u waarschijnlijk hier bent omdat je geïnteresseerd in hoe je zou kunnen hebben of moeten beantwoord sommige van deze problemen. Dus waarom niet we een kijkje nemen in deze sectie eerst? Zodat je snaren. Dit gaf je drie verschillende versies een programma dat was uiteindelijk bedoeld om een ​​string te krijgen van een gebruiker. Of het dat deed was overgelaten aan u om te bepalen. 

En we vroegen in vraag 0, veronderstellen dat versie 1 is samengesteld en uitgevoerd. Waarom zou het programma segfault? Op het eerste gezicht, suggesties waarom? Yeah. 

Publiek: Ik herinner me deze in een eerder voorbeeld van naar de char * s en het zien van de scan van de s en het zien, want het is een pointer, hoe heeft zij invloed hebben op wat je gescand? Is het is of het adres van s? 

DAVID J. Malan: OK. Goed. Dus uiteindelijk, de bron van een probleem Vermoedelijk zal verminderen die variabel is. En het is inderdaad een variabele. Het gegevenstype van deze variabele is char *, wat betekent dat het gaat om bevatten het adres van een personage. En daarin schuilt het inzicht. Het gaat om het adres bevatten een teken of, meer algemeen, de adres van het eerste teken in een hele blok karakters. 

Maar de vangst is dat scan s, doel in het leven, krijgt een adres en gegeven een formaat code, zoals% s, lezen een string in de brok van geheugen op dat adres. Maar omdat er geen gelijk-teken voor dat puntkomma op de eerste regel code, omdat we niet echt toewijzen elk geheugen met malloc, omdat het eigenlijk niet toewijzen een array van enige omvang, alle je doet is het lezen van de gebruiker keyboard input in sommige compleet garbage waarde, die is in s standaard. Dus kansen worden je gaat segfault als dat adres niet net zo toevallig een waarde die u kan worden, in feite, schrijven. Zo slecht niet toe te wijzen je geheugen daar. 

Dus in vraag 1, vroegen we, veronderstellen dat versie 2 is samengesteld en uitgevoerd. Waarom zou dit programma segfault? Dus dit is minder buggy. En er is eigenlijk maar een hand liggende manier waar u kunt leiden hier een segfault. En dit is thematisch. Elke keer dat we met behulp van c in het geheugen, wat zou je kunnen doen om een ​​segfault induceren met versie 2? 

PUBLIEK: Als u die ingang gebruiken in een tekenreeks die langer is dan 49 karakters. 

DAVID J. Malan: Precies. Elke keer zie je iets vaste lengte als het gaat om een ​​array uw radar moet doven dat dit zou kunnen zijn problematisch als je niet controleren van de grenzen van een array. En dat is hier het probleem. We zijn nog steeds met behulp van scanf. We zijn nog steeds met behulp van% s, wat betekent proberen een tekenreeks lezen van de gebruiker. Dat gaat worden ingelezen in s, die, op dit punt, is het effectief adres van een stuk van het geheugen of het equivalent. Het is de naam van een array tekens van het geheugen. 

Maar precies dat, als je een string te lezen die langer is dan 49 tekens, 49 omdat je ruimte nodig hebt voor de backslash 0, je gaat overstromen die buffer. En je zou je geluk hebben en in staat zijn om schrijf een 51 karakter, 52, 53. Maar op een gegeven moment, het besturingssysteem gaat zeggen, nee. Dit is zeker niet het geheugen jij mag aanraken. En het programma gaat segfault. 

Dus daar moet de heuristiek enige zijn keer dat je vaste lengte hebt, heb je om ervoor te zorgen dat je het controleren van de lengte van wat het ook is dat je probeert lezen erin. 

PUBLIEK: Dus op te lossen dat je zou kunnen een verklaring hebben de controle had eigenlijk is de lengte groter of kleiner dan? 

DAVID J. Malan: Absoluut. Je hoeft alleen een voorwaarde dat zegt, als het - of liever gezegd hoef je niet per se te kennen op voorhand hoeveel tekens de gebruiker gaat typen, omdat heb je kip en het ei. Pas als je hebt gelezen in met scanf kun je uitzoeken hoe lang het is. Maar op dat moment, het is te laat, omdat je het al hebt gelezen in sommige blok geheugen. Dus als een terzijde, de CS50 bibliotheek vermijdt dit probleem helemaal, recall met fgetc. En het leest een teken tegelijk, -tip toeing langs de wetenschap dat u kan een teken als niet overstromen je leest een voor een. 

De vangst is met getString recall is dat we voortdurend re-size dat stuk van het geheugen, die is gewoon een pijn. Het is een stuk van de lijnen van code om dat te doen. Dus een andere aanpak zou zijn om daadwerkelijk gebruik maken van een neef, dus te zeggen, van scanf. Er zijn varianten van veel van deze functies die daadwerkelijk controleert de lengte van hoeveel tekens je zou maximaal lezen. En je kon opgeven, niet lezen meer dan 50 tekens. Dus dat zou een andere aanpak, maar minder meegaand van grotere ingangen. 

Dus vraag 2 vraagt, stel dat versie 3 wordt gecompileerd en uitgevoerd. Waarom zou dat programma segfault? Dus dit is eigenlijk hetzelfde beantwoorden, hoewel ziet er een beetje liefhebber. We gebruiken malloc, dat aanvoelt als we geven ons meer opties. En dan zijn we vrijmaken dat geheugen op het einde. Het is nog steeds slechts 50 bytes van het geheugen. Dus we kunnen nog steeds proberen om te lezen in 51, 52, 1000 bytes. Het gaat om segfault voor dezelfde reden. 

Maar er is ook een andere reden. Wat kon rendement malloc naast het adres van een stuk van het geheugen? Het zou null terugkeren. En omdat we niet controleren op dat zouden we iets goed doen dom om een ​​andere reden, namelijk dat we misschien vertellen scanf, lezen invoer van de gebruiker via het toetsenbord in 0 locatie, AKA null. En ook dat zal zeker leiden tot een segfault. Dus voor het doel van de quiz is, zouden we hebben een van deze als een aanvaard geldige reden. Een identiek. Een daarvan is een beetje genuanceerder. 

Tenslotte, met betrekking tot het programma gebruik van het geheugen, hoe versie 2 doen en versie 3 verschillen? Dus voor wat het waard is, zagen we een schijnbaar eindeloze aanbod van mogelijke antwoorden op. En onder de antwoorden van mensen, wat we waren hoopte, maar we andere aanvaard dingen, was enige vermelding van de Dat versie 2 gebruikt de zogenaamde stack. Versie 3 is het gebruik van de heap. En functioneel, dit niet echt maken al dat veel van een verschil. Aan het eind van de dag, we zijn nog steeds net 50 bytes van het geheugen. 

Maar dat was een van de mogelijke antwoorden waren we op zoek naar. Maar je zult zien, als u uw quizzen terug van de TF's, dat we deden aanvaarden andere discussies van hun ongelijksoortige vormen van gebruik van het geheugen ook. Maar stack en heap zou zijn geweest een eenvoudig antwoord op te gaan met. Heeft u nog vragen? Ik geef je Rob. 

ROB BOWDEN: Dus probleem 4. Dit is degene waar je moest invullen het aantal bytes van alle deze verschillende soorten gebruikt. Dus eerste wat we zien. Ga uit van een 32-bit architectuur, als deze CS50 apparaat. Dus een van de fundamentele dingen over 32-bits architecturen, die ons vertelt precies hoe groot een pointer gaat om in de architectuur. 

Dus meteen, we weten dat elke pointer type is 32-bit of 4 bytes. Dus kijken naar deze tabel, een knooppunt * is een type pointer. Dat gaat worden 4 bytes. Struct knoop *, dat is letterlijk identiek aan knooppunt ster. En dat gaat worden 4 bytes. String, dus het maakt niet uit als een pointer nog niet, maar de typedef, een snaar is gewoon een char *, die is een type pointer. Dus dat gaat worden 4 bytes. 

Dus deze drie zijn 4 bytes. Nu, knooppunt en student zijn een beetje ingewikkelder. Dus kijken naar knooppunt en student, zien we knooppunt als een integer en een pointer. En leerling is twee pointers binnenkant van het. Dus in ieder geval voor ons geval hier, de manier we uiteindelijk berekening van het aantal Deze structuur is gewoon optellen alles dat er in de structuur. 

Dus voor knooppunt, hebben we een geheel getal, die 4 bytes. We hebben een pointer, die 4 bytes. En dus een knooppunt gaat tot het nemen van 8 bytes. En hetzelfde geldt voor studenten, hebben we een aanwijzer die 4 bytes en een pointer dat is 4 bytes. Dus dat gaat eindigen omhoog het zijn 8 bytes. Dus knooppunt en student zijn 8 bytes. En deze drie zijn alle 4 bytes. Vragen over zeggen? Ja. 

PUBLIEK: Is het een 64-bit architectuur, zou dat verdubbelen ze allemaal? 

ROB BOWDEN: Het zou niet verdubbelen allemaal. Dus 64-bit architectuur, het, opnieuw, veranderingen die fundamentele ding dat een pointer is nu 64 bits. Yeah. Dus een pointer is 8 bytes. Dus deze dat 4 bytes waren zullen 8 bytes. Een student, die twee pointers was, goed, nu het gaat om zijn 8 bytes, 8 bytes. Het gaat om 16 bytes te maken. 

Maar knooppunt nog 4 bytes. Dus deze pointer gaat zijn 8 bytes. Dit is 4 bytes. Dus een knooppunt is alleen maar zijn 12 bytes. Andere vragen op die ene? Dus de volgende, deze de HTTP status code. En je moest omstandigheden beschrijven waaronder deze macht aan u worden geretourneerd. een probleem dat ik hoorde dat sommige studenten hebben is dat ze geprobeerd om de fouten worden op het einde van de cliënt. Dus als we proberen om het verzoek in te dienen naar de server, gaat er iets fout aan onze kant. Maar in het algemeen, zijn deze codes wordt geretourneerd door de server. Dus willen we uitzoeken wat er gaande verkeerd of rechts op de server die zorgt ervoor dat deze dingen te worden geretourneerd. Dus waarom zou een server rendement statuscode 200? Elke gedachten? 

Yeah. Dus iets over succes het verzoek ging door. En ze zijn in staat om terug te keren wat je vroeg. Dus alles was prima. Hoe zit het met 302 gevonden? Yeah. 

Publiek: De server was op zoek voor wat je gevraagd. Maar kon het niet vinden. Dus er is een fout. 

ROB BOWDEN: Dus was de server op zoek naar wat je wilde. Dus gewoon kijken hier, 302 gevonden, het was in staat om het te vinden. 

Publiek: Het spijt me. Gevonden betekent dat ze vonden het. Sorry. 

ROB BOWDEN: Dus 302 gevonden. De server kan vinden wat je wilde. 

Publiek: Maar het is niet weer te geven? 

ROB BOWDEN: Het verschil tussen Dit 302 en 200 is dat het weet wat je wilt. Maar het is niet precies waar je wilde vragen. Dus 302 is een typisch redirect. Dus je hebt een pagina opgevraagd. Het weet, oh, ik wil u deze terug. Maar dit is op een andere URL. Dus hey, je eigenlijk wilt dit. 

DAVID J. Malan: Het is een stuk dat zei dat gaven we jullie een redirect functie dat de header functie gebruikt dat op zijn beurt afgedrukt locatie, colon, en vervolgens de URL waarnaar je wilt de gebruiker te weigeren. Ook al heb je niet zien 302 expliciet daar, dat is wat PHP zou magisch plaatst als de header zeggen precies wat Rob zei dat er - gevonden. Maar ga hier plaats. 

ROB BOWDEN: OK. Dus hoe zit het met 403 verboden? 

Publiek: Ik denk dat het dat de server is eigenlijk te zeggen dat de cliënt geen toegang tot de home page. 

ROB BOWDEN: Dus ja. Nou, waren de typische antwoord dat we verwacht is zoiets als, de bestanden niet op de juiste chmodded. Dat is waarschijnlijk onder welke omstandigheden je zag ze. Maar er is een reden dat de cliënt schuld zou kunnen zijn hier. Er is eigenlijk een andere statuscode - 401. Dus deze zijn zeer vergelijkbaar. 

401 is niet toegestaan. En 403 is verboden. En dus onbevoegd u uitsluitend als je niet bent ingelogd Maar het inloggen kan betekenen dat u bevoegd bent. Maar als je al aangemeld en nog steeds geen toestemming, dan je kunt ook verboden. Dus als je ingelogd bent en hoeft niet toestemming, verboden is ook iets wat je kunt krijgen. 

DAVID J. Malan: En het mechanisme die deze problemen meestal opgelost op de server via welk commando? Chmod, als het inderdaad een permissies geven op het bestand of de map. 

ROB BOWDEN: Dan 404 niet gevonden. Yeah. Dus in tegenstelling tot 302, waar het was precies niet waar je vraagt, maar het weet wat je wilt, dit, het heeft gewoon geen idee wat je wilt. En u bent niet vraagt iets geldig. 418 Ik ben een theepot en vervolgens 500 interne server. Dus waarom zou je die vandaan? 

Dus segfault - Ik eigenlijk niet weet wat de indeling standaard voor. Maar als je PHP-code had iets verkeerd in, in theorie, het kon eigenlijk segfault, waarbij deze 500 internal server error, iets is er mis met je server configuratie. Of er is een syntax error in uw PHP-code. Of er iets ergs aan de hand is. 

DAVID J. Malan: We zagen segfault onder de antwoorden van een paar mensen. En technisch gezien, kan het gebeuren. Maar dat zou een PHP, het programma geschreven door andere mensen, eigenlijk segfault, die alleen als die mensen geschroefd en schreef buggy code in hun tolk zou PHP zelf segfault. Dus ook al 500 is als een segfault in de geest, het is bijna altijd de gevolg van een configuratiebestand kwestie met uw webserver of, zoals Rob zei, een syntax error, zoals jij heeft een offerte heeft afgesloten. Of u een puntkomma ergens verloren. 

PUBLIEK: Dus voor de Shuttle PSET, ik denken toen ik het deed zodra ik klikte op de browser, maar niets kwam, wat zij noemden witte pagina. Maar het was omwille van de code. Ik denk dat was JavaScript, toch? 

ROB BOWDEN: Yeah. 

Publiek: Zou die fout nog komen? 

ROB BOWDEN: Dus je zou niet hebben gekregen deze fout omdat alles vanuit het perspectief van de webserver was helemaal prima. Maar u heeft opgevraagd index.html. U verzocht shuttle.js en service.js. En het was in staat om met succes terug te keren om u al die dingen - 200. OK. Het is pas wanneer uw browser probeerde te interpreteren van de JavaScript-code die Het is net, wacht, dit is niet geldige JavaScript-fout. Andere vragen? Oke. 

DAVID J. Malan: Dus de volgende up was nummer 11. En 11 was het engste voor een heleboel mensen. Dus het belangrijkste ding om te noteren was dat dit inderdaad over een dubbel gelinkte lijst. Maar dit hetzelfde als vorig jaar was niet dubbel gelinkte lijst probleem, die niet geven u de waarschuwing dat de lijst kan, in feite, zijn ongesorteerd. 

Dus het feit dat de lijst was ongesorteerd en het feit dat dat woord was onderstreepte er moest brengen dat dit eigenlijk een vereenvoudiging wat anders zou zijn geweest een meer uitdagend probleem en een langere. Dus een veel voorkomende fout was hier te zijn gekomen oplossing van vorig jaar op de ene pager en dan gewoon blindelings kopiëren dat af als het antwoord, dat is de juiste antwoord op een andere vraag in dezelfde geest. Maar de subtiliteiten hier waren als volgt. 

Dus een, we hebben een knooppunt verklaard en gedefinieerd op de gebruikelijke manier hier. Dan gedefinieerd we lijst van een mondiale pointer geïnitialiseerd op null. Dan blijkbaar is er twee functies we hebben prototypes voor hier, insert en te verwijderen. En dan hebben we enkele voorbeelden van code hier van het doen van een bos van inserties. En dan vragen wij u in te vullen de uitvoering insert hieronder dergelijke een manier dat het ingevoegd n in de lijst in constante tijd, ook onderstreept, zelfs indien reeds aanwezig. 

Dus de schoonheid van de mogelijkheid om in te voegen in constante tijd is dat het impliceert dat je moet invoegen het nieuwe knooppunt waar? In de voorste. Dus het elimineert, gelukkig, althans een van de zaken die wordt gebruikt om te eisen nog meer regels code, zoals het deed vorig jaar en zelfs in de klas toen we doorgepraat dit soort dingen met mensen en sommige verbale pseudo-code. Dus hier de oplossing, laten we overslaan dat alleen een visueel hebben op het scherm. 

Merk op dat we het volgende doen. En ook merken de andere vereenvoudiging was dat zelfs als het reeds aanwezig, dus dit betekent dat als het nummer is er al, je kunt gewoon blindelings plaats een andere kopie ervan. En ook dat was bedoeld om een ​​te zijn vereenvoudiging, zodat je zou kunnen focus op echt, sommige meer intellectueel interessante deel en niet zomaar een extra foutcontrole gezien de beperkte tijd. 

Dus in dit monster oplossing, we verdelen een wijzer op de linker kant hier om een ​​knooppunt. Nu, beseffen dat wijzer, als Rob zei, is slechts 32 bits. En het eigenlijk niet bevatten een adres tot u toewijzen het adres. En dat doen we op de rechter kant via malloc. Net als een goede burger, controleren we dat malloc is in feite nul, waardoor we niet per ongeluk te creëren een segfault hier. En elke keer dat je malloc gebruikt in het leven, je moet controleren op null, opdat je hebt een subtiele bug. 

Vervolgens initialiseren we dat null door toewijzen n en vorige en volgende. En in dit geval hier, ik geïnitialiseerd voorafgaand aan nul, omdat deze nieuwe knooppunt zal de nieuwe zijn begin van mijn lijst. Dus er gaat worden niets ervoor. En ik wil in wezen voegen de bestaande lijst naar de nieuwe knoop door die naast die gelijk is aan de lijst zelf. Maar ik ben gewoon nog niet klaar. Dus als al de lijst zelf bestond, en er ten minste een knooppunt al op zijn plaats, indien dit is de lijst hier en ik steek een nieuw knooppunt hier, ik moet ervoor zorgen dat mijn vroegere knooppunt wijst naar achteren om mijn nieuwe knooppunt, omdat dit, wederom, een dubbel gelinkte lijst. 

Dat doen wij ook een sanity check. Als de lijst niet null is, als er al een of meer knooppunten er dan toevoegen dat terug verwijzing zo te zeggen. En dan is het laatste wat we nodig hebben te doen is eigenlijk het actualiseren van de globale variabele lijst zelf te wijzen die nieuwe knoop. Yeah. 

PUBLIEK: In de aanwijzer [Onverstaanbaar] is gelijk aan nul, doet dat omgaan met de lijst omdat de lijst is nul? 

DAVID J. Malan: Nope. Dat is gewoon me die proactief voorzichtig, dat als dit mijn oorspronkelijke lijst met wellicht wat meer nodes hier en ik ben het invoegen van mijn nieuw knooppunt hierheen, er gaat niets meer dan hier te zijn. En ik wil dat idee vast te leggen door voorafgaand aan null op het nieuwe knooppunt. En vermoedelijk, als mijn code juist is en er is geen andere manier om in te voegen dan deze functie knooppunten vermoedelijk, zelfs als lijst heeft al een of meer knooppunten in, vermoedelijk de lijst, het eerste knooppunt, zou een vorige wijzer van null zelf. 

PUBLIEK: En gewoon een follow-up. De reden dat je pointer gezet volgende gelijken lijst wordt je maakt de aanwijzer voordat de lijst in dat het wijzend naar de volgende, denk ik - I Niet doen - geeft gewoon? 

DAVID J. Malan: Precies. En dus laten we het zien als twee gevallen hier echt, hoewel de Om we zullen ze overwegen is niet helemaal hetzelfde als de code. Maar op een hoog niveau, als dit betekent lijst en dit is een 32-bit aanwijzer het eenvoudigste scenario dat dit null standaard. En stel dat ik wil invoegen de nummer 50 was het eerste nummer. Dus ik ga om verder te gaan en toe te wijzen een knooppunt, die gaat bevatten drie velden - n, vorige en volgende. 

Ik ga naar het nummer 50 gezet hier, omdat n is. Dit zal de volgende zijn. En dit zal previous zijn. En dus wat moet ik doen in dit geval? Nou, ik heb net gedaan lijn 1 hier. Pointer n krijgt n. Ik ben dan zeg, vorige moeten krijgen null. Dus dit gaat nul beschouwd. Dan ga ik zeggen volgende gaat naar de lijst te krijgen. 

En dit werkt gewoon goed uit. Dit is null. En dus zeg ik, het nieuwe knooppunt's volgende gebied moeten krijgen wat dit is. Dus dat zet andere null daar. En dan is het laatste wat Ik weet is kijk dan hier. Als lijst is niet gelijk nul, maar is gelijk aan nul, dus slaan we dat helemaal. En dus alles wat ik nu doen is de lijst krijgt wijzer, die pictorially gevolg een foto als dat. Dus dat is een scenario. 

En degene die je vragen over specifiek is een situatie als deze, waar we al een lijst met knooppunten. En als ik terug te gaan in de oorspronkelijke probleemstelling, de volgende wij zullen Steek bijvoorbeeld is 34, alleen voor Ter wille van de discussie. Dus ik ga gewoon handig trekken die dan hier. Ik heb net malloced. Laten we aannemen dat ik het controleren op null. 

Nu, ik ga initialiseren n te zijn 34. En dit zal n zijn. Dit zal de volgende zijn. En dit zal previous zijn. Laten we ervoor zorgen dat ik niet krijg deze naar achteren. Vorige komt eerst in de definitie. Laat mij dit oplossen. Dit is vorige. Dit is de volgende. Hoewel deze identiek zijn, laten we het consistent. 

Vorige. Dit is de volgende. Dus ik heb net malloced mijn briefje, gecontroleerd voor null, toegewezen 34 in het knooppunt. Vorige krijgt null. Dus dat geeft me dat. Volgende krijgt lijst. Dus lijst is deze. Dus dit is hetzelfde nu als tekenen deze pijl, zodat ze wijzen op een dezelfde. En dan ga ik kijken of lijst is niet gelijk aan nul. En het is deze keer niet. Dan ga ik naar de lijst doen vorige krijgt pointer. 

Dus Voorgaande krijgt PTR. Dit heeft dus tot gevolg heeft dat een grafische pijl hier. En dat wordt een beetje golvende lijnen. En dan, tot slot, ik updaten lijst aan te wijzen pointer. Dus nu deze verwijst naar deze man. En nu, laten we doen een snelle sanity check. 

Hier is de lijst, dat is de globale variabele. Het eerste knooppunt is inderdaad 34, omdat Ik volg die pijl. En dat klopt, want ik wil Steek aan het begin van de lijst alle nieuwe knooppunten. Zijn volgende veld leidt mij tot deze man. Als ik ga door, ik raakte naast null. Dus er is geen lijst meer. Als ik nu op de vorige, krijg ik terug waar ik verwacht. 

Dus er zijn nog een paar aanwijzingen, uiteraard te manipuleren. Maar het feit dat je verteld te doen dit in constante tijd betekent dat u alleen hebben een eindig aantal dingen jij mag doen. En wat is dat nummer? Het kan een stap zijn. Het is misschien twee. Het is misschien 1.000 stappen. Maar het is eindig, wat betekent dat je niet kunt hebben enige vorm van een lus aan de hand hier, geen terugkeer, geen lussen. Het moet gewoon hard-coded lijnen van de code zoals we hebben in deze steekproef. 

Dus de volgende probleem 12 vroeg ons om Voltooiing van de uitvoering van remove onder zodanige wijze dat het verwijdert n van de lijst in lineaire tijd. Dus je moet een beetje meer hebben speelruimte nu. Misschien dat n aannemen, indien aanwezig in de lijst, aanwezig zal zijn niet meer dan een keer. En dat ook bedoeld is een quiz-based vereenvoudigende veronderstelling, dus dat als je het getal 50 ergens in de lijst, u ook niet zorgen te maken over blijven herhalen, op zoek naar alle mogelijke exemplaar van 50, die net zou delegeren in sommige minutia in beperkte tijd. 

Dus met verwijderen, dit was zeker uitdagender en meer code te schrijven. Maar op het eerste gezicht, eerlijk gezegd, is het misschien kijken overweldigend en als iets er is geen manier waarop je zou kunnen hebben komen met een quiz. Maar als we ons richten op de afzonderlijke stappen, hopelijk zal het plotseling staking u dat elk van deze individuele stappen maakt duidelijk zin achteraf. Dus laten we eens een kijkje nemen. 

Dus eerst, we initialiseren wijzer zijn lijst zelf. Want ik wil lineaire tijd, dat betekent Ik ga wat loop hebben. En een gemeenschappelijke manier om itereren over de knopen in lijst structuur of enigerlei structuur iteratief te nemen een pointer naar de voorzijde van de gegevens structuur en dan gewoon beginnen met het updaten en loop je weg door de gegevensstructuur. Dus ik ga om precies dat te doen. 

Terwijl wijzer, mijn tijdelijke variabele, is niet gelijk aan nul, laten we ga je gang en controleren. Heb ik geluk? Is het veld n in de knoop Ik ben momenteel kijken gelijk aan de nummer Ik ben op zoek naar? En zo ja, laten we iets doen. Nu, merken dit als voorwaarde omringt de gehele volgende regels code. Dit is het enige wat ik zorg over - vinden van een nummer in kwestie. Dus er is geen ander, die vereenvoudigt dingen conceptueel een beetje. 

Maar nu, realiseerde ik me, en je zou kunnen hebben pas besefte dat dit na te denken het door een beetje, er is eigenlijk twee gevallen hier. Een is waar het knooppunt is bovenaan begin van de lijst, die een beetje vervelend, want dat is een speciaal geval, omdat je te maken hebt met dit ding, dat is de enige anomalie. Overal elders in de lijst, het is hetzelfde. Er is een eerdere knooppunt en een volgende knooppunt, vorige knooppunt, volgende knooppunt. Maar deze man is een beetje speciaal als hij in het begin. 

Dus als de wijzer is gelijk aan de lijst zelf, dus als ik aan het begin van de lijst en heb n gevonden, moet ik om een ​​paar dingen te doen. Een, moet ik naar de lijst veranderen wijzen naar het volgende veld, 50. Dus stel dat ik probeer te verwijderen 34. Dus deze man heeft om te gaan weg in slechts een moment. 

Dus ik ga zeggen, lijst krijgt pijltje. Nou, dit is wijzer. Vervolgens wijst hier. Dus dit wordt deze pijl rechts veranderende nu hier te wijzen op deze man. Nu, vergeet niet, we hebben een tijdelijke variabele. Dus er is geen knooppunten wees, want ik heb ook deze man in mijn uitvoering van verwijderen. Dus nu, als de lijst zelf is niet nul, Ik moet een beetje iets te repareren. 

Ik moet er nu voor zorgen dat deze pijl, die eerder wijst 50-34, heeft dit te weg te gaan, want als ik probeer te ontdoen van 34, 50 had beter niet handhaven soort terugverwijzing naar het als pijl voorgesteld. Dus ik net deed deze lijn. Dus dan ben ik klaar. Die zaak is eigenlijk vrij eenvoudig. Afhakken van de kop van de lijst is relatief eenvoudig. 

Helaas is er dit vervelend anders blok. Dus nu moet ik het dossier te bestuderen waar er iets in het midden. Maar het is niet al te slecht, met uitzondering van voor de syntax zoals deze. Dus als ik niet aan het begin van de lijst, ik ben ergens in het midden. En deze lijn hier zegt, start op welk knooppunt u toch bezig bent. Ga naar volgend veld het vorige knooppunt en richt die op de aanwijzer. 

Laten we dit doen picturaal. Dat werd steeds ingewikkelder. Dus als ik een eerdere velden hier - laten we dit doen - volgende velden hier. Ik ga mijn pointers eerder vereenvoudigen dan trek je een hele hoop dingen heen en weer kriskras elkaar. En nu, laten we gewoon zeggen dat dit 1, 2, 3 ter wille van de discussie, zelfs hoewel dat niet meer in lijn met het probleem in kwestie. 

Dus hier is mijn gelinkte lijst. Ik ben op zoek naar twee in deze verwijderen bepaalde versie van het verhaal. Dus ik heb pointer bijgewerkt om worden gewezen op deze man. Dus dit is PTR. Hij wijst hier. Dit is de lijst, die bestaat wereldwijd als voorheen. En hij richt zich hier niet uit wat. En nu, ik ben op zoek naar twee te verwijderen. 

Dus als wijzer hier wijst, ben ik gaat volgen, schijnbaar, de vorige wijzer, die mij brengt bij 1. Ik ben vervolgens gaan zeggen dat de volgende veld, dat brengt me naar deze doos hier, gaat gelijke pijltje. Dus als deze wijzer, dit is de volgende. Dat betekent dat deze pijl behoeften om te wijzen op deze man. 

Dus wat dat regel code heeft slechts gedaan is een beetje van dit. En nu, dit is op zoek als een stap in de goede richting. We willen wezen tot 2 snip het midden van 1 en 3. Dus is het logisch dat we willen route deze pointer omheen. Dus deze volgende regel wordt gecontroleerd of wijzer volgende is niet nul, er is inderdaad iemand rechts van 2, dat betekent dat we ook moeten doen een beetje snip hier. 

Dus ik moet nu deze pointer volgen en het actualiseren van de vorige aanwijzer op deze man om een ​​beetje een te doen workaround hier het punt hier. En nu, visueel is dit leuk. Het is een beetje rommelig in dat er niemand wijst naar de 2 meer. 2 wijst naar links. En 2 wijst naar rechts. Maar hij kan doen wat hij wil, omdat hij is over te krijgen bevrijd. En het maakt niet uit wat deze waarden zijn niet meer. 

Wat belangrijk is dat de resterende jongens zijn boven routing en onder hem nu. En inderdaad, dat is wat we nu doen. We gratis wijzer, wat betekent dat we vertellen de besturingssysteem, bent u welkom om deze terug te vorderen. En dan tot slot, keren we terug. Else impliciet, als we zijn nog niet teruggekeerd, we moeten blijven zoeken. Dus wijzer gelijk pijltje net betekent bewegen hier deze kerel. Verplaats hier deze kerel. Verplaats deze man hier als, in feite, we hebben het nummer niet vinden we zijn nog op zoek naar. 

Dus eerlijk gezegd, het ziet er heel overweldigend, denk ik, op het eerste gezicht, vooral als je moeite met deze tijdens de quiz dan zien iets als dit. En je jezelf een schouderklopje. Nou, er is geen manier waarop ik zou kunnen hebben komen met die op de quiz. Maar ik zou zeggen, je kunt als je breken het op in deze individuele gevallen en gewoon doorheen lopen voorzichtig, zij het, toegegeven, onder stressvolle omstandigheden. 

Gelukkig, de foto gemaakt alles gelukkiger. Je zou dit in te trekken een aantal manieren. Je hoeft niet naar de kriskras doen ding hier. Je zou het kunnen doen met rechte lijnen zoals deze. Maar de essentie van dit probleem, in algemeen zou realiseren dat de foto in het einde moet een beetje kijken zoiets als dit, omdat constante tijd impliceerde dat je blijft jammen en jammen en jammen de nieuwe knooppunten in het begin van de lijst. Heeft u nog vragen? Waarschijnlijk de meest uitdagende van zeker de codering vragen. 

PUBLIEK: Dus is de lijst vergelijkbaar met hoofd in de voorgaande voorbeelden. 

DAVID J. MALAN: Precies, precies. Gewoon een andere naam voor een globale variabele. Wereldwijd wat? 

ROB BOWDEN: OK. Dus dit is het een waar je moest de paragraaf te schrijven. Sommige mensen schreven essays voor deze vraag. Maar je hoeft alleen maar om deze zes termen te gebruiken om te beschrijven wat er gebeurt als je probeert om contact facebook.com. Dus ik zal gewoon praten door het proces gebruik van al deze termen. Dus in onze browser, typen we facebook.com en druk op Enter. Dus onze browser gaat om een ​​te bouwen HTTP-verzoeken dat het gaat om sturen door een of ander proces bij Facebook voor Facebook om te reageren op ons met de HTML van de pagina. 

Dus wat is het proces die de HTTP-verzoek krijgt eigenlijk naar Facebook? Dus eerst moeten we vertalen Facebook.com. Dus gewoon de naam Facebook.com, waar eigenlijk doet het HTTP-verzoek moeten gaan? Dus moeten we vertalen Facebook.com een IP-adres, die uniek geeft aan wat de machine eigenlijk we willen deze aanvraag te sturen naar. Uw laptop heeft een IP-adres. Iets aangesloten op het internet heeft een IP-adres. 

Dus DNS, Domain Name System, dat is wat gaat de vertaling te behandelen van facebook.com naar een IP-adres dat je eigenlijk wilt opnemen. Dus nemen we contact op de DNS-servers en zeg, wat is facebook.com? Het zegt, oh, het is het IP-adres 190,212 iets, iets, iets. Oke. Nu, ik weet wat machine Ik wil contact opnemen. 

Dus dan kun je HTTP request sturen naar die machine. Dus hoe werkt het naar die machine? Nou, het verzoek gaat uit router naar router stuiteren. Vergeet niet het voorbeeld in de klas, waar we eigenlijk zagen de route die de pakketten nam toen we probeerden communiceren. We zagen het springen over de Atlantische Oceaan Oceaan op een punt of wat dan ook. 

Dus de laatste term poort. Dus dit is nu op uw computer. Kun je meerdere dingen op dit moment communiceren met internet. Dus ik kan worden uitgevoerd, bijvoorbeeld Skype. Ik zou kunnen hebben een webbrowser geopend. Ik zou iets hebben dat torrenting bestanden. Dus al deze dingen zijn communicatie met de internet op een bepaalde manier. 

Dus wanneer uw computer ontvangt een aantal gegevens van het internet, hoe werkt het weten welke toepassing eigenlijk wil dat de gegevens? Hoe weet of deze specifieke gegevens zijn bedoeld voor de torrenting toepassing in tegenstelling naar de web browser? Dus dit is het doel van havens die al deze toepassingen beweerde een poort op uw computer. Dus uw webbrowser zegt, hey, Ik luister op poort 1000. En uw torrenting programma zegt, Ik luister op poort 3000. En Skype zegt: Ik gebruik poort 4000. 

Dus als je een aantal gegevens op te halen die hoort een van deze toepassingen, de gegevens wordt aangegeven met welke poort het eigenlijk worden meegestuurd naar. Dus dit zegt, oh, ik behoor naar poort 1000. Ik weet dan moet ik dit doorsturen langs op mijn web browser. Dus de reden dat het relevant hier is dat webservers hebben de neiging om luisteren op poort 80. Dus toen ik contact Facebook.com, ik ben gecommuniceerd met bepaalde machine. Maar ik moet die poort van die zeggen machine Ik wil communiceren. En webservers neiging om luisteren op poort 80. 

Als ze wilden, konden ze het stellen dus het geeft als op poort 7000. En dan in een webbrowser, ik kon handmatig Facebook.com: 7000 tot stuurt het verzoek naar poort 7000 van Facebook webserver. 

DAVID J. Malan: En in dit geval, zelfs hoewel we niet eisen dat mensen Dit vermeld, in dit geval, wat port zou het verzoek eigenlijk naar? Probeer opnieuw. Precies. Niet op zoek naar dat, maar een subtiliteit dat is er niemand de laatste. 

ROB BOWDEN: Dus de HTTPS, want het is specifiek te luisteren naar de gecodeerd, het is op poort 4430. 

PUBLIEK: En e-mails zijn 25, toch? 

DAVID J. Malan: Outbound e 25, yep. 

ROB BOWDEN: Ik weet niet eens de meeste van weten het - alle van de lagere neiging om gereserveerd voor dingen. Ik denk dat alles onder 1024 is gereserveerd. 

PUBLIEK: Waarom zei je dat 3 was het verkeerde nummer? 

ROB BOWDEN: Omdat in een IP-adres, er vier groepen van cijfers. En ze zijn van 0 tot 255. Dus 192.168.2.1 is een veel voorkomende lokale netwerk IP-adres. Let op al die minder dan 255. Dus toen ik begon met 300, dat kon onmogelijk hebben is een van de nummers. 

DAVID J. Malan: Maar dat domme clip van - was het CSI, waar ze een getal dat te groot was voor het IP-adres. 

ROB BOWDEN: Heeft u vragen hierover? De volgende, dus volledige verandering in onderwerp, maar we hebben dit PHP array voor de huizen in de quad. En we hebben een ongeordende lijst. En we willen uitprinten elke lijst-item gewoon het huis in de naam voorkomt. Dus we hebben een foreach lus. Dus denk eraan, de syntax is foreach array item in de array. Dus door middel van elke iteratie van de lus, huis gaat over een van de te nemen waarden binnen de matrix. 

Op de eerste iteratie, huis zal Cabot House. Op een tweede iteratie, huis zal zijn Courier House en ga zo maar door. Dus voor elke quad als huis, we zijn gewoon af te drukken - je kon ook hebben herhaald - item in de lijst en vervolgens de naam van het huis en sluit vervolgens het item in de lijst. De accolades zijn hier optioneel. 

En dan hebben we ook gezegd in de vraag zelf, niet vergeten te sluiten de ongeordende lijst tag. Dus moeten we PHP te verlaten om dit te doen. Of we kunnen hebben herhaalde de sluiten ongeordende lijst tag. 

DAVID J. Malan: Ook hier prima zou zijn geweest om een ​​oude school te gebruiken voor lus met een $ i = 0 0 en het gebruik van tellingen achterhalen van de lengte van de straal. Helemaal prima ook, net een beetje wordier. 

PUBLIEK: Dus als je zou gaan [Onverstaanbaar], zou je doen - Ik vergeet wat de lus [onverstaanbaar] is. Zou u $ quad beugel i? 

DAVID J. Malan: Precies. Ja, precies. 

ROB BOWDEN: Anders nog iets? 

DAVID J. Malan: Oke. Trade-offs. Zo waren er trossen van antwoorden mogelijk elk van deze. We waren echt gewoon op zoek naar iets dwingend voor een kop en een keerzijde. En nummer 16 gevraagd, het valideren van gebruikers ingang client-side, zoals JavaScript, in plaats van server-side, als met PHP. Dus wat is een omgekeerde van doen client-side? 

Nou, een van de dingen die we voorgesteld is dat je latency te verminderen, omdat u niet hoeft bezig te houden met de server, die een paar kan duren milliseconden of zelfs een paar seconden door het vermijden van dat en net valideren van gebruikers input client-side door triggering een on-submit handler en just checking, hebben ze typt iets in voor de naam? Hebben ze iets typt in voor het e-mailadres? Hebben ze kiezen voor een studentenhuis uit het drop-down menu? 

U kunt ze geven onmiddellijke feedback met de computer gigahertz of wat ze hebben dat is eigenlijk op hun bureau. Dus het is gewoon een betere gebruikerservaring meestal ervaren. Maar een nadeel van het doen van client-side validatie, als je het doet zonder ook doen server-side validatie is dat bijna iedereen die uit CS50 weet dat je gewoon alle gegevens die u wilt kunt verzenden aan een server een aantal manieren. Eerlijk gezegd, in vrijwel elke browser, kunt u Klik rond in de instellingen en gewoon uitschakelen JavaScript, die zou, dus, uitschakelen elke vorm van validatie. 

Maar je moet ook nog wel herinneren dat zelfs ik deed wat mysterieuze dingen in de klas met behulp van telnet en eigenlijk doen alsof zijn een browser door het sturen van get verzoeken aan een server. En dat is zeker niet met behulp van een webbrowser. Dat is gewoon me typen van commando's een toetsenbord. Dus echt, elke programmeur binnen genoeg comfort met het web en HTTP zou kunnen sturen wat gegevens die hij of zij wil met een server zonder validatie. En als je server is niet ook het controleren, gaven zij mij een naam, is dit eigenlijk een geldig e-mailadres, deed ze kiezen voor een slaapzaal, kun je uiteindelijk Inzetten nep of gewoon lege gegevens in uw database, die waarschijnlijk is niet van plan om een ​​goede zaak zijn als je was in de veronderstelling dat het er was. 

Dus dit is een vervelend realiteit. Maar in het algemeen, client-side validatie is geweldig. Maar het betekent twee keer zoveel werk. Hoewel er bestaan ​​wel verschillende bibliotheken, JavaScript-bibliotheken voor bijvoorbeeld dat dit veel te maken, veel minder van een hoofdpijn. En je kunt een aantal van de code hergebruiken server-side, client-side. Maar besef dat het typisch meerwerk. Yeah. 

Publiek: Dus als we gewoon zei minder veilig - 

DAVID J. Malan: [Lacht] Ugh. Dat zijn altijd de hardere degenen te worden beslist. 

ROB BOWDEN: Dat zou zijn aanvaard. 

DAVID J. Malan: Wat? 

ROB BOWDEN: Ik heb dit probleem. Dat zou zijn aanvaard. 

DAVID J. Malan: Yeah. 

PUBLIEK: Cool. 

ROB BOWDEN: Maar we hebben niet accepteren de eerste - goed, wat we zochten is iets als je niet hoeft te communiceren met de server. We hebben niet gewoon accepteren sneller. 

Publiek: Hoe zit het met niet herlaad pagina? 

ROB BOWDEN: Ja. Dat was een geaccepteerd antwoord. 

DAVID J. Malan: iets waar we voelden het was meer dan waarschijnlijk niet waarschijnlijk dat je wist wat je was zeggen, dat is een moeilijke lijn te trekken soms. Met behulp van een gekoppelde lijst in plaats een array handhaven van een gesorteerde lijst van gehele getallen. Dus een upside we vaak aanhalen met gekoppelde lijsten die hun hele gemotiveerd introductie was je dynamiek krijgen. Ze kunnen groeien. Ze kunnen krimpen. U hoeft dus niet te springen door hoepels om daadwerkelijk te creëren meer geheugen met een array. Of je hoeft niet alleen zeggen, sorry, gebruiker. De array wordt gevuld. Dus dynamische groei van de lijst. Een nadeel echter van gelinkte lijsten? 

Publiek: Het is lineair. Zoeken op gelinkte lijst is lineair in plaats van wat je loggen 

DAVID J. Malan: Precies. Het zoeken op een gelinkte lijst is lineair, zelfs als het gesorteerd, want je kunt alleen volgen deze broodkruimels, deze pointers, vanaf het begin van de lijst aan het einde. U kunt random access en niet benutten, dus, binair zoeken, zelfs als het gesorteerd, die je zou kunnen doen met een array. En er is ook een andere prijs. Yeah. 

PUBLIEK: Geheugen inefficiënt? 

DAVID J. Malan: Yeah. Nou, dat zou ik niet per se zeggen inefficiënt. Maar het kost je meer geheugen, omdat je 32 bits voor elke behoefte knooppunt voor de extra aanwijzer op althans voor een afzonderlijk gelinkte lijst. Nu, als je alleen het opslaan van gehele getallen en je bent het toevoegen van de wijzer, dat is eigenlijk soort van niet-triviaal. Het verdubbelen van de hoeveelheid geheugen. Maar in werkelijkheid, als je het opslaan van een gelinkte lijst van structs dat zou kunnen hebben 8 bytes, 16 bytes, nog dan dat, misschien is het minder van een marginale kostprijs. Maar het is een kosten toch. Dus een van deze zou hebben is fijn als nadelen. 

18. PHP plaats van C schrijven een command-line programma. Dus hier is het vaak sneller in een taal zoals PHP of Ruby of Python. Je gewoon snel te openen een teksteditor. Je hebt veel meer functies voor u beschikbaar. PHP heeft de gootsteen van de functies, terwijl in C, u hebben zeer, zeer weinig. In feite, de jongens kennen de harde manier dat je niet hoeft hash tables. Je hoeft niet hebt gelinkte lijsten. Als u wilt dat deze, moet je zelf implementeren. 

Dus een upside van PHP of echt geen geïnterpreteerde taal is de snelheid waarmee je kunt code schrijven. Maar een nadeel, dit zagen we toen ik snel opgezweept een misspeller implementatie in college met behulp van PHP, is dat middels een geïnterpreteerde taal is meestal langzamer. En we zagen dat aantoonbaar met een toename in tijd vanaf 0,3 seconden tot 3 seconden, omdat de interpretatie dat werkelijk gebeurt. 

Een ander ondersteboven was dat je niet te compileren. Dus het versnelt ook de ontwikkeling overigens, omdat je niet hoeft twee stappen uitvoeren van een programma. Je hoeft alleen een. En dus dat is vrij meeslepend ook. Het gebruik van een SQL-database in plaats van een CSV-bestand om gegevens op te slaan. Dus SQL-database wordt gebruikt voor pset7. CSV-bestanden die u niet veel gebruikt. Maar je indirect worden gebruikt in pset7 als goed door te praten met Yahoo Finance. 

Maar CSV is net als een Excel-bestand, maar super eenvoudig, waarbij de kolommen gewoon demarked door komma's binnen van een anders tekstbestand. En met behulp van een SQL-database is een beetje meer dwingend. Het is een omgekeerde, omdat je dingen zoals selecteren en invoegen en verwijderen. En je krijgt, vermoedelijk, indexen die MySQL en andere databases, zoals Oracle, bouwen voor u in het geheugen, waarin betekent dat uw select is waarschijnlijk niet naar lineaire boven naar beneden zijn. Het eigenlijk gaat om iets te zoals binary search of iets in dezelfde geest. Dus ze zijn over het algemeen sneller. 

Maar een nadeel is dat het is gewoon meer werk. Het is meer inspanning. Je moet databases begrijpen. Je moet het op te zetten. U hebt een server te draaien die database op. U moet begrijpen hoe het te configureren. Dus dit zijn slechts deze soorten van de trade-offs. Overwegende dat een CSV-bestand, kunt u maak het met gedit. En je bent good to go. Er is geen complexiteit verder dan dat. 

Met behulp van een Trie in plaats van een hash table met aparte chaining te slaan een woordenboek met woorden die doen denken van pset5. Dus een probeert op zijn kop, in theorie althans, dat is wat? Constante tijd, tenminste als je hashen van elk van de afzonderlijke letters in een woord, zoals jij zou kunnen hebben voor pset5. Dat zou vijf hashes, zes hashes als er vijf of zes letters in het woord. En dat is vrij goed. En als er een bovengrens van hoe lang uw woorden zou kunnen zijn, dat is inderdaad asymptotisch constante tijd. 

Overwegende dat een hash table met aparte chaining, het probleem is er met dat type gegevensstructuur is dat de prestaties van uw algoritmen meestal afhankelijk van het aantal zaken reeds in de gegevensstructuur. En dat is zeker het geval met kettingen, waarbij de meer spullen je in een hash table, hoe langer die ketens gaan, wat betekent dat in het ergste geval, het ding dat je misschien op zoek naar is helemaal aan het einde van een van die ketens, die effectief delegeert in iets lineair. 

Nu, in de praktijk kan absoluut het geval dat een hash tabel met ketens sneller dan een vergelijkbare trie implementatie. Maar dat is om verschillende redenen, onder die probeert zijn gebruik maken van een heleboel geheugen dat kan, in feite, vertraag naar beneden, omdat je niet leuk voordelen van een zogenaamde caching, waar de dingen die dicht bij elkaar zijn geheugen kan worden benaderd vaak sneller. En soms kun je komen met een echt goede hash-functie. Zelfs als je een beetje van het afval geheugen, je zou inderdaad kunnen dingen te vinden snel en niet zo slecht als lineair. 

Dus in het kort, was er niet per se met een van deze een of zelfs twee specifieke dingen die we zochten. Echt iets overtuigend als een positieve en negatieve aspecten algemeen gevangen ons oog. 

ROB BOWDEN: Dus voor de kop, we deden niet accepteren op zijn eigen "sneller." U moest iets over te zeggen. Zelfs als je in theorie sneller gezegd, we wisten dat je soort van begrepen dat het een 0 of 1. En hash table, in theorie, is 0 of 1. Iets over runtime vermelden over het algemeen heb je de punten. Maar "sneller," de meeste van de oplossingen op het grote bord die werden pogingen waren objectief langzamer dan oplossingen dat waren hash tabellen. Dus sneller op zich is niet echt waar. 

DAVID J. Malan: Dom de Dom Dom. Ik ben waarschijnlijk de enige die beseft dat is hoe dat zou moeten worden uitgesproken, toch? 

ROB BOWDEN: Ik had eigenlijk geen idee. 

DAVID J. Malan: Het maakte gevoel in mijn hoofd. 

ROB BOWDEN: Ik doe deze. OK. Dus dit is het een waar je moest tekenen het diagram vergelijkbaar met je misschien hebben gezien op het verleden examens. Dus laten we gewoon kijken naar dit. Dus van de HTML-knooppunt, hebben we twee kinderen, het hoofd en het lichaam. Dus vertakken we - hoofd en lichaam. Het hoofd heeft een title tag. Dus we hebben een titel. 

Nu, het enige wat een heleboel mensen vergeten is dat deze tekst knooppunten zijn elementen binnen deze boom. Dus hier gebeuren we ze trekken als ovalen om ze te onderscheiden van deze typen knopen. Maar let ook hier hebben we de top, midden-en onderkant zal uiteindelijk op een tekstnodes. Dus vergeet die was enigszins van een veel voorkomende fout. 

Het lichaam heeft drie kinderen - deze drie divs. Dus div, div, div en vervolgens de tekst knooppunt kinderen van die divs. Dat is vrij veel het voor die vragen. 

DAVID J. Malan: En het is vermeldenswaard, hoewel we niet stilstaan ​​bij deze details in de tijd die we besteden aan JavaScript, dat de bestelling doet, in feit, materie technisch. Dus als hoofd komt voor lichaam in de HTML, dan moet lijken de links van lichaam in de werkelijke DOM. Dat zijn, in het algemeen, net FYI, iets geroepen document orde, waar het ertoe doet. En als je de uitvoering van een parser, een programma dat HTML leest in de bouw de boom in het geheugen, om eerlijk te zijn, dat is intuïtief waarschijnlijk wat je toch doen - van boven naar beneden, van links naar rechts. 

ROB BOWDEN: Vragen over zeggen? Doe ik de volgende? 

DAVID J. Malan: Zeker. 

ROB BOWDEN: OK. Dus dit is de bufferoverloop aanval vraag. Het belangrijkste ding om te herkennen is, goed, hoe zou een tegenstander truc dit programma in het uitvoeren willekeurige code? Dus argv1, de eerste command line argument programma, dat kan worden willekeurig lange. Maar hier gebruiken we memcpy kopiëren argv1, die hier is bar. We passeren het als het argument. En dus is het overnemen van de naam bar. 

Dus we memcpying bar in deze buffer c. Hoeveel bytes zijn we kopiëren? Nou hoeveel bytes bar overkomt worden gebruikt, de lengte van dit argument. Maar c is slechts 12 bytes groot. Dus als we een command line argumenten in te typen dat is langer dan 12 bytes, we zijn ga dit overstromen bijzonder buffer. Nu, hoe kan een tegenstander te misleiden de programmeren in het uitvoeren van willekeurige code? 

Dus vergeet niet dat hier belangrijkste belt foo. En zo is dan de belangrijkste oproepen foo. Laten we trekken dit. Dus hebben we onze stack. En belangrijkste heeft een stackframe onderaan. Op een gegeven moment, de belangrijkste oproepen foo. Nou, onmiddellijk, de belangrijkste oproepen foo. En dus foo krijgt zijn eigen stack frame. 

Nu, op een bepaald punt, foo gaat terug. En ging foo rendement, moeten we weten op welke lijn van code binnen van de belangrijkste we waren om te weten waar we moeten weer in de belangrijkste. We kunnen foo bellen vanuit een geheel bos van verschillende plaatsen. Hoe weten we waar om terug te keren? Nou, we moeten dat ergens op te slaan. 

Dus ergens rechts hier in de buurt, we slaan waar we moeten terug naar een keer foo rendement. En dit is het retouradres. Dus hoe een tegenstander zou kunnen profiteren hiervan is dat deze buffer c wordt opgeslagen, laten we zeggen, hier is c. We hebben dus 12 bytes voor c. Dit is c. En dit is foo's stack ring. Dus als de kwaadwillende gebruiker meer binnenkomt bytes dan 12 of zij een opdracht in line argument dat is langer dan 12 personages, dan gaan we naar overstromen deze buffer. 

We kunnen blijven gaan. En op een gegeven moment, gaan we ver genoeg dat we beginnen overschrijven dit retouradres. We dus zodra overschrijven het retouradres, Dit betekent dat wanneer foo rendementen, we terugkeren naar de plaats waar de kwaadwillende gebruiker vertelt dat het door welke waarde het aangaan, met welke tekens de gebruiker heeft ingevoerd. En dus als de kwaadwillende gebruiker wordt bijzonder slim, kan hij deze hebben terug naar ergens in de printDef functie of ergens in de malloc functie, zomaar ergens willekeurig. 

Maar nog meer slimme is wat als hij de gebruiker terug naar hier. En dan ga je het uitvoeren deze als regels code. Dus op dat punt, kan de gebruiker in te voeren wat hij wil in deze regio. En hij heeft de volledige controle over uw programma. Vragen over zeggen? Dus de volgende vraag is compleet de herimplementatie van foo een zodanige wijze dat het niet meer kwetsbaar is. 

Dus er is een paar manieren je kan dit gedaan hebben. We hebben nog steeds c alleen welzijn van lengte 12. Je zou dit kunnen zijn veranderd als onderdeel van uw oplossing. We hebben ook nog een cheque te maken zeker bar was niet null. Hoewel je niet nodig hebt dat voor het volledige krediet. Dus we eerst controleren van de snaarlengte van bar. Als het groter is dan 12, dan eigenlijk niet doen de kopie. Dus dat is een manier van vaststelling van het. 

Een andere manier van de vaststelling is in plaats van met c slechts een lengte van 12, laat het dan zijn lengte strlen (bar). Een andere manier van de vaststelling is eigenlijk gewoon terug. Dus als je had net gekregen ontdoen van al dit, als je gewoon alles had gewist regels code, zou u hebben gekregen volledige krediet, omdat deze functie eigenlijk niet alles bereiken. Het kopiëren van de command line argument in een aantal array in haar lokale stack frame. En dan is het ding terugkeert. En wat het ook volbracht is verdwenen. Dus rendement ook een voldoende manier om volledige krediet. 

DAVID J. Malan: Niet helemaal de geest van de vraag, maar per de aanvaardbare spec toch. 

ROB BOWDEN: Vragen over een van die? Het een ding dat je op zijn minst nodig te hebben compileren code. Dus hoewel technisch gezien ben je niet kwetsbaar als uw code niet compileren, hebben we niet accepteren. Geen vragen? OK. 

DAVID J. Malan: Wilt u om deze titel te zeggen? 

ROB BOWDEN: Nee. 

DAVID J. Malan: Dus in dit ene, dit was ofwel goed nieuws of slecht nieuws. Dit is letterlijk hetzelfde probleem als de eerste quiz. En het is bijna hetzelfde probleem als pset1. Maar het is bewust vereenvoudigd worden een eenvoudiger piramide, die kan worden opgelost met een licht eenvoudiger iteratie. En echt, wat we kregen bij hier was niet zozeer de logica, want waarschijnlijk, door dit punt, je bent comfortabeler dan je was week een met lussen of waarom loops, maar echt om elkaar te plagen dat je een beetje comfortabel met de notie dat PHP is niet alleen om wat programmering. Het kan zelfs worden gebruikt als een taal command line programma's te schrijven. 

En inderdaad, dat is wat we wilden om uw aandacht te vestigen op. Dit is een command line PHP-programma. Dus C code hier, terwijl juist in C, niet corrigeren voor PHP. Maar de code is echt hetzelfde. Als je de oplossingen voor Quiz vergelijken 0 tegen Quiz 1, zul je dat vinden het is bijna identiek, behalve sommige dollartekens en voor de Aangezien een gegevenstype. In het bijzonder, als we een kijkje nemen hier, je zult zien dat we herhalen, in dit geval, van 1 tot en met 7. 

We zouden het gedaan hebben 0-index. Maar soms, ik denk dat het gewoon mentaal makkelijker om na te denken over dingen van 1 tot 7. Als u wilt een blok, dan twee blokken, dan drie, dan dot, dot, dot zeven. We hebben j geïnitialiseerd op 1 en dan tellen op tot i. En alles is hier verder identiek. Maar opmerkelijk zijn een paar dingen. Wij geven u deze twee lijnen, deze eerste een, goofily genoemd als een keet voor scherpe knal. En dat alleen geeft u het pad, de map waarin een programma kan gevonden dat u wilt gebruiken om dit bestand te interpreteren. 

En dan is de lijn na dat van betekent natuurlijk voer PHP modus. En de lijn op de bodem betekent exit PHP modus. En deze werkt in het algemeen met geïnterpreteerde talen. Het is een beetje vervelend als je schrijven programma in een bestand genaamd foo.php. En dan je gebruikers moet gewoon vergeet niet, OK, om dit programma uit te voeren, ik maar "php ruimte foo.php." Soort vervelend als er niets anders. En het toont ook aan dat je programma wordt geschreven in PHP, die niet allemaal die verlichting voor de gebruiker. 

Dus je kunt het. Php totaal verwijderen herinnert uit lezing. En je kunt eigenlijk doen. / Foo als je hebt het chmodded doordat het uitvoerbaar. Dus chmod a + x foo zou moeten doen. En als je ook toevoegen de keet hier. Maar echt, het probleem was om op afdrukken van iets als dit. Geen HTML, geen C-code zeker, slechts enkele PHP. Dus Milo daarna terug in probleem 25. En in 25, kreeg je de volgende skelet code, en dat was een vrij eenvoudig webpagina. En het sappige gedeelte HTML-wise was beneden hier, waar we in het lichaam een vorm die unieke ID van de ingangen heeft binnenkant van die twee ingangen, een met een idee van de naam, een een idee van knop. 

De eerste was het type tekst, de tweede van het type in te dienen. En dus gaven we u, eigenlijk, meer ingrediënten dan je nodig had, net zo jullie hadden opties waarmee om dit probleem op te lossen. U hoeft niet strikt nodig al deze ID. Maar het staat je op te lossen het op verschillende manieren. En op de top, merkt dat was het doel leiden een venster als dit - Hallo, Milo! - om pop-up in de browser met behulp van de super simpel, als niet lelijk, alert functie. En zo, uiteindelijk, komt dit neer conceptueel een of andere manier te luisteren naar inzendingen van het formulier client-side , Niet de server-side, een of andere manier reageren op dat indiening door grijpen de waarde die de gebruiker heeft ingevoerd in het veld naam, en vervolgens weer te geven in het lichaam van een waarschuwing. 

Dus een manier waarop je dit kunt doen is met jQuery, die ziet er een beetje syntactisch verwarrend op het eerste. U kunt dit doen met pure DOM code - document.getelement door ID. Maar laten we eens kijken naar deze versie. Ik heb een paar belangrijke lijnen eerste. Dus een, hebben we deze lijn, dat is identiek aan wat je misschien hebt gezien in, geloof ik, form2.html van klasse in week 9. En dit is gewoon te zeggen, uit te voeren de volgende code wanneer het document klaar. Dit is alleen belangrijk omdat HTML-pagina's worden boven lezen beneden, van links naar rechts. 

En daarom, als je probeert te doen iets in de code hier om wat DOM element, sommige HTML-tag, dat is naar beneden hier, je doet het te vroeg, omdat dit nog niet ingelezen in het geheugen. Dus door dit te zeggen document.ready lijn, we zeggen, hier is een code, browser. Maar doe dit niet uitvoeren totdat de hele document klaar is, dat de DOM boom bestaat in het geheugen. Deze is een beetje meer eenvoudig, als syntactisch een beetje anders, waar ik zeg, pak het HTML-element wiens unieke identifier is ingangen. Dat is wat de hash-tag duidt, het unieke ID. En dan ik bel. Indienen. 

Dus. Hier dient een functie anders bekend als een werkwijze, die binnenkant van het object op de linker kant is er dat ik niet te benadrukken. Dus als je denkt van inputs als een object in het geheugen - en dat is het ook. Het is een knooppunt in een boom - . Indienen middel wanneer dit formulier met Deze ID wordt ingediend, voeren de volgende code. Kan me niet schelen wat de naam van de functie is dat ik het uitvoeren. Dus hier ben ik met behulp van, zoals voorheen, wat is zogenaamde lambda-functie of een anonieme functie. Het is helemaal niet intellectueel interessanter dan dat het geen naam heeft, wat fijn is als je alleen bent ooit nog eenmaal aan te roepen. En binnen is er ik eigenlijk behandelen de indiening van het formulier. Ik voor het eerst een variabele declareert genoemd waarde. En wat is dan het effect van deze gemarkeerd gedeelte hier nu? Wat doet dat op een hoog niveau voor mij? 

Publiek: Het wordt de waarde die de gebruiker niet in de onderstaande HTML. Het wordt dat ID en vervolgens vindt de waarde ervan. 

DAVID J. Malan: Precies. Het grijpt het knooppunt, wiens unieke identifier is de naam. Het wordt daarin de waarde, die is vermoedelijk wat de gebruiker getypt hem-of haarzelf. En dan slaat dat in de variabele genaamd waarde. Even terzijde, kan je ook gedaan dit een beetje anders. Volledig aanvaardbaar door iets te doen leugen var waarde krijgt document.getElementById. En dit is waarom het is een beetje vervelend om geen gebruik van jQuery. "Naam". Waarde. Zo volledig aanvaardbaar. Verschillende manieren om dit te doen. jQuery gewoon heeft de neiging om een ​​beetje meer beknopte en zijn zeker meer populair onder programmeurs. 

Nu, ik ben bezig met een beetje een gezond verstand controleren, omdat in het probleem verklaring we expliciet gezegd, als de gebruiker heeft nog niet getypt zijn of haar noemen, hebben geen waarschuwingen niet tonen. Maar je kunt controleren of die, door gewoon controleren op de lege string voor een citaat-unquote als er eigenlijk niets daar. Maar als het niet gelijk is aan offerte-unquote, Ik wil waarschuwingen bellen. En het interessante deel is dat we gebruiken de plus operator, die wat doet in JavaScript? Aaneenschakelen. Dus het is net PHPs dot operator. Zelfde idee, iets andere syntax. En ik ben gewoon het creëren van de string die zag je op het screenshot - Hallo, zo en zo. 

En dan de laatste detail is dit. Waarom moet ik valse binnenkant terug van deze anonieme functie? 

Publiek: Er is geen waarde. Je zet het in vorm. Het zegt alleen maar, als de waarde niet gelijk aan leeg, doe het dan. Er was een blanco in die onderwerping. 

DAVID J. Malan: OK. Voorzichtig. Er is niemand anders hier. En dat rendement valse buiten van de als de omstandigheden. Dus benadrukt deze lijn, return false, voert niet uit wat toen het formulier wordt ingediend. Wat betekent de terugkeer valse binnenkant van deze event handler, zoals dat heet, het evenement in kwestie zijnde indienen? 

Publiek: Omdat het slechts een keer gebeurt. 

DAVID J. Malan: Alleen gebeurt een keer. Niet helemaal. Yeah? 

Publiek: Het voorkomt dat het formulier indienen om het standaard gedrag, die de pagina reload zou maken. 

DAVID J. Malan: Precies. Dus ik ben overbelasting van de termijn in te dienen hier, want ik zeg, de vorm is worden voorgelegd. Maar zoals u voorstelt, is het eigenlijk niet ingediend in de ware HTTP manier. Wanneer u op Verzenden klikt, vanwege onze onSubmit handler, we onderscheppen dat formulier indienen bij wijze van spreken. We zijn dan doen ons ding met JavaScript-code. Maar ik ben met opzet terug vals, want wat ik niet willen dat er gebeurt een fractie van een seconde later is voor het hele formulier zich op het web te worden ingediend server met belangrijke waarde paren door het veranderen de URL naar iets als q = katten of wat we ook deden, bijvoorbeeld in de klas. Ik wil niet dat dit gebeurt, omdat er is geen server luisteren voor deze formulier indienen. Het is puur gedaan in JavaScript-code. En dat is waarom ik heb niet eens een actie attribuut op mijn vorm, omdat ik niet van plan om dit te laten ooit naar de server. 

Dus het wordt voorgelegd. Maar we onderscheppen die vorm indiening en het voorkomen van de standaard gedrag, die daadwerkelijk ga helemaal naar de server. 

Publiek: Dus het houden van het client-side. 

DAVID J. Malan: Keeping het client-side. Precies goed. Next up was mijn oh MySQL. 

ROB BOWDEN: OK. Dus deze eerste vraag was over het algemeen ruw voor mensen. Hoewel de latere ging het beter. Dus je moest de juiste gegevens kiezen types voor beide kolommen. En beide hebben sommige dingen over hen die maken de keuze moeilijk. Dus int was geen geldige Typ voor nummer. De reden hiervoor is een 12-cijferige rekeningnummers nummer, een int is niet groot genoeg om slaan totale cijfers. Dus zou een geldige keuze een grote zijn geweest int als je toevallig te weten dat. Een andere keuze had kunnen zijn een char gebied van lengte 12. Dus een van die zou hebben gewerkt. Int niet. 

Nu, balans, denk terug aan pset7. Dus we specifiek gebruikt decimaal naar opslaan van de waarde van aandelen of - 

DAVID J. Malan: Cash. 

ROB BOWDEN: Cash. We gebruikten decimaal om de hoeveelheid op te slaan geld dat de gebruiker heeft op dit moment. Dus de reden waarom we dat doen is want vergeet niet, drijvers. Er is floating point precisie. Het kan niet precies het geld op te slaan waarden als we willen hier. Dus decimaal nauwkeurig kunnen slaan iets te zeggen, twee decimalen. Daarom balans, we willen het decimale en niet drijven zijn. 

DAVID J. Malan: En ook, ook, hoewel het zou slim zijn geweest in andere contexten te denken, misschien is dit is een kans voor een int. Ik zal gewoon bijhouden dingen in centen. Omdat we expliciet toonde de standaard waarde van het 100.00, dat betekent dat het kon gewoon een int zijn. En nog een subtiliteit ook met nummer was dat het niet bedoeld was een strikvraag zijn. Maar herinneren dat een int in MySQL, zoals in C, althans in de apparaat, is 32-bits. En hoewel we je niet verwachten dat precies weten hoeveel cijfers die middelen, niet herinneren dat het grootste aantal je kan mogelijk vertegenwoordigen met een 32-bits getal is ongeveer wat? 

Welk nummer moet we altijd zeggen? 2 van de 32, wat ruwweg? Je hoeft niet precies te weten. Maar ruwweg is nuttig in het leven. Het is ongeveer 4 miljard. Dus hebben we gezegd dat een paar keer. Ik weet dat ik gezegd heb dat een paar keer. En het is ongeveer 4 miljard. En dat is een goede regel van de duim te weten. Als je 8 bits, 256 is het magische getal. Als u 32-bits, 4 miljard geven of te nemen. Dus als je gewoon opschrijven 4000000000, je zult zien dat het minder cijfers dan 12, waardoor het duidelijk niet genoeg zeggingskracht om het veroveren van een 12-cijferig rekeningnummer. 

ROB BOWDEN: OK. Dus de anderen ging het beter. Dus stel dat de bank legt een $ 20 per maand onderhoud vergoeding voor alle accounts. Met welke SQL-query kon de bank aftrekken $ 20 van elke rekenen, zelfs als het resulteert in een aantal negatieve saldi? Dus eigenlijk zijn er vier hoofdtypen van vragen - invoegen, selecteert, bijwerken en verwijderen. Dus wat doen we denken dat we hier gaan gebruiken? Updaten. 

Dus laten we eens een kijkje nemen. Dus hier zijn we updaten. Wat tabel worden we updaten accounts? Dus updaten accounts. En dan de syntax zegt, wat in de rekeningen van zijn werken we? Nou, we zetten we balans gelijk aan de huidige waarde van de balans minus 20. Dus dit zal alle rijen updaten van de rekeningen, het aftrekken $ 20 van de balans. 

DAVID J. Malan: Een veel voorkomende fout hier, ook al hebben we soms vergaf het, was om daadwerkelijk PHP code hier roepen de query functie of zetten aanhalingstekens rond alles wat niet nodig om daar te zijn. 

ROB BOWDEN: Vergeet niet dat MySQL een aparte taal van PHP. We toevallig te schrijven MySQL in PHP. En PHP is waarna het wordt naar de MySQL server. Maar je hoeft geen PHP nodig om communiceren met een MySQL server. 

DAVID J. Malan: Precies. Dus geen variabelen met dollartekens moet in deze context. Het kan gewoon allemaal van de wiskunde te doen binnen de database zelf. 

ROB BOWDEN: OK. Dus de volgende. Is dit de volgende? Yeah. Dus met wat SQL-query kon de bank de rekeningnummers van haar op te halen rijkste klanten die met saldi groter dan 1000? Dus welke van de vier belangrijkste soorten gaan we hier? Selecteren. Dus we willen selecteren. Wat willen we om te kiezen? Wat kolom willen we selecteren? We zullen specifiek willen te selecteren. Maar als je zei ster, we ook aanvaard dat. 

Dus kiezen nummer uit welke tafel? Accounts. En dan is de voorwaarde die we willen? Wanneer saldo groter dan 1000. We hebben aanvaard ook een grotere hoogste. Laatste. Met welke SQL-query kon de bank dicht, dat wil zeggen, verwijderen elke rekening die heeft een saldo van $ 0? Dus welke van de vier zijn wij gaat te willen gebruiken? Verwijderen. Dus de syntaxis voor dat? Verwijderen uit welke tafel? Accounts. En vervolgens aan de voorwaarde we willen verwijderen - waar saldo gelijk is aan nul. Dus verwijder alle rijen van accounts waarbij het saldo nul. Vragen over een van deze? Willen in de rij? 

DAVID J. Malan: Queue gids. Dus in dit ene, gaven we u een wat vertrouwde structuur die we onderzocht een beetje in de klas naast structs, die een data was structuur verwante geest. Het verschil echter met een wachtrij is dat we een of andere manier herinneren wie aan de voorzijde van de wachtrij in grote deel zodat we konden meer maken efficiënt gebruik van het geheugen, althans als we met behulp van een array. 

Omdat terugroepen, als we een array, als, Zo is de voorzijde van de rij, als ik in de rij hier, en dan iemand in de lijn krijgt achter mij, achter mij, achter mij, en een persoon stapt uit lijn, u kon, zoals we zagen een aantal van onze menselijke vrijwilligers in de klas, hebben iedereen verschuiven deze manier. Maar in het algemeen, heeft iedereen doen iets wat niet het beste gebruik van de tijd in een programma, want het betekent dat uw algoritme loopt in welke asymptotische looptijd? Het is lineair. 

En ik voel me als dat is nogal dom. Als de volgende persoon in de rij is de volgende persoon die wordt verondersteld in de te gaan opslag, ze niet allemaal samen bewegen. Laat die persoon worden geplukt wanneer de tijd komt, bijvoorbeeld. Dus we kunnen een beetje tijd daar besparen. En zo te doen dat, hoewel, dat betekent dat het hoofd van de wachtrij of de vooraan in de wachtrij gaat geleidelijk verplaatsen dieper en dieper in de array en uiteindelijk misschien eigenlijk wikkel rond als we met behulp van een array om de mensen op te slaan in deze wachtrij. Dus je kunt bijna denken aan de array als een cirkelvormige data structuur in die zin. 

Zodat je een of andere manier moeten bijhouden van de te houden grootte van het of echt het einde van het en wanneer het begin is. Dus stellen wij voor dat u verklaren een dergelijke wachtrij, roeping het q, slechts een letter. Dan stellen we dat het front geïnitialiseerd op nul en dat de grootte geïnitialiseerd op nul. 

Dus nu is er niets binnenkant van deze rij. En wij vragen u in te vullen de uitvoering van enqueue hieronder in zodanig dat de functie voegt n om het einde van q en dan geeft true. Maar als q vol is of negatief, de functie moet in plaats daarvan return false. En we gaven je een paar aannames. Maar ze zijn niet echt functioneel relevant, alleen dat bool bestaat, omdat, technisch, bool niet bestaan ​​in C, tenzij je onder andere een bepaalde header file. Dus dat was gewoon zorgen dat er werden er geen is dit een truc vraag soort dingen. 

Dus enqueue, we in de steekproef voorgesteld oplossingen te implementeren als volgt. Een, controleren we eerst het gemak, het laaghangende fruit. Als de wachtrij vol is of het nummer dat je probeert in te voegen is minder dan nul, wat we zeiden in de specificatie van het probleem moet niet worden toegestaan, omdat we alleen willen niet-negatieve waarden, dan moet je gewoon direct return false. Dus sommige relatief eenvoudig foutcontrole. Als al je wilt dat de werkelijke voegen nummer, je moest een beetje doen denken hier. En dit is waar het is een beetje vervelend mentaal, want je moet uitzoeken hoe wraparound behandelen. 

Maar de kiem van het idee hier is dat van belang voor ons is dat wraparound Vaak impliceert modulaire rekenkunde en de mod operator, het percentage kant, waar je kan gaan van een grotere waarde terug naar nul en dan een en twee en drie en dan terug rond nul, een en twee en drie enzovoort opnieuw en opnieuw. Dus de manier waarop we stellen voor om dit te doen is dat we willen index in de array met de naam nummers waar onze gehele getallen liggen. Maar om daar te komen, we willen eerst doen ongeacht de grootte van de wachtrij, maar vervolgens aan dat wat de Voor de lijst. En het effect van die zetten ons op de juiste positie in de wachtrij en niet van uitgaan dat de eerste persoon in de rij aan het begin, waarvoor hij ze absoluut kunnen zijn als we werden ook verschuiven iedereen. Maar we zijn gewoon het creëren van werk voor onszelf als we namen dat bepaald pad. 

Dus we houden relatief eenvoudig. We moeten niet vergeten dat we net een int toegevoegd aan de wachtrij. En dan gaan we gewoon terug waar. Ondertussen, in dequeue, vroegen we u het volgende doen. Implementeren zodanig dat dequeues, dat is verwijdert en keert terug, de int vooraan wachtrij. Om de int verwijderen, volstaat om het te vergeten. Je hoeft niet te zijn wat overschrijven. Dus het is eigenlijk nog steeds. Net als data op een harde schijf, we zijn gewoon het negeren van het feit dat het er nu. En als q leeg is, moeten we plaats terug negatief 1. Dus dit voelt arbitrair. Waarom keren negatief 1 in plaats van valse? Yeah. 

PUBLIEK: Q opslaat positieve waarden. Omdat je alleen positieve waarden opslaan in de q, negatieve is een fout. 

DAVID J. MALAN: OK, waar. Dus omdat we alleen het opslaan van positieve waarden of nul, dan is het prima om terug een negatieve waarde als een schildwacht waarde, een speciaal symbool. Maar je herschrijven geschiedenis daar, want de reden dat we alleen retoursysteem voor niet-negatieve waarden is omdat we willen hebben een sentinel waarde. Dus meer in het bijzonder, waarom niet gewoon return false in geval van fouten? Yeah. 

PUBLIEK: Je hebt gefaald een integer terug. 

DAVID J. Malan: Precies. En dit is waar C krijgt vrij beperkend. Als je zegt dat je gaat naar een int terug, heb je naar een int terug. Je kunt niet chique en beginnen terug te keren een bool of een float of een touw of iets dergelijks. Nu, ondertussen, JavaScript en PHP en andere talen kunnen, in feite, heb je verschillende terugkeren soorten waarden. En dat kan eigenlijk nuttig zijn, waar u zou kunnen positieve gehele getallen, nullen terug, negatieve gehele getallen, of valse of null zelfs fout betekenen. Maar we hebben niet dat veelzijdigheid in C. 

Dus met dequeue, wat we voorstellen te doen is - 

ROB BOWDEN: U kunt valse terugkeren. Het is gewoon dat vals is hash definiëren valse nul. Dus als je vals terugkeren, je bent terug op nul. En nul is een geldig ding in onze wachtrij, terwijl negatieve 1 is niet of valse toevallig negatief 1. Maar je moet niet eens moeten weten dat. 

DAVID J. Malan: Dat is waarom ik niet zeggen. 

ROB BOWDEN: Maar het was niet waar dat je niet vals kunt terugkeren. 

DAVID J. Malan: Zeker. Dus dequeue, merken we accepteren vervallen als argument. En dat is omdat we niet iets voorbij inch We willen alleen het element te verwijderen aan de voorkant van de wachtrij. Dus hoe kunnen we dat doen? Nou, ten eerste, laten we dit doen snel sanity check. Als de wachtrij grootte is 0, er is geen werk te doen. Terug negatief 1. Gedaan. Dus dat is een paar lijnen van mijn programma. Dus alleen vier lijnen blijven. 

Dus hier Ik besluit om te verlagen de grootte. En effectief decrementing de grootte betekent dat ik vergeten iets wat er in zit. Maar ik heb ook te werken waar de voorzijde van de nummers. Dus om dat te doen, moet ik twee dingen doen. Ik moet eerst herinneren wat het aantal is aan de voorkant van de wachtrij want ik moet dat ding terug. Dus ik wil niet per ongeluk vergeten over en overschrijven vervolgens. Ik ga gewoon om te onthouden in een int. 

En nu, ik wil updaten q.front te q.front 1. Dus als dit was de eerste persoon in lijn, nu, ik wil plus 1 doen om wijzen op de volgende persoon in de rij. Maar ik moet dat wraparound verwerken. En als de capaciteit is een wereldwijde constante, dat gaat mij toe om ervoor te zorgen als ik wijzen op de allerlaatste persoon in lijn, zal de modulo operatie brengen me terug naar nul bij de vooraan in de wachtrij. En dat zorgt voor de wraparound hier. En ga dan ik om terug te keren n. 

Nu, strikt genomen, niet ik moeten verklaren n. Ik hoefde niet om het te grijpen en op te slaan tijdelijk, omdat de waarde er nog steeds. Dus ik kon gewoon de juiste rekenkundige om het voormalige hoofd terug van de wachtrij. Maar ik voelde dat dit was meer duidelijk om daadwerkelijk pak de int, zet het in n, en dan terug dat voor de duidelijkheid maar niet strikt noodzakelijk. Psst. Ze zijn allemaal uitspreekbaar in mijn hoofd. 

ROB BOWDEN: Dus eerste vraag is de binaire boom probleem. Dus eerste vraag is, we zijn aangezien deze nummers. En we willen een of andere manier invoegen in deze knooppunten zodanig dat het een geldige binaire zoekboom. Zodat het een ding om te onthouden over binary search bomen is dat het niet alleen dat het ding naar links is minder en het ding om Rechts is groter. Het moet de gehele boom Links is minder, en de hele boom rechts is groter. 

Dus als ik 34 hier aan de top, en dan Ik zet 20 hier, dus dat is geldig zo ver, want 34 hier. 20 gaat naar links. Dus dat is minder. Maar ik kan niet zet dan 59 hier, omdat ook al 59 is aan de rechterkant van de 20, het is nog steeds links 34. Dus met die beperking in het achterhoofd, de gemakkelijkste manier om dit waarschijnlijk oplossen probleem is om gewoon soort van deze nummers - zo 20, 34, 36, 52, 59, 106. En voer dan deze van links naar rechts. 

Dus 20 gaat hier. 34 gaat hier. 36 gaat hier. 52, 59, 106. En je kon ook hebben bedacht met sommige inpluggen en realiseren, oh, wacht, ik heb niet genoeg nummers hebben om dit in te vullen hier. Dus ik moet reshift wat mijn route notitie gaat worden. Maar merk op dat in de laatste drie, indien je leest van links naar rechts, het is in oplopende volgorde. 

Dus nu willen we verklaren wat de struct gaat worden voor de knooppunten in deze boom. Dus wat hebben we nodig in een binaire boom? Dus we hebben een waarde van het type int, dus sommige int waarde. Ik weet niet wat wij noemen in de oplossing - int n. We moeten een aanwijzer naar de linkerkant kind en een pointer naar rechts kind. Dus het gaat er zo uitzien. En het zal echt kijken voordat wanneer heeft de dubbel-linked lijst spul, zo bericht - Ik ga moet scrollen alle weg terug naar probleem 11. 

Zo merkt het ziet er identiek aan deze, behalve wij toevallig deze bellen verschillende namen. We hebben nog steeds een geheel getal waarde en twee pointers. Het is gewoon dat in plaats van het behandelen van de pointers als wijzend naar het volgende ding en de vorige ding, we behandelen de pointers om te wijzen op een linker kind en rechts kind. OK. Dus dat is onze struct node. En nu, de enige functie moeten we implementeren hiervoor is traverse, die we willen gaan over de boom, drukkerij de waarden van de boom in orde. 

Dus hier kijken, zouden we willen afdrukken uit 20, 34, 36, 52, 59 en 106. Hoe gaan we dat bereiken? Dus het is redelijk vergelijkbaar. Als je zag in het verleden examen het probleem die je wilde om uit te printen de hele boom met komma's ertussen alles, het was eigenlijk zelfs eenvoudiger dan dat. Dus hier is de oplossing. Dit was aanzienlijk eenvoudiger als je het deed recursief. Ik weet niet of iemand geprobeerd het iteratief doen. 

Maar eerst moeten we ons basisscenario. Wat indien de wortel nul? Dan zijn we gewoon gaan om terug te keren. We willen niet om iets af te drukken. Anders gaan we te doorkruisen recursief naar beneden. Print de hele linkerkant deelboom. Dus drukken alles minder dan mijn huidige waarde. En dan ga ik mezelf af te drukken. En dan ga ik recurse langs mijn gehele rechter deelboom, dus alles groter dan mijn waarde. En dit gaat om af te drukken alles in orde is. Vragen over hoe dit eigenlijk volbrengt dat? 

Publiek: Ik heb een vraag op de [onverstaanbaar]. 

ROB BOWDEN: Dus een manier van benaderen elke recursieve probleem is om gewoon te denken over het leuk je moet denken over al de hoek gevallen. Dus bedenkt dat we willen print deze hele boom. Dus alles wat we zijn gaan richten op is dit bepaald knooppunt - 36. De recursieve aanroepen, we doen alsof die gewoon werken. Dus hier, deze recursieve oproep om traverse, we zonder erbij na te denken over, maar het doorkruisen van de linker drie, stel dat al afgedrukt 20 en 34 voor ons. En toen we uiteindelijk recursief roepen traverse op de Oke, dat zal correct worden afgedrukt 52, 59, en 106 voor ons. 

Dus aangezien dit kan printen 20, 34 en de andere kan afdrukken 52, 59, 108, alles wat we nodig hebben om te kunnen doen is druk onszelf in het midden van dat. Dus uitprinten alles voor ons. Print onszelf, zodat het huidige knooppunt afdrukken 36, regelmatige printf, en vervolgens drukken alles achter ons. 

DAVID J. Malan: Dit is waar recursie krijgt echt mooi. Het is deze geweldige sprong van het geloof waar je doet het kleinste beetje van het werk. En dan laat je iemand anders doet de rest. En dat iemand anders is, ironisch genoeg, u. Dus voor serieuze brownie points, indien je omhoog te bladeren op de vragen - 

ROB BOWDEN: Op de vragen? 

DAVID J. Malan: En een beetje naar beneden te de cijfers, weet iemand waar deze cijfers vandaan? 

ROB BOWDEN: Ik heb letterlijk geen idee. 

DAVID J. Malan: Ze verschijnen de hele quiz. 

Publiek: Zijn ze dezelfde nummers? 

DAVID J. Malan: Die getallen. Een beetje paasei. Dus voor degenen onder u online kijken op thuis, als u ons kan vertellen via e-mail naar heads@CS50.net wat de betekenis van deze terugkerende zes nummers zijn hele Quiz 1, zullen we je douche met verbazingwekkend oog op de finale lezing en een stressbal. Mooi, subtiel. 

ROB BOWDEN: Elke laatste vragen alles op de quiz?