David J. MALAN: Alle reg. So welkom by die eerste keer ooit CS50 nadoodse vir 'n toets. Ons het gedink ons ​​sou inlui hierdie tradisie hierdie jaar. En dit sal 'n geleentheid wees deur die loop oplossings vir die toets. En ons sal bespoedig of vertraag gebaseer op rente van diegene hier. 

So jy is waarskynlik hier omdat jy geïnteresseerd in hoe jy kan hê of beantwoord moet het 'n paar van hierdie probleme. So waarom nie ons neem 'n blik op hierdie artikel eerste? So kry snare. Dit het jy drie verskillende weergawes van 'n program wat uiteindelik bedoel om 'n string te kry van 'n gebruiker. Of dit gedoen het, was links na jou toe te bepaal. 

En ons in Vraag 0 gevra, veronderstel dat weergawe 1 is saamgestel en uitgevoer word. Hoekom kan die program segfault? Met die eerste oogopslag, enige voorstelle waarom? Ja. 

Publiek: Ek onthou dat dit in 'n vorige voorbeeld van kyk na die kar * s en sien die skandering van die s en sien, want dit is 'n wyser, hoe het dit invloed wat jy geskandeer? Is dit is of die adres van s? 

David J. Malan OK. Goed. So uiteindelik, die bron van 'n probleem is vermoedelik gaan te verminder aan daardie veranderlike s. En dit is inderdaad 'n veranderlike. Die data tipe wat veranderlike kar *, wat beteken dit gaan bevat die adres van 'n karakter. En daarin lê die insig. Dit gaan die adres van te bevat 'n karakter of, meer in die algemeen, die adres van die eerste karakter in 'n hele blok karakters. 

Maar die catch is dat scan s, doel in lewe, is 'n adres en gegee 'n formaat kode, soos% s lees 'n string in die stuk van geheue by daardie adres. Maar, want daar is geen gelyke teken voordat dat kommapunt op die eerste lyn van kode, omdat ons dit nie doen nie eintlik ken 'n geheue met malloc, want dit het nie eintlik Ken 'n verskeidenheid van 'n paar groot, al jy doen is om te lees die gebruiker se sleutelbord insette in sommige volledige vullis waarde, wat is in s by verstek. So is die kans jy gaan segfault indien daardie adres is nie net so gebeur 'n waarde wat jy kan wees, in werklikheid, skryf aan. So sleg nie toe te ken jou geheue is daar. 

So in vraag 1, het ons gevra, veronderstel dat weergawe 2 is saamgestel en uitgevoer word. Hoekom kan hierdie program segfault? So hierdie een is minder karretjie. En daar is eintlik net een ooglopende manier waar jy kan sneller 'n segfault hier. En dit is tematiese. Enige tyd wat ons gebruik c in die geheue, wat kan jy 'n segfault te oorreed met weergawe 2? 

Publiek: As jy dit gebruik om insette in 'n string wat is langer as 49 karakters. 

David J. MALAN: Presies. Enige tyd wat jy iets sien vaste lengte wanneer dit kom by 'n skikking, jou radar moet gaan af dat dit kan wees problematies as jy nie die beheer van die grense van 'n skikking. En dit is die probleem hier. Ons is nog steeds met behulp scanf. Ons is nog steeds met behulp van% s, wat beteken probeer 'n string om te lees van die gebruiker. Dit gaan in s gelees word, wat Op hierdie punt, is effektief die adres van 'n stuk van die geheue of is dit ekwivalent. Dit is die naam van 'n skikking van die karakters van die geheue. 

Maar presies dit, as jy lees 'n string dit is meer as 49 karakters, 49 omdat jy ruimte nodig vir die backslash 0, jy gaan om oor te loop dat buffer. En jy kan kry gelukkig en in staat wees om te skryf 'n 51 karakter, 52, 53. Maar op 'n sekere punt, die bedryfstelsel gaan om te sê, no. Dit is beslis nie die geheue jy mag aan te raak. En die program gaan segfault. 

So is daar, moet die heuristiek enige wees tyd wat jy het 'n vaste lengte, jy het om seker te maak jy die beheer van die lengte van wat dit ookal is wat jy probeer om te lees in dit. 

Publiek: So wat op te los, kan jy het 'n verklaring nagaan eintlik moes is die lengte groter as of minder as? 

David J. Malan Beslis. Jy moet net 'n voorwaarde wat sê, indien die - of eerder jy nie noodwendig weet nie vooraf hoeveel karakters die gebruiker gaan tik, want jy het hoender en die eier. Nie totdat jy lees dit in met scanf kan jy uitvind hoe lank dit is. Maar op daardie punt, is dit te laat, omdat jy reeds gelees het, in enige blok van die geheue. So as 'n eenkant, die CS50 biblioteek vermy hierdie kwessie heeltemal, onthou deur die gebruik van fgetc. En dit lui een van die karakters op 'n tyd, wenk saggies saam, met die wete dat jy kan nie 'n karakter as oorstroom jy lees een op 'n tyd. 

Die vangs is met getstring herroep is dat ons moet voortdurend weer grootte wat deel van die geheue, wat is net 'n pyn. Dit is 'n baie van die reëls van kode wat om te doen. So 'n benadering sou wees om te eintlik gebruik 'n neef, so om te praat, van scanf. Daar is weergawes van 'n groot deel van hierdie funksies wat eintlik gaan die lengte van hoeveel karakters jy mag maksimaal lees. En jy kan spesifiseer, lees nie meer as 50 karakters. So wat sou 'n ander benadering wees, maar minder tegemoetkomend van groter insette. 

So vraag 2 vra, veronderstel dat weergawe 3 is saamgestel en uitgevoer word. Hoekom kan die program segfault? So hierdie een is eintlik dieselfde beantwoord, selfs al is dit lyk 'n bietjie liefhebber. Ons gebruik malloc, wat voel soos gee ons onsself meer opsies. En dan is ons bevry wat geheue aan die einde. Dit is nog steeds net 50 grepe van die geheue. Sodat ons kan nog steeds probeer om te lees in 51, 52, 1000 grepe. Dit gaan segfault vir presies dieselfde rede. 

Maar daar is nog 'n rede ook. Wat anders kon terugkeer malloc buiten die adres van 'n stuk van die geheue? Dit kon terugkeer null. En omdat ons nie nagaan vir dat, sou ons doen iets dom vir 'n ander rede, en dit is dat ons kan vertel word scanf, lees die gebruiker se insette van die sleutelbord in 0 plek, alias null. En dit sal ook beslis sneller 'n segfault. So vir die toets se doel, ons sou aanvaar het een van dié as 'n geldige rede. Een daarvan is identies. Een is 'n bietjie meer genuanseerde. 

Laastens, met betrekking tot die program se gebruik van die geheue, hoe weergawe 2 en weergawe 3 verskil? So vir wat dit werd is, het ons 'n skynbaar oneindige toevoer van moontlike antwoorde op hierdie. En onder die mense se antwoorde, wat ons was hoop vir, maar ons ander aanvaar dinge, was 'n paar melding van die feit dat weergawe 2 gebruik die sogenaamde stapel. Weergawe 3 is die gebruik van die hoop. En funksioneel, beteken dit nie regtig alles maak wat veel van 'n verskil maak. Aan die einde van die dag, ons is nog steeds net om 50 grepe van die geheue. 

Maar dit was een van die moontlike antwoorde dat ons op soek na. Maar jy sien, as jy jou vasvrae terug van die TFS, wat ons gedoen het ander besprekings van aanvaar hul uiteenlopende gebruike van geheue as well. Maar stapel en hoop sou gewees het 'n maklike antwoord om te gaan met. Enige vrae? Ek gee jou Rob. 

ROB BOWDEN: So probleem 4. Dit is die een waar jy het om te vul in die aantal grepe uit al hierdie verskillende tipes gebruik. So die eerste ding wat ons sien. Aanvaar 'n 32-bis argitektuur, soos hierdie CS50 toestel. So een van die fundamentele dinge oor 32-bit platforms, wat ons vertel presies hoe groot 'n wyser gaan te wees in die argitektuur. 

So onmiddellik, weet ons dat 'n wyser tipe is 32-stukkies of 4 grepe. So kyk na hierdie tafel, 'n knoop * is 'n muis-tipe. Dit gaan wees 4 grepe. Struct knoop *, dit is letterlik identies aan knoop ster. En so wat gaan wees 4 grepe. String, sodat dit nie soos 'n lyk aanwijzer nie, maar die typedef, 'n string is net 'n kar *, wat is 'n muis-tipe. So wat gaan wees 4 grepe. 

So hierdie drie is al 4 grepe. Nou, knoop en student is 'n bietjie meer ingewikkeld. So kyk na knoop en student, sien ons node as 'n heelgetal en 'n wyser. En student is twee wysers binnekant van dit. So ten minste vir ons saak hier, die pad dat ons uiteindelik die berekening van die grootte van hierdie struct is net optel alles dit is binne-in die struct. 

So vir knoop, ons het 'n heelgetal is, wat 4 grepe. Ons het 'n wyser, wat 4 grepe. En so 'n knoop gaan te neem 8 grepe. En soortgelyk vir student, het ons 'n wyser wat 4 grepe en 'n ander wyser wat 4 grepe. So wat gaan aan die einde up om 8 grepe. So knoop en student is 8 grepe. En hierdie drie is al 4 grepe. Vrae oor dit? Ja. 

Publiek: Is dit was 'n 64-bietjie argitektuur, sou dit verdubbel almal van hulle? 

ROB BOWDEN: sou dit nie verdubbel almal van hulle. So 64-bis argitektuur, is dit weer, veranderinge wat fundamentele ding wat 'n wyser is nou 64 stukkies. Ja. So 'n wyser is 8 grepe. So het hierdie wat 4 grepe gaan wees 8 grepe. 'N Student, wat twee wysers, Wel, nou is dit gaan wees 8 grepe, 8 grepe. Dit gaan 16 grepe te maak. 

Maar 'n knoop is nog 4 grepe. So dit wyser gaan om 8 grepe. Dit is 4 grepe. So 'n knoop is slegs gaan te wees 12 grepe. Enige ander vrae oor daardie een? So die volgende een, dit is die HTTP status kode. En jy moes omstandighede te beskryf waaronder hierdie mag word aan u terugbesorg. een probleem wat ek gehoor het sommige studente het, is dat hulle probeer het om die foute op die kliënt se einde. So wanneer ons probeer om die versoek te maak na die bediener, iets gaan verkeerd aan ons kant. Maar oor die algemeen, hierdie kodes is van teruggestuur word deur die bediener. So wil ons om uit te vind wat gaan reg of verkeerd op die bediener wat veroorsaak hierdie dinge teruggestuur moet word. So hoekom kan 'n bediener opbrengste status kode 200? Enige gedagtes? 

