>> DAVID J. MALAN: Okay.
Så velkommen til den første nogensinde CS50 obduktion for en quiz.
Vi troede, vi ville indvie denne tradition i år.
Og det vil være en mulighed at gå gennem
løsninger til quizzen.
Og vi vil fremskynde eller sinke baseret på renter af dem her.
>> Så er du sikkert her, fordi du er interesseret i, hvordan du kunne have eller
burde have besvaret nogle af disse problemer.
Så hvorfor gør vi ikke tage et kig på dette afsnit først?
Så få strenge.
Dette gav dig tre forskellige versioner af et program, der var, i sidste ende,
beregnet til at få en snor fra en bruger.
Hvorvidt det gjorde det var overladt til dig at afgøre.
>> Og vi spurgte i spørgsmål 0, antage, at version 1 er
kompileret og henrettet.
Hvorfor kunne det program segfault?
Ved første øjekast, nogen forslag på, hvorfor?
Ja.
>> PUBLIKUM: Så jeg kan huske at se dette i en tidligere eksempel at se på
char * s og se scanningen af ​​s og se, fordi det er en pegepind, hvordan
påvirkede det, hvad du har scannet ind?
Er det s eller adressen på s?
>> DAVID J. MALAN: OK.
Godt.
Så i sidste ende, kilden til ethvert problem formentlig kommer til at reducere
denne variabel s.
Og det er faktisk en variabel.
Datatypen for denne variabel er char *, hvilket betyder, at det kommer til at
indeholde adressen på en karakter.
Og deri ligger indsigt.
Det kommer til at indeholde adressen på en karakter eller, mere generelt,
adressen på det første tegn i en hel blok af karakterer.
>> Men fangsten er, at scanning s, formål i liv, er givet en adresse og givet
et format kode, som% s, læse en snor i de luns af
hukommelsen på denne adresse.
Men fordi der er ingen lighedstegn før at semikolon den første
linje kode, fordi vi faktisk ikke tildele nogen hukommelse med
malloc, fordi det faktisk ikke tildele et array af nogle størrelse, alle
du laver læser brugerens tastatur input til nogle komplet
skrald værdi, hvilket er i s som standard.
Så oddsene er du vil segfault hvis at adressen ikke bare så ske
at være en værdi, som du kan, i virkeligheden, så skriv til.
Så slemt ikke at tildele din hukommelse der.
>> Så i spørgsmål 1, spurgte vi, antage, at version 2 er
kompileret og henrettet.
Hvorfor kan dette program segfault?
Så denne ene er mindre buggy.
Og der er virkelig kun én indlysende måde, hvor du kan
udløse en segfault her.
Og det er tematisk.
Enhver tid vi bruger c i hukommelsen, hvad kan du gøre for at fremkalde en segfault
med version 2?
>> PUBLIKUM: Hvis du bruger dette input i en streng, der er længere end 49
tegn.
>> DAVID J. MALAN: Præcis.
Hver gang du ser noget fast længde når det kommer til et array, din
radar skal gå væk fra at dette kunne være problematisk, hvis du ikke kontrollere
grænser for et array.
Og det er problemet her.
Vi bruger stadig scanf.
Vi bruger stadig% s, hvilket betyder, prøve at læse en streng fra brugeren.
Det kommer til at blive læst ind i s, der, på dette punkt, er effektivt
adressen på en luns af hukommelse eller det er tilsvarende.
Det er navnet på et array karakterer hukommelse.
>> Men præcis det, hvis du læser en streng der er længere end 49 tegn, 49
fordi du har brug for plads til backslash 0, du kommer til at løbe over
denne buffer.
Og du kan få heldige og være i stand til skrive en 51st karakter, 52., 53..
Men på et tidspunkt, OS vil sige, no.
Dette er absolut ikke hukommelse du får lov til at røre ved.
Og programmet kommer til at segfault.
>> Så der bør heuristik være gang du har fået fast længde, du har
at sikre, at du tjekker længden af, hvad det er du prøver
at læse i det.
>> PUBLIKUM: Så for at løse det, kan du have haft en erklæring tjekker faktisk
er længden større eller mindre end?
>> DAVID J. MALAN: Helt sikkert.
Du skal bare have en tilstand der siger, at hvis -
eller rettere behøver du ikke nødvendigvis kender på forhånd, hvor mange tegn på
brugeren kommer til at skrive, fordi du har hønen og ægget.
Ikke før du har læst det med scanf kan du regne ud, hvor lang tid det er.
Men på dette punkt, er det for sent, fordi du allerede har læst det i
nogle blok af hukommelse.
Så som en sidebemærkning de CS50 bibliotekets undgår dette spørgsmål helt, tilbagekaldelse
ved hjælp fgetc.
Og det lyder ét tegn ad gangen, tip-toeing sammen, vel vidende, at du
kan ikke løbe en karakter, hvis læse en ad gangen.
>> Fangsten er med getString tilbagekaldelse er at vi er nødt til konstant at re-size
at bid af hukommelse, som er bare en smerte.
Det er en masse linjer kode til at gøre det.
Så en anden fremgangsmåde ville være at faktisk bruger en fætter, så
til at tale, af scanf.
Der er varianter af en masse af disse funktioner, der faktisk tjekke
Længden af ​​hvor mange tegn kan du læse maksimalt.
Og du kunne specificere, ikke læse mere end 50 tegn.
Så det ville være en anden tilgang, men mindre imødekommende af større input.
>> Så spørgsmål 2 spørger, formoder, at versionen 3 er kompileret og henrettet.
Hvorfor kunne det program segfault?
Så denne ene er faktisk det samme answer, selvom det
ser lidt avanceret.
Vi bruger malloc, som føles som vi giver os selv flere muligheder.
Og så er vi frigør at hukommelse i slutningen.
Det er stadig kun 50 bytes hukommelse.
Så vi kan stadig forsøge at læse i 51, 52, 1000 byte.
Det kommer til at segfault for nøjagtig den samme grund.
>> Men der er en anden grund også.
Hvad andet kunne allokere afkast udover adressen på en luns af hukommelse?
Det kunne returnere null.
Og fordi vi ikke tjekker for det, kan vi gøre noget
dum anden grund, nemlig at vi kan fortælle scanf, læse
brugerens input fra tastaturet i 0 placering, AKA null.
Og det samme vil helt sikkert udløse en segfault.
Så for quizzen formål, vi ville har accepteret en af ​​disse som en
gyldig grund.
Den ene er identiske.
Den ene er lidt mere nuanceret.
>> Endelig med hensyn til programmets brug af hukommelse, hvordan gør version 2 og
version 3 forskellige?
Så for hvad det er værd, så vi en tilsyneladende endeløs forsyning af mulige
svar på dette.
Og blandt folks svar, hvad vi var håber på, men vi har accepteret andre
ting, var nogle omtale af kendsgerning, at version 2 bruger
den såkaldte stak.
Version 3 bruger bunke.
Og funktionelt, det ikke rigtig gøre alle, at meget af en forskel.
I slutningen af ​​dagen, er vi stadig bare at få 50 bytes hukommelse.
>> Men det var et af de mulige svar at vi ledte på.
Men du vil se, som du får dine quizzer tilbage fra TFS, at vi gjorde
acceptere andre diskussioner af deres forskellige anvendelser af hukommelse samt.
Men stable og bunke ville have været en let løsning til at gå med.
Eventuelle spørgsmål?
Jeg giver dig Rob.
>> ROB BOWDEN: So problem 4..
Dette er den ene, hvor du var nødt til at fylde i antallet af bytes ud af alle
disse forskellige typer anvendes.
Så første ting, vi ser.
Antag en 32-bit arkitektur, som denne CS50 apparatet.
Så en af ​​de grundlæggende ting om 32-bit arkitekturer, der fortæller os
præcis hvor stor en pointer går at være i arkitekturen.
>> Så det samme, vi ved, at enhver pointer type er 32-bit eller 4 byte.
Så se på dette bord, en node * er en pointer type.
Det kommer til at være 4 bytes.
Struct node *, det er bogstaveligt talt identisk med node stjerne.
Og så kommer til at være 4 bytes.
String, så det ikke ligner en pointer endnu, men typedef, en
streng er bare en char *, som er en pointer type.
Så det kommer til at være 4 bytes.
>> Så disse tre er alle 4 byte.
Nu node og elev er en smule mere kompliceret.
Så ser på node og elev, ser vi node et heltal og en pointer.
Og studerende er to pointere inde i den.
Så i det mindste for vores sag her, den måde at vi ender beregning af størrelsen af
denne struct er blot tilføje op alt der er inde i struct.
>> Så for node, har vi et heltal, hvilket er 4 byte.
Vi har en pegepind, hvilket er 4 byte.
Og så en knude går at tage op 8 byte.
Og tilsvarende for studerende, vi har en pointer, der er 4 bytes og en anden
pointer, der er 4 byte.
Så det kommer til at ende at blive 8 byte.
Så node og elev er 8 byte.
Og disse tre er alle 4 byte.
Spørgsmål om det?
Ja.
>> PUBLIKUM: Er det var en 64-bit arkitektur, der ville
fordoble dem alle?
>> ROB BOWDEN: Det ville ikke fordoble dem alle.
Så 64-bit arkitektur, er det, igen, ændringer, som grundlæggende ting, at en
pointer er nu 64 bits.
Ja.
Så en pointer er 8 byte.
Så disse, der var 4 byte vil være 8 byte.
En studerende, som var to pegepinde, Nå, nu det kommer til at
være 8 byte, 8 byte.
Det kommer til at gøre 16 bytes.
>> Men en node er stadig 4 byte.
Så denne pointeren går at være 8 byte.
Det er 4 byte.
Så en node er kun vil at være 12 byte.
Alle andre spørgsmål om at den ene?
Så den næste, er disse HTTP statuskoder.
Og du skulle beskrive forhold hvorunder disse kan
blive returneret til dig.
et problem, som jeg hørte nogle studerende er, at de forsøgte at gøre
fejl være på kundens ende.
Så når vi forsøger at gøre anmodningen til serveren, går noget
forkert på vores ende.
Men generelt er disse koder er bliver returneret af serveren.
Så vi ønsker at finde ud af, hvad der foregår forkert eller højre på den server,
forårsager disse ting, der skal returneres.
Så hvorfor kan en server returnerer status kode 200?
Nogen tanker?
>> Ja.
Så noget om held anmodningen gik igennem.
Og de er i stand til at vende tilbage uanset hvad du bad om.
Så alt var fint.
Hvad med 302 findes?
Ja.
>> PUBLIKUM: Serveren ledte for hvad du har bedt om.
Men det kunne ikke finde den.
Så der er en fejl.
>> ROB BOWDEN: Så serveren var udkig efter, hvad du ville.
Så bare at kigge her, 302 fundet, det var i stand til at finde det.
>> PUBLIKUM: Undskyld.
Fundet betyder, at de fandt det.
Undskyld.
>> ROB BOWDEN: So 302 fundet.
Serveren er i stand til at finde hvad du ville.
>> PUBLIKUM: Men det er ikke vise det?
>> ROB BOWDEN: Forskellen mellem dette 302 og 200 er, at den
ved, hvad du ønsker.
Men det er ikke præcis, hvor du ville spørge.
Så 302 er en typisk omdirigering.
Så du har anmodet om en side.
Den kender, åh, jeg vil at returnere dig dette.
Men det er på en anden URL.
Så hey, du rent faktisk ønsker dette.
>> DAVID J. MALAN: Det er et stykke, der sagde at vi gav jer en omdirigering
funktion, der anvendes header funktion , som til gengæld, udskrives placering,
colon og derefter webadresse, du vil afvise brugeren.
Selvom du ikke se 302 udtrykkeligt der, det er, hvad PHP
ville magisk Indsæt så header sige præcis, hvad Rob sagde, at der -
fundet.
Men gå her i stedet.
>> ROB BOWDEN: OK.
Så hvad med 403 forbudt?
>> PUBLIKUM: Jeg tror, ​​det er, at serveren er dybest set siger, at klienten
kan ikke få adgang til hjemmesiden.
>> ROB BOWDEN: Så ja.
Tja, det typiske svar, vi var forventer er noget lignende, de filer,
ikke chmodded korrekt.
Det er sandsynligvis under hvilke omstændigheder du så dem.
Men der er en grund til, at kunden kunne være skyld her.
Der er faktisk en anden status kode -
401.
Så disse er meget ens.
>> 401 er uautoriseret.
Og 403 er forbudt.
Og så uautoriseret du udelukkende få, hvis du ikke er logget ind
Men logger ind kan betyde at du har tilladelse.
Men hvis du allerede er logget ind, og du stadig ikke har tilladelse, så
du kan også få forbudt.
Så hvis du er logget ind og ikke har tilladelse, forbudt, er også
noget, du kan få.
>> DAVID J. MALAN: Og den mekanisme, disse problemer er som regel
løst på serveren er via hvilken kommando?
Chmod hvis det er faktisk en tilladelser udsteder på filen eller mappen.
>> ROB BOWDEN: Så 404 ikke fundet.
Ja.
Så i modsætning til 302, hvor det var ikke ligefrem hvor du spørger, men det ved, hvad
du ønsker, dette, det bare har ingen idé om, hvad du ønsker.
Og er du ikke anmoder om noget gyldigt.
418 Jeg er en tekande og derefter 500 intern server.
Så hvorfor kan du få det?
>> Så segfault -
Jeg ved faktisk ikke, den klassificering standard for denne.
Men hvis din PHP kode havde noget forkert i det, i teorien kunne
faktisk segfault, i hvilket tilfælde denne 500 intern serverfejl, noget
der er galt med din server konfiguration.
Eller der er en syntaksfejl i din PHP kode.
Eller noget slemt, der foregår.
>> DAVID J. MALAN: Vi kunne se segfault blandt nogle få folks svar.
Og teknisk, det kunne ske.
Men det ville være en PHP programmet er skrevet af andre mennesker, faktisk
segfaulted, som, hvis disse mennesker skruet op og skrev buggy kode i
deres tolk ville PHP selv segfault.
Så selv om 500 er som en segfault i ånden, det er næsten altid den
resultat af en konfigurationsfil emne med din webserver, eller som Rob sagde,
en syntaksfejl, ligesom du ikke lukke et tilbud.
Eller du har mistet et semikolon et sted.
>> PUBLIKUM: Så for Shuttle PSET, jeg tror da jeg gjorde det, når jeg klikkede på
browser, men intet kom op, hvad de kaldte hvide side.
Men det var på grund af koden.
Jeg tror, ​​det var JavaScript, right?
>> ROB BOWDEN: Ja.
>> PUBLIKUM: Gid fejl stadig komme op?
>> ROB BOWDEN: Så du ville ikke have fået denne fejl, fordi alt
fra webserveren perspektiv var helt fint.
Men du har anmodet index.html.
Du har anmodet om shuttle.js og service.js.
Og det var i stand til at vende tilbage til jer alle disse ting -
200.
OK.
Det er kun, når din browser forsøger at fortolke JavaScript-kode,
Det er ligesom, vent, det er ikke gyldigt JavaScript-fejl.
Andre spørgsmål?
Ok.
>> DAVID J. MALAN: Så næste op var nummer 11.
Og 11 var den mest skræmmende for en masse mennesker.
Så det vigtigste ting at bemærke her var, at dette var, ja, om
en dobbelt linket liste.
Men det var ikke det samme som sidste år dobbelt linkede liste problem,
som ikke giver dig det forbehold, at listen kunne i virkeligheden være usorteret.
>> Så det faktum, at listen var usorteret og det faktum, at dette ord var
understregede der var ment til at formidle at dette faktisk er en forenkling
af, hvad der ellers ville have været et mere udfordrende problem
og en længere.
Så en almindelig fejl her var at have sat sidste års løsning på dit ene
pager og så bare blindt kopiere denne ned som svar, som er den rigtige
svar på et andet spørgsmål samme ånd.
Men de finesser her var som følger.
>> Så man har vi erklæret en node og defineret i den sædvanlige måde her.
Så vi definerede liste over være en global pointer initialiseret til null.
Så tilsyneladende er der to funktioner vi har prototyper til her, indsætte
og fjerne.
Og så har vi nogle eksempler på kode her for at gøre en flok indrykninger.
Og så beder vi dig om at udfylde den gennemførelse af indsatsen under sådan
måde, at den indsætter n på listen i konstant tid, også understreget,
selv om der allerede er til stede.
>> Så skønheden i at være i stand til at indsætte i konstant tid, er, at det indebærer
at du er nødt til at indsætte det nye knudepunkt, hvor?
I den forreste.
Så det eliminerer heldigvis mindst en af ​​de sager, der bruges til at kræve
endnu flere linjer kode, ligesom det gjorde sidste år, og selv i klassen, når vi
talte gennem denne slags ting med mennesker og med nogle
verbal pseudokode.
Så i løsningen her, lad os springe over til at bare at have en visuel på
skærmen.
>> Bemærk, at vi gør følgende.
Og også bemærke den anden forenkling var, at selv om det er
allerede er til stede, så det betyder, at selvom nummeret er der allerede, kan du
bare blindt indsætte et andet kopi af den.
Og det blev også beregnet til at være en forenkling, så du kunne
fokusere på, virkelig, nogle af de mere intellektuelt interessant del og
ikke bare nogle ekstra fejlkontrol betragtning af den begrænsede tid.
>> Så i denne prøveopløsning, vi tildeler en markør på den venstre
side her til et knudepunkt.
Nu indser, at pointer, som Rob sagt, er kun 32 bits.
Og det gør ikke rent faktisk indeholder en adresse, indtil du
tildele den adressen.
Og vi gør det på højre hånd side via malloc.
Ligesom en god borger, kontrollerer vi, at malloc er ikke i virkeligheden, null, således at
vi ikke ved et uheld skaber en segfault her.
Og hver gang du bruger malloc i livet, du bør være kontrol for null, lest
du har en subtil fejl.
>> Så initialisere vi, at nul ved tildele n og tidligere og næste år.
Og i dette tilfælde her, jeg initialiseret tidligere til null, fordi denne nye
node kommer til at være den nye begyndelsen af ​​min liste.
Så der vil være intet før det.
Og jeg vil i det væsentlige føje eksisterende liste til den nye node ved
indstilling næste lige at liste sig selv.
Men jeg er ikke færdig endnu.
Så hvis selve listen allerede eksisterede, og der var mindst én node
allerede på plads, hvis det er den liste her, og jeg indsætte en ny node her, jeg
nødt til at sørge for, at min tidligere node peger bagud til min nye node,
fordi dette er, igen, en dobbelt linket liste.
>> Så vi gør en sanity check.
Hvis listen ikke er nul, hvis der er allerede én eller flere noder der, så
tilføje, at tilbage henvisning så at sige.
Og så den allersidste ting, vi har brug at gøre er faktisk opdatere den globale
variabel liste sig til at pege til denne nye knudepunkt.
Ja.
>> PUBLIKUM: I Markørpilen [Uhørligt] er lig med nul, betyder at
beskæftige sig med på listen, fordi listen er nul?
>> DAVID J. MALAN: Nope.
Det er simpelthen mig bliver proaktivt forsigtig i at såfremt denne er min
oprindelige liste med måske nogle flere knuder herovre og jeg indsætte min
ny node herovre, er der vil at være noget herovre.
Og jeg ønsker at fange denne idé ved at forud for
null på den nye node.
Og formentlig, hvis min kode er korrekt og der er ingen anden måde at indsætte
andre end denne funktion knudepunkter formentlig, selv om listen allerede
én eller flere noder i den, formentlig liste, det første knudepunkt, vil have en
foregående pointer null selv.
>> PUBLIKUM: Og lige en opfølgning.
Grunden til at du sætter markøren næste ligemænd Listen er du gør markøren
før liste, idet det peger til den næste, jeg gætte -
Jeg lad være -
bare lister?
>> DAVID J. MALAN: Præcis.
Og så lad os faktisk overveje to sager virkelig her, selvom
For vi vil overveje dem er ikke helt det samme som koden.
Men på et højt niveau, hvis denne udgør listen og dette er et 32-bit
markøren, simpleste scenario er at dette er nul som standard.
Og formoder jeg ønsker at indsætte nummer 50 var det første nummer.
Så jeg har tænkt mig at gå videre og tildele en knude, som kommer til at indeholde
tre områder -
n, forrige, og næste år.
>> Jeg har tænkt mig at sætte tallet 50 her, da dette vil være n..
Dette vil være næste.
Og det vil være tidligere.
Og så hvad skal jeg gøre i denne sag?
Tja, jeg har lige gjort linie 1 her.
Pointer n bliver n.
Jeg så at sige, tidligere bør få null.
Så dette vil være nul.
Så jeg har tænkt mig at sige næste kommer til at få listen.
>> Og det virker bare godt ud.
Det er nul.
Og så jeg siger, den nye node næste område bør få, hvad det er.
Så der sætter en anden nul der.
Og så den sidste ting Jeg gøre er at tjekke her.
Hvis listen ikke er lig med nul, men det er lig med nul, så vi springer at
helt.
Og så alt jeg gøre næste er listen får pointer, som billedligt resulterer i
et billede som dette.
Så det er et scenario.
>> Og den, du spurgte om specifikt er en situation som denne,
hvor vi allerede har en en-node listen.
Og hvis jeg går tilbage op i den oprindelige problemformulering, det næste vi vil
Indsæt sige er 34, bare for skyld diskussion.
Så jeg har tænkt mig at bare bekvemt trække det herovre.
Jeg har netop malloced.
Lad os antage jeg tjekker for null.
>> Nu, jeg har tænkt mig at initialisere n være 34..
Og det vil være n..
Dette vil være næste.
Og det vil være tidligere.
Lad os sørge for jeg ikke gjorde få dette baglæns.
Forrige kommer først i definitionen.
Lad mig ordne det.
Det er tidligere.
Dette er næste.
Selvom disse er ens, lad os holde det konsekvent.
>> Forrige.
Dette er næste.
Så jeg har bare malloced min note, kontrolleret for null, tildelt 34 i noden.
Forrige bliver nul.
Så det giver mig det.
Næste får listen.
Så listen er dette.
Så dette er det samme nu som at tegne dette pil, således at de peger på en
i det samme.
Og så er jeg kontrollere, hvis liste er ikke lig med nul.
Og det er ikke denne gang.
Så jeg har tænkt mig at gøre listen tidligere får pointer.
>> Så Forrige får PTR.
Så det har den virkning at sætte en grafisk pil her.
Og der er ved at blive lidt bølget, linjerne.
Og så, endelig, jeg opdatere liste til at pege på pointer.
Så nu dette peger på denne fyr.
Og nu, lad os gøre en hurtig tilregnelighed check.
>> Her er den liste, som er den globale variabel.
Det første knudepunkt er faktisk 34, fordi Jeg følger denne pil.
Og det er korrekt, fordi jeg ønsker at indsætte i begyndelsen af ​​listen
alle nye noder.
Hans næste felt fører mig til denne fyr.
Hvis jeg holde ud, jeg ramte næste er nul.
Så der er ikke mere på listen.
Hvis jeg ramte tidligere, får jeg tilbage, hvor jeg forventer.
>> Så der er stadig et par pointers, naturligvis at manipulere.
Men det faktum, at du fik at vide at gøre dette i konstant tid betyder, at du kun
har en begrænset række ting du lov til at gøre.
Og hvad er det nummer?
Det kunne være et skridt.
Det kan være to.
Det kunne være 1.000 trin.
Men det er begrænset, hvilket betyder, at du ikke kan have nogen form for looping foregår
her nogen rekursion ingen sløjfer.
Det er bare nødt til at være hårdt kodede linjer kode som vi har i denne prøve.
>> Så det næste problem 12 bedt os om at afslutte gennemførelsen af ​​remove
under en sådan måde, at det fjerner n fra listen i lineær tid.
Så du har en lidt mere vrikke værelse nu.
Du kan antage, at n, hvis nuværende på listen, vil være til stede
ikke mere end én gang.
Og det er også ment som en quiz-baserede forenklende antagelse, så
at hvis du finder det nummer 50 et eller andet sted på listen, behøver du ikke også
at bekymre sig om fortsat at gentage, på udkig efter alle mulige
kopi af 50, der bare ville uddelegere ind i nogle minutia i begrænset tid.
>> Så med remove, dette var absolut mere udfordrende og mere
kode til at skrive.
Men ved første øjekast, helt ærligt, det kan ser overvældende og som noget
der er ingen måde du kunne have komme med på en quiz.
Men hvis vi fokuserer på de enkelte trin, Forhåbentlig vil det pludselig
strejke dig, at hver af disse individuelle skridt en åbenbar mening
i bakspejlet.
Så lad os tage et kig.
>> Så det første, vi initialisere pointer at være liste selv.
Fordi jeg vil lineær tid, at midler Jeg har tænkt mig at have nogle loop.
Og en fælles måde at gentage over den knudepunkter i en liste struktur eller nogen form
struktur iterativt er at tage en pointer til den forreste del af data
struktur og så bare begynde at opdatere det og gå din vej
gennem datastruktur.
Så jeg har tænkt mig at gøre netop dette.
>> Mens pointer, min midlertidig variabel, er ikke lig med nul, lad os
gå videre og kontrollere.
Fik jeg heldig?
Er n felt i knude Jeg er i øjeblikket ser på lig med
nummer jeg leder efter?
Og hvis ja, lad os gøre noget.
Nu bemærke dette hvis betingelse omgiver hele
følgende linjer kode.
Det er det eneste, jeg bekymrer sig om - finde en pågældende nummer.
Så der er ingen andre steder, hvilket forenkler tingene begrebsmæssigt en lille smule.
>> Men nu, indså jeg, og du har måske kun realiseres dette efter at have tænkt
det gennem en bit, der er faktisk to sager her.
Er, hvor knuden er i toppen af ​​listen, der er en
lidt irriterende, fordi det er en særtilfælde, fordi du er nødt til at beskæftige sig
med denne ting, som er den eneste anomali.
Alle andre steder på listen, det er det samme.
Der er en tidligere node og en næste node forudgående knudepunkt, næste knudepunkt.
Men denne fyr er en lidt speciel hvis han er i begyndelsen.
>> Så hvis markøren svarer til listen selv, så hvis jeg er i begyndelsen af
listen, og jeg har fundet n, jeg har brug for til at gøre et par ting.
En, jeg nødt til at ændre listen til peger på det næste felt 50.
Så formoder, at jeg forsøger at fjerne 34.
Så denne fyr kom til at gå væk i bare et øjeblik.
>> Så jeg har tænkt mig at sige, liste bliver pointer næste.
Nå, det er pointer.
Næste peger herovre.
Så dette er ved at ændre denne pil til højre nu til at pege på denne fyr her.
Husk nu, at vi har en midlertidig variabel.
Så har vi ikke forældreløse nogen noder, fordi jeg har også denne fyr i min
implementering af fjerne.
Så nu, hvis listen i sig selv ikke er nul, Jeg skal lave en lille ting.
>> Jeg har brug for nu sørge for, at denne pil, som tidligere peger
50-34, har dette at gå væk, fordi hvis jeg forsøger at slippe
34, 50 havde bedre ikke opretholde nogen slags tilbage henvisning til det som
pil foreslået.
Så jeg gjorde bare denne linje.
Så jeg er færdig.
Denne sag er faktisk temmelig nemt.
Hugge hovedet af listen er relativt ligetil.
>> Desværre er der denne irriterende ellers blok.
Så nu er jeg nødt til at overveje sagen hvor der er noget i midten.
Men det er ikke alt for forfærdeligt, undtagen for syntaks som dette.
Så hvis jeg ikke er i begyndelsen af ​​det liste, jeg er et sted i midten.
Og denne linje her siger, start- uanset på hvilket node du er på.
Gå til forudgående knudepunkt næste felt og fremhæver dette ved markøren.
>> Lad os gøre det billedligt.
Det var ved at blive kompliceret.
Så hvis jeg har en tidligere marker her - lad os gøre det - næste områder her.
Jeg har tænkt mig at forenkle mine pejlemærker snarere end tegne en hel masse
tingene frem og tilbage på kryds og tværs hinanden.
Og nu, lad os bare sige, det er 1, 2, 3 af hensyn til diskussion, selv
selv om der ikke line op med det pågældende problem.
>> Så her er min linkede liste.
Jeg forsøger at fjerne to i dette bestemt version af historien.
Så jeg har opdateret pointer til pege på denne fyr.
Så dette er PTR.
Han peger her.
Dette er listen, der findes globalt som før.
Og han peger her uanset hvad.
Og nu, jeg prøver at fjerne to.
>> Så hvis pointer peger her, er jeg kommer til at følge, tilsyneladende den
tidligere pointer, der sætter mig ved 1.
Jeg derefter vil sige, at den næste område, hvilket bringer mig over til denne
ramme, vil lige pointer næste.
Så hvis dette pointer, det er næste.
Det betyder, at denne pil behov at pege på denne fyr.
>> Så hvad der linje kode har netop gjort, er en lille smule af dette.
Og nu, dette er at ligne en skridt i den rigtige retning.
Vi hovedsagelig ønsker at klippe 2 ud i midten af ​​1 og 3.
Så det giver mening, at vi ønsker at rute denne pointer omkring det.
Så denne næste linje er at kontrollere, hvis pointer næste ikke er nul, er der
faktisk en til højre for 2 det betyder at vi også nødt til at gøre
lidt snip her.
>> Så jeg nu nødt til at følge denne pointer og ajourføring af den tidligere markøren på
denne fyr til at gøre en lille smule af en omgå her pointen her.
Og nu, visuelt er det rart.
Det er lidt rodet i, at der er ingen peger på 2 længere.
2 peger til venstre.
Og 2 peger til højre.
Men han kan gøre, hvad han vil, fordi han er ved at blive befriet.
Og det er ligegyldigt, hvad disse værdier er længere.
>> Hvad der er vigtigt er, at de resterende fyre routing over
og under ham nu.
Og ja, det er hvad vi skal gøre næste.
Vi fri pointer, hvilket betyder, at vi fortæller operativsystem, er du velkommen
at kræve dette.
Og så endelig, vi vender tilbage.
Else implicit, hvis vi er ikke vendt tilbage endnu,
vi har fået til at holde udkig.
Så pointer lig pointer næste bare betyder flytte denne fyr her.
Flyt denne fyr her.
Flyt denne fyr her, hvis i virkeligheden, vi ikke finde nummeret
vi leder efter endnu.
>> Så ærligt, det ser helt overvældende, tror jeg, i første omgang
blik, især hvis du kæmpede med dette i løbet af quizzen så se
noget som dette.
Og du klappe dig selv på ryggen.
Tja, der er ingen måde, jeg kunne have komme op med, at der på quizzen.
Men jeg vil hævde, kan du, hvis du bryder det ned i disse individuelle
sager og bare gå igennem det omhyggeligt, omend ganske vist under
stressende omstændigheder.
>> Heldigvis billedet lavet alt gladere.
Du kan tegne dette i en række forskellige måder.
Du behøver ikke at gøre det kryds og tværs ting her.
Du kan gøre det med lige linjer som dette.
Men kernen i dette problem, i Generelt var at indse, at
billede i sidste ende skal se lidt noget som dette, fordi
konstant tid indebar, at du holder jamming og jamming og tilstopper
nye noder i begyndelsen af listen.
Eventuelle spørgsmål?
Sandsynligvis den mest udfordrende af helt sikkert den kodning spørgsmål.
>> PUBLIKUM: Så er listen ligner hovedet i tidligere eksempler.
>> DAVID J. MALAN: Præcis, præcis.
Bare et andet navn for en global variabel.
World wide hvad?
>> ROB BOWDEN: OK.
Så dette er den, hvor du skulle skrive stykket.
Nogle mennesker skrev essays for dette spørgsmål.
Men du skal bare bruge disse seks betingelser at beskrive, hvad der sker, når
du prøver at kontakte facebook.com.
Så jeg vil bare snakke igennem processen hjælp af alle disse vilkår.
Så i vores browser, vi skriver facebook.com og tryk på Enter.
Så vores browser kommer til at konstruere en HTTP anmode om, at det kommer til at sende
gennem nogle proces til Facebook for Facebook til at reagere på os med den
HTML sin side.
>> Så hvad er den proces, hvilken HTTP-anmodning
rent faktisk får på Facebook?
Så det første, vi har brug for at oversætte Facebook.com.
Så bare givet navnet Facebook.com, hvor faktisk gør det HTTP-anmodning
nødt til at gå?
Så vi er nødt til at oversætte Facebook.com til en IP-adresse, som entydigt
identificerer, hvad maskine vi faktisk ønsker at sende denne anmodning.
Din bærbare har en IP-adresse.
Noget der er forbundet til internettet har en IP-adresse.
>> Så DNS, Domain Name System, der er hvad der kommer til at håndtere oversættelsen
fra facebook.com til en IP-adresse, du rent faktisk ønsker at kontakte.
Så vi kontakte DNS-servere og sige, hvad der er facebook.com?
Den siger, åh, det er IP-adresse 190,212 noget, noget, noget.
Ok.
Nu ved jeg, hvad maskine Jeg vil kontakte.
>> Så du sende din HTTP-anmodning over til denne maskine.
Så hvordan det kommer til den maskine?
Nå, anmodningen går fra router til router hoppende.
Husk eksempel i klassen, hvor så vi faktisk den rute, som den
pakker tog da vi forsøgte at kommunikere.
Vi oplevede det hoppe over Atlanten Ocean på et tidspunkt eller hvad.
>> Så det sidste udtryk port.
Så dette er nu på din computer.
Du kan have flere ting i øjeblikket kommunikere med internettet.
Så jeg kan køre, siger, Skype.
Jeg kunne have en web browser åben.
Jeg kunne have noget at torrenting filer.
Så alle disse ting er kommunikerer med
internet eller anden måde.
>> Så når din computer modtager nogle data fra internettet, hvordan gør det
vide, hvad ansøgning faktisk ønsker, at de data?
Hvordan virker det, om denne særlige data beregnet til
torrenting ansøgning i modsætning til web browser?
Så dette er formålet med havne i det alle disse programmer har
hævdede en port på din computer.
Så din web browser siger, hey, Jeg lytter på port 1000.
Og din torrenting program siger, Jeg lytter på port 3000.
Og Skype siger, jeg bruger port 4000.
>> Så når du får nogle data, der hører til et af disse programmer, de data,
er markeret med hvilken port det faktisk skal sendes videre til.
Så det siger, åh, jeg tilhører til port 1000.
Jeg ved så er jeg nødt til at sende denne sammen til min browser.
Så grunden til det er relevant her er, at web-servere har tendens til at
lytte på port 80..
Så når jeg kontakter Facebook.com, jeg er kommunikation med nogle maskinen.
Men jeg er nødt til at sige, hvilken havn der maskine, jeg ønsker at kommunikere med.
Og webservere tendens til at være lytter på port 80.
>> Hvis de ville, kunne de sætte det op, så det lister som på port 7000.
Og så i en webbrowser, jeg kunne manuelt skrive Facebook.com: 7000 til
sende anmodningen til port 7000 af Facebooks webserver.
>> DAVID J. MALAN: Og i dette tilfælde, selv selvom vi ikke kræve, at folk
nævner dette, i dette tilfælde, hvad port ville anmodningen faktisk gå til?
Prøv igen.
Præcis.
Ikke på udkig efter det, men en underfundighed det er der ingen det sidste.
>> ROB BOWDEN: Så HTTPS, da det er lytter specifikt til
krypteret, det er på port 4430.
>> Publikum: og e-mails er 25, ikke?
>> DAVID J. MALAN: Udgående emails, 25, jep.
>> ROB BOWDEN: Jeg ved ikke engang kender de fleste af den - alle de lavere tendens til at være
forbeholdt ting.
Jeg tror, ​​at alt under 1024 er reserveret.
>> PUBLIKUM: Hvorfor sagde du 3 var forkert nummer?
>> ROB BOWDEN: Fordi i en IP-adresse, Der er fire grupperinger af cifre.
Og de er fra 0 til 255..
Så 192.168.2.1 er en fælles lokale netværk IP-adresse.
Bemærk alle af dem er mindre end 255..
Så da jeg startede med 300, at ikke kunne muligvis have
været et af numrene.
>> DAVID J. MALAN: Men det fjollet klip fra - var det CSI, hvor de havde en
nummer, der var for stor for IP-adressen.
>> ROB BOWDEN: Eventuelle spørgsmål vedrørende denne?
Den næste, så fuldstændig ændring i emne, men vi har denne PHP array for
husene i quad.
Og vi har en uordnet liste.
Og vi ønsker at udskrive et punkt på listen bare indeholder huset navn.
Så vi har en foreach løkke.
Så husk, syntaksen er foreach array som element i arrayet.
Så gennem hver iteration af løkken, Huset kommer til at tage på en af ​​de
værdier indeni array.
>> På den første iteration hus vil være Cabot House.
På en anden iteration, hus vil være Courier hus og så videre.
Så for hver quad som hus, er vi lige til at printe -
du også kunne have gentaget -
listen element og derefter husets navn og derefter lukke listeelement.
De krøllede parenteser er valgfri her.
>> Og så har vi også sagt i spørgsmålet selv, så husk at lukke
uordnet liste tag.
Så vi er nødt til at afslutte PHP mode For at gøre dette.
Eller vi kunne have gentaget den luk uordnet liste tag.
>> DAVID J. MALAN: Også fint her ville have været at bruge en gammel skole for
loop med en $ i = 0 0 og ved hjælp af tællinger finde ud af længden af ​​stråle.
Helt fint, bare lidt wordier.
>> PUBLIKUM: Så hvis du skulle [Uhørligt], du ville gøre -
Jeg glemmer, hvad løkken [uhørligt] er.
Vil du $ quad beslag jeg?
>> DAVID J. MALAN: Præcis.
Ja, præcis.
>> ROB BOWDEN: Noget andet?
>> DAVID J. MALAN: Okay.
Kompromisser.
Så der var bundter af svarene muligt for hver af disse.
Vi var egentlig bare på udkig efter noget overbevisende for en upside og
en ulempe.
Og nummer 16 spurgte, validering brugere ' input klientsiden, som med JavaScript,
i stedet for server-side, som med PHP.
Så hvad er en upside på laver client-side?
>> Tja, en af ​​de ting, vi har foreslået, er at du reducerer ventetid, fordi du
behøver ikke at bekymre kontakte server, hvilket kan tage et par
millisekunder eller endda et par sekunder ved at undgå det, og lige
validere brugernes input client-side ved udløser en on-indsende handler og
bare kontrol, de skriver noget i for navn?
Har de skriver noget i til email-adresse?
Har de vælger et kollegieværelse fra drop-down menu?
>> Du kan give dem øjeblikkelig tilbagemelding hjælp gigahertz computer
eller hvad de har, det er faktisk på deres skrivebord.
Så det er bare en bedre brugeroplevelse typisk oplever.
Men bagsiden af ​​medaljen at client-side validering, hvis du gør det uden også
laver validering server-side er, at mest nogen kommer ud af CS50 kender
at du bare kan sende data, du vil til en server som helst antal måder.
Helt ærligt, i de fleste enhver browser, kan du klikke rundt i indstillingerne og bare
slukke JavaScript, der ville, derfor deaktivere enhver form for
validering.
>> Men du måske også huske, at selv jeg gjorde nogle mystiske ting i klassen ved hjælp af
telnet og faktisk foregiver at være en browser ved at sende get
anmodninger til en server.
Og det er bestemt ikke ved hjælp af en JavaScript.
Det er bare mig at skrive kommandoer på et tastatur.
Så virkelig, enhver programmør indenfor nok komfort med internettet og HTTP
kunne sende hvad data, han eller hun ønsker til en server uden validering.
Og hvis din server ikke også kontrol, de gav mig et navn, er
dette faktisk en gyldig e-mail-adresse, gjorde de vælger et kollegieværelse, kan du ende
op indsætte falske eller bare blank data ind i din database, som sandsynligvis
kommer ikke til at være en god ting, hvis du antager det var der.
>> Så dette er en irriterende virkelighed.
Men generelt client-side validering er stor.
Men det betyder dobbelt så meget arbejde.
Selv om der eksisterer forskellige biblioteker, JavaScript-biblioteker for
eksempel, at gøre det meget, meget mindre af en hovedpine.
Og du kan genbruge noget af koden server-side, client-side.
Men indser, at det typisk ekstra arbejde.
Ja.
>> PUBLIKUM: Så hvis vi bare sagde mindre sikkert -
>> DAVID J. MALAN: [griner]
Ugh.
Det er altid sværere dem til at træffe afgørelse i sagen.
>> ROB BOWDEN Det ville er blevet godkendt.
>> DAVID J. MALAN: Hvad?
>> ROB BOWDEN: Jeg har oprettet dette problem.
Det ville have været accepteret.
>> DAVID J. MALAN: Ja.
>> PUBLIKUM: Fedt.
>> ROB BOWDEN: Men vi havde ikke acceptere for det første -
godt, hvad vi leder efter, er noget som du ikke behøver at
kommunikere med serveren.
Vi acceptere ikke bare hurtigere.
>> PUBLIKUM: Hvad ikke genindlæse siden?
>> ROB BOWDEN: Ja.
Det var et accepteret svar.
>> DAVID J. MALAN: Alt hvor vi følte det var mere sandsynligt end ikke sandsynligt
at du vidste, hvad du var siger, der er en hård
line til at trække nogle gange.
Ved hjælp af en sammenkædet liste i stedet i et array til at opretholde en
sorteret liste af heltal.
Så en upside vi ofte citerer med tilknytning lister, der motiverede deres helhed
introduktion var du får dynamik.
De kan vokse.
De kan krympe.
Så du behøver ikke at hoppe igennem tøndebånd til rent faktisk at skabe mere hukommelse
med et array.
Eller du behøver ikke at bare sige, undskyld, bruger.
Matrixen er fyldt.
Så dynamisk vækst på listen.
En ulempe dog af hægtede lister?
>> PUBLIKUM: Det er lineær.
Søgning på linket liste er lineær i stedet for hvad du logger ind
>> DAVID J. MALAN: Præcis.
Søgning på en linket liste er lineær, selv om det er sorteret, fordi du kan
kun følge disse brødkrummer, disse pegepinde, fra starten af ​​listen
til enden.
Du kan ikke udnytte random access og således binær søgning, selv om det er
sorteret, som du kunne gøre med et array.
Og der er også en anden pris.
Ja.
>> PUBLIKUM: Hukommelse ineffektiv?
>> DAVID J. MALAN: Ja.
Tja, jeg ville ikke nødvendigvis sige ineffektive.
Men det koster dig mere hukommelse, fordi du har brug for 32 bit for hver
node for yderligere pointer, på mindste for en enkelt bundet listen.
Nu, hvis du kun opbevare heltal og du tilføjer den pointer, der er
faktisk slags ikke-triviel.
Det er en fordobling af mængden af ​​hukommelse.
Men i virkeligheden, hvis du opbevarer et hægtet liste af structs, der kan have
8 byte, 16 bytes, endnu mere end det, det er måske mindre
af en marginal omkostning.
Men det er en pris alligevel.
Så enten af ​​dem ville have været fint som ulemper.
>> 18..
Brug af PHP i stedet for C at skrive en kommando-linje-program.
Så her er det ofte hurtigere at bruge en sprog som PHP eller Ruby eller Python.
Du skal bare hurtigt at åbne en tekst editor.
Du har mange flere funktioner til rådighed for dig.
PHP har køkkenvask funktioner, hvorimod i C, du
har meget, meget lidt.
Faktisk fyre kender den hårde måde at du ikke har hash-tabeller.
Du har ikke knyttet lister.
Hvis du vil have dem, skal du gennemføre dem selv.
>> Så en upside på PHP eller virkelig nogen fortolket sprog er den hurtighed
som du kan skrive kode.
Men en ulempe, vi så dette, da jeg hurtigt pisket op en misspeller
implementering i foredrag ved hjælp af PHP, er at ved hjælp af et fortolket sprog
er normalt langsommere.
Og vi så, at beviseligt med en stigning i tid fra 0,3 sekunder til 3
sekunder, på grund af den fortolkning, der rent faktisk sker.
>> Anden opadrettede var, at du ikke behøver at kompilere.
Så det også fremskynder udvikling øvrigt, fordi du ikke har
to trin til at køre et program.
Du skal bare have en.
Og så det er temmelig overbevisende som godt.
Ved hjælp af en SQL-database i stedet for en CSV-fil til at gemme data.
Så SQL database bruges til pset7.
CSV-filer, du ikke bruger meget.
Men du har brugt det indirekte i pset7 som godt ved at tale med Yahoo Finance.
>> Men CSV er ligesom en Excel-fil, men super enkel, hvor søjlerne er
bare demarked af kommaer inde i en ellers tekstfil.
Og ved hjælp af en SQL-database er lidt mere overbevisende.
Det er en upside, fordi du får tingene ligesom vælge og indsætte og slette.
Og du får, formentlig, indekser, MySQL og andre databaser, som
Oracle, bygge for dig i hukommelsen, hvilket betyder, at din vælger, er sandsynligvis ikke
vil være lineær top til bund.
Det er faktisk kommer til at være noget ligesom binær søgning eller noget
samme ånd.
Så de er generelt hurtigere.
>> Men en ulempe er, at det er bare mere arbejde.
Det er mere indsats.
Du er nødt til at forstå databaser.
Du er nødt til at sætte det op.
Du har brug for en server til at køre denne database den.
Du er nødt til at forstå hvordan den konfigureres.
Så disse er blot disse former for kompromisser.
Mens en CSV-fil, kan du oprette den med gedit.
Og du er god til at gå.
Der er ingen kompleksitet ud over dette.
>> Ved hjælp af en trie stedet for en hash tabel med separat kæde til at gemme et
ordbog af ord minder af pset5.
Så en forsøger upside i teorien i det mindste, er hvad?
Konstant tid, i hvert fald hvis du er hashing på hver af de enkelte
bogstaver i et ord, ligesom du kunne få for pset5.
Det kunne være fem hashes, seks hashes hvis der er fem eller seks
bogstaver i ordet.
Og det er temmelig godt.
Og hvis der er en øvre grænse for, hvordan længe dine ord kan være, det er
faktisk asymptotisk konstant tid.
>> Mens en hash tabel med separat kæde, problemet er der med det
type datastruktur er, at effektiviteten af ​​dine algoritmer normalt
afhænger af antallet af ting allerede i datastrukturen.
Og det er helt sikkert tilfældet med kæder, hvorved flere ting du sætter
i en hash tabel, jo længere de kæder gå, hvilket betyder i værste
tilfælde, de ting, du måske være på udkig efter er hele vejen i slutningen af ​​en
af disse kæder, som effektivt overdrages til noget lineært.
>> Nu, i praksis kunne det absolut være tilfældet, at en hash tabel med
kæder er hurtigere end en tilsvarende trie gennemførelse.
Men det er af forskellige årsager, blandt der forsøger at bruge en hel masse
hukommelse, der kan i virkeligheden, langsom ting ned, fordi du ikke får god
fordele af noget, der hedder caching, hvor ting, der er tæt på hinanden
i hukommelsen kan tilgås ofte hurtigere.
Og nogle gange kan du komme op med en rigtig god hash funktion.
Selv hvis du er nødt til at spilde en smule hukommelse, kan du faktisk være i stand til
finde ting hurtigt og ikke så slemt som lineært.
>> Så kort sagt, var der ikke nødvendigvis med nogen af ​​disse en eller endda to
specifikke ting, vi ledte efter.
Virkelig noget overbevisende som en upside og downside
generelt fanget vores øje.
>> ROB BOWDEN: Så for opadrettede, vi gjorde accepterer ikke på sin egen "hurtigere". Du
havde at sige noget om det.
Selv hvis du sagde teoretisk hurtigere, vi vidste, at du slags forstået
at det er 0 af 1.
Og hash tabel i teorien ikke er 0 1.
Nævne noget om runtime generelt fik du point.
Men "hurtigere", de fleste løsninger på den store bestyrelse, der blev forsøger var
objektivt langsommere end løsninger der var hash-tabeller.
Så hurtigere i sig selv er ikke sandt.
>> DAVID J. MALAN: Dom de DOM DOM.
Jeg er nok den eneste, der realiserer det er, hvordan det er meningen at
udtales, right?
>> ROB BOWDEN: Jeg havde faktisk ingen idé.
>> DAVID J. MALAN: Det gjorde mening i mit hoved.
>> ROB BOWDEN: Jeg gør det ene.
OK.
Så dette er den ene, hvor du var nødt til at tegne diagrammet ligner du måske
har set på tidligere eksamener.
Så lad os bare se på dette.
Så fra HTML node, vi har to børn, hovedet og kroppen.
Så vi forgrener - hoved og krop.
Hovedet har en titel tag.
Så vi har en titel.
>> Nu er den ene ting, en masse mennesker glemte er, at disse tekst noder er
elementer inden for dette træ.
Så her er vi tilfældigvis til at trække dem som ovaler at adskille dem fra disse
typer knudepunkter.
Men meddelelsen også her har vi top, midten og bunden vil ende med at blive
tekst noder.
Så glemmer de var noget af en almindelig fejl.
>> Kroppen har tre børn - disse tre divs.
Så div, div, div og derefter teksten node børn af disse divs.
Det er temmelig meget det for, at spørgsmål.
>> DAVID J. MALAN: Og det er værd at bemærke, selv om vi ikke dvæle ved disse
detaljer i den tid, vi bruger på JavaScript, at ordren gør, i
Faktisk stof teknisk.
Så hvis hoved kommer før kroppen i HTML, så det skal vises på
til venstre for kroppen i selve DOM.
At hans er generelt bare FYI, noget, der hedder dokument orden, hvor
det betyder noget.
Og hvis du var at gennemføre en parser, et program, der læser HTML i bygning
op i træet i hukommelsen, for at være ærlig, det er intuitivt sandsynligvis, hvad du
gøre alligevel - top til bund, venstre til højre.
>> ROB BOWDEN: Spørgsmål om det?
Skal jeg gøre det næste?
>> DAVID J. MALAN: Selvfølgelig.
>> ROB BOWDEN: OK.
Så dette er bufferoverløb angreb spørgsmål.
Den vigtigste ting at genkende her er, godt, hvordan kunne en modstander trick
dette program til udførelse vilkårlig kode?
Så argv1, den første kommandolinjen Argumentet for dette program, der kan være
vilkårligt lang.
Men her bruger vi memcpy til at kopiere argv1, som her er bar.
Vi passerer det som argument.
Og så det tager på navnet baren.
>> Så vi memcpying bar i denne buffer ca.
Hvor mange bytes vi kopierer?
Nå men mange bytes bar sker bruge, længden af ​​dette argument.
Men C er kun 12 bytes bred.
Så hvis vi skriver en kommandolinjeargument der er længere end 12 byte, er vi
kommer til at løbe over dette særlig puffer.
Nu, hvordan kan en modstander narre programmere i udførelse af vilkårlig kode?
>> Så husk, at her main kalder foo.
Og så så de vigtigste opkald foo.
Lad os trække dette.
Så vi har vores stak.
Og vigtigste har en stakrammen nederst.
På et tidspunkt, de vigtigste opkald foo.
Nå, det samme, de vigtigste opkald foo.
Og så foo får sin egen stak ramme.
>> Nu på et tidspunkt, foo kommer til at vende tilbage.
Og gik foo afkast, vi har brug for at vide på hvad linje kode inde i hoved, vi
var i orden at vide, hvor vi bør genoptages i main.
Vi kan kalde foo fra en hel masse forskellige steder.
Hvordan kan vi vide, hvor at vende tilbage?
Nå, vi er nødt til at gemme det et eller andet sted.
>> Så et eller andet sted lige her omkring, vi opbevarer hvor vi bør vende tilbage til en gang
foo afkast.
Og dette er afsenderadressen.
Så hvordan en modstander kan tage fordel på dette er det faktum, at
denne buffer C er gemt, lad os sige, lige her er c.
Så vi har fået 12 byte til ca.
Dette er ca.
Og det er foo stak ringen.
Så hvis ondsindet bruger indtaster mere bytes end 12 eller de indtaster en kommando
line argument, der er længere end 12 tegn, så vi kommer til at
overflow denne buffer.
>> Vi kan holde ud.
Og på et tidspunkt, går vi langt nok, at vi starter
overskrive denne returadresse.
Så når vi overskrive den returadresse, dette betyder, at når foo
afkast, vi vender tilbage til, hvor den ondsindet bruger fortæller det til ved
uanset værdi den trådte, uanset hvorledes tegn brugeren har indtastet.
Og så hvis ondsindet bruger bliver specielt smart, kan han have denne
vende tilbage til et sted i printDef funktion eller andet sted i allokere
funktion, lige som helst vilkårlig.
>> Men endnu mere smart er, hvad hvis han har brugeren tilbage til lige her.
Og så skal du begynde at udføre disse som linjer kode.
Så på dette punkt, kan brugeren indtaste hvad han vil ind i denne region.
Og han har fuldstændig kontrol over dit program.
Spørgsmål om det?
Det næste spørgsmål er fuldført reimplementation af foo på en sådan måde
at det ikke længere er sårbar.
>> Så der er et par måder du kunne have gjort dette.
Vi har stadig kun C er af længde 12.
Du kunne have ændret denne som en del af din løsning.
Vi har også tilføjet en check til at gøre sikker bar ikke var nul.
Selvom du ikke har brug for at for fuld kredit.
Så vi tjekker først snorlængde på baren.
Hvis det er større end 12, så faktisk ikke gøre kopien.
Så det er en måde at løse det.
>> En anden måde at løse det er i stedet for der c kun en længde 12, har det
være af en længde strlen (bar).
En anden måde at løse det er til rent faktisk bare vende tilbage.
Så hvis du lige havde fået fjernet alle dette, hvis du bare havde slettet alle
linjer kode, ville du have fået fuld kredit, da denne funktion
faktisk ikke udrette noget.
Det kopierer kommandolinjen argument ind i nogle array i
dens lokale stakrammen.
Og så de ting er tilbage.
Og hvad det dygtig er væk.
Så var afkastet også en tilstrækkelig måde at få fuld kredit.
>> DAVID J. MALAN: Ikke helt ånd spørgsmålet men acceptabel pr
spec alligevel.
>> ROB BOWDEN: Spørgsmål om noget af det?
Den ene ting, at du i det mindste nødvendigt at have kompilere kode.
Så selvom teknisk du ikke er sårbare, hvis din kode ikke
kompilere, vi ikke acceptere.
Ingen spørgsmål?
OK.
>> DAVID J. MALAN: Ønsker du at sige denne titel?
>> ROB BOWDEN: Nej.
>> DAVID J. MALAN: Så i dette ene, dette var enten gode nyheder eller dårlige nyheder.
Det er bogstaveligt talt det samme problem som den første quiz.
Og det er næsten det samme problem som pset1.
Men det var med vilje forenklet for at være en enklere pyramide, en, der kan være
løst med en lidt enklere iteration.
Og virkelig, hvad vi fik på her var ikke så meget logik,
fordi formentlig, ved dette punkt, er du mere komfortabel end du var
i uge ét med for løkker eller hvorfor loops, men virkelig at drille hinanden, at
du er lidt fortrolig med forestilling om, at PHP er ikke kun om, hvad
programmering.
Det kan faktisk bruges som et sprog at skrive kommandolinjeprogrammer.
>> Og ja, det er hvad vi forsøgte at henlede Deres opmærksomhed på.
Dette er en kommandolinje PHP program.
Så C kode, mens korrekt i C, ikke korrigere for PHP.
Men koden virkelig er den samme.
Hvis du sammenligner de løsninger til Quiz 0 imod Quiz 1, vil du opdage, at
det er næsten identiske, bortset nogle dollartegn og for
fraværet af en datatype.
Især hvis vi tager et kig her, vil du se, at vi gentage i denne
fald fra 1 op til 7.
>> Vi kunne have gjort det 0-indekset.
Men nogle gange tror jeg, det er bare mentalt lettere at tænke over tingene
fra 1 til 7.
Hvis du vil have en blok, så to blokke, så tre, så
prik, prik, prik syv.
Vi har j initialiseres til 1 og derefter regner med op til i.
Og alt her er ellers identisk.
Men værd at bemærke er et par ting.
Vi giver dig disse to linjer, denne første en, goofily navngivet som en molevitten
for skarp brag.
Og at netop angiver stien, mappe, hvor et program kan være
fandt, at du ønsker at bruge at fortolke denne fil.
>> Og så den linje efter, at af Selvfølgelig betyder indtaste PHP mode.
Og den linje allernederst betyder exit PHP mode.
Og det virker i almindelighed med fortolket sprog.
Det er lidt irriterende, hvis du skriver en program i en fil kaldet foo.php.
Og så dine brugere skal bare Husk, OK, at køre dette program, jeg
nødt til at skrive "php plads foo.php". Kind irriterende, hvis intet andet.
Og det afslører også, at dit program er skrevet i PHP, hvilket ikke er alle
at lysende for brugeren.
>> Så du kan fjerne det. Php helt huske fra foredraget.
Og du kan faktisk gøre. / Foo hvis du har chmodded det ved at gøre det
eksekverbare.
Så chmod a + x foo ville have gjort.
Og hvis du også tilføje molevitten her.
Men virkelig, problemet var at komme på udskrivning ud noget som dette.
Ingen HTML, ingen C-kode sikkert, blot nogle PHP.
Så Milo vendte derefter tilbage i problemet 25.
Og i 25, var du givet følgende skelet kode, som var en
temmelig simpel webside.
Og den saftige del HTML-wise var nede her, hvor vi har indersiden af ​​kroppen
en form, der har unikke id af input inderside, som var to indgange, den ene
med en idé om navn, en med en idé om knap.
>> Den første var typen tekst, den sekund af typen indsende.
Og så vi gav dig, faktisk, mere ingredienser, end du har brug for, lige så
du fyre havde muligheder, som at løse dette problem.
Du behøver ikke strengt nødvendigt alle disse ID'er.
Men det giver dig mulighed for at løse det på forskellige måder.
Og op i toppen, bemærke, at målet var at udløse
et vindue som dette -
Hej, Milo! -
at dukke op i browseren ved hjælp af super simpelt, hvis
ikke grim, alarm funktion.
Og så i sidste ende, det koges ned begrebsmæssigt en eller anden måde at lytte til
indsendelser af formen client-side , Ikke server-side, en eller anden måde
reagere på denne indsendelse af snuppe den værdi, som brugeren har indtastet
på feltnavnet og derefter vise det i kroppen af ​​en indberetning.
>> Så en måde du kan gøre dette på er med jQuery, der ser lidt
syntaktisk forvirrende ved første.
Du kan gøre dette med ren DOM kode - document.getelement med id.
Men lad os tage et kig på denne version.
Jeg har et par vigtige linjer først.
Så man har vi denne linje, der er identisk med det, du måske har set
i, tror jeg, form2.html fra klasse i uge 9..
Og det er bare at sige, udføre følgende kode, når
dokumentet er klar.
Det er vigtigt kun fordi HTML-sider læses fra top til
bund, venstre mod højre.
>> Og derfor, hvis du forsøger at gøre noget i kode op her til nogle DOM
element, nogle HTML-tag, der er ned her, du gør det for hurtigt,
fordi det har ikke engang er indlæst i hukommelsen.
Så ved at sige dette document.ready linje, vi siger,
her er noget kode, browser.
Men du behøver ikke udføre dette, før hele dokumentet er klar, dvs DOM
findes træ i hukommelsen.
Denne ene er lidt mere ligetil, hvis syntaktisk en
lidt anderledes, hvor jeg siger, grab HTML-element, hvis unikke
id er indgange.
Det er, hvad hash tag betegner den unikke id.
Og så jeg ringer. Indsende.
>> So. Indsende her er en funktion, ellers kendt som en fremgangsmåde, der er
indersiden af ​​objektet på venstre hånd side er der, at jeg ikke fremhæve.
Så hvis du tænker på input som et objekt i hukommelsen - og det er faktisk.
Det er en knude i et træ -
. Indsende midler, når denne formular med dette id er forelagt, udføre
følgende kode.
Jeg er ligeglad, hvad navnet på den Funktionen er jeg udfører.
Så her jeg bruger, som før, hvad er kaldt lambda funktion eller en
anonym funktion.
Det er slet ikke intellektuelt interessant andet end det ikke har noget navn,
hvilket er fint, hvis du kun nogensinde kommer til at kalde det en gang.
Og derinde jeg faktisk håndtere indsendelse af formularen.
Jeg først erklære en variabel kaldet værdi.
Og hvad er effekten af ​​denne fremhævet del her nu?
Hvad betyder det gøre på en højt til mig?
>> PUBLIKUM: Det bliver den værdi, som brugeren ikke gjorde i HTML nedenfor.
Det bliver at id og derefter finder værdien af ​​det.
>> DAVID J. MALAN: Præcis.
Det griber node, hvis unikke id er navnet.
Det får den værdi, deri, som er formentlig, hvad brugeren
indtastet ham eller hende selv.
Og så gemmer der i variabel kaldet værdi.
Som en sidebemærkning, kan du også have gjort dette lidt anderledes.
Helt acceptabelt ved at gøre noget løgn var værdi får
document.getElementById.
Og det er derfor, det er lidt trættende ikke at bruge jQuery.
"Navn". Værdi.
Så helt acceptabelt.
Forskellige måder at gøre dette. jQuery bare tendens til at være lidt mere kortfattet og
klart mere populær blandt programmører.
>> Nu, jeg laver lidt af en tilregnelighed check, fordi problemet
erklæring, vi udtrykkeligt sagt, hvis det bruger har endnu ikke indtastet hans eller hendes
navn, viser ikke en indberetninger.
Men du kan tjekke for, at ved blot kontrol af den tomme streng for en
quote-citat slut, hvis der er intet faktisk er der.
Men hvis det er ikke lig med citat-citat slut, Jeg vil ringe til advarsler.
Og det interessante del er, at vi bruger plus operatør, som
gør hvad i JavaScript?
Sammenkæde.
Så det er ligesom PHPs dot operatør.
Samme idé, lidt anderledes syntaks.
Og jeg blot at skabe den streng, du så på skærmen skud -
Hej, så og så.
>> Og så den sidste detalje er dette.
Hvorfor jeg tilbage falsk indeni af denne anonyme funktion?
>> PUBLIKUM: Der er ingen værdi.
Du sætter det i formularen.
Det bare siger, hvis værdi ikke svarende til tomme, så gør det.
Der var en blank i denne underkastelse.
>> DAVID J. MALAN: OK.
Vær dog forsigtig.
Der er ingen andre her.
Og at return false er udenfor af hvis forholdene.
Så dette fremhævede linje, return false, udfører ikke hvad når stof
formularen er sendt.
Hvad tilbage falsk Indersiden af event handleren, som det hedder,
den pågældende begivenhed være indsendelse?
>> PUBLIKUM: Fordi det kun sker én gang.
>> DAVID J. MALAN: Kun sker en gang.
Ikke helt.
Ja?
>> PUBLIKUM: Det forhindrer form fra indsendelse til standard opførsel,
hvilket ville gøre siden reload.
>> DAVID J. MALAN: Præcis.
Så jeg overbelastning udtrykket indsende her, fordi jeg siger, formen er
at blive sendt.
Men som du antyder, er det faktisk ikke blevet forelagt i den sande HTTP måde.
Når du klikker på Send, på grund af vores onSubmit handleren, vi opsnappe
at formularafsendelse så at sige.
Vi derefter gøre vores ting med JavaScript-kode.
Men jeg bevidst returnere falsk, fordi det, jeg ikke ønsker at ske en
splitsekund senere er for hele formular selv, der skal forelægges på nettet
server med centrale værdipar ved at ændre URL til at være noget lignende
q = katte eller hvad vi gjorde, for eksempel i klassen.
Jeg ønsker ikke, at det sker, fordi Der er ingen server lytte til dette
danne indsendelse.
Det er udelukkende gjort i JavaScript-kode.
Og det er derfor jeg ikke engang har en handling attribut på min form, fordi jeg
agter ikke for at dette kan nogensinde gå til serveren.
>> Så det er at blive sendt.
Men vi opsnappe denne formular indsendelse og forhindre standard
adfærd, som er rent faktisk gå hele vejen til serveren.
>> PUBLIKUM: Så holder det client-side.
>> DAVID J. MALAN: Hold det client-side.
Præcis højre.
Næste op var min oh MySQL.
>> ROB BOWDEN: OK.
Så det første spørgsmål var generelt uslebne for mennesker.
Selvom senere dem gik bedre.
Så du skulle vælge de korrekte data typer for begge disse kolonner.
Og begge disse har nogle ting om dem, at
gøre valget svært.
Så int ikke var et gyldigt skriv for nummer.
Årsagen er en 12-cifret konto nummer, en int er ikke stor nok til at
gemme samlede cifre.
Så et gyldigt valg ville have været en stor int hvis du tilfældigvis kender det.
Et andet valg kunne have været en char på længde 12.
Så enten af ​​dem ville have fungeret.
Int. ville ikke.
>> Nu, balance, tænke tilbage på pset7.
Så vi specifikt anvendes decimal til gemme værdien af ​​aktier eller -
>> DAVID J. MALAN: Kontant.
>> ROB BOWDEN: Kontant.
Vi brugte decimal til at lagre den mængde kontanter, som brugeren har i øjeblikket.
Så årsagen til at vi gør det er fordi huske, flåd.
Der er floating point i præcision.
Det kan ikke præcist gemme kontanter værdier som vi ønsker her.
Så decimal er i stand til præcist butik noget til, sige, to decimaler.
Det er derfor, balance, vi ønsker det være decimal og ikke flyde.
>> DAVID J. MALAN: Og også, også selvom det kunne have været smart i andre
sammenhænge til at tænke, måske denne er en chance for en int.
Jeg vil bare holde styr på ting i øre.
Fordi vi udtrykkeligt viste standard værdien af ​​at være 100,00, at
betyder, at det kunne bare være en int.
Og en anden underfundighed også med nummer var, at det ikke var ment
at være et trick spørgsmål.
Men husker at en int i MySQL, som i C, i det mindste i
apparat, er 32-bit.
Og selvom vi ikke forventer, at du vide præcis, hvor mange cifre der
midler, må minde om, at det største antal du kan repræsentere potentielt
med en 32-bit tal er omtrent, hvad?
>> Hvilket nummer har vi altid siger?
2 til 32, hvilket er det groft?
Du behøver ikke at vide præcist.
Men groft er nyttigt i livet.
Det er omtrent 4 mia.
Så vi har sagt, at et par gange.
Jeg ved, jeg har sagt, at et par gange.
Og det er omtrent 4 mia.
Og det er en god regel tommelfinger til at vide.
Hvis du har 8 bit, 256 er det magiske tal.
Hvis du har 32 bit, 4 milliarder give eller tage.
Så hvis du bare skrive ned 4 milliarder, du vil se, at det er færre cifre end
12, hvilket betyder, at der er helt klart ikke nok udtryksfuldhed til at fange en
12-cifret kontonummer.
>> ROB BOWDEN: OK.
Så de andre gik bedre.
Så antage, at banken pålægger en $ 20 månedligt
vedligeholdelse gebyr på alle konti.
Med hvad SQL-forespørgsel kunne banken fratrække 20 dollar fra hver tæller, også selvom
det resulterer i nogle negative saldi?
Så dybest set er der fire hovedtyper af forespørgsler -
indsætte, skal du vælge, opdatere og slette.
Så hvad gør vi tror, ​​vi er kommer til at bruge her?
Opdater.
>> Så lad os tage et kig.
Så her er vi opdaterer.
Hvad tabellen er vi opdatere konti?
Så opdatere konti.
Og så syntaksen siger, hvad i regnskabet er vi opdatere?
Nå, vi sætte balance svarende til aktuelle værdi af balance minus 20.
Så dette vil opdatere alle rækker af regnskaber, subtraktion
$ 20 fra saldoen.
>> DAVID J. MALAN: En almindelig fejl her, selv om vi undertiden tilgav det,
var faktisk have PHP kode her kalde forespørgslen funktion eller lægge
anførselstegn omkring alt, hvad der behøvede ikke at være der.
>> ROB BOWDEN: Husk, at MySQL er et separat sprog fra PHP.
Vi tilfældigvis skal skrive MySQL i PHP.
Og PHP er derefter sende det over til MySQL-serveren.
Men du behøver ikke PHP for at kommunikere med en MySQL-serveren.
>> DAVID J. MALAN: Præcis.
Så ingen variabler med dollartegn bør i denne sammenhæng.
Det kan bare gøre alle de matematik inden selve databasen.
>> ROB BOWDEN: OK.
Så den næste.
Er dette den næste?
Ja.
Så med hvad SQL-forespørgsel kunne banken hente kontonumre dens
rigeste kunder, dem med saldi større end 1.000?
Så hvilken af ​​de fire hovedtyper skal vi have her?
Vælg.
Så vi ønsker at markere.
Hvad ønsker vi at markere?
Hvad kolonne ønsker vi at markere?
Vi vil specifikt ønsker at vælge nummeret.
Men hvis du sagde stjerne, vi også accepteret det.
>> Så vælg et nummer fra hvad bordet?
Konti.
Og så den tilstand, vi ønsker?
Når saldo større end 1.000.
Vi accepterede også større end eller lig.
Sidste.
Med hvad SQL-forespørgsel kunne banken tæt, dvs slette enhver konto, der
har en balance på $ 0?
Så hvilken af ​​de fire er vi lyst til at bruge?
Slet.
Så syntaksen for det?
Slet fra hvad bordet?
Konti.
Og så betingelsen for, vi ønsker at slette -
hvor balancen er lig med nul.
Så sletter alle rækker fra konti hvor balancen er nul.
Spørgsmål om nogen af ​​disse?
Ønsker du at stå i kø?
>> DAVID J. MALAN: Kø vejledning.
Så i denne ene, vi gav dig en noget velkendt struktur, vi udforskede
bit i klassen ved siden af ​​structs, som var en data
struktur relateret på ånd.
Forskellen dog med en køen at vi havde en eller anden måde huske, hvem
var forrest i køen i vid del, så vi kunne gøre mere
effektiv udnyttelse af hukommelse, mindst hvis vi bruger et array.
>> Fordi huske, hvis vi har et array, hvis for eksempel er den forreste del af
køen, hvis jeg kommer ind i køen her, og så nogen får på linje
bag mig, bag mig, bag mig, og én person træder ud af linje, du
kunne, da vi så nogle af vores menneskelige frivillige i klassen, har alle
flytte denne måde.
Men generelt har alle gøre noget er ikke den bedste brug af tid
i et program, fordi det betyder, at din algoritmen løber i det
asymptotiske køretid?
Det er lineær.
>> Og jeg føler, at der er slags dumt.
Hvis den næste person på linje er den næste person, der er meningen at gå ind i
butikken, behøver de ikke alle har til at bevæge sig sammen.
Bare lad som person plukkede når den tid kommer, for eksempel.
Så vi kan spare lidt tid der.
Og så for at gøre det selv, det betyder at lederen af ​​køen eller
forrest i køen, vil gradvist bevæger sig dybere og dybere
i rækken, og i sidste ende kan faktisk wrap rundt, hvis vi bruger en
array til at gemme de mennesker i denne kø.
Så du kan næsten tænke på array som en cirkulær data
struktur i den forstand.
>> Så du en eller anden måde nødt til at holde styr på størrelsen af ​​det eller virkelig i slutningen af ​​det
og derefter, hvor begyndelsen af ​​det er.
Så vi foreslår, at du erklærer en sådan kø, kald
det q, blot ét bogstav.
Så foreslår vi, at den forreste være initialiseres til nul, og at størrelsen
initialiseres til nul.
>> Så lige nu, er der intet inde i køen.
Og vi beder dig om at fuldføre gennemførelse af enqueue nedenfor
en sådan måde, at funktionen tilføjer n udgangen af ​​q og derefter returnerer sandt.
Men hvis q er fuld eller negativ, funktionen skal i stedet returnere falsk.
Og vi gav dig et par antagelser.
Men de er ikke rigtig funktionelt relevant, findes netop bool,
fordi, teknisk bool ikke findes i C, medmindre du inkluderer en
vis header fil.
Så det var bare sørg for at der blev ingen er dette et trick
Spørgsmålet slags ting.
>> Så enqueue, vi foreslog i prøven løsninger til at gennemføre som følger.
Én, vi først kontrollere den lethed, de lavthængende frugter.
Hvis køen er fuld, eller det antal, du forsøger at indsætte, er mindre
end nul, som vi sagde i specifikation af burde problemet
ikke tilladt, fordi vi kun ønsker ikke-negative værdier, så skal du
bare return false straks.
Så nogle forholdsvis let fejlkontrol.
Hvis om du ønsker at tilføje, at den faktiske nummer, du havde at gøre en smule
tænker her.
Og det er, hvor det er lidt irriterende mentalt, fordi du er nødt til at
regne ud, hvordan man håndterer wraparound.
>> Men kimen til ideen her, der er af interesse for os er, at wraparound
indebærer ofte modulær aritmetik og MOD operatøren, procent side,
hvor man kan gå fra en større værdi tilbage til nul og derefter et og to og
tre og derefter tilbage rundt til nul, en og to og tre og så videre
igen og igen.
Så den måde, vi foreslår at gøre dette er at vi ønsker at indekset i den
vifte kaldet numre, vores heltal lyve.
Men for at komme der, vi først ønsker at gøre uanset størrelsen af ​​køen, men
derefter føje til, at uanset foran listen.
Og effekten af ​​det er at sætte os på den rigtige position i køen og
ikke antage, at den første person på linje er i begyndelsen, som han eller
hun absolut kunne være, hvis vi også flytte alle.
Men vi er blot at skabe arbejde for os selv, hvis vi tog
denne særlige vej.
>> Så vi kan holde det relativt simpelt.
Vi er nødt til at huske på, at vi bare tilføjet en int til køen.
Og så har vi bare returnere sandt.
I mellemtiden, i dequeue, bad vi dig til at gøre følgende.
Gennemføre det på en sådan måde, at det dequeues, der er Fjerner og returnerer,
int på forsiden af ​​køen.
For at fjerne int, er det tilstrækkeligt at glemme det.
Du behøver ikke at tilsidesætte sin bit.
Så det er stadig faktisk er der.
Ligesom data på en harddisk, vi bare ignorerer det faktum,
at det nu er der.
Og hvis q er tom, skal vi i stedet returnere negativ 1.
Så det føles vilkårlig.
Hvorfor returnerer negativ 1 i stedet for falsk?
Ja.
>> PUBLIKUM: Q er lagring positive værdier.
Da du kun gemmer positive værdier i q, negativ er en fejl.
>> DAVID J. MALAN: OK, sandt.
Så fordi vi kun er opbevaring af positiv værdier eller nul, så er det fint at
returnere en negativ værdi som en skildvagt værdi, et særligt symbol.
Men du omskrive historien der, fordi grunden til at vi er kun
returnere ikke-negative værdier er, fordi vi ønsker at
har en skildvagt værdi.
Så mere specifikt, hvorfor ikke bare return false i tilfælde af fejl?
Ja.
>> PUBLIKUM: Du har fejlet at returnere et heltal.
>> DAVID J. MALAN: Præcis.
Og det er her C får temmelig begrænsende.
Hvis du siger du vil til at returnere en int, har du
til at returnere en int.
Du kan ikke få fancy og begynde at vende tilbage en bool eller en flyder eller en
snor eller noget lignende.
Nu, i mellemtiden, JavaScript og PHP og nogle andre sprog kan faktisk,
har du returnere anderledes typer af værdier.
Og det kan faktisk være nyttigt, hvor du kunne returnere positive Ints, nuller,
negative int'er, eller falske eller null selv at betyde fejl.
Men vi behøver ikke at alsidighed i C.
>> Så med dequeue, hvad vi foreslår at gøre, er -
>> ROB BOWDEN: Du kan vende tilbage falsk.
Det er bare, at falsk er hash definere falsk til nul.
Så hvis du vender tilbage falsk, du returnere nul.
Og nul er en gyldig ting i vores kø, henviser negativ 1 er ikke hvis
falsk skete for at være negativ 1..
Men du bør ikke engang brug for at vide det.
>> DAVID J. MALAN: Det er hvorfor jeg ikke sige det.
>> ROB BOWDEN: Men det var ikke sandt at du ikke kan returnere falsk.
>> DAVID J. MALAN: Selvfølgelig.
Så dequeue, mærke vi accepterer ugyldig som sit argument.
Og det er, fordi vi ikke er passerer noget i.
Vi ønsker blot at fjerne elementet forrest i køen.
Så hvordan kan vi gå om at gøre dette?
Nå, det første, lad os gøre det hurtig tilregnelighed check.
Hvis køstørrelsen er 0, er der intet arbejde, der skal gøres.
Retur negativ 1.
Udført.
Så det er et par linjer af mit program.
Så kun fire linjer tilbage.
>> Så her jeg beslutter at formindske størrelse.
Og decrementing størrelse effektivt betyder, at jeg glemmer
noget er derinde.
Men jeg er også nødt til at opdatere, hvor forsiden af ​​tallene.
Så for at gøre det, jeg har brug for at gøre to ting.
Jeg har brug for først at huske, hvad nummeret er forrest i køen,
fordi jeg har brug for at returnere den ting.
Så jeg ønsker ikke at uheld glemmer om det, og derefter overskrive den.
Jeg skal bare huske på en int.
>> Og nu, jeg ønsker at opdatere q.front skal q.front +1.
Så hvis dette var den første person i linje nu, jeg ønsker at gøre plus 1 til
pege på den næste person i linje.
Men jeg er nødt til at håndtere det wraparound.
Og hvis kapacitet er en global konstant, der kommer til at tillade mig at sørge
da jeg pege på den allersidste person strækning, modulo operation bringe
mig tilbage til nul ved forrest i køen.
Og der håndterer wraparound her.
Og så vil jeg gå videre til at vende tilbage n..
>> Nu, strengt taget, det gjorde jeg ikke nødt til at erklære n..
Jeg behøvede ikke at få fat i det og gemme det midlertidigt, fordi værdien er
der stadig.
Så jeg kunne bare gøre det rigtige aritmetiske til at returnere den tidligere leder
i køen.
Men jeg følte bare, at det var mere klar til rent faktisk at få fat i int, sætte det
i n, og derefter vende tilbage som for klarhedens skyld, men
ikke strengt nødvendigt.
Psst.
De er alle udtales i mit hoved.
>> ROB BOWDEN: So første spørgsmål er binært træ problem.
Så første spørgsmål er, at vi givet disse numre.
Og vi ønsker at en eller anden måde indsætte dem i disse knudepunkter, således at det er en
gyldig binær søgning træ.
Så én ting at huske om binære søgetræer er, at det ikke er
bare, at de ting til venstre er mindre, og ting at
højre er større.
Det skal være, at hele træet til venstre er mindre, og hele træet
til højre er større.
>> Så hvis jeg sætter 34 her i toppen, og derefter Jeg sætter 20 her, så det er gyldigt, så
langt, fordi 34 heroppe.
20 går til venstre.
Så det er mindre.
Men jeg kan ikke derefter sætte 59 her, fordi selv om 59 er på højre side af 20
det er stadig til venstre 34.
Så med denne begrænsning i tankerne, nemmeste måde nok at løse dette
Problemet er bare at sortere af disse numre -
så 20, 34, 36, 52, 59, 106.
Og derefter indsætte dem fra venstre til højre.
>> Så 20 går her.
34. går her.
36. går her.
52, 59, 106.
Og du også kunne have regnet ud med nogle tilslutte og realisere,
Åh, vent, jeg har ikke nok numre at udfylde dette i herovre.
Så jeg har brug for at reshift hvad min rute note bliver.
Men bemærk, at der i de sidste tre, hvis du læser fra venstre mod højre, er det i
stigende orden.
>> Så nu ønsker vi at erklære, hvad struct vil være for
knudepunkter i dette træ.
Så hvad har vi brug for i et binært træ?
Så vi har en værdi af typen int, så nogle int værdi.
Jeg ved ikke, hvad vi kaldte det i opløsningen -
int n.
Vi har brug for en pointer til venstre barn og en pointer til den rigtige barn.
Så det kommer til at se sådan ud.
Og det vil faktisk se, før hvornår har den dobbelt-linked
liste ting, så varsel -
Jeg har tænkt mig at skulle rulle hele vej tilbage ned til problem 11.
>> Så bemærker det ser identisk med dette, medmindre vi bare tilfældigvis kalde disse
forskellige navne.
Vi har stadig et heltal værdi og to pointere.
Det er bare at i stedet for at behandle pejlemærker, som peger på den næste ting
og den tidligere ting, vi behandler markørerne til at pege på en venstre barn
og højre barn.
OK.
Så det er vores struct node.
Og nu er den eneste funktion, vi er nødt til at redskab til dette er travers, som
vi ønsker at gå over træet, trykning de værdier af træet i rækkefølge.
>> Så ser her, ville vi ønsker at udskrive ud 20, 34, 36, 52, 59, og 106.
Hvordan kan vi opnå det?
Så det er temmelig ens.
Hvis du har set i fortiden eksamen problemet at man ønskede at udskrive
hele træet med kommaer i mellem alt, det var faktisk endnu
lettere end det.
Så her er løsningen.
Dette var betydeligt lettere hvis du gjorde det rekursivt.
Jeg ved ikke, om nogen har forsøgt at gøre det iterativt.
>> Men først har vi vores base case.
Hvad hvis roden er nul?
Så vil vi bare at vende tilbage.
Vi ønsker ikke at udskrive noget.
Else vi kommer til at krydse rekursivt ned.
Udskriv hele venstre undertræ.
Så udskrive alt mindre end min nuværende værdi.
Og så har jeg tænkt mig at printe selv.
Og så har jeg tænkt mig at recurse ned min hele højre undertræ, så alt
større end min værdi.
Og det kommer til at udskrive ud af alt i orden.
Spørgsmål om, hvordan det rent faktisk udretter det?
>> PUBLIKUM: Jeg har et spørgsmål på [uhørligt].
>> ROB BOWDEN: Så en måde at nærme enhver rekursive problem er bare at tænke
om det, som du nødt til at tænke om alle de sager Corner.
Så mener, at vi ønsker at udskrive hele dette træ.
Så alt vi kommer til at fokusere på er netop denne node -
36..
De rekursive kald, vi lader de bare arbejde.
Så her, denne rekursivt kald til travers, vi uden at tænke
om det, bare gennemkører venstre tre, forestille sig, at der allerede udskriver 20
og 34 for os.
Og så når vi til sidst rekursivt call travers på
rigtigt, vil det korrekt udskrive 52, 59, og 106 for os.
>> Så da dette kan udskrive 20, 34, og den anden kan udskrive 52, 59, 108,
alt, hvad vi nødt til at være i stand til at gøre, er at udskrive os selv i midten af ​​det.
Så udskrive alt før os.
Print os selv, så den aktuelle node print 36, regelmæssig printf og derefter
udskrive alt efter os.
>> DAVID J. MALAN: Her rekursion bliver virkelig smukke.
Det er denne fantastiske spring af tro, hvor du gør den mindste smule arbejde.
Og så skal du lade en ellers gøre resten.
Og at en anden er, ironisk nok, du.
Så for alvorlige brownies punkter, hvis du rulle op på spørgsmålene -
>> ROB BOWDEN: På spørgsmål?
>> DAVID J. MALAN: Og lidt ned for tallene, er der nogen vide, hvor
disse tal kommer fra?
>> ROB BOWDEN: Jeg har bogstaveligt talt ingen idé.
>> DAVID J. MALAN: De vises hele quizzen.
>> PUBLIKUM: Er de de samme numre?
>> DAVID J. MALAN: Disse tal.
En lille påskeæg.
Så for dem af jer ser online på hjem, hvis du kan fortælle os via e-mail til
heads@CS50.net hvilken betydning af disse tilbagevendende seks numre er
hele Quiz 1 vil vi bad dig med forbløffende opmærksomhed på det sidste
foredrag og en stress bold.
Nice, subtil.
>> ROB BOWDEN: Nogle sidste spørgsmål om noget på quiz?