DAVID J. MALAN: Greit. Så velkommen til den første noensinne CS50 post mortem for en quiz. Vi trodde vi skulle innvie denne tradisjonen i år. Og dette vil være en mulighet å gå gjennom løsninger til quiz. Og vi vil fremskynde eller forsinke basert på renter av dem her. 

Så du er sannsynligvis her fordi du er interessert i hvordan du kan ha eller burde ha besvart noen av disse problemene. Så hvorfor ikke vi ta en titt på denne delen først? Så det å få strenger. Dette ga deg tre forskjellige versjoner av et program som var, til slutt, ment å få en streng fra en bruker. Hvorvidt det gjorde det var overlatt til deg å bestemme. 

Og vi spurte i Spørsmål 0, anta at versjon 1 er kompilert og henrettet. Hvorfor kan programmet segfault? Ved første øyekast, noen forslag på hvorfor? Yeah. 

PUBLIKUM: Så jeg husker å se dette i et tidligere eksempel på å se på char * s og se skanning av s og se fordi det er en peker, hvordan gjorde det påvirke hva du skannet inn? Er det s eller adressen til s? 

DAVID J. MALAN: OK. Bra. Så til slutt, kilden til problemet er antagelig kommer til å redusere til den variabelen s. Og det er faktisk en variabel. Datatypen til den variabelen er char *, noe som betyr at det kommer til å inneholde adressen for et tegn. Og deri ligger innsikt. Det kommer til å inneholde adressen til en art eller, mer generelt, Adressen til det første tegnet i en hel blokk av tegn. 

Men fangsten er at skanning s, formål i liv, blir gitt en adresse og gitt et format kode, som% s, lese en streng i den del av minnet på denne adressen. Men fordi det er ingen likhetstegn før at semikolon på den første linje med kode, fordi vi ikke egentlig bevilge noe minne med malloc, fordi det gjorde faktisk ikke allokere en matrise av en viss størrelse, alt du gjør er å lese brukerens tastaturet innspill til noen komplett søppel verdi, som er i s som standard. Så oddsen er at du kommer til å segfault hvis at adressen ikke bare så skje å være en verdi som du kan, faktisk, skrive til. Så ille ikke å tildele hukommelsen der. 

Så det er snakk om en, spurte vi, anta at versjon 2 er kompilert og henrettet. Hvorfor kan dette programmet segfault? Så dette er mindre buggy. Og det er egentlig bare ett opplagte måten hvor du kan utløse en segfault her. Og dette er tematisk. Hver gang vi bruker c i minne, hva kan du gjøre for å indusere en segfault med versjon 2? 

PUBLIKUM: Hvis du bruker som innspill i en streng som er lengre enn 49 tegn. 

DAVID J. MALAN: Nettopp. Hver gang du ser noe fast lengde når det kommer til en matrise, din radar bør gå av at dette kan være problematisk hvis du ikke sjekker grensene for en matrise. Og det er problemet her. Vi fortsatt bruker scanf. Vi er fortsatt bruker% s, som betyr prøve å lese en streng fra brukeren. Det kommer til å bli lest inn s, som, på dette punktet, er effektivt adressen til en del av minnet eller er det tilsvarende. Det er navnet på en matrise tegn i minne. 

Men akkurat det, hvis du leser en streng som er lengre enn 49 tegn, 49 fordi du trenger plass til backslash 0, kommer du til å renne over som buffer. Og du kan ha flaks og være i stand til skrive et 51st karakter, 52., 53.. Men på et tidspunkt, OS kommer til å si, nei. Dette er definitivt ikke minne du har lov til å røre. Og programmet kommer til å segfault. 

Derfor er det, bør de heuristikker være en hvilken som helst gang du har fast lengde, har du å sørge for at du sjekker lengden av hva det er du prøver for å lese inn i den. 

PUBLIKUM: Så for å løse det, kan du har hatt en uttalelse sjekker faktisk er lengden større eller mindre enn? 

DAVID J. MALAN: Absolutt. Du har bare en tilstand som sier, hvis - eller rettere sagt du ikke nødvendigvis kjenner på forhånd hvor mange tegn det brukeren kommer til å skrive, fordi du har høna og egget. Ikke før du har lest det på med scanf kan du finne ut hvor lang tid det er. Men på dette punktet, er det for sent, fordi du allerede har lest det inn en minneblokk. Så som en side, CS50 bibliotek unngår dette problemet helt, tilbakekalling ved hjelp fgetc. Og den leser ett tegn om gangen, tip-toeing sammen, vel vitende om at du kan ikke overskylle en karakter hvis du leser en om gangen. 

Fangsten er med getstring tilbakekalling er at vi må stadig re-størrelse som del av minne, som er bare en smerte. Det er en rekke linjer med kode for å gjøre det. Så annen tilnærming ville være å faktisk bruke en fetter, så å snakke, av scanf. Det finnes varianter av mange av disse funksjoner som faktisk sjekke lengden på hvor mange tegn du kan lese maksimalt. Og du kunne spesifisere, ikke les mer enn 50 tegn. Slik det ville være en annen tilnærming, men mindre imøtekommende av større innganger. 

Så spørsmål 2 spør, antar at versjon 3 er kompilert og henrettet. Hvorfor kan det programmet segfault? Så dette er faktisk den samme svare på, selv om det ser litt mer avansert. Vi bruker malloc, som føles som vi gir oss selv flere alternativer. Og så skal vi frigjøre at hukommelse i enden. Det er fortsatt bare 50 byte minne. Så vi kan likevel prøve å lese i 51, 52, 1000 bytes. Det kommer til å segfault for nøyaktig den samme grunn. 

Men det er en annen grunn for. Hva annet kunne malloc retur foruten adressen til en del av minnet? Det kunne returnere null. Og fordi vi ikke er sjekker for det, kan vi gjøre noe dumt for en annen grunn, som er at vi kan fortelle scanf, lese brukerens input fra tastaturet inn 0 beliggenhet, AKA null. Og det vil også definitivt utløse en segfault. Så for quiz formål, ville vi har akseptert en av dem som en gyldig grunn. En er identiske. Det ene er litt mer nyansert. 

Til slutt, med hensyn til programmets bruk av minne, hvordan versjon 2 og versjon 3 forskjellige? Så for hva det er verdt, så vi en tilsynelatende endeløs forsyning av mulig svar på dette. Og blant folks svar, hva vi var håper på, men vi aksepterte andre ting, var noen omtale av faktum at versjon 2 bruker den såkalte stabelen. Versjon 3 bruker haugen. Og funksjonelt, gjør dette egentlig ikke gjør alt så mye av en forskjell. På slutten av dagen, er vi fremdeles bare å få 50 byte minne. 

Men det var en av de mulige svar at vi var ute på. Men du vil se, som du får dine quizer tilbake fra TFs, som vi gjorde akseptere andre diskusjoner om deres ulike bruk av minne i tillegg. Men stable og heap ville ha vært et enkelt svar å gå med. Eventuelle spørsmål? Jeg gir deg Rob. 

ROB BOWDEN: Så problemet fire. Dette er en hvor du måtte fylle i antall bytes av all disse ulike typer som brukes. Så første vi ser. Anta en 32-bits arkitektur, som dette CS50 apparatet. Så en av de grunnleggende ting om 32-bits arkitekturer, forteller at oss nøyaktig hvor stor en peker kommer til å være i arkitekturen. 

Så umiddelbart, vi vet at noen peker typen er 32-bits eller 4 bytes. Så se på denne tabellen, en node * er en peker type. Det kommer til å være fire byte. Struct node *, det er bokstavelig talt identisk med node stjerne. Og så det kommer til å være fire byte. String, så det ser ikke ut som en pekeren ennå, men typedef, en string er bare en char *, som er en pekertypen. Så det kommer til å bli fire byte. 

Så disse tre er alle fire byte. Nå, node og student er litt mer komplisert. Så se på node og student, ser vi node som et heltall, og en peker. Og student er to pekere på innsiden av den. Så i hvert fall for vår sak her, måten som ender vi opp med å beregne størrelsen dette struct er bare legge opp alt som er inne i struct. 

Så for node, har vi et heltall, som er 4 byte. Vi har en peker, som er 4 byte. Og så en node går å ta opp 8 byte. Og tilsvarende for student, har vi en peker som er 4 byte og en annen peker som er 4 byte. Så det kommer til å ende opp som 8 byte. Så node og student er 8 byte. Og disse tre er alle fire byte. Spørsmål om det? Ja. 

PUBLIKUM: Er det var en 64-bit arkitektur, ville det doble dem alle? 

ROB BOWDEN: Det ville ikke doble dem alle. Så 64-bits arkitektur, det, igjen, endringer som grunnleggende ting som en pekeren er nå 64 bits. Yeah. Så en peker er 8 byte. Så disse som var 4 byte kommer til å være 8 byte. En student, som var to pekere, vel, nå kommer det til å være 8 byte, 8 byte. Det kommer til å gjøre 16 bytes. 

Men en node er fortsatt fire byte. Så denne pekeren kommer å være 8 byte. Dette er 4 byte. Så en node er bare kommer å være 12 bytes. Eventuelle andre spørsmål om den? Så den neste, disse er HTTP statuskoder. Og du måtte beskrive forhold under hvilke disse kan bli returnert til deg. ett problem som jeg hørte noen studenter har er at de forsøkte å gjøre feil være på kundens slutten. Så når vi prøver å gjøre forespørselen til serveren, går noe feil på vår side. Men generelt, disse kodene er som returneres av serveren. Så vi ønsker å finne ut hva som skjer galt eller rett på serveren som forårsaker disse tingene for å bli returnert. Så hvorfor kan en server avkastning statuskode 200? Noen tanker? 

Yeah. Så noe om hell forespørselen gikk gjennom. Og de er i stand til å returnere uansett hva du spurte om. Så alt var fint. Hva med 302 funnet? Yeah. 

PUBLIKUM: Serveren var ute for det du ba om. Men det kunne ikke finne den. Så det er en feil. 

ROB BOWDEN: Så var serveren på jakt etter hva du ville. Så bare ser her, 302 funnet, det var i stand til å finne den. 