Ja. So iets suksesvol versoek het deur. En hulle is in staat om terug te keer alles wat jy gevra het. So alles is fine. Wat van 302 gevind? Ja. 

Publiek: Die bediener is op soek na vir wat jy versoek. Maar dit kan dit nie vind nie. So daar is 'n fout. 

ROB BOWDEN: So het die bediener was soek na wat jy wil hê. So soek net hier, 302 gevind, dit was in staat om dit te vind. 

Publiek: Ek is jammer. Gevind beteken dat hulle het dit vind. Jammer. 

ROB BOWDEN: So 302 gevind. Die bediener in staat is om te vind wat jy wou hê. 

Publiek: Maar dit is nie te vertoon? 

ROB BOWDEN: Die verskil tussen hierdie 302 en 200 is dat dit weet wat jy wil. Maar dit is nie presies waar wou jy vra. So 302 is 'n tipiese aanstuur. So jy het 'n bladsy. Dit weet, o, ek wil om terug te keer nie. Maar dit is op 'n ander URL. So hey, wat jy eintlik wil hê nie. 

David J. MALAN: Dit is 'n stuk wat gesê dat ons het julle 'n aanstuur funksie wat gebruik word om die kop funksie wat op sy beurt, uitgedruk plek, kolon, en dan die URL na wat jy wil die gebruiker te verwerp. Selfs al is jy nie sien nie 302 het uitdruklik daar, dit is wat PHP sou mettertyd voeg as die kop sê presies wat Rob daar gesê - gevind. Maar gaan hier plaas. 

ROB BOWDEN: OK. So, wat oor 403 verbied? 

Publiek: Ek dink dit is dat die bediener is basies sê dat die kliënt kan nie toegang tot die tuisblad. 

ROB BOWDEN: So ja. Wel, die tipiese antwoord wat ons was verwag is iets soos die lêers is nie toepaslik chmodded. Dit is waarskynlik onder watter omstandighede jy hulle sien. Maar daar is 'n rede dat die kliënt hier kon wees by die skuld. Daar is eintlik 'n ander status kode - 401. So dit is baie soortgelyk. 

401 is ongemagtigde. En 403 is verbode. En so ongemagtigde jy eksklusief kry as jy nie in geteken Maar in te teken kan beteken dat jy gemagtig is. Maar as jy reeds aangemeld en jy nog nie toestemming het nie, dan jy kan ook verbode. So as jy aangemeld en het nie toestemming, verbode is ook iets wat jy kan kry. 

David J. Malan en die meganisme deur wat hierdie probleme is gewoonlik opgelos op die bediener is via wat opdrag? Chmod, as dit is inderdaad 'n regte uitreik op die lêer of gids. 

ROB BOWDEN: Toe 404 nie gevind nie. Ja. So in teenstelling met 302 waar dit was nie presies waar jy vra, maar dit weet wat wat jy wil, dit is, is dit net het geen idee wat jy wil. En jy is nie die versoek iets geldig is. 418 Ek is 'n teepot en dan 500 interne bediener. So hoekom sou jy dit? 

So segfault - Ek het eintlik nie ken nie die gradering standaard vir hierdie. Maar as jou PHP-kode het iets verkeerd in dit, in teorie, kan dit eintlik segfault, in watter geval, hierdie 500 interne bediener fout, iets is verkeerd met jou bediener se opset. Of is daar 'n fout in jou PHP-kode. Of iets wat sleg is aan die gang. 

David J. Malan Ons het sien segfault onder 'n paar mense se antwoorde. En tegnies, kan dit gebeur. Maar dit sou wees om 'n PHP, die program geskryf deur ander mense, eintlik segfaulted, wat net as die mense verfrommeld en geskryf karretjie kode in hul tolk sou PHP self segfault. So selfs al 500 is soos 'n segfault in die gees, dit is byna altyd die gevolg van 'n konfigurasielêer kwessie met jou web bediener of, as Rob gesê, 'n fout, soos jy het nie 'n kwotasie te sluit. Of jy 'n kommapunt verloor iewers. 

Publiek: So vir die taxi pset, ek dink toe ek dit gedoen het toe ek gebruik is die leser, maar niks gekom, wat hulle genoem wit bladsy. Maar dit was as gevolg van die kode. Ek dink dit was JavaScript, reg? 

ROB BOWDEN: Ja. 

Publiek: Sou die fout nog kom? 

ROB BOWDEN: So sal jy nie gekry het hierdie fout, want alles uit die web bediener se perspektief was heeltemal fyn. Maar jy versoek index.html. Jy versoek shuttle.js en service.js. En dit was in staat om terug te keer aan jou al hierdie dinge - 200. OK. Dit is eers wanneer die leser probeer die JavaScript-kode interpreteer wat Dit is soos, wag, dit is nie geldig JavaScript fout. Enige ander vrae? Alle regte. 

David J. Malan So volgende up was nommer 11. En 11 was die scariest vir 'n klomp mense. So is die belangrikste ding om daarop te let was dat dit inderdaad oor 'n dubbel gekoppel lys. Maar dit was nie die dieselfde as verlede jaar se dubbelgeskakelde lys probleem, wat nie gee jou die voorbehoud dat Die lys kan, in werklikheid, wees ongesorteerde. 

So die feit dat die lys was ongesorteerde en die feit dat die woord was onderstreep daar was bedoel om te dra dat dit eintlik 'n vereenvoudiging van wat andersins sou gewees het 'n meer uitdagende probleem en 'n langer een. So 'n algemene fout hier was om te sit verlede jaar se oplossing op jou een pager en dan net blindelings kopieer wat af as die antwoord, wat is die regte antwoord op 'n ander vraag soortgelyke in gees. Maar die subtiele hier was soos volg. 

So, het ons dit 'n knoop verklaar en omskryf in die gewone manier hier. Daarna het ons gedefinieer lys van 'n globale wyser geïnisialiseer te null. Dan glo, is daar twee funksies ons het prototipes vir hier, vul en verwyder. En dan het ons 'n paar voorbeelde kode hier doen 'n klomp van die invoegings. En dan vra ons u om te voltooi die implementering van insetsel hieronder in sulke 'n manier dat dit voeg n in die lys in konstante tyd, ook onderstreep, selfs al reeds teenwoordig. 

So het die skoonheid van die staat om in te voeg in konstante tyd is dat dit impliseer wat jy hoef te plaas die nuwe knoop waar? In die voorkant. So dit elimineer, gelukkig, ten minste een van die gevalle wat gebruik word om te vereis nog meer reëls van die kode, soos dit gedoen het verlede jaar en selfs in die klas wanneer ons gepraat deur hierdie soort ding met mense en met 'n paar verbale pseudokode. So in die oplossing hier, laat ons spring oor aan dié net 'n visuele op te hê die skerm. 

Let daarop dat ons die volgende doen. En ook kennis van die ander vereenvoudiging was dat selfs al is dit reeds teenwoordig, so dit beteken selfs al die nommer is reeds daar, jy kan net blindelings 'n ander een afskrif daarvan. En dit was ook bedoel om 'n te wees vereenvoudiging, sodat jy kan fokus op, regtig, sommige van die meer intellektueel interessante deel en nie net 'n paar ekstra foutkontroles gegewe die beperkte tyd. 

So in hierdie monster oplossing, ons ken 'n wyser op die linker kant hier om 'n knoop. Nou, besef dat wyser, soos Rob sê, is slegs 32 stukkies. En dit maak nie eintlik bevat 'n adres totdat jy gee dit die adres. En ons doen dit op die regterkant kant via malloc. Soos 'n goeie burger, het ons seker maak dat malloc is nie, in werklikheid, null, sodat ons nie per ongeluk nie ' 'n segfault hier. En enige tyd wat jy malloc gebruik in die lewe, het jy moet beheer word for null, sodat jy het 'n subtiele fout. 

Dan inisialiseer ons dat null deur toeken N en vorige en die volgende. En in hierdie geval hier, ek geïnisialiseer vorige te null, want hierdie nuwe knoop gaan na die nuwe wees die begin van my lys. So daar gaan wees niks voor dit. En ek wil in wese voeg die bestaande lys aan die nuwe knoop deur die opstel van die volgende gelyk om homself te noem. Maar ek is nie net nog gedoen. So as die lys self reeds bestaan, en daar was ten minste een knoop reeds in plek is, al is dit in die lys hier en ek sit 'n nuwe node hier, ek nodig om seker te maak dat my voormalige knoop agtertoe wys aan my nuwe knoop, want dit is weer, 'n dubbel gekoppel lys. 

So doen ons 'n gesonde verstand tjek. As die lys is nie null, indien daar is reeds een of meer nodes daar is, dan voeg dit terug verwysing om so te praat. En dan is die heel laaste ding wat ons nodig om te doen is eintlik werk om die globale veranderlike lys self te wys daardie nuwe knoop. Ja. 

Publiek: In die wyser pyl [Onhoorbaar] is gelyk aan nul, doen dit gaan met die lys, want die lys is van nul? 

David J. Malan Nee. Dit is net vir my om proaktief versigtig, in dat indien dit is my oorspronklike lys met miskien 'n bietjie meer nodes hier en ek is die inbring van my nuwe node hier, daar gaan niks meer as om hier te wees. En ek wil hê dat die idee om te vang deur die oprigting van die vorige aan nul op die nuwe knoop. En vermoedelik, as my kode is korrek en daar is geen ander manier te voeg nodes anders as om hierdie funksie, vermoedelik, selfs al is lys het reeds een of meer nodes in dit, vermoedelik die lys, die eerste knoop, sal 'n vorige wyser van nul self. 

Publiek: En net 'n follow-up. Die rede waarom jy sit wyser volgende gelykes lys is jy maak die wyser voordat lys in wat dit is wys na die volgende, ek dink - Ek moenie - net noem? 

David J. MALAN: Presies. En so laat ons eintlik kyk na twee gevalle hier regtig nie, selfs al is die Om ons sal hulle oorweeg is nie heeltemal dieselfde as die kode. Maar op 'n hoë vlak, as dit verteenwoordig lys en dit is 'n 32-bietjie wyser, die eenvoudigste scenario is dat dit nietig is by verstek. En dink ek wil voeg die nommer 50 was die eerste getal. So ek gaan om voort te gaan en ken 'n knoop, wat gaan bevat drie velde - n, vorige en volgende. 

Ek gaan die nommer 50 te sit hier, want dit sal n wees. Dit sal die volgende wees. En dit sal wees vorige. En ja, wat kan ek doen in hierdie geval? Wel, ek het net gedoen hier reël 1. Pointer n kry n. Ek is dan sê, vorige moet kry null. So dit gaan van nul. Toe ek gaan om te sê die volgende gaan lys te kry. 

En dit werk net goed uit. Dit is nul. En so ek sê, die nuwe node se volgende gebied moet kry wat dit is. So wat stel 'n ander null daar. En dan is die laaste ding wat Ek is hier om te gaan. As die lys is nie gelyk aan nul nie, maar dit is gelyk aan nul, so ons slaan wat geheel en al. En so al wat ek nou doen is lys kry wyser, wat picturaal lei tot 'n foto soos dit. So dit is een scenario. 

En die een wat jy is te vra oor spesifiek is 'n situasie soos hierdie, waar ons reeds 'n een-knoop list. En as ek gaan terug tot in die oorspronklike probleemstelling, die volgende wat ons sal voeg sê, is 34, net vir ter wille van die bespreking. So ek gaan net gerieflik teken dat hier. Ek het net malloced. Kom ons neem Ek check for null. 

Nou, ek gaan inisialiseer n te wees 34. En dit sal wees n. Dit sal die volgende wees. En dit sal wees vorige. Kom ons maak seker dat ek nie kry dit terug. Vorige kom eerste in die definisie. Laat my dit regmaak. Dit is die vorige. Dit is die volgende. Selfs al is dit is identies, laat ons hou dit konsekwent. 

Vorige. Dit is die volgende. So ek het net malloced my kennis, nagegaan for null, wat 34 in die knoop. Vorige kry null. So wat gee my dat. Volgende kry lys. So lys is nie. So, dit is nou dieselfde as die opstel van hierdie pyl, sodat hulle na die een in dieselfde. En dan is ek seker te maak dat die lys is nie gelyk aan nul. En dit is nie hierdie tyd. Dan gaan ek n lys te doen vorige kry wyser. 

So 'n lys van vorige kry PTR. So dit het die effek van om 'n grafiese pyl hier. En dit is 'n bietjie golwende, die lyne. En dan, laastens, ek werk lys om te wys op Wijzer. So nou is dit wys om hierdie man. En nou, laat ons 'n vinnige gesonde verstand tjek. 

Hier is die lys, wat die globale veranderlike. Die eerste nodus is inderdaad 34, want Ek volg wat pyl. En dit is nie korrek nie omdat ek wil voeg aan die begin van die lys alle nuwe nodes. Sy volgende veld lei my aan hierdie man. As ek gaan hou, slaan ek die volgende is leeg. So daar is nie meer die lys. As ek getref vorige, ek kry terug na waar ek verwag. 

So is daar nog 'n paar wenke, natuurlik, te manipuleer. Maar die feit dat hulle jou vertel het om te doen dit in konstante tyd beteken dat jy net het 'n beperkte aantal van die dinge jy mag doen nie. En wat is die getal? Dit mag dalk 'n stap wees. Dit mag dalk twee. Dit kan wees 1000 stappe. Maar dit is eindig, wat beteken dat jy nie enige soort van herhaling aangaan hier, geen rekursie, geen loops. Dit is net gekry het om hard-gekodeerde lyne van die kode soos ons in hierdie voorbeeld. 

So het die volgende probleem 12 gevra om ons te voltooi die implementering van verwyder hieronder in so 'n manier dat dit verwyder n uit die lys in lineêre tyd. So jy het 'n bietjie meer wikkel kamer nou. Jy kan dat n aanvaar, indien teenwoordig in die lys, sal teenwoordig wees nie meer as een keer. En ook dit is bedoel om te wees 'n toets-gebaseerde vereenvoudig aanname, so dat as jy die nommer 50 iewers in die lys, wat jy doen nie ook hoef te bekommer oor die voortsetting te Itereer, op soek na elke moontlike afskrif van 50, wat net sou oorgaan in 'n paar minutia in beperkte tyd. 

So met verwyder, hierdie een was beslis meer uitdagend en meer kode te skryf. Maar met die eerste oogopslag, eerlik, kan dit kyk oorweldigend en soos iets daar is geen manier wat jy kan hê kom met 'n quiz. Maar as ons fokus op die individuele stappe, Hopelik sal dit skielik slaan jy dat elkeen van hierdie individuele stappe maak duidelik sin in retrospek. So kom ons neem 'n blik. 

So die eerste, ons inisialiseer wyser wees lys self. Want ek wil lineêre tyd, wat beteken dat Ek gaan 'n paar lus te hê. En 'n gemeenskaplike manier om Itereer oor die nodes in 'n lys struktuur of enige soort struktuur iteratief is om te neem 'n wyser na die voorkant van die data struktuur en dan net begin opdatering en dit loop jou pad deur die data struktuur. So ek gaan om presies dit te doen. 

Terwyl wyser, my tydelike veranderlike, is nie gelyk aan nul, laat gaan voort en kyk. Het ek gelukkig? Is die n veld in die knoop Ek is tans kyk na gelykstaande aan die aantal Ek is op soek na? En as dit so is, laat ons iets doen. Nou, dit agterkom indien toestand rondom die hele volgende reëls van die kode. Dit is die enigste ding wat ek omgee - vind 'n aantal in die vraag. So daar is geen ander is, wat dinge konseptueel 'n bietjie. 

Maar nou, het ek besef, en jy kan net besef dit na te dink dit deur 'n bietjie, daar is eintlik twee gevalle hier. Een daarvan is waar die knoop is by die die begin van die lys, wat 'n klein irriterende, want dit is 'n spesiale geval, want jy het om te gaan met hierdie ding, wat is die enigste anomalie. Oral anders in die lys, dit is dieselfde ding. Daar is 'n vorige knoop en 'n volgende knoop, vorige knoop, knoop volgende. Maar hierdie man is 'n bietjie spesiale As hy aan die begin. 

So as die wyser is gelyk aan die lys self, so as ek aan die begin van die lys en ek het n gevind, wat ek nodig het 'n paar dinge om te doen. Een, ek moet n lys te verander verwys na die volgende veld, 50. So dink dat ek probeer te verwyder 34. So hierdie man se het om te gaan weg in net 'n oomblik. 

So ek gaan om te sê, 'n lys kry aanwijzer volgende. Wel, dit is wyser. Volgende wys hier. So, dit is die verandering van hierdie pyl reg nou om te wys op hierdie man hier. Nou, onthou, ons het 'n tydelike veranderlike. So het ons nie gelaat enige nodes, want Ek het ook hierdie man in my implementering van verwyder. Dus, indien lys self is nie null, Ek het 'n bietjie iets op te los. 

Ek moet nou seker maak dat hierdie pyl, wat voorheen wys 50-34, het dit te weg te gaan, want as ek probeer om ontslae te raak van 34, 50 beter nie enige handhaaf soort van terug verwysing na dit as die pyl voorgestel. So ek het net hierdie lyn. So dan is ek gedoen het. Daardie geval is eintlik redelik maklik. Die afkap van die hoof van die lys is relatief eenvoudig. 

Ongelukkig is daar hierdie irriterende anders blok. So nou, ek het die saak te oorweeg waar daar is iets in die middel. Maar dit is nie te erg nie, behalwe vir sintaksis soos hierdie. So as ek nie aan die begin van die lys, ek is iewers in die middel. En hierdie lyn hier sê, begin op watter knoop jy op. Gaan na die vorige node se volgende gebied en wys dat die wyser. 

Kom ons doen dit picturaal. Dit was om te kry ingewikkeld. So as ek 'n vorige velde hier - Kom ons doen dit - volgende velde hier. Ek gaan my verwysings na eerder vereenvoudig as teken 'n hele klomp van die dinge heen en weer en kruis en dwars mekaar. En nou, laat ons net sê dit is 1, 2, 3 ter wille van bespreking, selfs hoewel dit nie in lyn met die probleem in die vraag. 

So hier is my lys gekoppel. Ek probeer twee te verwyder in hierdie spesifieke weergawe van die storie. So ek het wyser opgedateer te word verwys na hierdie man. So dit is PTR. Hy is hier wys. Dit is lys, wat bestaan wêreldwyd as tevore. En hy is hier wys nie saak wat. En nou, ek probeer om te verwyder twee. 

So as wyser hier wys, is ek gaan volg, blykbaar, die vorige wyser, wat stel my by 1. Ek is dan gaan om te sê dat die volgende gebied, en dit bring my aan hierdie boks hier, gaan gelyk wyser volgende. So as dit wyser, dit is volgende. Dit beteken dat hierdie pyl behoeftes om te verwys na hierdie man. 

So, wat die lyn van die kode het net gedoen is om 'n bietjie van hierdie. En nou, is dit lyk soos 'n stap in die regte rigting. Ons wil in wese op 2 uit te knip van die middel van 1 en 3. So maak dit sin dat ons wil roete hierdie wyser rondom dit. So hierdie volgende lyn te keur indien wyser volgende is nie nul is, is daar inderdaad iemand aan die regterkant van 2, dit beteken dat ons ook moet doen 'n bietjie knip hier. 

So ek moet nou hierdie wyser om te volg en werk die vorige wyser op hierdie man 'n bietjie van 'n om te doen tydelike oplossing hier die punt hier. En nou, visueel dit is nice. Dit is 'n bietjie slordig in dat daar niemand wat dui op die 2 nie. 2 dui op die linkerkant. En 2 dui op die regterkant. Maar hy kan doen wat hy wil, want hy is oor te bevry te raak. En dit maak nie saak wat daardie waardes is nie. 

Wat belangrik is, is dat die oorblywende ouens bo routing en onder hom nou. En inderdaad, dit is wat ons nou doen. Ons gratis wyser, wat beteken dat ons vertel die bedryfstelsel, is jy welkom om dit te herwin. En dan laastens, ons terugkeer. Anders onvoorwaardelik, as ons het nie teruggekeer het nie, ons het om te hou soek. So wyser gelyk wyser volgende net beteken skuif hierdie man hier. Skuif hierdie man hier. Skuif hierdie man hier indien, in werklikheid, Ons het nie die aantal ons soek nog. 

So gesê, dit lyk heeltemal oorweldigend, dink ek, op die eerste oogopslag, veral as jy sukkel met hierdie Tydens die toets dan sien iets soos hierdie. En jy jouself klop op die skouer. Wel, daar is geen manier wat ek kan hê kom met wat op die quiz. Maar ek sou argumenteer, jy kan as jy breek dit af in die individuele gevalle en net loop deur dit versigtig, al is dit weliswaar onder stresvolle omstandighede. 

Gelukkig het die prentjie gemaak alles gelukkiger. Jy kan dit stel in 'n aantal van maniere. Jy hoef nie die kriskras te doen ding hier. Jy kan dit doen met reguit lyne soos hierdie. Maar die kern van die probleem, in algemene, was om te besef dat die prentjie in die einde moet kyk 'n bietjie iets soos hierdie, want konstante tyd te kenne gegee dat jy hou storing en storing en storing die nuwe nodes aan die begin van die lys. Enige vrae? Waarskynlik die mees uitdagende van beslis die kodering vrae. 