PUBLIKUM: Jeg beklager. Funnet betyr at de fant det. Unnskyld. 

ROB BOWDEN: Så 302 funnet. Tjeneren er i stand til å finne hva du ville. 

PUBLIKUM: Men det er ikke å vise det? 

ROB BOWDEN: Forskjellen mellom Dette 302 og 200 er at den vet hva du ønsker. Men det er ikke akkurat der du ønsket å spørre. Så 302 er en typisk redirect. Så du har bedt om en side. Det vet, oh, jeg vil å returnere deg dette. Men dette er på en annen nettadresse. Så hei, du faktisk ønsker dette. 

DAVID J. MALAN: Det er et stykke som sa at vi ga dere en redirect funksjon som brukes overskriften funksjon som, i sin tur, trykket ut plassering, kolon, og deretter webadressen du ønsker å avvise brukeren. Selv om du ikke ser 302 eksplisitt der, er at hva PHP ville magisk sett som header si nøyaktig hva Rob sa det - funnet. Men gå her i stedet. 

ROB BOWDEN: OK. Så hva med 403 forbudt? 

PUBLIKUM: Jeg tror det er at serveren er i utgangspunktet si at klienten får ikke tilgang til hjemmesiden. 

ROB BOWDEN: Så ja. Vel, den typiske svaret vi var forventer er noe som, filene ikke oppgitt korrekte rettigheter på riktig måte. Det er trolig under hvilke omstendigheter du så dem. Men det er en grunn til at klienten kunne være på feil her. Det er faktisk en annen statuskode - 401. Så disse er svært like. 

401 er uautorisert. Og 403 er forbudt. Og så uautorisert du utelukkende få hvis du ikke er logget inn Men å logge inn kan bety at du er autorisert. Men hvis du allerede er logget på, og du fremdeles ikke har tillatelse, så du kan også få forbudt. Så hvis du er logget inn og ikke har tillatelse, er også forbudt noe du kan få. 

DAVID J. MALAN: Og den mekanismen som disse problemene er vanligvis løst på serveren er via hvilken kommando? Chmod, hvis det er faktisk en tillatelser utstede på filen eller katalogen. 

ROB BOWDEN: Da 404 ikke funnet. Yeah. Så i motsetning til 302 hvor det var ikke akkurat hvor du spør, men det vet hva du ønsker, dette, det bare har ingen anelse om hva du ønsker. Og du ikke ber om noe gyldig. 418 Jeg er en tekanne og deretter 500 interne server. Så hvorfor kan du få det? 

Så segfault - Jeg faktisk ikke vet gradering standard for dette. Men hvis din PHP-koden hadde noe galt i det, i teorien, det kunne faktisk segfault, i så fall, dette 500 Internal Server Error, noe er galt med serverens konfigurasjon. Eller er det en syntaksfeil i din PHP-kode. Eller noe ille som skjer. 

DAVID J. MALAN: Vi fikk se segfault blant noen få folks svar. Og teknisk sett, kunne det skje. Men det ville være en PHP, programmet skrevet av andre mennesker, faktisk segfaulted, som bare hvis disse menneskene skrudd opp og skrev buggy kode i deres tolk ville PHP selv segfault. Så selv om 500 er som en segfault i ånden, er det nesten alltid Resultatet av en konfigurasjonsfil problem med webserveren eller, som Rob sa, en syntaksfeil, som deg ikke lukke et tilbud. Eller du mistet et semikolon et sted. 

PUBLIKUM: Så for Shuttle PSett, jeg tror når jeg gjorde det en gang jeg klikket leseren, men ingenting kom opp, det de kalte hvit side. Men det var på grunn av koden. Jeg tror det var Javascript, ikke sant? 

ROB BOWDEN: Yeah. 

PUBLIKUM: Vil at feilen fortsatt komme opp? 

ROB BOWDEN: Så du ville ikke ha fått denne feilen fordi alt fra webserveren perspektiv var helt greit. Men du ba index.html. Du har bedt om shuttle.js og service.js. Og det var i stand til å vende tilbake til dere alle disse tingene - 200. OK. Det er bare når nettleseren forsøkte å tolke Javascript-kode som Det er som, vent, dette er ikke gyldig Javascript-feil. Eventuelle andre spørsmål? OK. 

DAVID J. MALAN: Så neste opp var nummer 11. Og 11 var den skumleste for mange mennesker. Så det viktigste å merke seg her , var at dette var, ja, om en dobbelt lenket liste. Men dette var ikke det samme som fjorårets dobbelt lenket liste problem, som ikke gir deg det forbeholdet at listen kunne faktisk være usortert. 

Så det faktum at listen var usortert og det faktum at det ordet var understreket det var ment å formidle at dette er faktisk en forenkling av hva som ellers ville ha vært en mer utfordrende problem og en lengre. Så en vanlig feil her var å ha satt fjorårets løsning på en personsøker og deretter bare blindt kopiere den ned som svar, som er den høyre svare på et annet spørsmål lignende i ånden. Men spissfindigheter her var som følger. 

Så, vi har en node erklært og definert på vanlig måte her. Da vi definert liste over være en global pekeren initialisert til null. Så tydeligvis er det to funksjoner vi har prototyper for her, insert og fjern. Og så har vi noen eksempelkode her av å gjøre en haug med innsettinger. Og så ber vi deg om å fullføre gjennomføring av innsatsen under på en slik en slik måte at den setter n inn i listen i konstant tid, også understreket, selv om allerede er til stede. 

Så det fine med å være i stand til å sette inn i konstant tid er at det innebærer at du må sette inn den nye noden der? Inn i det fram. Så det eliminerer, heldigvis, i hvert fall en av de tilfeller som tidligere krevde enda flere linjer med kode, som det gjorde i fjor, og selv i klassen når vi snakket gjennom denne type ting med mennesker og med noen verbal pseudo-kode. Så i løsningen her, la oss hoppe over I tillegg bare for å ha en visuell on skjermen. 

Legg merke til at vi gjør følgende. Og også legge merke til den andre forenkling var at selv om det er allerede til stede, så dette betyr at selv om nummeret allerede er der, du kan bare blindt sette inn en annen kopi av den. Og det, også, var ment å være en forenkling, slik at du kan fokusere på, virkelig, noen av de mer intellektuelt interessant del og ikke bare noen ekstra feilkontroll gitt begrenset tid. 

Så i denne prøveoppløsning, vi fordele en peker til venstre hånd side her til en node. Nå innser at pekeren, som Rob sa, er bare 32 bits. Og det gjør faktisk ikke inneholder en adresse til deg tilordne den adressen. Og vi gjør det på høyre hånd side via malloc. Som en god borger, sjekker vi at malloc ikke er i virkeligheten null, slik at vi ikke tilfeldigvis lage en segfault her. Og hver gang du bruker malloc i livet, du bør sjekke for null, så du har en subtil feil. 

Da vi initial at null ved tildele n og forrige og neste år. Og i dette tilfellet her, jeg initialisert tidligere til null, fordi denne nye node kommer til å bli den nye begynnelsen av listen min. Så det kommer til å bli ingenting før det. Og jeg vil egentlig tilføye eksisterende liste til den nye noden ved innstilling neste lik å liste seg selv. Men jeg er ikke ferdig ennå. Så hvis selve lista allerede eksisterte, og det var i det minste en node som allerede er på plass, hvis dette er en liste her og jeg setter inn en ny node her, jeg må sørge for at min tidligere node peker bakover til min nye noden, fordi denne er igjen en dobbelt lenket liste. 

Så vi gjør en mental helse sjekk. Hvis listen er ikke null, hvis det er allerede en eller flere noder der, og deretter legge til at tilbake henvisning så å si. Og så den aller siste vi trenger å gjøre er å faktisk oppdatere den globale variabelliste selv å peke til den nye noden. Yeah. 

PUBLIKUM: I pekeren pilen [Uhørbart] er lik null, gjør at forholde seg til listen fordi listen er null? 

DAVID J. MALAN: Nope. Det er rett og slett meg å være proaktivt forsiktig, i at dersom dette er min opprinnelige listen med kanskje noen flere noder over her og jeg setter min ny node over her, det kommer å være noe over her. Og jeg ønsker å fange den tanken ved å sette tidligere til null på den nye node. Og antagelig, hvis min kode er korrekt og det er ingen annen måte å sette inn andre enn denne funksjonen noder, formodentlig allerede har selv om liste en eller flere noder i den, formodentlig listen, den første node, ville ha en forrige pekeren over null selv. 

PUBLIKUM: Og bare en oppfølging. Grunnen til at du setter markøren ved siden av likhets Listen er du gjør pekeren før listen i at den peker til den neste, tror jeg - Vet ikke, - bare lister? 

DAVID J. MALAN: Nettopp. Og så la oss faktisk vurdere to tilfeller her egentlig, selv om For vi vil vurdere dem er ikke helt det samme som koden. Men på et høyt nivå, dersom dette representerer liste, og dette er en 32-bit pekeren, er den enkleste scenariet at dette er null som standard. Og antar at jeg vil sette inn nummer 50 var det første nummeret. Så jeg kommer til å gå videre og fordele en node, som kommer til å inneholde tre felt - n, forrige, og neste. 

Jeg kommer til å sette nummer 50 her, fordi dette vil være n. Dette vil være neste. Og dette vil være tidligere. Og så hva må jeg gjøre i dette tilfellet? Vel, jeg har nettopp gjort linje 1 her. Pointer n blir n. Jeg så å si, tidligere bør få null. Så dette kommer til å være null. Så jeg kommer til å si neste kommer til å få listen. 

Og dette fungerer bare godt ut. Dette er null. Og så jeg sier, den nye noden neste feltet bør få hva dette er. Så det setter en annen null der. Og så det siste Jeg er sjekke her. Hvis listen ikke er lik null, men det er lik null, så vi hoppe over den helt. Og så alt jeg gjøre neste er listen blir pekeren, som billedlig resulterer i et bilde sånn. Så det er ett scenario. 