Publiek: So is lys soortgelyk aan kop in die vorige voorbeelde. 

David J. MALAN: Presies, presies. Net 'n ander naam vir 'n globale veranderlike. Wêreldwyd wat? 

ROB BOWDEN: OK. So dit is die een waar jy het die paragraaf te skryf. Sommige mense essays geskryf vir hierdie vraag. Maar jy hoef net hierdie ses terme te gebruik te beskryf wat gebeur wanneer jy probeer om te kontak facebook.com. So ek sal net praat deur middel van die proses met behulp van al hierdie terme. So in ons leser, tik ons ​​facebook.com en druk Enter. So ons leser gaan 'n te bou HTTP versoek dat dit gaan om te stuur deur 'n proses te Facebook vir Facebook om te reageer op ons met die HTML van sy bladsy. 

So, wat is die proses wat die HTTP-versoek eintlik kry om te Facebook? So die eerste, moet ons te vertaal Facebook.com. Dus net die naam gegee Facebook.com, waar eintlik nie die HTTP-versoek nodig het om te gaan? So het ons nodig het om te vertaal Facebook.com 'n IP-adres, wat uniek identifiseer wat masjien wat ons eintlik wil hierdie versoek te stuur na. Jou laptop het 'n IP-adres. Enigiets verbind tot die internet het 'n IP-adres. 

So DNS, Domain Name System, wat wat gaan om die vertaling te hanteer van facebook.com na 'n IP adres wat jy eintlik wil kontak. So het ons kontak die DNS-bedieners en sê: Wat is facebook.com? Dit sê, o, dit is IP adres 190,212 iets, iets, iets. Alle regte. Nou, ek weet wat die masjien Ek wil te kontak. 

So dan is jy jou HTTP-versoek stuur oor daardie masjien. So hoe gaan dit kry om die masjien? Wel, die versoek gaan uit router te router weerkaats. Onthou die voorbeeld in die klas, waar ons eintlik die roete sien dat die pakkies het toe ons probeer te kommunikeer. Ons het dit spring oor die Atlantiese Oseaan Ocean by een punt of wat ook al. 

So het die laaste kwartaal hawe. So, dit is nou op jou rekenaar. Jy kan verskeie dinge tans kommunikasie met die internet. So ek kan loop, sê, Skype. Ek het dalk 'n webblaaier oop. Ek kan iets het wat torrenting lêers. So al hierdie dinge is kommunikasie met die internet in een of ander manier. 

So wanneer jou rekenaar 'n paar data ontvang van die internet, hoe dit weet wat aansoek eintlik wil die data? Hoe werk dit weet of hierdie spesifieke data is bedoel vir die torrenting aansoek teengestaan aan die web leser? So, dit is die doel van die hawens in daardie al hierdie programme het beweer dat 'n poort op jou rekenaar. So jou webblaaier sê, hey, Ek luister op poort 1000. En jou torrenting program sê, Ek luister op poort 3000. En Skype sê, ek gebruik port 4000. 

So wanneer jy 'n paar data wat behoort aan een van hierdie aansoeke, die data gemerk is met wat die hawe is dit eintlik moet saam gestuur word. So dit sê, o, ek behoort na die hawe 1000. Ek weet dan moet ek dit te stuur saam met my web browser. So die rede waarom dit is hier ter sprake is dat web bedieners is geneig om te luister op poort 80. So toe ek kontak Facebook.com, ek is kommunikeer met 'n paar masjien. Maar ek moet sê watter hawe van daardie masjien wat ek wil om te kommunikeer met. En web bedieners is geneig om te wees luister op poort 80. 

As hulle wou, kon hulle dit stel up so dit sit as op poort 7000. En dan in 'n webblaaier, ek kon hand te tik Facebook.com: 7000 te stuur die inligting na die hawe 7000 van Facebook se web bediener. 

David J. Malan En in hierdie geval, selfs het ons nie nodig dat mense noem dit, in hierdie geval, wat die hawe sou die versoek eintlik gaan? Probeer weer. Presies. Nie op soek na daardie, maar 'n subtiliteit dit is daar nie een van die laaste. 

ROB BOWDEN: So het die HTTPS, want dit is luister spesifiek vir die geïnkripteer, dit is op poort 4430. 

Publiek: En e-pos is 25, reg? 

David J. Malan Outbound e-posse, 25, yep. 

ROB BOWDEN: Ek het nie eens die meeste van weet die - al die laer kinders is geneig om te wees voorbehou vir die dinge. Ek dink alles onder 1024 is voorbehou. 

Publiek: Waarom het jy gesê 3 was die verkeerde nommer? 

ROB BOWDEN: Want in 'n IP-adres, daar is vier groeperings van syfers. En hulle is 0-255. So 192.168.2.1 is 'n algemene plaaslike netwerk IP adres. Let almal is minder as 255. So toe ek begin met 300, wat kon nie moontlik ' is een van die getalle. 

David J. Malan Maar wat dom clip uit - dit was CSI, waar hulle 'n getal wat was te groot vir die IP-adres. 

ROB BOWDEN: Enige vrae oor hierdie? Die volgende een, so volkome verandering in onderwerp, maar ons het hierdie PHP skikking die huise in die quad. En ons het 'n On-geordende lys. En ons wil uit te druk elke lys item net met die huis se naam. So het ons 'n foreach lus. So onthou, die sintaksis is foreach skikking as item in die skikking. So deur elke iterasie van die lus, huis gaan om te neem op een van die waardes binnekant van die skikking. 

Op die eerste iterasie, huis sal wees Cabot House. Op 'n tweede iterasie, huis sal wees Courier House en so aan. So vir elke quad as huis, ons is net gaan druk - jy kan ook weerklank het - die lys van die huis se naam item en dan en dan sluit die lys item. Die krulhakies is opsioneel hier. 

En dan het ons ook in die vraag gesê self, onthou om te sluit die On-geordende lys tag. Dus moet ons PHP modus te verlaat Ten einde dit te doen nie. Of ons kan eggo die sluit On-geordende lys tag. 

David J. Malan ook fyn sou hier is 'n ou skool vir gebruik lus met 'n $ i = 0 0 en gebruik tellings uit te vind die lengte van die straal. Heeltemal fyn te, net 'n bietjie wordier. 

Publiek: So as jy op pad was na [Onhoorbaar], sou jy doen - Ek vergeet wat die lus [onhoorbaar] is. Wil jy $ quad bracket ek? 

David J. MALAN: Presies. Ja, presies. 

ROB BOWDEN: Enigiets anders? 

David J. MALAN: Alle reg. Trade-offs. So was daar trosse van antwoorde moontlik vir elk van hierdie. Ons is regtig net op soek na iets dwingende vir 'n onderstebo en 'n nadeel. En die getal 16 gevra, geldigmaking gebruikers insette kliënt-kant, soos met JavaScript, in plaas van bediener-kant, soos met PHP. So, wat is 'n onderstebo van doen kliënt-kant? 

Wel, een van die dinge wat ons voorgestel is dat jy verminder latency, want jy hoef nie te pla kontak met die bediener, wat dalk 'n paar millisekondes of selfs 'n paar sekondes deur die vermyding van daardie en net validering van gebruikers se insette kliënt-kant deur verwek 'n op-stuur hanteerder en kyk net, het hulle tik iets in vir die naam? Het hulle iets tik in vir e-pos adres? Het hulle kies om 'n koshuiskamer van die drop-down menu? 

Jy kan oombliklike terugvoer gee hulle die gebruik van die rekenaar gigahertz of wat ook al hulle dit is eintlik op hul lessenaar. So dit is net 'n beter gebruikers ervaar tipies. Maar 'n nadeel van doen kliënt-kant goedgekeur is, as jy dit doen sonder om ook doen bediener-kant validering is dat mees iemand uit CS50 kom weet dat jy net kan stuur data wat jy wil hê aan 'n bediener enige aantal maniere. Om eerlik te wees, in die meeste enige leser, kan jy Klik om in die instellings en net afskakel JavaScript, wat, Daarom, skakel enige vorm van validering. 

Maar jy moet ook kan onthou dat selfs ek het 'n paar dinge afstandgeveg in die klas gebruik telnet en eintlik voorgee om 'n leser deur die stuur get versoeke om 'n bediener. En dit is beslis nie die gebruik van enige JavaScript. Dit is net vir my tik opdragte op 'n klavier. So regtig, enige programmeerder binne genoeg gemak met die web en HTTP kon stuur wat data wat hy of sy wil aan 'n bediener sonder bevestiging. En as jou bediener is nie ook nagaan, het hulle vir my 'n naam, is dit is eintlik 'n geldige e-posadres het, het hulle kies om 'n koshuiskamer, kan jy uiteindelik up inbring valse of net leeg data in jou databasis, wat waarskynlik is nie van plan om 'n goeie ding wees as jy is die veronderstelling dat dit daar was. 

So, dit is 'n irriterende werklikheid. Maar in die algemeen, kliënt-kant validering is groot. Maar dit beteken twee keer soveel werk. Hoewel daar wel bestaan ​​verskeie biblioteke, JavaScript biblioteke Byvoorbeeld, wat maak dit baie, veel minder van 'n hoofpyn. En jy kan onthou 'n paar van die kode bediener-kant, kliënt-kant. Maar nie besef dat dit is tipies addisionele werk. Ja. 

Publiek: So as ons net gesê minder veilig - 

David J. Malan [lag] Ugh. Dit is altyd die harder kinders te beoordeel. 

ROB BOWDEN: Dit sou aanvaar is. 

David J. MALAN: What? 

ROB BOWDEN: Ek het hierdie probleem. Dit sou aanvaar het. 

David J. Malan Ja. 

Publiek: Cool. 

ROB BOWDEN: Maar ons het dit nie aanvaar vir die eerste een - Wel, wat ons soek, is iets soos wat jy hoef nie te kommunikeer met die bediener. Ons het nie net vinniger nie. 

Publiek: Wat nie herlaai bladsy? 

ROB BOWDEN: Ja. Dit was 'n aanvaarde antwoord. 

David J. Malan Enigiets waar ons voel dit was meer geneig as nie waarskynlik dat jy weet wat jy was sê, wat is 'n moeilike lyn soms trek. Met behulp van 'n gekoppelde lys plaas van 'n skikking te handhaaf 'n gesorteer lys van heelgetalle. So 'n onderstebo ons dikwels noem met gekoppelde lyste wat gemotiveer hul hele bekendstelling was jy dinamika. Hulle kan groei. Hulle kan krimp. So jy hoef nie te spring deur hoops om werklik te skep meer geheue met 'n verskeidenheid. Of jy het nie net sê, jammer, gebruiker. Die skikking is vol. So dinamiese groei van die lys. 'N nadeel al van geskakelde lyste? 