Og den du ble spurt om spesielt er en situasjon som dette, der vi allerede har en ett-nodelisten. Og hvis jeg går tilbake i den opprinnelige problemstilling, det neste vi vil sette inn si er 34, bare for skyld diskusjonen. Så jeg kommer til å like praktisk tegne det over her. Jeg har nettopp malloced. La oss anta jeg sjekker for null. 

Nå kommer jeg til å initialisere n å være 34. Og dette vil være n. Dette vil være neste. Og dette vil være tidligere. La oss sørge for at jeg ikke gjorde det få dette bakover. Forrige kommer først i definisjonen. La meg fikse dette. Dette er forrige. Dette er neste. Selv om disse er identiske, la oss holde det konsekvent. 

Forrige. Dette er neste. Så jeg har bare malloced mitt notat, sjekket for null, tildelt 34 inn i noden. Forrige får null. Så det gir meg det. Neste blir listen. Så listen er dette. Så dette er den samme nå som å tegne denne arrow, slik at de peker til en i samme. Og så sjekker jeg om liste er ikke lik null. Og det er ikke denne gangen. Så jeg kommer til å gjøre listen forrige får pekeren. 

Så listen forrige får PTR. Så dette har effekten av å sette en grafisk pil her. Og det begynner å bli litt bølget, linjene. Og så, til slutt, kan jeg oppdatere liste for å peke på pekeren. Så nå dette peker til denne fyren. Og nå, la oss gjøre en rask tilregnelighet sjekk. 

Her er listen, som er den globale variabelen. Den første noden er faktisk 34, fordi Jeg følger at pilen. Og det er riktig fordi jeg ønsker å Sett på begynnelsen av listen alle nye noder. Hans neste felt fører meg til denne fyren. Hvis jeg fortsetter, jeg traff neste er null. Så det er ikke mer listen. Hvis jeg traff tidligere, får jeg tilbake der jeg forventer. 

Så det er fortsatt noen tips, åpenbart, for å manipulere. Men det faktum at du fikk beskjed om å gjøre dette i konstant tid betyr at du bare har et endelig antall ting du har lov til å gjøre. Og hva er det nummeret? Det kan være ett skritt. Det kan være to. Det kan være tusen trinn. Men det er begrenset, noe som betyr at du ikke kan har noen form for looping skjer her, ingen rekursjon, ingen løkker. Det er bare nødt til å være hardkodede linjer av kode som vi har i dette utvalget. 

Så neste problem 12 ba oss om å fullføre implementeringen av remove nedenfor, på en slik måte at det fjerner n fra listen i lineær tid. Så har du et litt mer slingringsmonn nå. Du kan anta at n, hvis det finnes i listen, vil være til stede ikke mer enn én gang. Og som også er ment å være en quiz-baserte forenkle antakelse, så at hvis du finner nummeret 50 et sted i listen, gjør du ikke også trenger å bekymre deg om å fortsette å iterere, på jakt etter alle mulige kopi av 50, noe som bare ville devolve inn noen småarbeidet i begrenset tid. 

Så med fjerne, var dette definitivt mer utfordrende og mer kode for å skrive. Men ved første øyekast, ærlig, det kan ser overveldende og som noe det er ingen måte du kan ha komme opp med på en quiz. Men hvis vi fokuserer på de enkelte trinn, Forhåpentligvis vil det plutselig slå deg at hver av disse individuelle trinn gjør åpenbart fornuftig i ettertid. Så la oss ta en titt. 

Så først, initial vi pekeren å være liste selv. Fordi jeg ønsker lineær tid, det betyr Jeg kommer til å ha noen sløyfe. Og en felles måte å iterere over noder i en listestruktur eller en hvilken som helst form av struktur iterativt er å ta en peker til forsiden av data struktur og så bare begynne å oppdatere det og gå din vei via datastruktur. Så jeg kommer til å gjøre akkurat det. 

Mens pekeren, min midlertidig variabel, er ikke lik null, la oss gå videre og sjekke. Fikk jeg heldig? Er det n-feltet i node Jeg er for tiden ser på lik nummer jeg leter etter? Og hvis så, la oss gjøre noe. Nå merke dette hvis tilstanden omgir hele Følgende linjer med kode. Dette er det eneste jeg bryr meg om - å finne et antall aktuelle. Så det er ingen andre, noe som forenkler ting konseptuelt litt. 

Men nå, innså jeg, og du kan ha bare innsett dette etter å ha tenkt det gjennom en bit, det er faktisk to tilfeller her. Den ene er hvor noden er på baks begynnelsen av listen, som er en litt irriterende, fordi det er en spesielt tilfelle, fordi du har å forholde med denne tingen, som er det eneste avvik. Alle andre steder i listen, det er den samme tingen. Det er en tidligere node og en neste node, forrige node, neste node. Men denne fyren er en litt spesiell hvis han er i begynnelsen. 

Så dersom pekeren er lik listen seg selv, så hvis jeg er i begynnelsen av listen, og jeg har funnet n, jeg trenger å gjøre et par ting. En, må jeg endre listen til peke til neste felt, 50. Så antar at jeg prøver å fjerne 34. Så denne fyren har å gå bort på bare et øyeblikk. 

Så jeg kommer til å si, liste blir markøren ved siden av. Vel, er denne pekeren. Neste peker over her. Så dette er i endring denne pilen til høyre nå å peke på denne fyren her. Nå, husk at vi har en midlertidig variabel. Så vi ikke har foreldreløse noen noder, fordi jeg har også denne fyren i min gjennomføring av remove. Så nå, er hvis listen selv ikke null, Jeg trenger å fikse litt noe. 

Jeg må nå sørge for at denne pilen, som er tidligere peker 50-34, har dette å gå bort, fordi hvis jeg prøver å bli kvitt av 34, 50 hadde bedre ikke opprettholde noen slags tilbake henvisning til det som pil foreslått. Så jeg bare gjorde denne linjen. Så da er jeg ferdig. Den saken er faktisk ganske enkelt. Hakking hodet av listen er relativt ukomplisert. 

Dessverre, det er dette irriterende annet blokk. Så nå må jeg vurdere saken hvor det er noe i midten. Men det er ikke så forferdelig, med unntak for syntaks som dette. Så hvis jeg ikke er i begynnelsen av liste, jeg er et sted i midten. Og denne linjen her sier, start uansett hvilken node du er på. Gå til forrige node neste felt og peker på at på pekeren. 

La oss gjøre dette billedlig. Det begynte å bli komplisert. Så hvis jeg har en tidligere felt her - la oss gjøre dette - neste felt her. Jeg kommer til å forenkle mine pekere heller enn tegne en hel haug med ting frem og tilbake på kryss og tvers hverandre. Og nå, la oss bare si at dette er en, to, 3 av hensyn til diskusjonen, selv selv om det ikke er på linje med angjeldende problem. 

Så her er min lenket liste. Jeg prøver å fjerne to i denne bestemt versjon av historien. Så jeg har oppdatert pekeren til peke mot denne fyren. Så dette er PTR. Han peker her. Dette er listen, som eksisterer globalt som før. Og han peker her uansett hva. Og nå, jeg prøver å fjerne to. 

Så hvis pilen peker her, jeg kommer til å følge, tilsynelatende, den forrige pekeren, som setter meg på en. Jeg deretter kommer til å si at neste feltet, noe som bringer meg over til dette boksen her, kommer til å lik markøren ved siden av. Så hvis denne pekeren, er dette neste. Det betyr at denne pilen behov å peke på denne fyren. 

Så hva som kodelinje har bare gjort er en liten bit av dette. Og nå, dette ser ut som en skritt i riktig retning. Vi egentlig ønsker å avklipt to ut av midt i en og tre. Derfor er det fornuftig at vi ønsker å rute denne pekeren rundt det. Så dette neste linje er å sjekke om pekeren neste er ikke null, det er faktisk noen til høyre på 2, det betyr at vi også må gjøre et lite klipp her. 

Så jeg trenger nå å følge denne pekeren og oppdatere forrige pekeren på denne fyren å gjøre en liten bit av en omgå her poenget her. Og nå, visuelt dette er fint. Det er litt rotete i at det er ingen peker på to lenger. 2 peker til venstre. Og to peker mot høyre. Men han kan gjøre hva han vil, fordi han er i ferd med å bli frigjort. Og det spiller ingen rolle hva disse verdiene er lenger. 

Det som er viktig er at de resterende gutta er ruting ovenfor og under ham nå. Og ja, det er hva vi skal gjøre videre. Vi gratis pekeren, noe som betyr at vi fortelle operativsystem, er du velkommen å gjenvinne denne. Og så til slutt, går vi tilbake. Else implisitt, hvis vi har ikke kommet tilbake ennå, vi er nødt til å holde utkikk. Så pekeren tilsvarer markøren ved bare betyr flytte denne fyren her. Flytt denne fyren her. Flytt denne fyren her hvis, faktisk, vi fant ikke nummeret vi leter etter enda. 

Så ærlig, ser det helt overveldende, tror jeg, i første øyekast, spesielt hvis du kjempet med dette i løpet av quiz deretter se noe sånt som dette. Og du klappe deg selv på ryggen. Vel, det er ingen måte jeg kunne ha komme opp med det på quiz. Men jeg vil hevde, du kan hvis du bryte det ned i disse individuelle saker og bare gå gjennom det nøye, riktignok, riktignok under stressende omstendigheter. 

Heldigvis, bilde laget alt lykkeligere. Du kan trekke dette i en rekke måter. Du trenger ikke å gjøre det crisscrossing tingen her. Du kan gjøre det med rett linjer som dette. Men hovedpunkt av dette problemet, i Generelt, var til å innse at den Bildet til slutt skal se litt noe sånt som dette, fordi konstant tid underforstått at du holder jamming og jamming og jamming nye noder i begynnelsen av listen. Eventuelle spørsmål? Sannsynligvis den mest utfordrende av sikkert koding spørsmål. 

PUBLIKUM: Så er liste som ligner på høyest i tidligere eksempler. 

DAVID J. MALAN: Akkurat, akkurat. Bare et annet navn for en global variabel. World wide hva? 