Publiek: Dit is lineêr. Soek op geskakelde lys is lineêre in plaas van wat jy teken in 

David J. MALAN: Presies. Soek op 'n geskakelde lys is lineêre, selfs al is dit gesorteer, want jy kan Volg die volgende broodkrummels, hierdie wysers, vanaf die begin van die lys aan die einde. Jy kan nie die invloed van ewekansige toegang en Dus, binêre soek, selfs al is dit gesorteer, wat jy kan doen met 'n skikking. En daar is ook 'n ander koste. Ja. 

Publiek: Memory ondoeltreffende? 

David J. Malan Ja. Wel, ek wil nie noodwendig sê ondoeltreffend. Maar dit beteken kos meer geheue, want jy moet 32 ​​stukkies vir elke knoop vir die bykomende wyser, op minste vir 'n enkel gekoppel lys. Nou, as jy net die berging van heelgetalle en jy die muis wil byvoeg, dis eintlik soort van nie-triviaal. Dit is die verdubbeling van die bedrag van die geheue. Maar in werklikheid, as jy 'n stoor gekoppel lys van structs wat dalk 8 grepe, 16 grepe, selfs meer as dit, dalk is dit minder van 'n marginale koste. Maar dit is 'n koste nietemin. So een van dié sou het is fyn as nadele. 

18. Die gebruik van PHP plaas van C te skryf 'n opdrag-lyn program. So hier is, is dit dikwels vinniger te gebruik om 'n taal soos PHP of Ruby of Python. Jy moet net vinnig oop 'n teks editor. Jy het baie meer funksies aan u beskikbaar. PHP het die kombuis wasbak van funksies, terwyl dit in C, moet jy het 'n baie, baie min. Trouens, ouens die ken op die harde manier dat jy nie hash tabelle. Jy het geen lyste gekoppel het. As jy wil hê dat die, wat jy hoef te dit self implementeer. 

So een onderstebo van PHP of eintlik enige geïnterpreteer taal is die spoed waarmee jy kode skryf. Maar 'n nadeel, ons het dit gesien toe ek vinnig opgesweep n misspeller implementering in lesing met behulp van PHP, is dat die gebruik van 'n geïnterpreteer taal is gewoonlik stadiger. En ons sien dat aantoonbaar met 'n verhoog in die tyd van 0,3 sekondes tot 3 sekondes, as gevolg van die interpretasie wat eintlik gebeur. 

Nog 'n onderstebo was dat jy hoef nie te stel. So dit versnel ook die ontwikkeling tot Terloops, want jy het nie twee stappe te loop 'n program. Jy moet net een. En so dit is mooi dwingende as well. Gebruik van 'n SQL databasis in plaas van CSV data te stoor. So SQL databasis word gebruik vir pset7. CSV lêers wat jy het nie veel gebruik. Maar jy kan dit gebruik indirek in pset7 as goed deur te praat met Yahoo Finansies. 

Maar CSV is net soos 'n Excel lêer, maar super eenvoudige, waar die kolomme is net demarked deur kommas binnekant van 'n andersins teks lêer. En die gebruik van 'n SQL databasis 'n bietjie meer aantreklik. Dit is 'n onderstebo, omdat jy dinge soos kies en voeg en te skrap. En jy, vermoedelik, indekse wat MySQL en ander databasis, soos Oracle, bou vir jou in die geheue, wat beteken dat jou kies is waarskynlik nie gaan lineêre bo tot onder te wees. Dit is eintlik gaan om iets te wees soos binêre soek of iets soortgelyke in gees. So hulle is oor die algemeen vinniger. 

Maar 'n nadeel is dat Dit is net meer werk. Dit is meer moeite. Jy het databasisse te verstaan. Jy het dit op te rig. Jy moet 'n bediener uit te voer die databasis op. Jy moet verstaan hoe om dit te stel. So dit is net hierdie soorte trade-offs. Terwyl 'n CSV-lêer, kan jy skep dit met gedit. En jy is goed om te gaan. Daar is geen kompleksiteit as dit nie. 

Gebruik van 'n Trie plaas van 'n hutstabel met aparte aaneenskakeling te slaan 'n woordeboek van woorde wat herinner van pset5. So 'n probeer onderstebo, in teorie ten minste, is wat? Konstante tyd, ten minste as jy hashing op elk van die individuele letters in 'n woord, soos jy mag hê vir pset5. Dit kan wees vyf allegaartjies, ses hashes as daar vyf of ses letters in die woord. En dit is redelik goed. En as daar 'n bogrens op hoe lank jou woorde kan wees, dis inderdaad asymptotically konstante tyd. 

Terwyl 'n hash tafel met aparte chaining, die probleem is daar met die soort data struktuur is dat die prestasie van jou algoritmes gewoonlik hang af van die aantal van die dinge wat reeds in die data struktuur. En dit is beslis die geval met kettings, waardeur die meer dinge wat jy sit in 'n gemors tafel, hoe langer die kettings gaan, wat beteken in die ergste geval, die ding wat jy dalk op soek na is al die pad aan die einde van 'n van daardie kettings, wat effektief wentel in iets lineêre. 

Nou, in die praktyk, kan dit absoluut die geval dat 'n hash tafel met kettings is vinniger as 'n ooreenstemmende Trie implementering. Maar dit is vir verskeie redes, onder wat drieë gebruik om 'n hele klomp van die geheue wat kan, in werklikheid, stadige dinge af, omdat jy nie lekker kry nie voordele van iets genoem kas, waar dinge wat naby aan mekaar in die geheue kan verkry word dikwels meer vinnig. En soms kan jy kom met 'n baie goeie hash funksie. Selfs al het jy 'n bietjie van te mors geheue, jy kan inderdaad in staat wees om te vind dinge vinnig en nie so erg soos lineêr. 

Dus, in kort, daar was nie noodwendig met enige van hierdie een of selfs twee spesifieke dinge wat ons soek. Werklik iets oortuigend as 'n onderstebo en negatiewe algemeen ons oog gevang het. 

ROB BOWDEN: So vir die onderstebo, ons het nie aanvaar nie op sy eie "vinniger." Jy het iets daaroor te sê. Selfs as jy teoreties vinniger gesê, ons het geweet dat jy soort van verstaan dis 0 van 1. En hash tafel, in teorie, is nie 0 of 1. Noem niks oor runtime algemeen het jy die punte. Maar "vinniger," die meeste van die oplossings op die groot bord wat drieë was objektief stadiger as oplossings wat hash tabelle. So vinniger in en van die self is nie regtig waar nie. 

David J. Malan Dom de Dom Dom. Ek is waarskynlik die enigste een wat besef dit is hoe dit veronderstel is om te word uitgespreek, reg? 

ROB BOWDEN: Ek het eintlik geen idee nie. 

David J. MALAN: Dit het sin in my kop. 

ROB BOWDEN: Ek is besig met hierdie een. OK. So dit is die een waar jy moes trek die diagram soortgelyk aan jy dalk gesien het op verlede eksamens. So laat ons net kyk na hierdie. So van die HTML-knoop, het ons twee kinders, die kop en die liggaam. So het ons tak - die kop en lyf. Die kop het 'n titel merk. So het ons 'n titel. 

Nou, die een ding wat 'n klomp mense vergeet is dat hierdie teks nodes elemente in die boom. So hier is ons gebeur om hulle te trek as ovale om hulle te onderskei van dié tipes knope. Maar kennisgewing ook hier het ons top, middel, en onderste sal uiteindelik 'n teks knope. So vergeet die ietwat van 'n gemeenskaplike fout. 

Die liggaam het drie kinders - hierdie drie divs. So div, div, div en dan die teks knoop kinders van die divs. Dit is pretty much dit vir daardie vrae. 

David J. Malan En dit is die moeite werd om daarop te let, selfs al het ons nie op hierdie woon nie besonderhede in die tyd wat ons spandeer op JavaScript, dat die einde nie, in Trouens, saak tegnies. So as hoof kom voor in die liggaam HTML, dan moet dit lyk asof die verlaat van die liggaam in die werklike DOM. Dat sy is, in die algemeen, net FYI, iets genoem dokument einde, waar dit maak nie saak. En as jy die uitvoering van 'n ontleder, 'n program wat HTML lees in die bou in die boom in die geheue, om eerlik te wees, dit is intuïtief waarskynlik wat jy doen in elk geval - van bo na onder, links na regs. 

ROB BOWDEN: Vrae oor dit? Moet ek doen die volgende een? 

David J. MALAN: Natuurlik. 

ROB BOWDEN: OK. So dit is die Bufferschrijding aanval vraag. Die belangrikste ding om hier te erken, is, Wel, hoe kan 'n teenstander truuk hierdie program in die uitvoering van arbitrêre kode? So argv1, die eerste opdrag lyn argument tot hierdie program, kan dit wees arbitrêr lank. Maar hier is ons met behulp van memcpy te kopieer argv1, wat hier is bar. Ons is om dit as die argument. En so is dit die neem van die naam bar. 

So ons memcpying bar in hierdie buffer c. Hoeveel bytes is ons kopieer? Wel egter baie grepe bar gebeur word met behulp van die lengte van die argument. Maar c is slegs 12 grepe wyd. So as ons tik 'n command line argument dit is meer as 12 grepe, ons is gaan om dit te oorstroom veral buffer. Nou, hoe kan 'n teenstander mislei die program na die uitvoering van enige kode? 

So onthou dat hier hoof roep cat. En so is daar dan hoof oproepe foo. Kom ons teken nie. So het ons ons stapel. En die belangrikste 'n stapel raam aan die onderkant. Op 'n sekere punt, hoof oproepe foo. Wel, onmiddellik, hoof oproepe foo. En so cat kry sy eie stapel raam. 

Nou, op 'n punt, cat gaan om terug te keer. En toe cat opbrengste, het ons nodig het om te weet op watter lyn van die kode binnekant van die belangrikste ons was om te weet waar Ons moet weer in die belangrikste. Ons kan cat bel uit 'n hele klomp van verskillende plekke. Hoe weet ons waar om terug te keer? Wel, ons moet dit iewers te stoor. 

So iewers hier rond, ons slaan waar ons moet terugkeer om weer cat opbrengste. En dit is die terugkeer adres. So, hoe 'n teenstander kan voordeel trek hiervan is die feit dat hierdie buffer c gestoor word, laat sê, hier is c. So ons het 12 grepe vir c. Dit is c. En dit is cat se stapel ring. So as die kwaadwillige gebruiker meer grepe as 12 of hulle 'n opdrag lyn argument wat langer as 12 karakters, dan gaan ons oorloop hierdie buffer. 