ROB BOWDEN: OK. Så dette er en hvor du måtte skrive avsnittet. Noen mennesker skrev essays for dette spørsmålet. Men du trenger bare å bruke disse seks vilkår å beskrive hva som skjer når du prøver å kontakte facebook.com. Så jeg vil bare snakke gjennom prosessen ved hjelp av alle disse begrepene. Så i nettleseren vår, vi skriver facebook.com og trykk Enter. Så leseren vår kommer til å konstruere en HTTP be om at det kommer til å sende gjennom noen prosess på Facebook for Facebook til å svare på oss med HTML sin side. 

Så hva er den prosessen som HTTP-forespørsel faktisk kommer til Facebook? Så først må vi oversette Facebook.com. Så bare gitt navnet Facebook.com, der faktisk gjør HTTP-forespørsel trenger å gå? Så vi trenger å oversette Facebook.com til en IP-adresse, som unikt identifiserer hvilken maskin vi egentlig ønsker å sende denne forespørselen til. Din bærbare har en IP-adresse. Alt som er koblet til internett har en IP-adresse. 

Så DNS, Domain Name System, er at hva som kommer til å håndtere oversettelse fra facebook.com til en IP-adresse som du faktisk ønsker å kontakte. Så vi kontakte DNS-serverne og si, hva er facebook.com? Den sier, oh, er det IP-adressen 190,212 noe, noe, noe. OK. Nå, jeg vet hva maskin Jeg ønsker å ta kontakt. 

Så da du sende HTTP-forespørsel over til den maskinen. Så hvordan få det til at maskinen? Vel, går forespørselen fra ruter til ruter retur. Husk eksemplet i klassen, der vi faktisk så den ruten som pakker tok da vi prøvde å kommunisere. Vi så det hopper over Atlanterhavet Ocean på ett punkt eller hva. 

Så det siste leddet port. Så dette er nå på datamaskinen. Du kan ha flere ting i dag kommunisere med internett. Så jeg kan være i gang, sier Skype. Jeg kan ha en nettleser åpen. Jeg kan ha noe som torren filer. Så alle disse tingene er kommuniserer med Internett på noen måte. 

Så når datamaskinen mottar noen data fra internett, hvordan det vet hvilket program faktisk ønsker dataene? Hvordan det vet om denne spesielle data er ment for torren søknad i motsetning til nettleseren? Så dette er hensikten med porter i det alle disse programmene har hevdet en port på datamaskinen. Så din nettleser sier, hey, Jeg lytter på port 1000. Og din torren programmet sier, Jeg lytter på port 3000. Og Skype sier, jeg bruker port 4000. 

Så når du får noen data som hører til en av disse programmer, data er merket med hvilken port det faktisk skal sendes med til. Så dette sier, oh, hører jeg til port 1000. Jeg vet da trenger jeg å videresende dette sammen til min nettleser. Så grunnen til det er relevant her er at webservere tendens til lytte på port 80. Så når jeg kontakter Facebook.com, er jeg kommunisere med noen maskin. Men jeg trenger å si hvilken port av at maskin jeg ønsker å kommunisere med. Og webservere pleier å være lytter på port 80. 

Hvis de ville, kunne de sette den opp slik at den lister som på port 7000. Og så i en nettleser, jeg kunne manuelt skrive Facebook.com: 7000 til sende forespørsel til port 7000 av Facebook webserver. 

DAVID J. MALAN: Og i dette tilfellet, selv selv om vi ikke kreve at folk nevner dette, i dette tilfellet, hvilken port ville forespørselen faktisk gå til? Prøv på nytt. Nettopp. Ikke ute etter det, men en subtilitet det er det ingen de siste. 

ROB BOWDEN: Så HTTPS, siden det er lytter spesielt for den kryptert, er det på port 4430. 

Målgruppe: og e-poster er 25, ikke sant? 

DAVID J. MALAN: Outbound e-post, 25, yep. 

ROB BOWDEN: Jeg vet ikke engang de fleste av det - alle de nederste pleier å være reservert for ting. Jeg tror alt under 1024 er reservert. 

PUBLIKUM: Hvorfor sa du 3 var feil nummer? 

ROB BOWDEN: Fordi i en IP-adresse, det er fire grupperinger av sifre. Og de er fra 0 til 255.. Så 192.168.2.1 er en vanlig lokale IP-adressen for nettverket. Legg merke til alle de som er mindre enn 255. Så når jeg begynte med 300, som kunne umulig ha vært ett av numrene. 

DAVID J. MALAN: Men det dumme klipp fra - var det CSI, hvor de hadde en tall som var for stor for IP-adressen. 

ROB BOWDEN: Eventuelle spørsmål om dette? Den neste, slik at fullstendig endring i tema, men vi har denne PHP array for husene i quad. Og vi har en ikke-sorterte liste. Og vi ønsker å skrive ut hvert listepunkt bare inneholder huset navn. Så vi har en foreach loop. Så husk, syntaksen er foreach matrise som element i matrisen. Så gjennom hver iterasjon av sløyfen, Huset kommer til å ta på en av de verdier inne i matrisen. 

På den første iterasjon, hus vil være Cabot House. På en andre iterasjon, huset vil være Courier hus og så videre. Så for hver quad som huset, er vi bare kommer til å skrive ut - du også kunne ha gjentatt - listeelementet, og deretter huset navn og deretter lukke listeelementet. Klammeparentes er valgfritt her. 

Og da vi sa også i spørsmålet seg selv, husk å lukke sorterte liste tag. Så må vi gå ut PHP-modus for å gjøre dette. Eller vi kunne ha gjentatt den lukke sorterte liste tag. 

DAVID J. MALAN: Også fint her ville har vært å bruke en gammel skole for sløyfe med en $ i = 0 0 og bruker teller til regne ut lengden av strålen. Helt greit også, bare litt wordier. 

PUBLIKUM: Så hvis du skulle [Uhørbart], ville du gjøre - Jeg glemmer hva loopen [uhørbart] er. Vil du $ quad brakett jeg? 

DAVID J. MALAN: Nettopp. Ja, akkurat. 

ROB BOWDEN: Noe annet? 

DAVID J. MALAN: Greit. Avveininger. Så var det bunter av svar mulig for hver av disse. Vi var egentlig bare ute etter noe overbevisende for en oppside og en ulempe. Og nummer 16 spurte, validere brukere ' innspill klientsiden, som med Javascript, i stedet for server-side, som med PHP. Så hva er en oppside på gjør klientsiden? 

Vel, er en av de tingene vi foreslo at du reduserer ventetid, fordi du trenger ikke å bry kontakte server, noe som kan ta noen millisekunder eller enda et par sekunder ved å unngå det og bare validere brukernes innspill på klientsiden ved utløser en on-sender handler og bare sjekke, fikk de skriver noe for navn? Visste de skriver noe i for e-postadresse? Visste de velger en dorm fra rullegardinmenyen? 

Du kan gi dem umiddelbar tilbakemelding bruker gigahertz datamaskin eller hva de har som er faktisk på sitt skrivebord. Så det er bare en bedre brukeropplevelse oppleve typisk. Men en Ulempen med å gjøre klientsiden validering, hvis du gjør det uten også gjøre server-side validering er at mest alle som kommer ut av CS50 vet at du kan bare sende alle data du vil til en server som en rekke måter. Oppriktig, i de fleste hvilken som helst nettleser, kan du Klikk rundt i innstillingene og bare slå av Javascript, noe som ville, derfor deaktivere noen form for validering. 

Men du også kanskje husker at selv jeg gjorde noen uforståelige ting i klassen ved hjelp telnet og faktisk late som være en nettleser ved å sende get forespørsler til en server. Og det er absolutt ikke bruker noen Script. Det er bare meg å skrive kommandoer på et tastatur. Så egentlig, enhver programmerer innenfor nok komfort med nettet og HTTP kunne sende uansett data han eller hun ønsker til en server uten validering. Og hvis serveren ikke er også sjekker, gjorde de gi meg et navn, er dette faktisk en gyldig e-postadresse, gjorde de velger en sovesal, kan du ende opp å sette inn falske eller bare blank data inn i databasen, noe som trolig ikke kommer til å være en god ting hvis du var forutsatt at det var der. 

Så dette er en irriterende virkelighet. Men generelt, klient-side validering er stor. Men det betyr dobbelt så mye arbeid. Selv om det ikke eksisterer ulike biblioteker, Javascript-biblioteker for eksempel, som gjør dette mye, mye mindre av en hodepine. Og du kan bruke noen av koden server-side, klientsiden. Men innser at det er typisk merarbeid. Yeah. 

PUBLIKUM: Så hvis vi bare sa mindre sikker - 

DAVID J. MALAN: [ler] Ugh. De er alltid vanskeligere seg til å avgjøre. 

ROB BOWDEN: Det ville har blitt akseptert. 

DAVID J. MALAN: Hva? 

ROB BOWDEN: Jeg skapte dette problemet. Det ville ha blitt akseptert. 

DAVID J. MALAN: Yeah. 

PUBLIKUM: Cool. 

ROB BOWDEN: Men vi ikke akseptere for den første - vel, hva vi var ute etter er noe som du ikke trenger å kommunisere med serveren. Vi aksepterte ikke bare raskere. 

PUBLIKUM: Hva om ikke laste siden? 

ROB BOWDEN: Ja. Det var en akseptert svar. 

DAVID J. MALAN: alt hvor vi følte det var mer sannsynlig enn ikke sannsynlig at du visste hva du var si, som er en hard linje for å trekke noen ganger. Ved hjelp av en lenket liste i stedet i en matrise for å opprettholde en sortert liste av heltall. Så en oppside vi ofte sitere med koblede lister som motiverte deres hele Innføringen var du får dynamikk. De kan vokse. De kan krympe. Så du trenger ikke å hoppe gjennom ringer å faktisk skape mer minne med en matrise. Eller du trenger ikke å bare si, beklager, bruker. Matrisen er fylt. Så dynamisk vekst av listen. En ulempe skjønt av lenkede lister? 

PUBLIKUM: Det er lineær. Søke på lenket liste er lineær i stedet for det du logge inn 