Ons kan gaan hou. En op 'n sekere punt, ons gaan ver genoeg dat ons begin vervang van hierdie terugkeer adres. So wanneer ons vervang die adres, Dit beteken dat wanneer cat opbrengste, ons terugkeer na waar die kwaadwillige gebruiker vertel dat dit deur watter waarde dit het, wat ookal karakters die gebruiker aangegaan is. En so, as die kwaadwillige gebruiker om veral slim, hy kan dit hê terug te keer na iewers in die printDef funksie of iewers in die malloc funksie, net oral arbitrêr. 

Maar selfs meer slim is wat as hy die gebruiker terug te keer na hier. En dan moet jy begin uitvoer dit as reëls van die kode. So op daardie stadium, kan die gebruiker tik wat hy wil in hierdie streek. En hy het volle beheer oor jou program. Vrae oor dit? So is die volgende vraag voltooi die herimplementatie van cat in so 'n manier dat dit nie meer kwesbaar. 

So daar is 'n paar van die maniere jy kon dit gedoen het. Ons het nog net c synde 'n lengte van 12. Jy kan verander hierdie as deel van die oplossing. Ons het ook bygevoeg 'n tjek te maak seker bar was nie null. Al het jy nie nodig het wat vir volle krediet. So ons eerste die beheer van die string lengte van bar. As dit is meer as 12, dan nie eintlik doen die kopie. So dit is een manier om van die vasstelling van dit. 

Nog 'n manier van die vasstelling van dit in plaas van met c net 'n lengte van 12, het dit wees van lengte StrLen (bar). Nog 'n manier van die vasstelling van dit eintlik net terug te keer. So as jy het net ontslae geraak het van al hierdie, as jy het net verwyder al reëls van die kode, sou jy gekry het volle krediet, aangesien hierdie funksie nie eintlik enigiets te bereik. Dit is die kopiëring van die command line argument in 'n paar skikking in sy plaaslike stapel raam. En dan is die ding terugkeer. En wat dit volbring is weg. So terugkeer was ook 'n voldoende manier om volle krediet. 

David J. Malan nie heeltemal die gees van die vraag, maar aanvaarbaar per die spec nietemin. 

ROB BOWDEN: Vrae oor enige van daardie? Die een ding wat jy ten minste nodig het die opstel van kode. So selfs al is jy tegnies nie kwesbaar as jou kode doen nie stel, het ons nie aanvaar dat. Geen vrae? OK. 

David J. Malan Wil jy hierdie titel te sê? 

ROB BOWDEN: No 

David J. Malan So in hierdie een, is hierdie was óf goeie nuus of slegte nuus. Dit is letterlik dieselfde probleem as die eerste toets. En dit is byna dieselfde probleem as pset1. Maar dit was doelbewus vereenvoudig te wees 'n eenvoudiger piramide, een wat kan wees opgelos met 'n effens eenvoudiger iterasie. En regtig, wat ons was om te hier is nie soseer die logika, want waarskynlik deur hierdie punt, is jy meer gemaklik as jy was in week een met vir sirkelroetes of hoekom loops, maar regtig uitmekaar te terg wat jy is 'n bietjie gemaklik met die idee dat PHP is nie net oor wat ontwikkeling. Dit kan eintlik as 'n taal wat gebruik word command line programme te skryf. 

En inderdaad, dit is wat ons probeer jou aandag te vestig op. Dit is 'n command line PHP program. So C-kode hier, terwyl korrekte in C nie korrek vir PHP. Maar die kode is regtig dieselfde. As jy die oplossings vir Quiz vergelyk 0 teen Quiz 1, sal jy vind dat dit is byna identies, behalwe vir paar dollar tekens en vir die afwesigheid van 'n data tipe. In die besonder, as ons neem 'n blik hier, Jy sal sien dat ons Itereer, in hierdie geval, vanaf 1 tot en met 7. 

Ons kon gedoen het om dit 0 indeks. Maar soms, ek dink dit is net verstandelik makliker om te dink oor dinge 1-7. As jy wil 'n blok, dan twee blokke, dan drie, dan dot, dot, dot sewe. Ons het j word geïnisialiseer 1 en dan toe op tot i. En alles hier is andersins identiese. Maar waardig van die nota is 'n paar dinge. Ons gee jou hierdie twee lyne, die eerste een, goofily aangewys as 'n kaboedel vir 'n skerp knal. En dat net spesifiseer die pad, die gids, waarin 'n program kan gevind dat jy wil gebruik hierdie lêer te interpreteer. 

En dan is die lyn daarna, van Natuurlik beteken betree PHP af. En die lyn aan die heel onderste beteken uitgang PHP af. En dit werk, in die algemeen, met tale vertaal. Dit is soort van irriterende as jy skryf 'n program in 'n lêer genaamd foo.php. En dan jou gebruikers moet net Onthou, OK, hierdie program uit te voer, het ek het om te tik "PHP ruimte foo.php." Soort irriterende as niks anders nie. En dit het ook onthul dat jou program is in PHP, wat nie alle skriftelike dat insiggewend vir die gebruiker. 

So kan jy die. PHP heeltemal verwyder onthou uit die lesing. En jy kan eintlik doen nie. / Foo as jy chmodded dit deur dit uitvoerbaar nie. So chmod + x 'n cat sou gedoen het nie. En as jy ook voeg die kaboedel hier. Maar regtig, is die probleem om te uit te druk iets soos hierdie. Geen HTML, geen C-kode beslis, net 'n paar PHP. So Milo dan terug in probleem 25. En in 25, het jy die volgende gegewe geraamte kode, wat was 'n eenvoudig webblad. En die sappige deel HTML-wyse was af hier, waar ons binnekant van die liggaam 'n vorm wat unieke ID van insette binnekant van wat twee insette, een met 'n idee van 'n naam, 'n met 'n idee van die knoppie. 

Die eerste was die tipe teks, die tweede tipe dien. En so het ons julle dit eintlik meer bestanddele as jy nodig het, net so julle ouens het opsies waarmee Om hierdie probleem op te los. Jy nie streng nodig nie al hierdie name. Maar dit kan jy op te los dit in verskillende maniere. En tot by die top, sien dat Die doel was om te aktiveer 'n venster soos hierdie - Hallo, Milo! - pop up in die leser met behulp van die super eenvoudige, indien nie lelik, waarskuwing funksie. En so, uiteindelik, kom neer konseptueel een of ander manier te luister vir voorleggings van die vorm kliënt-kant , Nie die bediener-kant, een of ander manier reageer op dat die indiening deur gryp die waarde wat die gebruiker getik in die naam veld, en dan vertoon dit in die liggaam van 'n waarskuwing. 

So 'n manier wat jy kan doen, is om met jQuery, wat 'n bietjie lyk sintakties verwarrende by die eerste. Jy kan dit doen met suiwer DOM-kode - document.getelement deur ID. Maar laat ons neem 'n blik op hierdie weergawe. Ek het 'n paar van die belangrike lyne eerste. So een, ons het hierdie lyn, wat identies aan wat jy dalk gesien het in, glo ek, form2.html van die klas in week 9. En dit is net te sê, uit te voer die volgende kode toe die dokument is gereed. Dit wat belangrik is net omdat HTML bladsye is top lees onder, links na regs. 

En daarom, as jy probeer om te doen iets in die kode hier na 'n paar DOM element, sommige HTML tag, dis af hier, jy doen dit te gou, want dit het nie eens is in die geheue te lees. So sê die document.ready lyn, sê ons, hier is 'n paar kode, leser. Maar voer nie, totdat die hele dokument gereed is, dit is die DOM boom bestaan ​​in die geheue. Hierdie een is 'n bietjie meer eenvoudig, as sintakties 'n bietjie anders, waar ek sê, gryp die HTML element wie se unieke identifiseerder is insette. Dit is wat die hash tag dui die unieke ID. En dan is ek 'n beroep. Dien. 

So. Dien hier is 'n funksie, anders bekend as 'n metode, wat binnekant van die voorwerp op die linker kant is daar dat ek nie lig. So as jy dink van insette as 'n voorwerp in die geheue - en inderdaad is dit. Dit is 'n knoop in 'n boom - . Indien middel wanneer hierdie vorm met hierdie ID ingedien is, voer die volgende kode. Ek gee nie om wat die naam van die funksie is ek die uitvoering. So hier Ek gebruik, soos voorheen, wat is genoem die lambda funksie of 'n anonieme funksie. Dit is glad nie intellektueel interessante anders as dit het nie 'n naam, wat is goed as jy net ooit gaan om dit te keer bel. En binne-in daar het ek eintlik hanteer die indiening van die vorm. Ek het eers verklaar 'n veranderlike genoem waarde. En dan wat is die uitwerking van hierdie uitgelig gedeelte hier en nou? Wat beteken dat jy doen op 'n hoë vlak vir my? 

Publiek: Dit raak die waarde wat die gebruiker het nie in die HTML hieronder. Dit raak dat ID en dan bevind dat die waarde van dit. 

David J. MALAN: Presies. Dit gryp die knoop, wie se unieke identifiseerder is die naam. Dit raak die waarde daarin, wat is, vermoedelik, wat die gebruiker hom-of haarself getik. En dan is dit die winkels wat in die veranderlike genoem waarde. As 'n eenkant, kan jy ook 'n gedoen 'n bietjie anders. Heeltemal aanvaarbaar om iets te doen leuen var waarde kry document.getElementById. En dit is die rede waarom dit is 'n bietjie vervelige om nie jQuery gebruik. "Naam". Waarde. So heeltemal aanvaarbaar. Verskillende maniere om dit te doen. jQuery net geneig is om 'n bietjie meer bondige en beslis meer gewild onder programmeerders. 

Nou, ek is besig met 'n bietjie van 'n gesonde verstand kyk, want in die probleem verklaring ons uitdruklik gesê het, as die gebruiker het nog nie getik sy of haar noem, nie 'n waarskuwings wys. Maar jy kan kyk vir daardie, met net kontrole vir die leë string vir 'n quote-unquote as daar niks werklik daar. Maar as dit is nie gelyk aan quote-unquote, Ek wil kennisgewings te noem. En die interessante deel hier is dat ons gebruik die plus operateur, wat doen wat in JavaScript? Koppel. So dit is soos PHPs dot operateur. Dieselfde idee, effens anders sintaks. En ek is net die skep van die string wat jy sien op die skerm geskiet - Hallo, so en so. 

En dan is die laaste detail is dit. Hoekom moet ek terugkeer valse binnekant van hierdie anonieme funksie? 

Publiek: Daar is geen waarde nie. Jy het dit in die vorm. Dit sê net, as waarde is nie gelyk aan leë, dan doen dit. Daar was 'n leë in die voorlegging. 