DAVID J. MALAN: Nettopp. Søke på en lenket liste er lineær, selv om det er i orden, fordi du kan bare følg disse brødsmuler, disse pekere, fra starten av listen til enden. Du kan ikke utnytte random access og, dermed, binære søk, selv om det er sorteres, at du kunne gjøre med en matrise. Og det er også en annen kostnad. Yeah. 

PUBLIKUM: Minne ineffektiv? 

DAVID J. MALAN: Yeah. Vel, det ville jeg ikke nødvendigvis si ineffektiv. Men det koster deg mer minne, fordi du trenger 32 bits for hver node for den ekstra pekeren, på minste for en enkeltvis lenket liste. Nå, hvis du bare lagrer heltall og du legger pekeren, er at faktisk slags ikke-triviell. Det er en dobling av mengden minne. Men i virkeligheten, hvis du lagrer en lenket liste av structs som kan ha 8 byte, 16 bytes, enda mer enn det, kanskje det er mindre av en marginal kostnad. Men det er en kostnad likevel. Så noen av disse ville har vært fint som ulempene. 

18. Ved hjelp av PHP i stedet for C for å skrive et kommandolinjeprogrammet. Så her er det ofte raskere å bruke en språk som PHP eller Ruby eller Python. Du bare raskt åpne opp en tekst editor. Du har mange flere funksjoner tilgjengelig for deg. PHP har kjøkkenvasken av funksjoner, mens i C, du har veldig, veldig lite. Faktisk, gutta kjenner den harde måten at du ikke har hash tabeller. Du trenger ikke ha koblet lister. Hvis du vil ha dem, må du implementere dem selv. 

Så en oppside på PHP eller egentlig noen tolket språk er hurtighet som du kan skrive kode. Men en ulempe, så vi dette når jeg raskt pisket opp en misspeller implementering i foredrag ved hjelp av PHP, er at det å bruke et tolket språk vanligvis går tregere. Og vi så at beviselig med en økning i tid fra 0,3 sekunder til 3 sekund, på grunn av tolkningen som faktisk skjer. 

En annen opp var at du trenger ikke å kompilere. Så det også raskere utvikling forresten, fordi dere ikke har to trinn til å kjøre et program. Du har bare ett. Og så det er ganske overbevisende også. Ved hjelp av en SQL database i stedet for en CSV-fil til å lagre data. Så SQL database brukes for pset7. CSV-filer du ikke bruker mye. Men du brukte det indirekte i pset7 som vel ved å snakke med Yahoo Finance. 

Men CSV er akkurat som en Excel-fil, men super enkelt, hvor kolonnene er bare demarked med komma inne av en ellers tekstfil. Og ved hjelp av en SQL-database er en litt mer overbevisende. Det er en oppside, fordi du får ting som velge og sette inn og slette. Og du får, formodentlig, indekser som MySQL og andre databaser, som Oracle, bygge for deg i minne, som betyr at velger er trolig ikke kommer til å være lineær topp til bunn. Det er faktisk kommer til å være noe som binære søk eller noe lignende i ånden. Så de er generelt raskere. 

Men en ulempe er at det er bare mer arbeid. Det er mer innsats. Du må forstå databaser. Du må sette det opp. Du trenger en server for å kjøre at databasen på. Du må forstå hvordan du konfigurerer den. Så dette er bare disse typer avveininger. Mens en CSV-fil, kan du lage den med gedit. Og du er flink til å gå. Det er ingen kompleksitet utover det. 

Ved hjelp av en trie i stedet for en hash table med separat kjeding til å lagre en ordbok over ord som minner av pset5. Så en prøver oppside, i teorien minst, er hva? Konstant tid, i hvert fall hvis du er hashing på hver av de enkelte bokstavene i et ord, som deg kan ha for pset5. Det kan være fem hashes, seks hashes om det er fem eller seks bokstavene i ordet. Og det er ganske bra. Og hvis det er en øvre grense for hvor lenge dine ord kan være, er at faktisk asymptotisk konstant tid. 

Mens en hash tabell med separat chaining, problemet der med at type datastruktur er at ytelsen til algoritmer som regel avhenger av flere ting allerede i datastrukturen. Og det er definitivt tilfellet med kjeder, der flere ting du putter inn i en nøkkeltabell, jo lengre disse kjeder gå, noe som betyr at i verste tilfelle, er det ting du kan være ute etter er helt ved enden av en av disse kjeder, som effektivt tilfaller til noe lineær. 

Nå, i praksis, kan det helt være slik at en nøkkeltabell med kjedene er raskere enn en tilsvar trie gjennomføring. Men det er ulike årsaker, blant som prøver å bruke en hel masse minne som kan, faktisk, langsomme ting ned, fordi du ikke får fin fordelene av noe som kalles caching, hvor ting som er nær hverandre i minnet kan nås ofte raskere. Og noen ganger kan du komme opp med en virkelig god hash-funksjon. Selv om du må kaste bort en bit av minne, kan du faktisk være i stand til å finne ting fort og ikke like ille som lineært. 

Så kort sagt, det var ikke nødvendigvis med en hvilken som helst av disse en eller to spesifikke ting vi var ute etter. Virkelig noe overbevisende som en oppside og nedside generelt fanget vår øyet. 

ROB BOWDEN: Så for oppsiden, vi gjorde ikke akseptere på sin egen "raskere." Du hadde å si noe om det. Selv om du sa teoretisk raskere, Vi visste at du slags forstått at det er 0 av 1. Og hash table, i teorien, er ikke 0 på en. Nevne noe om runtime generelt fikk du poeng. Men "raskere", de fleste av løsningene på den store bord som ble forsøk var objektivt tregere enn løsninger som var hash tabeller. Så raskere i seg selv er egentlig ikke sant. 

DAVID J. MALAN: Dom de dom dom. Jeg er trolig den eneste som innser det er sånn som er ment å skal uttales, ikke sant? 

ROB BOWDEN: Jeg hadde faktisk ingen anelse. 

DAVID J. MALAN: Det gjorde følelse i hodet mitt. 

ROB BOWDEN: Jeg gjør dette. OK. Så dette er en hvor du måtte trekke diagrammet ligner du kanskje har sett på tidligere eksamener. Så la oss bare se på dette. Så fra HTML node, har vi to barn, hodet og kroppen. Så vi gren - hode og kropp. Hodet har en tittel tag. Så vi har en tittel. 

Nå er det én ting mange mennesker glemte er at disse tekstnoder er elementer innenfor dette treet. Så her er vi tilfeldigvis trekke dem som ovaler å skille dem fra disse typer noder. Men legg merke til også her har vi toppen, midten, og nederst vil ende opp med å bli tekstnoder. Så glemmer de som var noe av en vanlig feil. 

Kroppen har tre barn - disse tre divs. Så div, div, div og deretter teksten node barn av disse divs. Det er ganske mye det for at spørsmålene. 

DAVID J. MALAN: Og det er verdt å merke seg, selv om vi ikke dvele ved disse detaljer i den tiden vi bruker på Javascript, at rekkefølgen gjør, i Faktisk, uansett teknisk. Så hvis hodet kommer før kroppen i HTML, så det skal vises til igjen av kroppen i selve DOM. At hans er, generelt, bare så dere vet det, noe som kalles dokumentorden der det spiller ingen rolle. Og hvis du var å implementere en parser, et program som leser HTML i bygningen opp treet i minnet, for å være ærlig, det er intuitivt nok det du gjøre uansett - topp til bunn, venstre til høyre. 

ROB BOWDEN: Spørsmål om det? Bør jeg gjøre det neste? 

DAVID J. MALAN: Sure. 

ROB BOWDEN: OK. Så dette er buffer overkjørt angrep spørsmål. Det viktigste å gjenkjenne her er, vel, hvordan kan en motstander triks dette programmet til å utføre vilkårlig kode? Så argv1, den første kommandolinjen argumentet til dette programmet, kan det være vilkårlig lang. Men her vi bruker memcpy å kopiere argv1, som her er bar. Vi passerer det som argument. Og så det er å ta på navnet bar. 

Så vi memcpying bar inn i denne bufferen c. Hvor mange byte er vi kopierer? Vel men mange bytes bar skjer med skal bruke, lengden på det argumentet. Men c er bare 12 bytes bred. Så hvis vi skriver en kommandolinje argument som er lengre enn 12 byte, er vi kommer til å renne over dette Spesielt buffer. Nå, hvordan kan en motstander lure programmere inn utføring vilkårlig kode? 

Så husk at her Hoved kaller foo. Og så da hoved samtaler foo. La oss trekke dette. Så vi har vår stabelen. Og hoved har en stabel ramme på bunnen. På et tidspunkt, hoved samtaler foo. Vel, umiddelbart, hoved samtaler foo. Og så foo får sin egen stack ramme. 

Nå, på et tidspunkt, foo kommer til å gå tilbake. Og gikk foo avkastning, må vi vite på hva kodelinje innsiden av hoved vi var for å vite hvor vi bør fortsette i hoved. Vi kan kalle foo fra en hel haug med forskjellige steder. Hvordan vet vi hvor du skal gå tilbake? Vel, vi trenger å lagre det et sted. 

Så et sted rett rundt her, vi lagrer hvor vi bør gå tilbake til en gang foo avkastning. Og dette er returadressen. Så hvordan en motstander kan dra nytte på dette er det faktum at denne bufferen c er lagret, la oss si, her er c.. Så vi har fått 12 byte for c.. Dette er ca. Og dette er foo stack ring. Så hvis den ondsinnede brukeren angir mer byte enn 12 eller de inn i en kommando Argumentet som er lengre enn 12 tegn, så vi kommer til å renne over denne bufferen. 

Vi kan holde det gående. Og på et tidspunkt, går vi langt nok at vi begynner skrive denne returadresse. Så når vi overskrive returadresse, Dette betyr at når foo avkastning, er vi tilbake til der den ondsinnet bruker er å fortelle det til etter uansett verdi det inn, etter hva tegn brukeren angitt. Og så hvis den ondsinnede brukeren blir spesielt flink, kan han ha denne tilbake til et sted i printDef funksjon eller et sted i malloc funksjon, bare noe vilkårlig. 

Men enda mer smart er hva om han har brukeren tilbake til akkurat her. Og så begynner du å utføre disse som linjer med kode. Så på det punktet, kan brukeren angi hva han vil i denne regionen. Og han har full kontroll over programmet. Spørsmål om det? Så det neste spørsmålet er fullført reimplementation av foo på en slik måte at det ikke lenger er sårbart. 

Så det er et par måter du kunne ha gjort dette. Vi har fortsatt c bare å være av lengde 12. Du kunne ha endret dette som en del av løsningen. Vi har også lagt til en sjekk for å gjøre at linjen ikke var null. Selv om du ikke trenger som for full kreditt. Så vi sjekker først hyssinglengde på bar. Hvis den er større enn 12, så ikke faktisk gjøre kopien. Så det er en måte å fikse det. 

En annen måte å feste det istedenfor ha c bare være av lengde 12, har det være av lengde strlen (bar). En annen måte å feste den er å faktisk bare tilbake. Så hvis du nettopp hadde blitt kvitt alle dette, hvis du nettopp hadde slettet alt linjer med kode, ville du ha fått full kreditt, siden denne funksjonen den trenger ikke å utrette noe. Det kopiere kommandolinjen argument i noen array i sin lokale stack ramme. Og så ting er på vei tilbake. Og uansett hva det dyktig er borte. Så tilbake var også en tilstrekkelig måte å få full kreditt. 

DAVID J. MALAN: Ikke helt ånd spørsmålet, men akseptabelt per den spec likevel. 

ROB BOWDEN: Spørsmål om noe av det? Den ene tingen som du minst nødvendig å ha kompilere kode. Så selv om teknisk du er ikke sårbare hvis koden ikke kompilere, gjorde vi ikke akseptere det. Ingen spørsmål? OK. 

DAVID J. MALAN: Vil du ha å si denne tittelen? 

ROB BOWDEN: Nei. 

DAVID J. MALAN: Så i denne, dette var enten gode nyheter eller dårlige nyheter. Dette er bokstavelig talt det samme problemet som den første quiz. Og det er nesten det samme problem som pset1. Men det var bevisst forenklet å være en enklere pyramide, en som kan bli løses med en litt enklere iterasjon. Og egentlig, hva vi får til her ikke var så mye logikken, fordi sannsynligvis, etter dette punkt, er du mer komfortable enn du var i uke én med for sløyfer eller hvorfor løkker, men virkelig å erte hverandre at du er litt komfortabel med forestillingen om at PHP er ikke bare om hva programmering. Det kan faktisk brukes som et språk å skrive kommandolinjeprogrammer. 

Og ja, det er det vi prøver å trekke oppmerksomheten din til. Dette er en kommandolinje PHP program. Så C-kode her, mens korrekt i C, ikke korrigere for PHP. Men koden virkelig er den samme. Hvis du sammenligner løsninger for Quiz 0 mot Quiz 1, vil du finne at det er nesten identiske, bortsett noen dollartegn og for Fravær av en datatype. Spesielt hvis vi tar en titt her, vil du se at vi reagere, i dette fall fra en opp gjennom syv. 

Vi kunne ha gjort det 0-indeksen. Men noen ganger, jeg tror det er bare mentalt lettere å tenke på ting 1-7. Hvis du vil ha en blokk, og deretter to blokker, og deretter tre, deretter prikk, prikk, prikk syv. Vi har j blir initialisert til en og deretter telling på opp til i. Og alt her er på annen måte identiske. Men verdt å merke er et par ting. Vi gir deg disse to linjene, denne første en, goofily navngitt som en shebang for skarpe smell. Og det bare angir banen, den mappen, der et program som kan være funnet ut at du vil bruke å tolke denne filen. 

Og deretter linjen etter det, av Selvfølgelig betyr inn PHP-modus. Og linjen helt nederst betyr exit PHP-modus. Og dette fungerer, generelt, med tolket språk. Det er litt irriterende hvis du skriver en programmet i en fil som heter foo.php. Og så brukerne må bare husk, OK, for å kjøre dette programmet, jeg nødt til å skrive "php plass foo.php." Kind av irriterende hvis ingenting annet. Og det avslører også at programmet er skrevet i PHP, som ikke er alt som opplysende for brukeren. 

Så du kan fjerne den. Php helt husker fra forelesning. Og du kan faktisk gjøre. / Foo hvis du har oppgitt korrekte rettigheter det ved å gjøre det kjørbar. Så chmod a + x foo ville ha gjort det. Og hvis du også legge til shebang her. Men egentlig, problemet var å komme på skrive ut noe sånt som dette. Ingen HTML, ingen C-kode sikkert, bare litt PHP. Så Milo deretter tilbake i problemet 25. Og i 25, ble du gitt følgende skjelett-kode, som var en ganske enkel web-side. Og saftig del HTML-messig var ned her, hvor vi har inne i kroppen en form som har en unik ID av innganger innsiden av som var to innganger, en med en idé om navn, en med en idé om knappen. 

Den første var å skrive inn tekst, den andre av type sender. Og så vi ga deg, faktisk, mer ingredienser enn du trengte, bare så dere hadde alternativer som å løse dette problemet. Du trenger strengt tatt ikke trenger alle disse ID-ene. Men det tillater deg å løse det på forskjellige måter. Og opp på toppen, legge merke til at målet var å utløse et vindu som dette - Hei, Milo! - å dukke opp i nettleseren ved hjelp super enkelt, hvis ikke stygg, varslingsfunksjonen. Og så, til slutt, koker dette ned konseptuelt å liksom lytter etter innleveringer av skjemaet klientsiden , Ikke på serversiden, liksom reagerer på at innlevering av gripe den verdien som brukeren har skrevet på navnefeltet, og deretter vise det i kroppen av et varsel. 

Så en måte du kan gjøre dette på er med jQuery, som ser litt syntaktisk forvirrende i starten. Du kan gjøre dette med ren DOM kode - document.getelement etter ID. Men la oss ta en titt på denne versjonen. Jeg har et par viktige linjer først. Så ett, har vi denne linjen, som er identisk med hva du kanskje har sett i, tror jeg, form2.html fra klassen i uke ni. Og dette er bare å si, utføre følgende kode når dokumentet er klar. Dette blir viktig bare fordi HTML-sider leses ovenfra og bunn, venstre til høyre. 

Og derfor, hvis du prøver å gjøre noe i kode her oppe til noen DOM element, noen HTML-kode, som er ned her, du gjør det for tidlig, fordi dette har ikke engang blitt lest inn i minnet. Så ved å si dette document.ready linjen, vi sier, her er noen kode, browser. Men ikke utføre dette før hele Dokumentet er klar, er at DOM tre finnes i minnet. Dette er en litt mer grei, hvis syntaktisk en litt annerledes, hvor jeg sier, grip HTML-elementet hvis unike identifikator er innganger. Det er det hash tag betegner den unike ID. Og da jeg ringer. Sende. 

Så. Sende inn her er en funksjon, ellers kjent som en metode, er at innsiden av objektet på venstre hånd siden er det at jeg ikke markere. Så hvis du tenker på innganger som et objekt i minnet - og faktisk er det. Det er en node i et tre - . Sende hjelp når dette skjemaet med denne ID er sendt inn, utføre følgende kode. Jeg bryr meg ikke om hva navnet på den Funksjonen er jeg utfører. Så her jeg bruker, som før, hva er kalt lambda funksjon eller en anonym funksjon. Det er ikke i det hele tatt intellektuelt interessant annet enn det har ikke noe navn, som er greit hvis du er bare noen gang kommer til å kalle det en gang. Og inni der jeg faktisk håndtere innsending av skjemaet. Jeg først erklære en variabel kalt verdi. Og hva er da effekten av dette uthevet del her nå? Hva gjør det på en høyt nivå for meg? 

PUBLIKUM: Det blir verdien som brukeren ikke i HTML-koden nedenfor. Det blir som ID og deretter finner verdien av den. 

DAVID J. MALAN: Nettopp. Det griper node, hvis unike identifikator er navnet. Det blir verdien i dette, noe som er, formodentlig, hva brukeren skrev ham eller henne selv. Og så den lagrer det i variabel kalt verdi. Som en side, kan du også gjort dette litt annerledes. Helt akseptabelt ved å gjøre noe løgn Var verdi får document.getElementById. Og dette er grunnen til at det er litt kjedelig å ikke bruke jQuery. "Navn". Verdi. Så helt akseptabelt. Ulike måter å gjøre dette. jQuery bare har en tendens til å være litt mer konsis og definitivt mer populært blant programmerere. 

Nå, jeg gjør litt av en mental helse sjekk, fordi i problemet utsagn vi eksplisitt sa, hvis brukeren har ennå ikke skrevet hans eller hennes navn, viser ikke en varsler. Men du kan se etter det, bare ved å sjekker for den tomme strengen for en quote-unquote hvis det er ingenting faktisk det. Men hvis det ikke er lik quote-unquote, Jeg vil ringe varsler. Og det interessante her er at vi bruker pluss operatør, som gjør hva i Javascript? Sette sammen. Så det er som Phps dot operatør. Samme idé, litt annen syntaks. Og jeg bare lage strengen som du så på skjermbildet - Hei, så og så. 

Og så den siste detalj er dette. Hvorfor jeg return false inne av denne anonym funksjon? 

PUBLIKUM: Det er ingen verdi. Du setter den i formen. Den sier bare, hvis verdi er ikke lik blank, så gjør det. Det var en blank i at innlevering. 

DAVID J. MALAN: OK. Forsiktig om. Det er ingen andre her. Og at return false er utenfor av hvis forholdene. Så dette markerte linjen, return false, utfører uansett hva når skjemaet er sendt. Hva retur falsk innsiden av denne hendelseshåndterer, som det heter, hendelsen i spørsmålet være innlevering? 

PUBLIKUM: Fordi det bare skjer én gang. 

DAVID J. MALAN: Kun skjer én gang. Ikke helt. Yeah? 