David J. Malan OK. Versigtig. Daar is niemand anders hier. En dat terugkeer valse buite van die indien toestande. So dit uitgelig lyn, terug valse, voer nie saak wat toe die vorm ingedien word. Wat beteken valse binnekant van die terugkeer geval hanteerder, soos dit genoem word, die geval in die vraag synde voorlegging? 

Publiek: Omdat dit gebeur net een keer. 

David J. Malan gebeur net een keer. Nie heeltemal nie. Ja? 

Publiek: Dit verhoed dat die vorm van indiening van die standaard gedrag, wat sou die bladsy herlaai. 

David J. MALAN: Presies. So ek oorlaai die term lê hier, want ek sê, die vorm is ingedien word. Maar as jy voor, dit is eintlik nie ingedien in die ware HTTP manier. As jy Stuur klik, as gevolg van ons onSubmit hanteerder, ons onderskepping wat deel vorm van die voorlegging so te praat. Ons is dan doen ons ding met JavaScript-kode. Maar ek doelbewus terugkeer valse, want wat ek wil nie om te gebeur 'n split sekonde later is vir die hele vorm self aan die web ingedien word bediener met sleutel waarde pare deur die verandering die URL iets te wees q = katte of wat ook al wat ons gedoen het, byvoorbeeld in die klas. Ek wil nie hê dat dit gebeur nie, want Daar is geen bediener luister vir hierdie vorm indien. Dit is suiwer gedoen in JavaScript-kode. En dit is die rede waarom ek het nie eens 'n aksie kenmerk op my vorm, want ek nie van plan is om dit te ooit gaan na die bediener. 

So dit is wat ingedien is nie. Maar ons is onderskepping wat vorm voorlegging en die voorkoming van die standaard gedrag, wat eintlik gaan al die pad na die bediener. 

Publiek: So hou dit kliënt-kant. 

David J. MALAN: Hou dit kliënt-kant. Presies reg. Volgende aan die beurt was my o MySQL. 

ROB BOWDEN: OK. So die eerste vraag was oor die algemeen rowwe vir mense. Hoewel die lateres het beter. So jy het die korrekte data te kies tipes vir beide van hierdie kolomme. En beide van hulle het 'n paar dinge oor die wat die keuse moeilik. So int was nie 'n geldige tik vir die nommer. Die rede hiervoor is 'n 12-syfer-rekening nommer, 'n int is nie groot genoeg is om te stoor totale syfers. So 'n geldige keuse 'n groot sou gewees het int as jy gebeur om te weet dat. Nog 'n keuse kon gewees het 'n kar gebied van lengte 12. So een van dié sou gewerk het. Int wou nie. 

Nou, balans, dink terug aan pset7. So het ons spesifiek gebruik desimale te slaan die waarde van die aandele of - 

David J. Malan Cash. 

ROB BOWDEN: Cash. Ons gebruik die bedrag van die desimale te stoor kontant wat die gebruiker op die oomblik het. So die rede waarom ons doen wat want, onthou, dryf. Daar is swaai punt in presisie. Dit kan nie juis die stoor van die kontant waardes soos ons wil hier. So desimale presies te stoor om iets te sê, twee desimale plekke. Dit is waarom die balans, ons dit wil hê te desimale en nie dryf nie. 

David J. Malan En ook, ook, al dit kan slim gewees het in ander konteks te dink, miskien is dit is 'n kans vir 'n int. Ek sal net track hou van dinge in pennies. Omdat ons uitdruklik het die standaard waarde daarvan 100.00, wat beteken dit kan net 'n int. En 'n ander subtiel te met die getal was dat dit was nie bedoel 'n truuk vraag te wees. Maar onthou dat 'n int in MySQL, soos in C, ten minste in die toestel, is 32-bit. En selfs al het ons nie verwag nie om jou te weet presies hoeveel syfers wat middel, nie onthou dat die grootste aantal jy kan potensieel verteenwoordig met 'n 32-bis getal is ongeveer wat? 

Watter getal ons altyd sê nie? 2 aan die 32, wat is wat ongeveer? Jy hoef nie te weet presies. Maar min is nuttig in die lewe. Dit is ongeveer 4000000000. So ons het gesê dat 'n paar keer. Ek weet ek het gesê dat 'n paar keer. En dit is ongeveer 4000000000. En dit is 'n goeie reël van die duim te leer ken. As jy 8 stukkies, 256 is die magie nommer. As jy 32 stukkies, 4 miljard gee of neem. So as jy skryf net af 4000000000, Jy sal sien dat dit is minder as syfers 12, wat beteken dit is duidelik nie genoeg uitdrukking te vang 'n 12-syfer rekening nommer. 

ROB BOWDEN: OK. So het die ander kinders het beter. So veronderstel dat die bank stel 'n $ 20 maandelikse onderhoud fooi op alle rekeninge. Met watter SQL navraag kon die bank trek $ 20 uit elke telling, selfs al dit lei tot 'n negatiewe saldo? So basies, is daar vier hooftipes navrae - voeg, kies, te verander en te verwyder. So wat doen ons dink ons ​​is gaan hier gebruik? Werk. 

So kom ons neem 'n blik. So hier is ons opdatering. Wat tafel is ons opdatering rekeninge? So afhangende van rekeninge. En dan is die sintaksis sê, wat in rekeninge is ons opdatering? Wel, ons die opstel van balans gelyk aan die huidige waarde van minus 20. So dit sal werk al die rye van rekeninge, af te trek $ 20 uit die balans. 

David J. MALAN: 'n algemene fout hier, selfs al het ons soms vergewe nie, was eintlik 'PHP-kode hier roep die navraag funksie of om aanhalingstekens rondom alles wat het nie nodig om daar te wees. 

ROB BOWDEN: Onthou dat MySQL is 'n aparte taal van PHP. Ons gebeur te word skryf MySQL in PHP. En PHP dan stuur oor die MySQL bediener. Maar jy hoef nie PHP ten einde te kommunikeer met 'n MySQL bediener. 

David J. MALAN: Presies. Sodat daar geen veranderlikes met dollar tekens moet in hierdie konteks. Dit kan net nie al die wiskunde binne die databasis self. 

ROB BOWDEN: OK. So die volgende een. Is dit die volgende een? Ja. So met wat SQL navraag kon die bank haal die rekening nommers van sy rykste kliënte, diegene met 's groter as 1000? So wat van die vier hooftipes gaan ons hier? Kies. So wil ons kies. Wat wil ons kies? Wat kolom wil ons kies? Ons sal spesifiek wil nommer te kies. Maar as jy sê sterre, ons ook aanvaar dat. 

So kies nommer van wat tafel? Rekeninge. En dan is die toestand wat ons wil hê? Waar balans groter as 1000. Ons het ook 'n groter aanvaar as of gelyk. Laaste een. Met watter SQL navraag kon die bank naby, maw, elke rekening verwyder wat het 'n bedrag van $ 0? So wat van die vier is ons gaan wil gebruik? Verwyder. So het die sintaksis vir daardie? Verwyder van wat tafel? Rekeninge. En dan is die voorwaarde waarop Ons wil verwyder - waar balans gelyk is aan nul. So verwyder alle rye uit rekeninge waar die balans is nul. Vrae oor enige van hierdie? Wil om te ry? 

David J. Malan tou gids. So in hierdie een, het ons julle gegee het 'n ietwat bekende struktuur wat ons ondersoek 'n bietjie in die klas naas structs, wat 'n data struktuur wat verband hou in die gees. Die verskil egter met 'n tou is dat ons moes een of ander manier te onthou wat was aan die voorkant van die tou, in 'n groot deel sodat ons meer kan maak doeltreffende gebruik van die geheue, ten minste As ons gebruik 'n skikking. 

Omdat Onthou, as ons 'n skikking, indien byvoorbeeld, is dit die voorkant van die tou, as ek in die tou hier, en dan iemand kry in lyn agter my, agter my, agter my, en een persoon stappe van die lyn, jy kon, soos ons gesien het 'n paar van ons menslike vrywilligers in die klas, het almal skuif op hierdie manier. Maar in die algemeen, met almal te doen iets is nie die beste gebruik van tyd in 'n program, want dit beteken dat jou algoritme loop in watter asimptotiese loop tyd? Dit is lineêr. 

En ek voel soos dit is soort van dom. As die volgende persoon in lyn is die volgende persoon wat veronderstel is om te gaan in die winkel, het hulle nie almal om saam te beweeg. Laat daardie persoon gepluk word wanneer die tyd kom, byvoorbeeld. So kan ons 'n bietjie van die tyd te bespaar daar. En om dit te doen dat alhoewel, wat beteken dat dat die hoof van die tou of die voorkant van die tou gaan progressief dieper en dieper beweeg in die skikking en uiteindelik mag eintlik draai om as ons met behulp van 'n verskeidenheid mense te slaan in hierdie tou. So kan jy amper dink aan die skikking as 'n omsendbrief data struktuur in die sin dat. 

So jy een of ander manier het die spoor van die te hou grootte van dit of regtig die einde van dit en dan waar die begin van dit is. So stel ons voor dat jy verklaar een so 'n ry, roeping dit Q, net een letter. Toe ons voor dat die voorkant geïnisialiseer aan nul is en dat die grootte word geïnisialiseer aan nul. 

So nou, daar is niks binnekant van die tou. En ons vra u om te voltooi die implementering van enqueue hieronder in so 'n manier dat die funksie voeg N die einde van Q en dan terug waar. Maar as q is vol of negatief is, die funksie moet eerder terugkeer onwaar. En ons het vir julle 'n paar aannames. Maar hulle is nie regtig funksioneel relevant, net dat Bool bestaan, want tegnies, Bool nie bestaan ​​in C nie, tensy jy 'n sekere kop lêer. So wat maak net seker dat daar is nie, is dit 'n truuk vraag soort van ding. 

So enqueue ons in die monster voorgestelde oplossings soos volg te implementeer. Een, het ons eers die gemak, die lae-hangende vrugte. As die tou is vol of die getal wat jy probeer om te voeg, is minder as nul, wat ons het in die spesifikasie van die probleem moet nie toegelaat word nie, want ons wil net nie-negatiewe waardes, dan moet jy net terugkeer onmiddellik onwaar. So 'n paar relatief maklik Fouttoetsing. As al wat jy wil byvoeg dat die werklike nommer, jy het 'n bietjie te doen dink hier. En dit is waar dit is 'n bietjie irriterend geestelik, want jy het om te uit te vind hoe wraparound te hanteer. 

Maar die kiem van die idee hier is dat van belang vir ons is dat wraparound dikwels impliseer modulêre rekenkunde en die mod-operateur, die persent kant, waar jy kan gaan van 'n groter waarde terug na nul en dan een en twee en drie en dan weer terug om te nul, een en twee en drie en so meer weer en weer. So het die manier waarop ons dit doen, is stel voor dat ons nie wil kruip in die skikking met die naam nommers waar ons heelgetalle lê. Maar om daar te kom, moet ons eers wil doen ongeag die grootte van die tou is, maar dan voeg by dat wat ook al die voorkant van die lys is. En die effek van wat ons te sit op die regte posisie in die tou en nie aanvaar dat die eerste persoon in lyn is aan die begin, wat hy of Sy het absoluut kan wees as ons Daar is ook die verskuiwing van almal. Maar ons is maar net die skep van werk vir onsself as ons het daardie spesifieke pad. 

Sodat ons dit kan hou relatief eenvoudig. Ons moet onthou dat ons net bygevoeg 'n int na die tou. En dan het ons net terug waar. Intussen, in dequeue, het ons gevra jy die volgende te doen. Implementeer dit op so 'n manier dat dit dequeues, wat en hef opbrengste, die int aan die voorkant van die tou. Die int te verwyder, is dit voldoende om dit te vergeet. Jy hoef nie sy deel te ignoreer. So dit is nog steeds eintlik daar. Net soos data op 'n hardeskyf, ons is maar net ignoreer die feit dat dit nou daar. En as q leeg is, moet ons plaas terug negatiewe 1. So dit voel arbitrêre. Hoekom terugkeer negatiewe 1 in plaas van vals? Ja. 

Publiek: Q stoor positiewe waardes. Omdat jy net positiewe waardes te stoor in die Q, negatiewe is 'n fout. 

David J. MALAN: OK, waar is. So, want ons is net te stoor positiewe waardes of nul is, dan is dit goed om te terugkeer 'n negatiewe waarde as 'n brandwag waarde, 'n spesiale simbool. Maar jy herskryf die geskiedenis is daar, omdat die rede waarom ons is net terugkeer nie negatiewe waardes is omdat ons wil het 'n brandwag waarde. So meer spesifiek, hoekom nie net terugkeer valse in gevalle van foute? Ja. 

Publiek: Jy het misluk 'n heelgetal terug te keer. 

David J. MALAN: Presies. En dit is waar C kry mooi beperkende. As jy sê jy gaan 'n int om terug te keer, het jy 'n int om terug te keer. Jy kan nie fancy en begin terugkeer 'n Bool of 'n float of 'n string of iets soos dit. Nou, intussen, JavaScript en PHP en 'n paar ander tale, in werklikheid, het jy terugkeer verskillende tipes waardes. En dit kan eintlik nuttig wees, waar jy kan positiewe ints, nulle terugkeer, negatiewe ints, of valse of null selfs fout aan te dui. Maar ons het nie daardie veelsydigheid in C. 

So met dequeue, wat ons voor te doen, is om - 

ROB BOWDEN: Jy kan terugkeer onwaar. Dit is net dat valse is hash definieer vals nul. So as jy valse terugkeer, jy terugkeer nul. En 'n nul is 'n geldige ding in ons ry, terwyl negatiewe 1 is nie, indien valse gebeur te wees negatief 1. Maar jy moet nie eens nodig om te weet dat. 

David J. Malan Dis Daarom het ek nie sê nie. 

ROB BOWDEN: Maar dit is nie waar nie dat jy nie vals kan terugkeer. 

David J. MALAN: Natuurlik. So dequeue, sien ons aanvaar nietig sy argument. En dit is omdat ons nie verbygaande enigiets in Ons wil net die element te verwyder aan die voorkant van die tou. So, hoe kan ons te werk gaan om dit te doen? Wel, die eerste, laat ons dit doen vinnige gesonde verstand tjek. As die tou grootte is 0, is daar geen werk wat gedoen moet word. Terug negatiewe 1. Gedoen. So dit is 'n paar lyne van my program. So net vier lyne te bly. 

So hier het ek besluit om te Trek ' die grootte. En effektief decrementing die grootte beteken dat ek vergeet iets is daar in. Maar ek het ook by te werk waar die voorkant van die getalle is. So om dit te doen, moet ek twee dinge te doen. Ek moet eers onthou wat die aantal is aan die voorkant van die tou, want ek moet die ding om terug te keer. So ek wil nie per ongeluk vergeet daaroor en dan oorskryf nie. Ek gaan net om te onthou in 'n int. 

En nou, ek wil om te werk q.front te q.front word 1. So as dit was die eerste persoon in lyn, nou, ek wil plus 1 te doen om te wys op die volgende persoon in lyn. Maar ek het dat wraparound te hanteer. En as kapasiteit is 'n globale konstante, wat gaan om my om seker te maak as ek verwys na die heel laaste persoon in word, sal die modulo werking te bring my terug na nul op die voorkant van die tou. En dit hanteer die wraparound hier. En dan het ek gaan na n terugkeer. 

Nou, streng gesproke, ek het nie het n te verklaar. Ek het nie om dit aan te gryp en stoor dit tydelik, want die waarde nog steeds daar. So ek kon net nie die reg om rekenkundige die voormalige hoof om terug te keer van die tou. Maar ek het net gevoel dat dit meer duidelik om werklik die int gryp, het dit in n, en dan terug te keer dat ter wille van duidelikheid se maar nie streng nodig. Psst. Hulle is almal uitspreekbare in my kop. 

ROB BOWDEN: So eerste vraag is die binêre boom probleem. So die eerste vraag is, ons is gegee om hierdie getalle. En ons wil een of ander manier plaas dit in Hierdie nodes so dat dit 'n geldig binêre soek boom. So het die een ding om te onthou oor binêre soek bome is dat dit nie net dat die ding aan die linkerkant is minder en die ding te die reg is groter. Dit moet wees dat die hele boom te links is minder, en die hele boom aan die regterkant is groter. 

So as ek 34 hier aan die bokant, en dan Ek sit 20 hier, so dit is geldig so ver, want 34 tot hier. 20 gaan aan die linkerkant. So dit is minder. Maar ek kan nie dan sit 59 hier, want selfs al 59 is op die regte van 20, dit is nog steeds aan die linkerkant van 34. So met daardie beperking in gedagte, die maklikste manier van waarskynlik die oplossing van hierdie probleem is net soort van hierdie getalle - so 20, 34, 36, 52, 59, 106. En dan voeg diegene van links na regs. 

So 20 gaan hier. 34 gaan hier. 36 gaan hier. 52, 59, 106. En jy kan ook uitgepluis het met sommige steek in en besef, O, wag, ek het nie genoeg getalle om dit te vul hier. So ek moet reshift wat my roetenotastelsel gaan wees. Maar let dat in die laaste drie, indien jy lees van links na regs, is dit in toenemende orde. 

So nou, ons wil om te verklaar wat die struct gaan wees vir die nodes in hierdie boom. So wat moet ons in 'n binêre boom? So ons het 'n waarde van die tipe int, so 'n paar int waarde. Ek weet nie wat ons geroep dit in die oplossing - int n. Ons moet 'n verwysing na die linker-kind en 'n verwysing na die regte kind. So dit gaan om te kyk soos hierdie. En dit sal eintlik kyk voor wanneer het die dubbel-gekoppelde lys dinge, so kennisgewing - Ek gaan hê om te blaai om al die pad terug af na die probleem 11. 

So sien dit lyk identies aan hierdie, Behalwe ons net gebeur om dit te noem verskillende name. Ons het nog 'n heelgetal waarde en twee wysers. Dit is net dat in plaas van die behandeling van die wysers as verwys na die volgende ding en die vorige ding, ons behandel die wysers om te wys op 'n links kind en regs kind. OK. So dit is ons struct knoop. En nou, die enigste funksie wat ons nodig het om te implementeer, want dit is deurkruis, wat ons wil om te gaan oor die boom, drukwerk die waardes van die boom in orde is. 

So soek hier, sou ons wil druk uit 20, 34, 36, 52, 59, en 106. Hoe kan ons bereik wat? So dit is redelik soortgelyk. As jy in die afgelope eksamen het die probleem wat jy wou om uit te druk die hele boom met kommas tussen alles, dit was eintlik selfs makliker as dit. So hier is die oplossing. Dit is aansienlik makliker As jy dit gedoen het rekursief. Ek weet nie of iemand probeer om dit te doen iteratief. 

Maar eers, moet ons ons basis geval. Wat as die wortel van nul? Daarna het ons gaan net om terug te keer. Ons wil nie iets te druk. Anders gaan ons deurkruis rekursief af. Druk die hele linker boomstruktuur inskuif nie. So druk alles minder as my huidige waarde. En dan gaan ek myself te druk. En dan gaan ek recursief down my hele reg substructuur, so alles groter as my waarde. En dit gaan druk uit alles in orde is. Vrae oor hoe dit eintlik accomplishes dit? 

Publiek: Ek het 'n vraag op die [onhoorbaar]. 

ROB BOWDEN: So een manier om nader enige rekursiewe probleem is net te dink daaroor wil jy hê om te dink oor al die hoek gevalle. So is van mening dat ons wil druk die hele boom. So al wat ons gaan om te fokus op is hierdie spesifieke knoop - 36. Die rekursiewe oproepe, ons voorgee dié wat net werk. So hier is dit rekursiewe oproep te deurkruis, het ons sonder om selfs te dink daaroor, net dwars deur die linker drie, dink dat daar reeds druk 20 en 34 vir ons. En dan wanneer ons uiteindelik rekursief noem deurkruis op die reg, dit sal korrek druk 52, 59, en 106 vir ons. 

So gegee dat dit kan druk 20, 34, en die ander kan druk 52, 59, 108, Al wat ons moet in staat wees om te doen is om druk onsself in die middel van daardie. So druk alles voor ons. Druk onsself, sodat die knoop druk 36, gereelde printf, en dan druk alles agter ons aan. 

David J. Malan Dit is waar rekursie regtig mooi. Dit is hierdie wonderlike sprong van geloof waar jy doen die kleinste bietjie van die werk. En dan moet jy laat iemand anders doen die res. En dat iemand anders is, ironies genoeg, jy. So vir ernstige poeding punte, indien jy blaai op die vrae - 

ROB BOWDEN: Op die vrae? 

David J. Malan en af ​​in 'n bietjie te die nommers, nie almal weet waar hierdie getalle kom uit? 

ROB BOWDEN: Ek het letterlik geen idee nie. 

David J. Malan Hulle verskyn Regdeur die toets. 

Publiek: Is hulle dieselfde getalle? 

David J. Malan Diegene nommers. 'N bietjie Easter eier. So vir die van julle kyk aanlyn by huis, as jy kan ons vertel via e-pos aan heads@CS50.net wat die betekenis van hierdie herhalende ses nommers is Dwarsdeur Quiz 1, sal ons u stort met ongelooflike aandag aan die finale lesing en 'n stress bal. Nice, subtiel. 

ROB BOWDEN: Enige laaste vrae oor enige iets op die quiz?