PUBLIKUM: Det forhindrer form fra innsending til standard oppførsel, noe som ville gjøre det siden reload. 

DAVID J. MALAN: Nettopp. Så jeg overbelastning begrepet sende inn her, fordi jeg sier, er den formen blir sendt inn. Men som du foreslår, det er faktisk ikke blitt sendt i den sanne HTTP måte. Når du klikker Send, på grunn av vår onsubmit handler, vi avskjær at innsending av skjemaet så å si. Vi deretter gjøre våre ting med Javascript-kode. Men jeg er bevisst retur falsk, fordi det jeg ikke vil skje en brøkdels sekund senere er for hele skjemaet seg til å bli sendt til nettet server med sentrale verdi-par ved å endre URL til å være noe sånt q = katter eller hva vi gjorde, for eksempel i klassen. Jeg ønsker ikke at det skal skje, fordi det er ingen server lytting for denne danne innsending. Det er utelukkende gjort i Javascript-kode. Og det er derfor jeg ikke engang har en handling attributt på formen min, fordi jeg har tenkt ikke for at dette skal noen gang gå til serveren. 

Så det blir sendt inn. Men vi avskjære at skjema innlevering og hindre standard oppførsel, noe som er å faktisk gå hele veien til serveren. 

PUBLIKUM: Så å holde det på klientsiden. 

DAVID J. MALAN: Keeping det klientsiden. Helt riktig. Neste opp var min oh MySQL. 

ROB BOWDEN: OK. Så dette første spørsmålet var generelt grov for folk. Selv om de senere meldinger gikk bedre. Så du måtte velge den riktige data typer for begge disse kolonnene. Og begge disse har noen ting om dem som gjøre valget vanskelig. Så int var ikke en gyldig skriver for nummer. Årsaken til at en 12-sifret konto nummer, er ikke stor nok til en int lagre totalt sifre. Så et gyldig valg ville ha vært en stor int hvis du vet det. Et annet valg kan ha vært en røye felt av lengde 12. Så noen av disse ville ha fungert. Int. ville ikke. 

Nå, balanse, tenker tilbake til pset7. Så vi spesielt brukt desimal til lagre verdien av aksjer eller - 

DAVID J. MALAN: Cash. 

ROB BOWDEN: Cash. Vi brukte desimal å lagre mengden kontanter som brukeren har i dag. Så grunnen til at vi gjør det er fordi, husk, flyter. Det er flyttall i presisjon. Det kan ikke presist lagre kontanter verdier som vi ønsker her. Så desimal er i stand til nettopp butikken noe å, si, to desimaler. Det er derfor balansen, vi vil ha det å være desimal og ikke flyte. 

DAVID J. MALAN: Og også, også, selv om det kan ha vært flink i andre sammenhenger å tenke, kanskje dette er en sjanse for en int. Jeg vil bare holde styr på ting i pennies. Fordi vi eksplisitt viste standard Verdien av å være 100,00, som betyr at det kan bare være en int. Og en annen finesse også med tall var at det ikke var ment å være et lurespørsmål. Men husker at en int i MySQL, som i C, i det minste i apparatet, er 32-bit. Og selv om vi ikke forventer at du skal vet nøyaktig hvor mange sifre som middel, husker at det største antallet du kan representere potensielt med et 32-biters tall er omtrent hva? 

Hvilket nummer skal vi alltid si? 2 til 32, som er det lag? Du trenger ikke å vite nøyaktig. Men er omtrent nyttig i livet. Det er omtrent 4 milliarder. Så vi har sagt at et par ganger. Jeg vet jeg har sagt det et par ganger. Og det er omtrent 4 milliarder. Og det er en god regel Tommelfinger å vite. Hvis du har 8 bits, 256 er det magiske tallet. Hvis du har 32 bits, 4 milliarder gi eller ta. Så hvis du bare skrive ned 4 milliarder kroner, vil du se at det er færre sifre enn 12, noe som betyr at det er helt klart ikke nok uttrykksfullhet å fange en 12-sifret kontonummer. 

ROB BOWDEN: OK. Så de andre som gikk bedre. Så antar at banken pålegger en $ 20 månedlig vedlikehold avgift på alle kontoer. Med hva SQL-spørring kunne banken trekke $ 20 fra hver teller, selv om det resulterer i noen negative saldoer? Så i utgangspunktet er det fire hovedtyper av spørsmål - sette inn, velge, oppdatere og slette. Så hva gjør vi tror vi er kommer til å bruke her? Oppdater. 

Så la oss ta en titt. Så her er vi oppdaterer. Hva bordet er vi oppdaterer kontoene? Så oppdaterer kontoene. Og da syntaksen sier, hva i regnskapet er vi oppdaterer? Vel, vi sette balanse lik Nåverdien av balanse minus 20. Så dette vil oppdatere alle rader kontoer, subtrahere $ 20 fra balansen. 

DAVID J. MALAN: En vanlig feil her, selv om vi noen ganger tilga det, var å faktisk ha PHP-kode her ringer spørringen funksjonen eller sette anførselstegn rundt alt som ikke trenger å være der. 

ROB BOWDEN: Husk at MySQL er et eget språk fra PHP. Vi måtte skrive MySQL i PHP. Og PHP er da å sende det over til MySQL server. Men du trenger ikke PHP for å kommunisere med en MySQL server. 

DAVID J. MALAN: Nettopp. Så ingen variabler med dollartegn skal i denne sammenheng. Det kan bare gjøre alt regnestykket innenfor selve databasen. 

ROB BOWDEN: OK. Så den neste. Er dette den neste? Yeah. Så med hva SQL-spørring kunne banken hente kontonumrene til dens rikeste kundene, de med balanserer større enn 1000? Så hvilke av de fire hovedtyper skal vi ønsker her? Velg. Så vi ønsker å velge. Hva ønsker vi å velge? Hva kolonnen vi ønsker å velge? Vi vil spesielt ønske for å velge nummer. Men hvis du sa stjerner, vi også akseptert det. 

Så velger du nummeret fra hva tabellen? Kontoer. Og da tilstanden vi ønsker? Der hvor balansen er større enn 1,000. Vi har også akseptert større enn eller lik. Siste. Med hva SQL-spørring kunne banken tett, dvs. slette hver konto som har en balanse på $ 0? Så hvilken av de fire vi kommer til å ønske å bruke? Slett. Så syntaksen for det? Slett fra hva tabellen? Kontoer. Og da tilstanden som vi ønsker å slette - hvor balanse er lik null. Så slette alle rader fra kontoer der balansen er null. Spørsmål om noen av disse? Lyst til å stå i kø? 

DAVID J. MALAN: Kø guide. Så i denne, ga vi deg en noe kjent struktur som vi utforsket en bit i klasse sammen av structs, som var en data struktur relatert i ånden. Forskjellen dog med en kø er at vi måtte liksom huske hvem var på forsiden av kø i stor del, slik at vi kunne gjøre mer effektiv bruk av minnet, minst hvis vi bruker en matrise. 

Fordi tilbakekalling, hvis vi har en matrise, hvis, for eksempel, er dette den foran køen, hvis jeg kommer inn i køen her, og deretter noen får i kø bak meg, bak meg, bak meg, og en person går ut av linjen, du kunne, som vi så noen av vår menneskelige frivillige i klassen, har alle skifte denne måten. Men generelt, har alle gjøre noe er ikke den beste bruken av tid i et program, fordi det betyr at algoritmen kjører i hva asymptotisk kjøretid? Det er lineær. 

Og jeg føler at det er litt dumt. Dersom den neste person i linje er neste person som er ment å gå inn i butikken, har de ikke alle har til å bevege seg sammen. Bare la vedkommende bli plukket ut når den tid kommer, for eksempel. Så vi kan spare litt tid der. Og så for å gjøre det selv, det betyr at leder på køen, eller foran i køen skal gradvis bevege seg dypere og dypere inn i en array og til slutt kanskje faktisk vikle rundt hvis vi bruker en array til å lagre folket i denne kø. Så du kan nesten tenke på matrise som en sirkulær data struktur i den forstand. 

Så du liksom har å holde styr på størrelsen på det eller virkelig slutten av det og hvor begynnelsen av det er. Så vi foreslår at du erklærer en slik kø, kall det q, bare én bokstav. Da foreslår vi at fronten være initialisert til null og at størrelsen initialiseres til null. 

Så akkurat nå, er det ingenting innsiden av det køen. Og vi ber deg om å fullføre gjennomføring av enqueue nedenfor i en slik måte at funksjonen legger n i slutten av q, og deretter returnerer sant. Men hvis q er full eller negativ, Funksjonen skal i stedet return false. Og vi ga deg et par forutsetninger. Men de er egentlig ikke funksjonelt relevant, finnes bare som bool, fordi, teknisk sett, ikke bool eksisterer i C med mindre du inkluderer en viss header-fil. Så det var bare å sørge for at det ble ingen er dette et triks Spørsmålet type ting. 

Så enqueue, vi foreslo i utvalget løsninger for å gjennomføre på følgende måte. One, må vi først sjekke den enkle, de lavthengende frukt. Dersom køen er full, eller det antall som du prøver å sette inn er mindre enn null, som vi sa i spesifikasjon av problemet bør ikke være tillatt, fordi vi bare vil ikke-negative verdier, så bør du bare return false umiddelbart. Så noen relativt lett feilkontroll. Dersom om du ønsker å legge til at faktiske nummer, måtte du gjøre litt av tenker her. Og det er her det er litt irriterende mentalt, fordi du må finne ut hvordan de skal håndtere wraparound. 

Men kimen til ideen her som er av interesse for oss er at wraparound ofte innebærer modulær aritmetikk og mod operatør, den prosentvise side, hvor du kan gå fra en større verdi tilbake til null, og deretter en og to, og tre, og deretter tilbake rundt null, en og to og tre, og så videre igjen og igjen. Så måten vi foreslår å gjøre dette er at vi ønsker å indeksere inn i matrise kalt tall der våre heltall ligge. Men for å komme dit, vi først ønsker å gjøre uansett størrelsen av køen er, men deretter legge til at uansett foran på listen er. Og effekten av det er å sette oss på den riktige posisjon i køen og ikke anta at den første personen i kø er i begynnelsen, noe som han eller hun absolutt kunne være hvis vi ble også skiftende alle. Men vi er bare å skape arbeid for oss selv om vi tok den aktuelle banen. 

Så vi kan holde det relativt enkelt. Vi må huske at vi bare lagt en int i køen. Og da har vi bare returnere true. I mellomtiden, i dequeue, vi spurte du gjøre følgende. Implementere den på en slik måte at den dequeues, som er fjerner og avkastning, int foran i køen. For å fjerne int, er det nok å glemme det. Du trenger ikke å overstyre sin bit. Så det er fortsatt faktisk det. Akkurat som data på en harddisk, vi bare ignorerer det faktum at det er nå der. Og hvis q er tom, bør vi i stedet returnere negativ en. Så dette føles vilkårlig. Hvorfor gå tilbake negative 1 i stedet for falsk? Yeah. 

PUBLIKUM: Q er lagring positive verdier. Siden du bare lagre positive verdier i q, er negativ en feil. 

DAVID J. MALAN: OK, sant. Så fordi vi bare lagrer positive verdier eller null, så det er greit å returnere en negativ verdi som en sentinel verdi, et spesielt symbol. Men du omskriving historie der, fordi årsaken til at vi er bare retur ikke-negative verdier er fordi vi ønsker å har en sentinel verdi. Så mer spesifikt, hvorfor ikke bare tilbake falsk i tilfeller med feil? Yeah. 

PUBLIKUM: Du har sviktet å returnere et heltall. 

DAVID J. MALAN: Nettopp. Og det er her C blir ganske begrensende. Hvis du sier at du kommer å returnere en int, har du å returnere en int. Du kan ikke få fancy og begynne retur en bool eller en flåte eller en streng eller noe sånt. Nå, i mellomtiden, Javascript og PHP og noen andre språk kan faktisk har du retur annerledes typer verdier. Og det kan faktisk være nyttig, der du kan returnere positive Ints, nuller, negative ints, eller usann eller null selv å betegne feil. Men vi har ikke det allsidighet i C. 

Så med dequeue, hva vi foreslår å gjøre er - 

ROB BOWDEN: Du kan returnere false. Det er bare den falske er hasj definere falsk null. Så hvis du return false, du returnerer null. Og null er en gyldig ting i vår kø, mens negative 1 er ikke dersom falsk skjedde til å være negativ en. Men du bør ikke engang trenger å vite det. 

DAVID J. MALAN: Det er hvorfor jeg ikke si det. 

ROB BOWDEN: Men det var ikke sant at du ikke kan returnere false. 

DAVID J. MALAN: Sure. Så dequeue, merker vi aksepterer ugyldig som sin argument. Og det er fordi vi ikke er passerer noe i. Vi ønsker bare å fjerne elementet foran i køen. Så hvordan kan vi gå om du gjør dette? Vel, først, la oss gjøre dette rask tilregnelighet sjekk. Hvis køen størrelse er 0, er det noe arbeid som må gjøres. Returnere negativ en. Ferdig. Så det er noen få linjer av mitt program. Så bare fire linjer forbli. 

Så her jeg velger å minske størrelse. Og minskning av størrelsen effektivt betyr at jeg glemmer noe er der inne. Men jeg må også oppdatere der forsiden av tallene er. Så for å gjøre det, trenger jeg å gjøre to ting. Trenger jeg først å huske hva nummeret er på forsiden av køen, fordi jeg trenger å returnere den tingen. Så jeg ønsker ikke å tilfeldigvis glemmer om det og deretter overskrive den. Jeg bare kommer til å huske i en int. 

Og nå, jeg ønsker å oppdatere q.front å bli q.front en. Så hvis dette var den første personen i linje, nå, ønsker jeg å gjøre pluss en til peke på den neste person i linje. Men jeg må håndtere at wraparound. Og hvis kapasiteten er en global konstant, som kommer til å tillate meg å sørge for at som jeg peker på den aller siste personen i linje, vil modul-handling bringe me tilbake til null ved foran i køen. Og som håndterer wraparound her. Og så fortsetter jeg å gå tilbake n. 

Nå, strengt tatt, det gjorde jeg ikke nødt til å erklære n. Jeg trengte ikke å ta tak i det og lagre det midlertidig, fordi verdien ligger det fortsatt. Så jeg kunne bare gjøre det rette aritmetikk å returnere tidligere leder av køen. Men jeg følte bare at dette var mer klar å faktisk ta tak i int, legg den i n, og deretter tilbake som for klarhet skyld, men ikke strengt nødvendig. Psst. De er alle pronounceable i hodet mitt. 

ROB BOWDEN: Så første spørsmål er den binært tre problem. Så første spørsmål er, vi er gitt disse tallene. Og vi ønsker å liksom sette dem inn disse nodene slik at det er en gyldig binært søketre. Så en ting å huske om binære søketrær er at det ikke er bare at den tingen til venstre er mindre og det å høyre er større. Det må være at hele treet til til venstre er mindre, og hele treet til høyre er større. 

Så hvis jeg legger 34 her på toppen, og deretter Jeg satt 20 her, så det er gyldig så langt, fordi her 34 opp. 20 går mot venstre. Så det er mindre. Men jeg kan da ikke sette 59 her, fordi selv om 59 er på høyre side av 20, det er fortsatt til venstre på 34.. Så med denne begrensningen i tankene, enkleste måten sannsynligvis løse dette Problemet er å bare sortere av disse tallene - slik at 20, 34, 36, 52, 59, 106.. Og så setter de fra venstre til høyre. 

Så 20 går her. 34 går her. 36 går her. 52, 59, 106.. Og du også kunne ha funnet ut med noen plugge inn og realisere, oh, vent, jeg har ikke nok tall å fylle dette inn over her. Så jeg trenger å reshift hva min rute notat kommer til å være. Men legge merke til at i den endelige tre, hvis du leser fra venstre til høyre, er det i stigende rekkefølge. 

Så nå ønsker vi å erklære hva struct kommer til å være for noder i dette treet. Så hva trenger vi i et binært tre? Så vi har en verdi av typen int, så noen int verdi. Jeg vet ikke hva vi kalte det i oppløsningen - int n. Vi trenger en peker til venstre barn og en peker til høyre for barnet. Så det kommer til å se slik ut. Og det vil faktisk se før når ble det dobbelt-linked liste ting, så varsel - Jeg er nødt til å bla alle vei ned igjen til problemet 11. 

Så merker det ser identisk med denne, bortsett fra at vi bare måtte ringe disse forskjellige navn. Vi har fortsatt et heltall verdi og to pekere. Det er bare det at i stedet for å behandle pekere som peker til neste ting og den forrige ting, vi behandler pekere til å peke på et venstre barn og høyre barn. OK. Så det er vårt struct node. Og nå, den eneste funksjon vi trenger å implementere til dette er traversen, hvilken vi ønsker å gå over treet, trykking ut verdiene av de tre i rekkefølge. 

Så ser her, ville vi ønsker å skrive ut med 20, 34, 36, 52, 59, og 106. Hvordan kan vi oppnå det? Så det er ganske lik. Hvis du så i det siste eksamen problemet at du ønsket å skrive ut hele treet med komma i mellom alt, var det faktisk enda enklere enn det. Så her er løsningen. Dette var betydelig enklere hvis du gjorde det rekursivt. Jeg vet ikke om noen forsøkte å gjøre det iterativt. 

Men først må vi vår base case. Hva om roten er null? Så vi bare kommer til å gå tilbake. Vi ønsker ikke å skrive noe. Else vi kommer til å traversere rekursivt ned. Skriv ut hele venstre subtre. Så ut alt mindre enn min nåværende verdi. Og så kommer jeg til å skrive meg selv. Og så kommer jeg til å recurse ned min hele høyre subtre, så alt større enn min verdi. Og dette kommer til å skrive ut ut alt i orden. Spørsmål om hvordan dette faktisk oppnår det? 

PUBLIKUM: Jeg har et spørsmål på [uhørbart]. 

ROB BOWDEN: Så en måte å tilnærme noen rekursive problemet er å bare tenke om det som du må tenke om alle hjørne tilfeller. Så tenk på at vi ønsker å skrive ut hele dette treet. Så alt vi kommer til å fokusere på er dette bestemt node - 36. De rekursive samtaler, vi later de bare fungere. Så her, dette rekursive kall til travers, vi uten å tenke om det, bare krysser venstre tre, forestille seg at allerede skriver ut 20 og 34 for oss. Og så når vi til slutt rekursivt kaller traversen på rett, vil det riktig ut 52, 59 og 106 for oss. 

Så gitt at dette kan skrive ut 20, 34, og den andre kan skrive ut 52, 59, 108, alt vi trenger for å være i stand til å gjøre er å skrive ut oss selv i midten av det. Så skrive ut alt før oss. Skriv ut oss selv, slik at den aktuelle noden print 36, vanlig printf, og deretter skrive ut alt etter oss. 

DAVID J. MALAN: Dette er hvor rekursjon blir virkelig vakker. Det er denne fantastiske porsjon tro hvor du gjør den minste bit av arbeid. Og så la noen andre gjøre resten. Og at noen andre er, ironisk nok, du. Så for alvorlige brownie poeng, hvis du blar opp på spørsmålene - 

ROB BOWDEN: På spørsmål? 

DAVID J. MALAN: Og ned litt til tallene, er det noen som vet hvor disse tallene kommer fra? 

ROB BOWDEN: Jeg har bokstavelig talt ingen anelse om. 

DAVID J. MALAN: De vises hele quizen. 

PUBLIKUM: Er de de samme tallene? 

DAVID J. MALAN: Disse tallene. Et lite påskeegg. Så for de av dere ser på nettet på hjemme, hvis du kan fortelle oss via e-post til heads@CS50.net hvilken betydning av disse tilbakevendende seks tallene er hele Quiz 1, vil vi dusje deg med fantastisk oppmerksomhet på finale foredrag og en stress ball. Nice, subtil. 

ROB Bowden: Noen siste spørsmål om noe på quiz?