>> DAVID J. MALAN: Okej.
Så välkommen till den första någonsin CS50 obduktion för en frågesport.
Vi trodde vi skulle inviga denna tradition i år.
Och detta kommer att bli ett tillfälle att gå igenom
lösningar på frågesport.
Och vi kommer att påskynda eller sakta ner baserade om intresse av dem här.
>> Så du är förmodligen här för att du är intresserad av hur du kan ha eller
borde ha svarat något av dessa problem.
Så varför inte vi titta i detta avsnitt först?
Så få strängar.
Detta gav dig tre olika versioner av ett program, som var slutligen
tänkt att få en sträng från en användare.
Oavsett om det gjorde det var lämnas till dig att avgöra.
>> Och vi frågade i fråga 0, Anta att version 1 är
kompileras och exekveras.
Varför skulle det program segfault?
Vid första anblicken, några förslag varför?
Yeah.
>> PUBLIK: Jag minns att jag såg detta i ett tidigare exempel på att titta på
char * s och ser genomsökningen av s och ser att det är en pekare, hur
gjorde det påverka det du skannat in?
Är det är eller adressen till s?
>> David J. MALAN: OK.
Bra.
Så i slutändan, källan till alla problem är förmodligen kommer att minska
till den variabeln s.
Och det är verkligen en variabel.
Datatypen för denna variabel är char *, vilket innebär att det kommer att
innehålla adressen till ett tecken.
Och däri ligger insikten.
Det kommer att innehålla adressen till en art eller, mer allmänt,
adressen för det första tecknet i ett helt block av tecken.
>> Men kruxet är att skanna s, syfte i liv, ges en adress och ges
ett format kod, som% s, läsa en sträng i en stor bit av
minne på den adressen.
Men eftersom det inte finns något likhetstecken före att semikolon på första
kodrad, eftersom vi egentligen inte allokera minne med
malloc, eftersom det faktiskt inte avsätta en matris av någon storlek, alla
du gör är att läsa användarens tangentbordsinmatning i en komplett
skräp värde, vilket är i s standard.
Så oddsen är att du kommer att segfault om den adressen är inte bara så råkar
vara ett värde som du kan, i själva verket, skriv till.
Så dåligt att inte tilldela ditt minne där.
>> Så i fråga 1, frågade vi, Anta att version 2 är
kompileras och exekveras.
Varför kan det här programmet segfault?
Så den här är mindre buggig.
Och det finns egentligen bara en självklart sätt där du kan
utlösa en segfault här.
Och detta är tematiskt.
Varje gång vi använder c i minnet, vad kan du göra för att framkalla en segfault
med version 2?
>> PUBLIK: Om du använder den ingången i en sträng som är längre än 49
tecken.
>> DAVID J. MALAN: Exakt.
Varje gång du ser något fast längd när det kommer till en array, din
radar ska gå av att detta kan vara problematiskt om du inte kontrollerar
Gränserna för en array.
Och det är problemet här.
Vi använder fortfarande scanf.
Vi är fortfarande använder% s, vilket innebär att försöka att läsa en sträng från användaren.
Det kommer att läsas in i er, som, vid denna punkt, är effektivt
adressen för en bit av minnet eller motsvarande.
Det är namnet på en matris tecken i minnet.
>> Men just det, om du läser en sträng som är längre än 49 tecken, 49
eftersom du behöver utrymme för backslash 0, du kommer att svämma över
som buffert.
Och du kan ha tur och kunna skriver en 51: a karaktär, 52: a, 53: e.
Men någon gång, OS kommer att säga nej.
Detta är definitivt inte minnet du är tillåtet att röra vid.
Och programmet kommer att segfault.
>> Så det bör heuristik vara någon tid du har fast längd, har du
att se till att du kontrollerar längden av vad det är du försöker
att läsa in den.
>> PUBLIK: Så för att lösa det, du kan ha haft ett uttalande kontroll faktiskt
är den längd som är större eller mindre än?
>> DAVID J. MALAN: Absolut.
Du har bara ett villkor som säger, om -
eller snarare du inte nödvändigtvis vet i förväg hur många tecken som den
Användaren kommer att skriva, eftersom du har hönan och ägget.
Inte förrän du har läst den in med scanf kan du räkna ut hur lång tid det är.
Men på den punkten, det är för sent, eftersom du redan har läst det i
några block av minne.
Så Inom parentes de CS50 biblioteks undviker denna fråga helt och hållet, minns
genom användning fgetc.
Och den läser ett tecken i taget, tip-toeing längs vet du att du
kan inte spilla en karaktär om man läser en i taget.
>> Fångsten är med getString minns är att vi hela tiden måste ändra storlek
att bit av minnet, vilket är bara en smärta.
Det är en hel del rader kod för att göra det.
Så en annan lösning skulle vara att använder faktiskt en kusin, så
att tala, i scanf.
Det finns varianter av en hel del av dessa funktioner som faktiskt kontrollerar
Längden på hur många tecken du kan läsa maximalt.
Och du kan ange, inte läser mer än 50 tecken.
Så det skulle vara ett annat tillvägagångssätt, men mindre tillmötesgående av större ingångar.
>> Så fråga 2 frågar, antar att version 3 kompileras och exekveras.
Varför skulle det programmet segfault?
Så den här är faktiskt samma svara på, även om det
ser lite snyggare.
Vi använder malloc, vilket känns som vi ger oss fler alternativ.
Och sedan ska vi frigöra det minne i slutet.
Det är fortfarande bara 50 byte minne.
Så vi kan fortfarande försöka läsa i 51, 52, 1000 bytes.
Det kommer att segfault för exakt samma anledning.
>> Men det finns en annan anledning också.
Vad mer kan malloc avkastning förutom adressen till en bit av minne?
Det kan returnera null.
Och eftersom vi inte kollar efter det, skulle vi kunna göra något
dumt av en annan anledning, nämligen att Vi kan berätta scanf, läsa
användarens input från tangentbordet in 0 plats, AKA null.
Och det också, kommer definitivt utlösa en segfault.
Så för frågesport syfte, vi skulle har accepterat någon av dem som en
giltigt skäl.
En är identiska.
Man är lite mer nyanserad.
>> Slutligen, med avseende på programmets användning av minne, hur gör version 2 och
version 3 skiljer sig åt?
Så för vad det är värt, såg vi en till synes oändligt utbud av möjliga
svar på detta.
Och bland människors svar, vad vi var hoppas på, men vi accepterade andra
saker, var någon omnämnande av faktum att version 2 använder
den så kallade stacken.
Version 3 använder heap.
Och funktionellt, gör detta inte riktigt göra så mycket av en skillnad.
Vid slutet av dagen, vi är fortfarande bara få 50 byte minne.
>> Men det var en av de möjliga svaren att vi undersöker.
Men du ser, som du får dina frågesporter tillbaka från TF, att vi gjorde
acceptera andra diskussioner om deras skilda användningar av minne också.
Men stack och heap skulle ha varit ett enkelt svar för att gå med.
Några frågor?
Jag ger dig Rob.
>> ROB BOWDEN: Så problemet 4.
Det är det där du var tvungen att fylla av antalet bytes av alla
dessa olika typer används.
Så första vi ser.
Antag en 32-bitars arkitektur, som den här CS50 apparat.
Så en av de grundläggande sakerna 32-bitars arkitekturer, berättar att
exakt hur stor en pekare kommer att vara i arkitekturen.
>> Så omedelbart, vi vet att alla pekare typ är 32-bits eller 4 byte.
Så titta på denna tabell, en nod * är en pekare typ.
Det kommer att vara 4 byte.
Struct node *, det är bokstavligt talat identisk med noden stjärna.
Och så det kommer att bli 4 byte.
String, så det inte ser ut som en pekaren ännu, men typedef, en
strängen är bara en char *, som är en pekare typ.
Så det kommer att bli 4 byte.
>> Så dessa tre är alla 4 byte.
Nu, nod och elev är lite mer komplicerat.
Så titta på nod och student, ser vi noden som ett heltal och en pekare.
Och eleven är två pekare inne i den.
Så åtminstone för vårt fall här, vägen att vi hamnar beräkna storleken på
denna struct är bara lägga upp allt som är inne i struct.
>> Så för nod, har vi ett heltal, vilket är fyra byte.
Vi har en pekare, som är fyra byte.
Och så en nod går att ta upp åtta byte.
Och på samma sätt för eleven, vi har en pekare som är 4 byte och annat
pekare som är 4 byte.
Så det kommer att sluta upp att vara 8 byte.
Så nod och elev är 8 byte.
Och dessa tre är alla 4 byte.
Frågor på det?
Ja.
>> Publik: Är det var en 64-bitars arkitektur, skulle det
fördubbla dem alla?
>> ROB BOWDEN: Det skulle inte fördubbla dem.
Så 64-bitars arkitektur, det, återigen, förändringar som grundläggande sak som en
Pekaren är nu 64 bitar.
Yeah.
Så en pekare är 8 byte.
Så dessa som var 4 byte kommer att vara 8 byte.
En student, som var två pekare, bra, nu det kommer att
vara 8 byte, 8 byte.
Det kommer att göra 16 byte.
>> Men en nod är fortfarande fyra bitgrupper.
Så här pekaren går vara 8 byte.
Detta är fyra byte.
Så en nod kommer bara att vara 12 byte.
Alla andra frågor om den?
Så nästa, dessa är HTTP-statuskoder.
Och du var tvungen att beskriva omständigheter under vilka dessa kan
tillbaka till dig.
ett problem som jag hörde några studenter har är att de försökt göra
fel att vara på kundens slut.
Så när vi försöker göra begäran till servern, går något
fel på vår ände.
Men generellt är dessa koder som returneras av servern.
Så vi vill ta reda på vad som händer rätt eller fel på servern som
orsakar dessa saker som ska returneras.
Så varför kan en server åter statuskod 200?
Några tankar?
>> Yeah.
Så något om framgång ansökan gick igenom.
Och de är kan återvända vad du bad om.
Så allt var bra.
Vad sägs om 302 hittade?
Yeah.
>> PUBLIK: Servern var ute för vad du begärt.
Men det kunde inte hitta den.
Så det finns ett fel.
>> ROB BOWDEN: Så servern var letar efter vad du ville ha.
Så bara titta här, 302 hittade, den kunde hitta den.
>> PUBLIK: Jag är ledsen.
Hittade innebär att de hittade den.
Ursäkta.
>> ROB BOWDEN: Så 302 hittats.
Servern kan hitta vad du ville.
>> PUBLIK: Men det är inte att visa det?
>> ROB BOWDEN: Skillnaden mellan denna 302 och 200 är att det
vet vad du vill.
Men det är inte precis där du ville fråga.
Så 302 är en typisk omdirigering.
Så du begärt en sida.
Den vet, åh, jag vill ha att återvända dig här.
Men det är på en annan webbadress.
Så hey, du verkligen vill detta.
>> DAVID J. MALAN: Det är en pjäs som sagt att vi gav er en omdirigering
funktion som används rubrik funktion som i sin tur skrivas ut plats,
kolon, och sedan den URL som du vill avvisa användaren.
Även om du inte såg 302 uttryckligen det, är det vad PHP
skulle magiskt sätt in som rubrik att säga exakt vad Rob sade att det -
hittas.
Men gå här istället.
>> ROB BOWDEN: OK.
Så hur är 403 förbjudna?
>> PUBLIK: Jag tycker det är att servern är i princip säger att klienten
kan inte komma åt hemsidan.
>> ROB BOWDEN: Så ja.
Tja, det typiska svaret var vi förväntar sig något liknande, filerna
inte chmodded lämpligt sätt.
Det är antagligen under vilka omständigheter du såg dem.
Men det finns en anledning till att kunden kan vara fel här.
Det finns faktiskt en annan statuskod -
401.
Så dessa är mycket lika.
>> 401 är otillåten.
Och 403 är förbjudet.
Och så obehöriga att du enbart få om du inte är inloggad i.
Men att logga in kan betyda att du är behörig.
Men om du redan är inloggad och du fortfarande har inte behörighet, sedan
du kan också få förbjudna.
Så om du är inloggad och inte har tillåtelse, är förbjudet också
något som du kan få.
>> DAVID J. MALAN: Och den mekanism genom vilket dessa problem är vanligtvis
löst på servern är via vilken kommando?
Chmod, om det är verkligen en behörigheter utfärda på filen eller katalogen.
>> ROB BOWDEN: Sedan 404 hittades inte.
Yeah.
Så till skillnad från 302 där det var inte precis där du frågar, men det vet vad
du vill, det här, bara har det ingen aning om vad du vill.
Och du inte begär något giltigt.
418 Jag är en tekanna och sedan 500 intern server.
Så varför skulle du det?
>> Så segfault -
Jag vet faktiskt inte graderingen standard för detta.
Men om din PHP-kod hade något fel i det, i teorin, kan det
faktiskt segfault, i vilket fall detta 500 internt serverfel, något
är fel med din servers konfiguration.
Eller det finns ett syntaxfel i din PHP-kod.
Eller något hemskt är på gång.
>> DAVID J. MALAN: Vi såg segfault bland några människors svar.
Och tekniskt sett, kan det hända.
Men det skulle vara ett PHP, programmet skrivna av andra människor, faktiskt
segfaulted, vilket endast om dessa personer skruvas upp och skrev buggig kod i
deras tolk skulle PHP i sig segfault.
Så även om 500 är som en segfault i anden, är det nästan alltid den
Resultatet av en konfigurationsfil fråga med din webbserver eller, som Rob sa,
ett syntaxfel, som du inte stänga en offert.
Eller du förlorat ett semikolon någonstans.
>> PUBLIK: Så för Shuttle pset, jag tänker när jag gjorde det när jag klickade på
browser, men ingenting kom upp, vad de kallade vit sida.
Men det var på grund av koden.
Jag tror att det var JavaScript, eller hur?
>> ROB BOWDEN: Ja.
>> PUBLIK: Skulle felet fortfarande komma upp?
>> ROB BOWDEN: Så du skulle inte ha fått detta fel eftersom allt
från webbservern perspektiv var helt bra.
Men du begärt index.html.
Du begärde shuttle.js och service.js.
Och det kunde framgångsrikt återvända till er alla dessa saker -
200.
OK.
Det är bara när webbläsaren försökte tolka JavaScript-kod som
det är som att, vänta, det är inte giltiga JavaScript-fel.
Fler frågor?
Okej.
>> DAVID J. MALAN: Så nästa upp var nummer 11.
Och 11 var den mest skrämmande för många människor.
Så det viktigaste att notera här var att detta var, sannerligen, om
en dubbelt länkad lista.
Men det var inte samma som förra årets dubbelt länkad lista problem,
vilket inte gav dig det förbehållet att listan kan faktiskt vara osorterat.
>> Så det faktum att listan var osorterat och det faktum att det ordet var
struken det var tänkt att förmedla att detta faktiskt är en förenkling
av vad som annars skulle ha varit en mer utmanande problem
och en längre.
Så ett vanligt misstag här var att ha lagt förra årets lösning på en
personsökare och sedan bara blint kopiera den ner som svar, vilket är rätt
svara på en annan fråga liknande anda.
Men subtiliteter här var följande.
>> Så en, vi har en nod deklarerat och definieras på det vanliga sättet här.
Sedan definierade vi listan med en global pekare initieras till null.
Sen tydligen finns det två funktioner Vi har prototyper till här, insats
och ta bort.
Och sedan har vi några exempelkod här att göra en massa insättningar.
Och så ber vi dig att fylla i genomförande av insatsen nedan i sådan
sätt att den infogar n in i listan i konstant tid, underströk också,
även om den redan är närvarande.
>> Så skönheten i att kunna sätta in i konstant tid är att det innebär
att du måste sätta in den nya noden där?
Into the front.
Så det eliminerar, tack och lov, åtminstone en av de ärenden som tidigare krävde
ännu fler rader kod, som det gjorde förra året och även i klassen när vi
pratat igenom sånt med människor och med viss
verbal pseudokod.
Så i lösningen här, låt oss hoppa över till att bara ha en visuellt på
skärmen.
>> Lägg märke till att vi gör följande.
Och också att märka den andra förenklingar var att även om det är
redan finns, så det betyder även om numret är redan där, du kan
bara blint sätta in en annan kopia av den.
Och det också var tänkt att vara en förenkling, så att du kan
fokusera på, egentligen, några av de mer intellektuellt intressant del och
inte bara några extra felkontroll med tanke på den begränsade tid.
>> Så i denna provlösning, vi fördela en pekare på vänster
sida här till en nod.
Nu, inser att pekare, som Rob säger, är bara 32 bitar.
Och det behöver inte faktiskt innehåller en adress tills du
tilldela den adressen.
Och vi gör det på den högra sida via malloc.
Som en god medborgare, kontrollerar vi att malloc inte, i själva verket, null, så att
vi inte av misstag skapa en segfault här.
Och varje gång du använder malloc i livet, du ska kolla efter null, lest
du har en subtil bugg.
>> Då initiera vi att noll genom tilldela n och tidigare och nästa.
Och i det här fallet, jag initieras tidigare till noll, eftersom det nya
nod kommer att bli den nya början på min lista.
Så det kommer att bli ingenting innan.
Och jag vill i huvudsak bifoga befintlig lista till den nya noden med
inställningen nästa lika att lista sig.
Men jag är inte klar ännu.
Så om själva listan redan fanns, och det fanns minst en nod
redan finns på plats, om detta är den lista här och jag sätter in en ny nod här, jag
måste se till att min tidigare nod pekar bakåt till min nya noden,
eftersom detta är, återigen, en dubbelt länkad lista.
>> Så vi gör en sundhetskontroll.
Om listan inte är noll, om det finns redan en eller flera noder där, då
tillägga att tillbaka referens så att säga.
Och sedan det allra sista vi behöver göra är att faktiskt uppdatera den globala
variabel lista sig till punkt till den nya noden.
Yeah.
>> PUBLIK: I Pilpekaren [OHÖRBAR] är lika med noll, gör att
hantera listan eftersom listan är noll?
>> DAVID J. MALAN: Nope.
Det är helt enkelt att jag är proaktivt försiktig, i det att om detta är mitt
ursprungliga listan med kanske några fler noder hit och jag sätter i mitt
nya noden över här, har det gå att vara något över här.
Och jag vill fånga den idén genom att ställa in tidigare till
null om den nya noden.
Och förmodligen, om min kod är korrekt och det finns inget annat sätt att infoga
andra än denna funktion noder, förmodligen, redan har, även om listan
en eller flera noder i det, förmodligen den lista, den första noden, skulle ha en
tidigare pekare av null själv.
>> PUBLIK: Och bara en uppföljning.
Anledningen till att du sätter pekaren nästa jämlikar Listan är du gör pekaren
innan listan i att den pekar till nästa, antar jag -
Jag inte -
bara listar?
>> DAVID J. MALAN: Exakt.
Och så låt oss faktiskt överväga två fall här egentligen, även om
För vi ska betrakta dem är inte riktigt samma som koden.
Men på en hög nivå, om detta utgör listan och detta är en 32-bitars
pekare, är det enklaste scenariot att detta är null som standard.
Och antar att jag vill infoga nummer 50 var det första numret.
Så jag ska gå vidare och fördela en nod, som kommer att innehålla
tre områden -
n tidigare, och nästa.
>> Jag kommer att sätta nummer 50 här, eftersom detta kommer att bli n.
Detta kommer att bli nästa.
Och detta kommer att bli tidigare.
Och så vad gör jag i det här fallet?
Tja, jag har precis gjort linje 1 här.
Pointer n blir n..
Jag då säger, tidigare borde bli null.
Så det här kommer att bli noll.
Då ska jag säga nästa kommer att få listan.
>> Och detta bara fungerar bra.
Detta är null.
Och så jag säger, den nya noden nästa område bör få vad detta är.
Så det sätter en annan null där.
Och sedan det sista Jag är kolla här.
Om listan inte är lika med noll, men det är lika med noll, så vi hoppar över att
helt och hållet.
Och så allt jag gör härnäst är listan blir pekare, som bildmässigt resulterar i
en bild så.
Så det är ett scenario.
>> Och det som du frågade om specifikt är en situation som denna,
där vi redan har en en-nod lista.
Och om jag går tillbaka upp i den ursprungliga problemformuleringen, nästa vi kommer
infoga säga är 34, bara för skull diskussionen.
Så jag ska bara bekvämt rita det här borta.
Jag har precis malloced.
Låt oss anta att jag kollar på null.
>> Nu ska jag initiera n att vara 34.
Och detta kommer att bli n.
Detta kommer att bli nästa.
Och detta kommer att bli tidigare.
Låt oss se till att jag inte gjorde det få detta bakåt.
Tidigare kommer först i definitionen.
Jag löser det här.
Detta är tidigare.
Det här är nästa.
Även om dessa är identiska, låt oss hålla det konsekvent.
>> Föregående.
Det här är nästa.
Så jag har bara malloced min anmärkning, kontrolleras för null, tilldelade 34 in i noden.
Föregående blir null.
Så det ger mig det.
Nästa blir listan.
Så listan är detta.
Så det är samma nu som att dra detta arrow, så att de pekar på en
i samma.
Och sedan jag kontrollera om listan inte är lika med noll.
Och det är inte den här gången.
Sen kommer jag att göra-lista tidigare får pekaren.
>> Så lista tidigare blir PTR.
Så det här har effekten av att lägga en grafisk pil här.
Och det börjar bli lite vågig, raderna.
Och sedan, slutligen, uppdatera jag lista för att peka på pekare.
Så nu detta pekar på den här killen.
Och nu, låt oss göra en snabb sundhetskontroll.
>> Här är listan, vilket är den globala variabeln.
Den första noden är, faktiskt, 34, eftersom Jag följer den pilen.
Och det är rätt att jag vill sätt in i början av listan
alla nya noder.
Hans nästa fält leder mig till den här killen.
Om jag fortsätter att gå, jag slog nästa är null.
Så det finns ingen mer lista.
Om jag träffade tidigare, får jag tillbaka där jag förväntar mig.
>> Så det finns fortfarande några tips, uppenbarligen, att manipulera.
Men det faktum att du fick höra att göra detta i konstant tid innebär att du bara
har ett ändligt antal saker du är tillåtet att göra.
Och vad är det numret?
Det kan vara ett steg.
Det kan vara två.
Det kan vara 1.000 steg.
Men det är ändlig, vilket innebär att du inte kan har någon form av looping pågår
här, ingen rekursion, inga loopar.
Det bara måste vara hårdkodade linjer av kod som vi har i detta prov.
>> Så nästa problem 12 bad oss slutföra genomförandet av remove
nedan på ett sådant sätt att den tar bort n från listan i linjär tid.
Så du har lite mer wigglerum nu.
Du kan anta att n, om den finns i listan, kommer att närvara
inte mer än en gång.
Och som också är tänkt att vara en frågesport-baserad förenklande antagandet, så
att om du hittar nummer 50 någonstans i listan, behöver du inte också
behöver oroa sig för att fortsätta iterera, letar efter alla möjliga
kopia av 50, vilket bara skulle överlåta i någon minutiae i begränsad tid.
>> Så med ta bort, den här var definitivt mer utmanande och mer
kod för att skriva.
Men vid första anblicken, ärligt talat, kan det ser överväldigande och som något
det finns inget sätt du kan få komma med på en frågesport.
Men om vi fokuserar på de enskilda stegen, Förhoppningsvis kommer det plötsligt
slå dig om att var och en av dessa individuella steg gör uppenbara mening
i efterhand.
Så låt oss ta en titt.
>> Så först, initiera vi pekare vara själva listan.
Eftersom jag vill ha linjär tid, det betyder Jag kommer att ha en viss slinga.
Och ett vanligt sätt att iterera över noder i en liststruktur eller någon form
med strukturen iterativt är att ta en pekare till den främre delen av den registrerade
struktur och sedan bara börja uppdatera det och gå din väg
genom datastrukturen.
Så jag kommer att göra just det.
>> Medan pekare, min tillfälliga variabel, inte är lika med noll, låt oss
gå vidare och kolla.
Fick jag lycklig?
Är det n fältet i noden är jag idag tittar på lika med
nummer jag letar efter?
Och i så fall, låt oss göra något.
Nu märker detta om villkor omger hela
Följande kodrader.
Detta är det enda jag bryr mig om - att hitta en rad i fråga.
Så det finns ingen annanstans, vilket förenklar saker begrepps lite.
>> Men nu insåg jag, och du kan ha bara insåg detta efter att ha tänkt
det genom en bit, det finns faktiskt två fall här.
En är där noden är vid början av listan, vilket är en
lite irriterande, eftersom det är en specialfall, eftersom du måste ta itu
med denna sak, som är den enda anomali.
Överallt annars i listan, det är samma sak.
Det finns en tidigare nod och ett nästa nod, tidigare nod, nästa nod.
Men den här killen är lite speciell om han är i början.
>> Så om pekaren är lika listan sig själv, så om jag är i början av
listan och jag har hittat n, jag behöver att göra ett par saker.
Man, jag behöver ändra listan till pekar på det nästkommande fältet, 50.
Så antar att jag försöker för att ta bort 34.
Så den här killen fick gå bort på bara ett ögonblick.
>> Så jag ska säga, lista blir pekaren nästa.
Nåväl, detta är pekare.
Nästa pekar hit.
Så detta förändras denna pil höger nu för att peka på den här killen här.
Nu, kom ihåg, vi har en temporär variabel.
Så vi har inte föräldralösa några noder, eftersom jag också har den här killen i min
genomförandet av remove.
Så nu, är om listan i sig inte är noll, Jag behöver rätta till en liten sak.
>> Jag måste nu se till att den här pilen, som tidigare pekar
50-34, har detta att gå bort, för om jag försöker bli
av 34, 50 hade bättre inte behålla någon typ av tillbaka referens till det som
pil föreslog.
Så jag gjorde just denna linje.
Så då jag är klar.
Detta mål är faktiskt ganska lätt.
Hugga av huvudet av listan är relativt rättfram.
>> Tyvärr, det är det här irriterande annat block.
Så nu har jag att behandla ärendet där det finns något i mitten.
Men det är inte så hemskt, utom för syntax som denna.
Så om jag inte är i början av den lista, jag är någonstans i mitten.
Och denna linje här säger, start oavsett på vilken nod som du är på.
Gå till föregående nodens nästa fält och pekar att vid pekaren.
>> Nu gör vi det bildmässigt.
Det började bli komplicerad.
Så om jag har ett tidigare fält här - låt oss göra detta - nästa fält här.
Jag kommer att förenkla mina pekare snarare än dra en hel massa
saker fram och tillbaka kors och tvärs varandra.
Och nu, låt oss bara säga att det är 1, 2, 3 av hänsyn till diskussionen, och med
men som inte stämmer med problemet i fråga.
>> Så här är min länkad lista.
Jag försöker att ta bort två i detta särskild version av berättelsen.
Så jag har uppdaterat pekare till peka på den här killen.
Så det här är PTR.
Han pekar här.
Detta är listan, som föreligger globalt som tidigare.
Och han pekar här oavsett vad.
Och nu, jag försöker att ta bort två.
>> Så om pekaren pekar här, jag är kommer att följa, som synes, den
föregående pekare, som sätter mig på 1.
Jag sedan kommer att säga att nästa område, vilket leder mig över till detta
rutan här, kommer att lika pekare intill.
Så om detta pekare, är detta nästa.
Det innebär att denna pil behov att peka på den här killen.
>> Så vad som kodrad har bara gjort är lite av detta.
Och nu, det ser ut som en steg i rätt riktning.
Vi vill i huvudsak att klippa två ut i mitten av ett och tre.
Så det är logiskt att vi vill drar denna pekare runt den.
Så här nästa rad kontrollerar om pekare Nästa är inte noll, det finns
indeed någon till höger om två, det innebär att vi också måste göra
lite snip här.
>> Så jag måste nu följa detta pekare och uppdatera den tidigare pekaren på
den här killen för att göra lite av en komma runt här poängen här.
Och nu, det är visuellt trevligt.
Det är lite rörigt i att det finns ingen en pekar på två längre.
2 pekar åt vänster.
Och 2 pekar åt höger.
Men han kan göra vad han vill, eftersom han är på väg att bli befriad.
Och det spelar ingen roll vad dessa värden är längre.
>> Det som är viktigt är att den återstående killar routing ovan
och under honom nu.
Och faktiskt, det är vad vi ska göra härnäst.
Vi fri pekare, vilket innebär att vi berättar operativsystem, är du välkommen
att återta detta.
Och så slutligen återvänder vi.
Else förstått, om vi har inte kommit tillbaka ännu,
vi måste fortsätta leta.
Så pekaren är lika med pekaren intill bara innebär att flytta den här killen här.
Flytta den här killen här.
Flytta den här killen här om, i själva verket vi hittade inte numret
vi söker ännu.
>> Så ärligt talat, det ser helt överväldigande, tror jag, i första
blick, särskilt om du kämpade med detta under testet sedan se
ungefär så här.
Och du klappa dig själv på ryggen.
Tja, det finns inget sätt jag kunde ha komma med det på frågesport.
Men jag skulle vilja hävda, du kan om du bryter det i dessa individuella
fall och bara gå igenom det omsorgsfullt, om än visserligen under
stressande förhållanden.
>> Tack och lov, den bild som skapas allt lyckligare.
Du kan dra det här i ett antal olika sätt.
Du behöver inte göra det kors och tvärs sak här.
Du kan göra det med rak linjer som denna.
Men kontentan av detta problem, i allmänhet var att inse att den
Bilden till slut skulle se lite ungefär så här, eftersom
konstant tid innebar att du håller fastnar och fastnar och störa ut
nya noder i början i listan.
Några frågor?
Förmodligen den mest utmanande av förvisso de kodande frågor.
>> PUBLIK: Så är listan liknar huvudet i tidigare exempel.
>> DAVID J. MALAN: Exakt, exakt.
Bara ett annat namn för en global variabel.
World wide vad?
>> ROB BOWDEN: OK.
Så det här är den där du var tvungen att skriva punkt.
Vissa människor skrev essäer för denna fråga.
Men du behöver bara använda dessa sex villkor att beskriva vad som händer när
du försöker kontakta facebook.com.
Så jag ska bara prata igenom processen genom att använda alla dessa villkor.
Så i vår läsar skriver vi facebook.com och tryck på Retur.
Så vår webbläsare kommer att konstruera en HTTP begära att det kommer att skicka
genom någon process till Facebook för Facebook att reagera på oss med
HTML på sin sida.
>> Så vad är den process genom vilken HTTP-begäran
faktiskt kommer till Facebook?
Så först måste vi översätta Facebook.com.
Så bara fick namnet Facebook.com, där faktiskt gör HTTP-begäran
måste gå?
Så vi behöver översätta Facebook.com till en IP-adress, som unikt
identifierar vilken maskin vi faktiskt vill skicka förfrågan till.
Din bärbara dator har en IP-adress.
Något som är ansluten till Internet har en IP-adress.
>> Så DNS, Domain Name System, är det vad som kommer att hantera översättning
från facebook.com till en IP-adress som du verkligen vill kontakta.
Så vi kontakta DNS-servrar och säg, vad är facebook.com?
Den säger, åh, det är IP-adress 190,212 något, något, något.
Okej.
Nu vet jag vad maskin Jag vill kontakta.
>> Så då du skickar din HTTP-begäran över till den maskinen.
Så hur det blir med den maskinen?
Tja, går en begäran från router till router studsande.
Minns exemplet i klassen, där vi faktiskt såg den väg som den
paket tog när vi försökte att kommunicera.
Vi såg den hoppa över Atlanten Ocean på en punkt eller vad som helst.
>> Så den sista termen porten.
Så detta är nu på din dator.
Du kan ha flera saker idag kommunicerar med Internet.
Så jag kan köra, säg, Skype.
Jag kanske har en webbläsare öppen.
Jag kanske har något som torrenta filer.
Så alla dessa saker är som kommunicerar med den
internet på något sätt.
>> Så när din dator tar emot en del data från internet, hur fungerar det
vet vad programmet faktiskt vill ha uppgifterna?
Hur vet den om detta uppgifter är avsedd för
torrenta tillämpning i motsats till webbläsaren?
Så detta är syftet med hamnar i det alla dessa program har
hävdade en port på datorn.
Så din webbläsare säger, hej, Jag lyssnar på port 1000.
Och din torrenta programmet säger, Jag lyssnar på port 3000.
Och Skype säger, jag använder port 4000.
>> Så när du får lite uppgifter som hör till en av dessa tillämpningar, data
är märkt med vilken port det faktiskt ska skickas med till.
Så här säger, åh, jag tillhör till port 1000.
Jag vet då jag måste vidarebefordra denna tillsammans med min webbläsare.
Så anledningen till att det är relevant här är att webbservrar brukar
lyssna på port 80.
Så när jag kontaktar Facebook.com, jag är kommunicerar med vissa maskin.
Men jag måste säga vilken hamn som maskin som jag vill kommunicera med.
Och webbservrar brukar vara lyssnar på port 80.
>> Om de ville, de kunde ställa in den upp så att den listar som på port 7000.
Och sedan i en webbläsare, jag kunde manuellt skriva Facebook.com: 7000 till
skicka förfrågan till port 7000 av Facebooks webbserver.
>> DAVID J. MALAN: Och i detta fall, till och med även om vi inte kräver att människor
nämner detta, i det här fallet, vilken port skulle begäran faktiskt gå till?
Försök igen.
Exakt.
Inte ute efter det, men en finess det är det ingen sista.
>> ROB BOWDEN: Så HTTPS, eftersom det är lyssnar specifikt för
krypterad, det är på port 4430.
>> Publik: Och e-post är 25, eller hur?
>> DAVID J. MALAN: Outbound e-post, 25, japp.
>> ROB BOWDEN: Jag vet inte ens de flesta av den - som alla de lägre tenderar att vara
reserverade för saker.
Jag tror att allt under 1024 är reserverad.
>> PUBLIK: Varför sa du 3 var fel nummer?
>> ROB BOWDEN: För i en IP-adress, Det finns fyra grupper av siffror.
Och de är från 0 till 255.
Så 192.168.2.1 är en vanlig lokalt nätverk IP-adress.
Lägg märke till alla de som är mindre än 255.
Så när jag började med 300, att kunde omöjligen ha
varit ett av numren.
>> DAVID J. MALAN: Men det dumma klipp från - var det CSI, där de hade en
nummer som var för stor för IP-adressen.
>> ROB BOWDEN: Har du frågor om detta?
Den nästa, så fullständig förändring i ämne, men vi har denna PHP-array för
husen i quad.
Och vi har en oordnad lista.
Och vi vill skriva ut varje post i listan bara innehåller huset namnet.
Så vi har en foreach loop.
Så kom ihåg, syntaxen är foreach array som objekt i arrayen.
Så genom varje iteration av slingan, Huset kommer att ta på en av de
värden inne i matrisen.
>> På den första iterationen, hus blir Cabot House.
På en andra iteration, hus kommer vara Courier hus och så vidare.
Så för varje quad som hus, vi är bara att skriva ut -
du kan också ha ekade -
listobjektet och sedan husets namn och stäng sedan listobjektet.
Klammer hängslen är valfria här.
>> Och då sa vi också i fråga sig själv, kom ihåg att stänga
oordnad lista tag.
Så vi måste gå ur PHP-läge för att göra detta.
Eller vi kunde ha ekade stäng oordnad lista tag.
>> DAVID J. MALAN: Också bra här skulle har varit att använda en gammal skola för
slinga med en $ i = 0 0 och använda räknas till räkna ut längden på strålen.
Helt bra också, precis lite wordier.
>> PUBLIK: Så om ni skulle [OHÖRBAR], skulle du göra -
Jag glömmer vad slingan [OHÖRBAR] är.
Skulle du $ quad fäste jag?
>> DAVID J. MALAN: Exakt.
Ja, exakt.
>> ROB BOWDEN: Något annat?
>> DAVID J. MALAN: Okej.
Avvägningar.
Så det fanns knippen av svaren möjligt för var och en av dessa.
Vi var egentligen bara ute efter något övertygande för en upp-och
en nackdel.
Och nummer 16 frågade, validera användare " ingång på klientsidan, som med JavaScript
istället för serversidan, som med PHP.
Så vad är en uppsida på gör klientsidan?
>> Tja, är en av de saker som vi föreslagit att du minskar latensen, eftersom du
behöver inte bry kontakta server, vilket kan ta några
millisekunder eller ens ett par sekunder genom att undvika det och bara
validering av användarnas input klientsidan genom utlöser en på-lämna handler och
bara kolla, de skriver något för namn?
Har de skriver något in för e-postadress?
Har de väljer en sovsal från rullgardinsmenyn?
>> Du kan ge dem omedelbar respons använder gigahertz dator
eller vad de har som är faktiskt på sitt skrivbord.
Så det är bara en bättre användar typiskt erfarenhet.
Men en nackdel med att göra på klientsidan validering, om du gör det utan att också
göra validering på serversidan är att de flesta någon som kommer ut av CS50 vet
att du bara kan skicka alla data som du vill till en server som helst antal sätt.
Ärligt talat, de flesta alla webbläsare kan du klicka runt i inställningarna och bara
stänga av JavaScript, som, Därför inaktivera alla former av
validering.
>> Men du också kanske kommer ihåg att även jag gjorde några mystiska saker i klass med hjälp av
telnet och faktiskt låtsas vara en webbläsare genom att skicka get
förfrågningar till en server.
Och det är verkligen inte med användning av någon JavaScript.
Det är bara jag skriva kommandon vid ett tangentbord.
Så egentligen, någon programmerare inom tillräckligt komfort med webben och HTTP
kunde skicka de data som han eller hon vill till en server utan validering.
Och om din server inte också kontroll, gav de mig ett namn, är
detta faktiskt en giltig e-postadress, gjorde de väljer en sovsal, kan du sluta
upp sätta in falska eller bara tom uppgifter in i din databas, vilket troligen
kommer inte att vara bra om du räknade med att det var där.
>> Så detta är en irriterande verklighet.
Men i allmänhet, klientsidan validering är stor.
Men det betyder dubbelt så mycket arbete.
Även om det existerar olika bibliotek, JavaScript-bibliotek för
exempel att göra detta mycket, mycket mindre av en huvudvärk.
Och du kan återanvända en del av koden serversidan, klientsidan.
Men inser att det är normalt merarbete.
Yeah.
>> PUBLIK: Så om vi bara sa mindre säker -
>> DAVID J. MALAN: [skratt]
Ugh.
De är alltid svårare som ska döma.
>> ROB BOWDEN: Det skulle har godkänts.
>> DAVID J. MALAN: Vad?
>> ROB BOWDEN: Jag skapade det här problemet.
Det skulle ha godkänts.
>> DAVID J. MALAN: Ja.
>> PUBLIK: Cool.
>> ROB BOWDEN: Men vi accepterade inte för det första en -
bra, det vi söker efter är något som du inte behöver
kommunicera med servern.
Vi accepterade inte bara snabbare.
>> PUBLIK: Hur är inte ladda om sidan?
>> ROB BOWDEN: Ja.
Det var ett accepterat svar.
>> DAVID J. MALAN: Allt där vi kände det var mer troligt än inte troligt
att du visste vad du var säger, vilket är en tuff
linje för att rita ibland.
Med hjälp av en länkad lista istället i en matris för att upprätthålla en
sorterad lista med heltal.
Så en upp och vi ofta citera med länkade listor som motiverade sin helhet
introduktion var du dynamik.
De kan växa.
De kan krympa.
Så du behöver inte hoppa genom fälgar att faktiskt skapa mer minne
med en array.
Eller du behöver inte bara säga, förlåt, användare.
Matrisen är fylld.
Så dynamisk tillväxt av listan.
En nackdel dock av länkade listor?
>> PUBLIK: Det är linjär.
Sökning på länkad lista är linjär istället för vad du loggar in
>> DAVID J. MALAN: Exakt.
Söka på en länkad lista är linjär, även om den är sorterad, eftersom du kan
bara följa dessa brödsmulor, dessa pekare, från början av listan
till slutet.
Du kan inte utnyttja random access och, sålunda, binär sökning, även om det är
sorteras, att du kunde göra med en array.
Och det finns också en annan kostnad.
Yeah.
>> PUBLIK: Minne ineffektiv?
>> DAVID J. MALAN: Ja.
Tja, jag skulle inte nödvändigtvis säga ineffektivt.
Men det kostar dig mer minne, eftersom du behöver 32 bitar för varje
nod för den ytterligare pekare, vid stone för en enskilt länkad lista.
Nu, om du bara vill lagra heltal och du lägger pekaren, det är
faktiskt slags icke-trivial.
Det är en fördubbling av mängden minne.
Men i verkligheten, om du lagrar en länkad lista av structs som kan ha
8 byte, 16 byte, ännu mer än så, kanske är mindre
av en marginalkostnad.
Men det är en kostnad ändå.
Så någon av dem skulle har varit bra som nackdelar.
>> 18.
Använda PHP istället för C att skriva en kommandorad program.
Så här är det ofta snabbare att använda en språk som PHP eller Ruby eller Python.
Du bara snabbt öppna upp en textredigerare.
Du har många fler funktioner tillgängliga för dig.
PHP har diskbänken av funktioner, medan i C, du
har mycket, mycket lite.
Faktum är killar det vet den hårda vägen att du inte har hashtabeller.
Du behöver inte ha länkade listor.
Om du vill ha dem, måste du genomföra dem själv.
>> Så en uppåt av PHP eller egentligen något tolkat språk är snabbheten
med vilken du kan skriva kod.
Men en nackdel, vi såg detta när jag snabbt piskade upp en misspeller
genomförande i föreläsning med PHP, är att med hjälp av ett tolkat språk
är oftast långsammare.
Och vi såg att bevisligen med en öka i tid från 0,3 sekunder till 3
sekunder, på grund av tolkningen som faktiskt händer.
>> En annan uppåtsidan var att du behöver inte kompilera.
Så det snabbar också upp utvecklingen för övrigt, eftersom du inte har
två steg för att köra ett program.
Du har bara en.
Och så det är ganska övertygande också.
Genom att använda en SQL-databas istället för att en CSV-fil för att lagra data.
Så SQL databas används för pset7.
CSV-filer som du inte använder mycket.
Men du använde det indirekt i pset7 som väl genom att tala med Yahoo Finance.
>> Men CSV är precis som en Excel-fil, men super enkelt, där kolumnerna är
bara demarked med kommatecken inne av en annars textfil.
Och med hjälp av en SQL-databas är lite mer övertygande.
Det är en upp, eftersom du får saker liksom välja och infoga och ta bort.
Och du får, förmodligen, index som MySQL och andra databaser, t.ex.
Oracle, bygga för dig i minnet, vilket innebär att din select är förmodligen inte
kommer att vara linjär topp till botten.
Det är faktiskt kommer att bli något som binär sökning eller något
liknande anda.
Så de är i allmänhet snabbare.
>> Men en nackdel är att det är bara mer arbete.
Det är mer ansträngning.
Du måste förstå databaser.
Du måste ställa in den.
Du behöver en server för att köra databasen på.
Du måste förstå hur man konfigurerar den.
Så det är bara dessa typer av kompromisser.
En CSV-fil, kan du skapa den med gedit.
Och du är bra att gå.
Det är ingen komplicerad än så.
>> Med hjälp av en trie stället för en hashtabell med separat kedja för att lagra en
lexikon över ord som påminner av pset5.
Så en försöker upp i teorin åtminstone, är vad?
Konstant tid, åtminstone om du är hashing på var och en av de enskilda
bokstäver i ett ord, som du kan ha för pset5.
Det kan vara fem hash, sex hashar om det finns fem eller sex
bokstäverna i ordet.
Och det är ganska bra.
Och om det finns en övre gräns för hur länge dina ord kan vara, det är
indeed asymptotiskt konstant tid.
>> En hash-tabell med separat kedja, problemet där med att
typ av datastruktur är att den resultatet av dina algoritmer vanligtvis
beror på flera saker redan i datastrukturen.
Och det är definitivt fallet med kedjor, varvid mer grejer du sätter
in i en hash-tabell, ju längre de kedjor gå, vilket innebär i värsta
fall, det du kanske letar efter är hela vägen vid slutet av en
av dessa kedjor, som effektivt ankommer till något linjär.
>> Nu, i praktiken kan det absolut vara så att en hash-tabell med
kedjorna är snabbare än en motsvarande trie genomförande.
Men det är av olika skäl, bland som försöker använda en hel del
minne som kan, i själva verket, långsamt saker ner, eftersom du inte får bra
fördelarna med något som kallas caching, där saker som är nära varandra
i minnet kan nås ofta snabbare.
Och ibland kan man komma med en riktigt bra hashfunktion.
Även om du har att slösa bort lite av minne, du kanske faktiskt kunna
hitta saker snabbt och inte så illa som linjärt.
>> Så kort sagt, det var inte nödvändigtvis med någon av dessa en eller till och med två
specifika saker som vi sökte.
Verkligen något övertygande som en upp-och nedsidan
allmänhet fångade vårt öga.
>> ROB BOWDEN: Så för uppåtsidan, vi gjorde inte acceptera på egen hand "snabbare." Ni
hade att säga något om det.
Även om du sa teoretiskt snabbare, Vi visste att du slags förstått
att det är 0 av 1.
Och hashtabell, i teorin, är inte 0 av 1.
Att nämna något om körtid allmänhet fick du poäng.
Men "snabbare," de flesta av lösningarna på den stora styrelsen som försöker var
objektivt långsammare än lösningar det var hashtabeller.
Så snabbare i och för sig är inte riktigt sant.
>> DAVID J. MALAN: Dom de dom dom.
Jag är nog den enda som inser det är hur det är tänkt att
uttalas, eller hur?
>> ROB BOWDEN: Jag hade faktiskt ingen aning.
>> DAVID J. MALAN: Det gjorde känsla i mitt huvud.
>> ROB BOWDEN: Jag gör det här.
OK.
Så det här är den där du var tvungen att dra diagrammet liknar du kanske
har sett på tidigare tentor.
Så låt oss titta bara på det här.
Så från HTML-nod, vi har två barn, huvudet och kroppen.
Så vi gren - huvud och kropp.
Huvudet har en titel tagg.
Så vi har en titel.
>> Nu, en sak en massa människor glömt är att dessa textnoder är
element inom detta träd.
Så här råkar vi att dra dem som ovaler för att skilja dem från dessa
typer av noder.
Men varsel även här har vi toppen, mitten och botten kommer att hamna
textnoder.
Så glömmer dem var något av ett vanligt misstag.
>> Kroppen har tre barn - dessa tre divs.
Så div, div, div och sedan texten nod barn i dessa divar.
Det är ganska mycket det för att frågor.
>> DAVID J. MALAN: Och det är värt att notera, även om vi inte uppehålla mig vid dessa
detaljer i den tid vi spenderar på JavaScript, som ordern gör, i
Faktum är, oavsett tekniskt.
Så om huvudet kommer före kropp i HTML, då det ska visas att den
kvar i kroppen i själva DOM.
Att hans är, i allmänhet, bara FYI, något som kallas dokument ordning, där
det spelar roll.
Och om du genomföra en parser, ett program som läser HTML i byggnad
upp i trädet i minnet, för att vara ärlig, det är intuitivt nog vad du
göra ändå - uppifrån och ned, vänster till höger.
>> ROB BOWDEN: Frågor på det?
Ska jag göra nästa?
>> DAVID J. MALAN: Visst.
>> ROB BOWDEN: OK.
Så detta är den buffertöverskridning attack fråga.
Det viktigaste att inse här är, väl, hur kan en motståndare trick
detta program till att köra godtycklig kod?
Så argv1, den första kommandoraden Argumentet för detta program, kan det vara
godtyckligt lång.
Men här vi använder memcpy att kopiera argv1, vilket här är bar.
Vi passerar det som argument.
Och så det tar på namnfältet.
>> Så vi memcpying bar i denna buffert c..
Hur många bytes vi kopierar?
Jo men många byte bar händer använder, längden på detta argument.
Men c är bara 12 byte bred.
Så om vi skriver en kommandorad argument som är längre än 12 byte, vi är
kommer att svämma över detta speciella buffert.
Nu, hur kan en motståndare lura programmera in att köra godtycklig kod?
>> Så kom ihåg att här Huvud ringer foo.
Och så då huvud samtal foo.
Låt oss göra detta.
Så vi har vår stack.
Och huvud har en stack ram vid bottnen.
Vid något tillfälle, huvud samtal foo.
Tja, omedelbart, huvud samtal foo.
Och så foo får sin egen stack ram.
>> Nu, någon gång, foo kommer att återvända.
Och gick foo avkastning, måste vi veta på vilken kodrad inuti huvud vi
var för att veta var Vi bör återupptas i main.
Vi kan kalla foo från helhet massa olika ställen.
Hur vet vi var de ska återvända?
Tja, vi måste lagra det någonstans.
>> Så någonstans runt här, vi lagrar där vi bör återgå till en gång
foo avkastning.
Och detta är den returadress.
Så hur en motståndare kan utnyttja av detta är det faktum att
denna buffert c lagras, låt oss säga, här är c..
Så vi har 12 byte för c..
Det här är c..
Och detta är foo stack ring.
Så om det skadliga användaren anger mer byte än 12 eller så anger ett kommando
line argument som är längre än 12 tecken, då vi kommer att
flöda över denna buffert.
>> Vi kan hålla igång.
Och någon gång, vi går långt nog att vi börjar
skriva över denna returadress.
Så när vi skriver över avsändaradressen, detta innebär att när foo
avkastning, vi återvänder till varhelst angripare säger till den att genom
oavsett värde det in, oberoende av hur tecken användaren angett.
Och så om den angripare är att särskilt smart, kan han ha denna
återvända till någonstans i printDef funktion eller någonstans i malloc
funktion, var som helst godtycklig.
>> Men ännu mer smart är det som om han har användaren återvända till just här.
Och då du börjar köra dessa som rader kod.
Så på den punkten, kan användaren ange vad han vill in i denna region.
Och han har fullständig kontroll över ditt program.
Frågor på det?
Så nästa fråga är klar reimplementation av foo på ett sådant sätt
att det inte längre är utsatta.
>> Så det finns ett par sätt du kunde ha gjort det här.
Vi har fortfarande c endast vara av längden 12.
Du kan ha ändrat detta som en del av lösningen.
Vi har också lagt till en kontroll att göra säkert bar var inte noll.
Även om du inte behöver att för full poäng.
Så vi kollar först stränglängd bar.
Om det är större än 12, då faktiskt inte göra kopian.
Så det är ett sätt att fastställa det.
>> Ett annat sätt att fastställa att det är i stället för har c bara ha längden 12, har det
ha längden strlen (bar).
Ett annat sätt att fastställa att det är att faktiskt bara tillbaka.
Så om du hade just fått bort alla detta, om du bara hade tagit bort alla
rader kod, skulle du ha fått full kredit, eftersom denna funktion
egentligen inte uträtta något.
Den kopierar kommandoraden argument i någon samling i
dess lokala stacken ramen.
Och sedan den saken återvänder.
Och vad det åstadkommit är borta.
Så avkastningen var också en tillräcklig sätt att få full kredit.
>> DAVID J. MALAN: Inte riktigt anda frågan men acceptabelt per den
spec ändå.
>> ROB BOWDEN: Frågor om något av detta?
En sak som man åtminstone behövs för att ha kompilera kod.
Så även om du tekniskt sett inte är sårbara om din kod inte
sammanställa, vi inte acceptera det.
Inga frågor?
OK.
>> DAVID J. MALAN: Vill du ha att säga denna titel?
>> ROB BOWDEN: Nej.
>> DAVID J. MALAN: Så i den här, det här var antingen bra eller dåliga nyheter.
Detta är bokstavligen samma problem som den första frågesporten.
Och det är nästan samma problem som pset1.
Men det var avsiktligt förenklats för att vara en enklare pyramid, en som kan vara
lösas med en något enklare iteration.
Och egentligen, vad vi fick på här var inte så mycket logik,
därför sannolikt, vid det här laget, du bekvämare än du var
i veckan en med för slingor eller varför loopar, men egentligen för att reta ifrån varandra att
du är lite bekväm med uppfattningen att PHP är inte bara om vad
programmering.
Den kan faktiskt användas som ett språk att skriva kommandoraden program.
>> Och faktiskt, det är vad vi försökte för att uppmärksamma er på.
Detta är en kommandorad PHP-program.
Så C-kod här, medan korrekt i C, inte korrigera för PHP.
Men koden är egentligen samma.
Om du jämför de lösningar för Quiz 0 mot Quiz 1, ser du att
det är nästan identiska, med undantag för några dollartecken och för
frånvaron av en datatyp.
I synnerhet om vi tar en titt här, ser du att vi iterera, i detta
fall, från 1 upp till 7.
>> Vi kunde ha gjort det 0 index.
Men ibland, jag tror att det bara mentalt lättare att tänka på saker
från 1 till 7.
Om du vill ha ett kvarter, sedan två block, sedan tre, sedan
prick, prick, prick sju.
Vi har j initieras till 1 och sedan räknar upp till mig.
Och allting här är i övrigt identisk.
Men värt att notera är ett par saker.
Vi ger dig dessa två linjer, denna första en, goofily namnges som ett shebang
för kraftig smäll.
Och som bara anger sökvägen, den mapp, i vilken ett program kan vara
fann att du vill använda att tolka den här filen.
>> Och sedan raden efter att av Naturligtvis innebär skriva PHP-läge.
Och linjen längst ner innebär exit PHP-läge.
Och detta fungerar i allmänhet med tolkade språk.
Det är ganska irriterande om du skriver ett program i en fil som heter foo.php.
Och då användarna måste bara minns, OK, för att köra det här programmet, jag
måste skriva "php utrymme foo.php." Kind av irriterande om inte annat.
Och det också avslöjar att ditt program är skriven i PHP, vilket är inte allt
att belysa för användaren.
>> Så du kan ta bort. Php helt och hållet minns från föreläsningen.
Och du kan faktiskt göra. / Foo om du har chmodded det genom att göra det
körbar.
Så chmod a + x foo skulle ha gjort det.
Och om du också lägga till Shebang här.
Men egentligen var det problem att få på skriva ut ungefär så här.
Ingen HTML, ingen C-kod säkert, bara några PHP.
Så Milo återvände sedan i problem 25.
Och i 25, du fick följande skelett-kod, som var en
ganska enkel webbsida.
Och den saftiga delen HTML-wise var nere här, där vi har insidan av kroppen
en form som har en unik ID-ingångar inuti vilken var två ingångar, en
med en idé om namn, en med en idé om knappen.
>> Den första var typ text, den andra av typen in.
Och så vi gav dig, faktiskt, mer ingredienser än vad du behövde, bara så
ni hade alternativ med vilka att lösa detta problem.
Du behöver inte strikt behöver alla dessa ID.
Men det tillåter dig att lösa det på olika sätt.
Och uppe i toppen, märker att målet var att utlösa
ett fönster så här -
Hej, Milo! -
att dyka upp i webbläsaren med hjälp av super enkelt, om
inte ful, varningsfunktion.
Och så, i slutändan leder detta begreppsmässigt på något sätt lyssna efter
inlagor i form klientsidan , Inte på serversidan, på något sätt
svara på detta påstående genom ta tag i värde som användaren skrivit
in till namnfältet, och sedan visar det i kroppen av en varning.
>> Så ett sätt du kan göra detta är med jQuery, som ser lite
syntaktiskt förvirrande i början.
Du kan göra detta med ren DOM-kod - document.getelement med ID.
Men låt oss ta en titt på denna version.
Jag har ett par viktiga linjer först.
Så en, har vi denna linje, vilket är identiskt med det som du kanske har sett
i, tror jag, form2.html från klass i vecka 9.
Och detta är bara säga, exekvera följande kod när
dokumentet är färdigt.
Detta är viktigt bara för att HTML-sidor läses uppifrån och
botten, vänster till höger.
>> Och därför, om du försöker att göra något i koden här uppe till viss DOM
element, en del HTML-tagg, det är ner Här, du gör det för tidigt,
eftersom detta har inte ens lästs in i minnet.
Så genom att säga detta document.ready linje, vi säger,
här är lite kod, webbläsare.
Men inte utföra detta tills hela dokumentet är färdigt, är att DOM
träd förekommer i minnet.
Den här är lite mer okomplicerad, om syntaktiskt en
lite annorlunda, då jag säger, grab HTML-element vars unika
Identifieraren är ingångar.
Det är vad det hash-taggen betecknar den unika ID.
Och då jag ringer. Skicka.
>> So. Inkomma här är en funktion, annars känd som en metod, som är
insidan av objekt på vänster sida där som jag inte lyfta.
Så om du tänker på insatsvaror som ett objekt i minnet - och faktiskt är det.
Det är en nod i ett träd -
. In medel när denna form med detta ID lämnas in, exekvera
följande kod.
Jag bryr mig inte vad namnet på den Funktionen är att jag utför.
Så här jag använder, som tidigare, vad är kallas lambda funktion eller
anonym funktion.
Det är inte alls intellektuellt intressant än den har inget namn,
vilket är bra om du bara någonsin kommer att kalla det en gång.
Och inne där jag faktiskt hantera inlämnandet av formuläret.
Jag förklarar först en variabel kallas värde.
Och vad är då effekten av detta markerad del här nu?
Vad gör det på ett hög nivå för mig?
>> Publik: Det blir det värde som användaren inte i HTML-koden nedan.
Det blir detta ID och sedan finner värdet av det.
>> DAVID J. MALAN: Exakt.
Det tar tag i noden, vars unika Identifieraren är känt.
Det blir det värde i den och som är förmodligen det som användaren
skrev sig själv.
Och då den lagrar det i variabel som heter värde.
Inom parentes kan man också ha gjort det lite annorlunda.
Helt acceptabelt genom att göra något lögn var värdet får
document.getElementById.
Och det är därför det är lite jobbigt att inte använda jQuery.
"Namn". Värde.
Så helt acceptabelt.
Olika sätt att göra detta. jQuery bara tenderar att vara lite mer kortfattad och
definitivt mer populärt bland programmerare.
>> Nu, jag gör lite av en sanity ta, eftersom det i det problemet
uttalande vi uttryckligen sagt, om Användaren har ännu inte skrivit sin
namn, visar inte ett larm.
Men du kan kontrollera om det, genom att bara kontroll för den tomma strängen för en
quote-unquote om det finns ingenting faktiskt där.
Men om det inte är lika med citat-unquote, Jag vill ringa varningar.
Och det intressanta här är att vi använder plus aktör och som
gör vad i JavaScript?
Sammanfoga.
Så det är som phps prick operatör.
Samma idé, något annorlunda syntax.
Och jag bara skapa den sträng som du såg på skärmen skott -
Hej, så och så.
>> Och sedan i minsta detalj är det.
Varför jag returnera false insida av denna anonyma funktion?
>> PUBLIK: Det finns inget värde.
Du sätter den i formen.
Den säger bara, om värdet inte lika tomt, så gör det.
Det fanns en tomt i detta påstående.
>> David J. MALAN: OK.
Försiktig.
Det finns ingen annan här.
Och det retur falskt är utanför av om förhållandena.
Så detta markerade linjen, returnera false, utför oavsett vad när
formuläret skickas.
Vad åter falsk insidan av denna händelsehanterare, som det kallas,
den aktuella händelsen vara underkastelse?
>> PUBLIK: Eftersom det bara händer en gång.
>> DAVID J. MALAN: händer bara en gång.
Inte riktigt.
Yeah?
>> PUBLIK: Det hindrar formen från lämna in till standardbeteendet,
vilket skulle göra sidan omladdning.
>> DAVID J. MALAN: Exakt.
Så jag överbelasta termen in här, eftersom jag säger, är den form
lämnas in.
Men som du föreslår, det är faktiskt inte lämnats in i den sanna HTTP vägen.
När du klickar på Skicka, på grund av vår onSubmit handler, vi avlyssning
det formulär så att säga.
Vi ska sedan göra vår grej med JavaScript-kod.
Men jag medvetet åter falskt, eftersom det som jag inte vill ska hända en
ögonblick senare är för hela formen själv som ska lämnas in till webben
server med Nyckelvärdesparen genom att ändra URL för att vara något liknande
q = katter eller vad vi gjorde, till exempel, i klassen.
Jag vill inte att det ska ske, eftersom det finns ingen server lyssnar för detta
bilda underkastelse.
Det är helt gjort i JavaScript-kod.
Och det är därför jag inte ens har en åtgärder attribut på min blankett, eftersom jag
har inte för avsikt att detta skall någonsin gå till servern.
>> Så det lämnas in.
Men vi avlyssnar formuläret underkastelse och förhindra den förvalda
beteende, vilket är att faktiskt gå hela vägen till servern.
>> PUBLIK: Så håller det på klientsidan.
>> DAVID J. MALAN: Hålla det klientsidan.
Exakt rätt.
Nästa upp var min oh MySQL.
>> ROB BOWDEN: OK.
Så denna första fråga var allmänt grov för människor.
Även om de senare gick bättre.
Så du var tvungen att välja rätt uppgifter typer för båda dessa kolumner.
Och båda dessa har någon saker om dem som
göra valet svårt.
Så int var inte ett giltigt skriver för numret.
Orsaken är en 12-siffrig konto nummer, är inte tillräckligt stor för att en int
lagra totala siffror.
Så ett giltigt val skulle ha varit en stor int om du råkar veta att.
Ett annat val skulle ha varit en röding gäller längd 12.
Så någon av dem skulle ha fungerat.
Int skulle inte.
>> Nu, balans, tänker tillbaka på pset7.
Så vi använde specifikt decimaltal till lagra värdet av aktier eller -
>> DAVID J. MALAN: Cash.
>> ROB BOWDEN: Cash.
Vi använde decimal för att lagra den mängd pengar som användaren har för tillfället.
Så anledningen till att vi gör det är eftersom, kom ihåg, flyter.
Det finns flyttal i precision.
Det kan inte exakt förvara kontanter värden som vi vill ha här.
Så decimal kan exakt butik något att, säga, två decimaler.
Därför balans, vi vill ha det vara decimala och inte flyta.
>> DAVID J. MALAN: Och dessutom, också, fast det kanske varit smart i andra
sammanhang att tänka, kanske detta är en chans för en int.
Jag ska bara hålla reda på saker i småpengar.
Eftersom vi visade tydligt standard Värdet av att vara 100,00, att
betyder att det kan bara vara en int.
Och en annan finess också med nummer var att det inte var tänkt
att vara en kuggfråga.
Men minns att en int i MySQL, i C, åtminstone på liknande
apparat, är 32-bitars.
Och även om vi förväntar oss inte att du vet exakt hur många siffror som
medel, kommer ihåg att det största antalet du kan representera potentiellt
med ett 32-bitars nummer är ungefär vad?
>> Vilket nummer har vi alltid säger?
2 till 32, vilket är vad ungefär?
Du behöver inte veta exakt.
Men i stort sett är bra i livet.
Det är ungefär 4 miljarder.
Så vi har sagt att ett par gånger.
Jag vet att jag har sagt att ett par gånger.
Och det är ungefär 4 miljarder.
Och det är en bra regel av tummen för att veta.
Om du har 8 bitar, 256 är det magiska numret.
Om du har 32 bitar, 4 miljard ge eller ta.
Så om du bara skriver ner 4 miljarder, ser du att det är färre siffror än
12, vilket innebär att det är helt klart inte tillräckligt uttrycksfullhet för att fånga en
12-siffriga kontonummer.
>> ROB BOWDEN: OK.
Så de andra som gick bättre.
Så antar att banken medför en $ 20 per månad
underhållsavgift på alla konton.
Med vilken SQL-fråga kan banken dra av $ 20 från varje greve, även om
det resulterar i en del negativa saldon?
Så i princip finns det fyra huvudsakliga typer av frågor -
infoga, markera, uppdatera och ta bort.
Så vad gör vi tror att vi är kommer att använda här?
Uppdatera.
>> Så låt oss ta en titt.
Så här är vi uppdaterar.
Vad tabellen vi uppdaterar konton?
Så uppdatera konton.
Och sedan syntaxen säger, vad i konton vi uppdaterar?
Tja, vi ställer balans lika med nuvärdet av balans minus 20.
Så det här kommer att uppdatera alla rader konton, subtrahera
$ 20 från balansen.
>> DAVID J. MALAN: Ett vanligt misstag här, även om vi ibland förlät det,
var att faktiskt ha PHP-kod här anropa frågefunktionen eller sätta
citattecken runt allt som behövde inte vara där.
>> ROB BOWDEN: Kom ihåg att MySQL är ett separat språk från PHP.
Vi råkar skriva MySQL i PHP.
Och PHP är sedan skicka det över till MySQL-servern.
Men du behöver inte PHP för att kommunicera med en MySQL-server.
>> DAVID J. MALAN: Exakt.
Så inga variabler med dollartecken bör i detta sammanhang.
Det kan bara göra allt matten i själva databasen.
>> ROB BOWDEN: OK.
Så nästa.
Är det nästa?
Yeah.
Så med vilken SQL-fråga kan banken hämta kontonumren i sin
rikaste kunderna, de med saldon som överstiger 1.000?
Så vilken av de fyra huvudtyperna ska vi vill ha här?
Välj.
Så vi vill markera.
Vad vill vi välja?
Vilken kolumn vill vi välja?
Vi kommer specifikt vill för att välja nummer.
Men om du sa stjärna, vi också accepterat att.
>> Så välj nummer från vilken tabell?
Konton.
Och då det tillstånd vi vill ha?
När balans som är större än 1000.
Vi accepterade också större än eller lika.
Sista.
Med vilken SQL-fråga kan banken nära, dvs ta bort varje konto som
har ett saldo på $ 0?
Så vilken av de fyra är vi kommer att vilja använda?
Ta bort.
Så syntaxen för det?
Radera från vilken tabell?
Konton.
Och då det tillstånd som Vi vill ta bort -
där balansen är lika med noll.
Så ta bort alla rader från konton där saldot är noll.
Frågor om någon av dessa?
Vill du köa?
>> DAVID J. MALAN: Kö guide.
Så i den här, vi gav dig en något välbekant struktur som vi utforskade en
bit i klass jämsides av structs, vilket var en data
struktur relaterade till innebörden.
Skillnaden dock med en kö är att vi var tvungna att på något sätt komma ihåg vem
var längst fram i kön, i stor del så att vi kunde göra mer
effektiv användning av minnet, åtminstone om vi med hjälp av en matris.
>> Därför minns, om vi har en array, om, till exempel, är det på framsidan av
kön, om jag kommer in i kö här, och sedan någon får i linje
bakom mig, bakom mig, bakom mig, och en person kliver över gränsen, du
kunde, som vi såg några av våra mänskliga frivilliga i klassen, har alla
flytta detta sätt.
Men i allmänhet, att ha alla göra något som inte är den bästa användningen av tid
i ett program, eftersom det innebär att din algoritmen körs i vad
asymptotisk gångtid?
Den är linjär.
>> Och jag känner att det är ganska dumt.
Om nästa person i raden är nästa Den som har tänkt att gå in i
store, behöver de inte alla har att röra sig tillsammans.
Bara låta den personen ska plockas bort när tiden är inne, till exempel.
Så vi kan spara lite tid där.
Och så för att göra det ändå, innebär att att chefen för kön eller
fram i kön kommer att successivt gå djupare och djupare
i arrayen och så småningom kanske faktiskt linda runt om vi använder en
array för att lagra människor i denna kö.
Så du kan nästan tänka på array som en cirkulär uppgifter
struktur i den meningen.
>> Så du på något sätt har att hålla reda på storleken på det eller egentligen slutet på den
och sedan var början på den är.
Så föreslår vi att du deklarerar en sådan kö, kallelse
det q, bara en bokstav.
Därefter föreslår vi att den främre vara initialiseras till noll och att storleken
initialiseras till noll.
>> Så just nu, det finns inget insidan av den kön.
Och vi ber dig att fylla i genomförande av enqueue nedan i
sådant sätt att den funktionen lägger n till slutet av q och sedan returnerar true.
Men om q är full eller negativt, det Funktionen ska istället returnera false.
Och vi gav er ett par antaganden.
Men de är inte riktigt funktionellt relevant, finns just det bool,
eftersom tekniskt sett inte bool finns i C om du inte har en
visst header-fil.
Så det var bara till att det inte var inte det här ett trick
fråga sånt.
>> Så enqueue föreslog vi i urvalet lösningar för att genomföra följande.
Man kontrollerar vi först den lätthet, de lågt hängande frukter.
Om kön är full eller det nummer som du försöker sätta in är mindre
än noll, som vi sade i specifikation av problemet bör
inte tillåtas, eftersom vi bara är intresserad av icke-negativa värden, så ska du
bara returnera false omedelbart.
Så några relativt enkla felkontroll.
Om om du vill lägga till det faktiska nummer, var du tvungen att göra lite
tänker här.
Och det är där det är lite irriterande mentalt, eftersom du måste
räkna ut hur man hanterar wraparound.
>> Men fröet till idén här att det är av intresse för oss är att wraparound
ofta innebär modulär aritmetik och mod operatör, procentsidan,
där du kan gå från ett större värde tillbaka till noll och sedan ett och två och
tre och sedan tillbaka runt till noll, ett och två och tre och så vidare
igen och igen.
Så hur vi föreslår att göra detta är att vi vill index till
array kallas tal där våra heltal ljuga.
Men för att komma dit, vi först vill göra oavsett storleken på kön är utan
Lägg sedan till att oavsett framför listan är.
Och effekten av det är att sätta oss på rätt position i kön och
inte utgå från att den första personen i raden är i början, som han eller
hon absolut skulle vara om vi också skiftande alla.
Men vi bara skapar arbete för oss själva om vi tog
denna speciella väg.
>> Så vi kan hålla det relativt enkelt.
Vi måste komma ihåg att vi bara lagt en int till kön.
Och då är vi tillbaka bara sant.
Under tiden, i dequeue, frågade vi du göra följande.
Genomföra den på ett sådant sätt att det dequeues, är som tar bort och avkastning,
int längst fram i kön.
För att ta bort int räcker det att glömma det.
Du behöver inte åsidosätta sin bit.
Så det är fortfarande faktiskt där.
Precis som data på en hårddisk, vi bara ignorera det faktum
att det nu finns.
Och om q är tomt, bör vi istället tillbaka negativt 1.
Så det här känns godtyckliga.
Varför åter negativ 1 istället för falskt?
Yeah.
>> PUBLIK: Q lagrar positiva värden.
Eftersom du bara lagra positiva värden i k, är negativ ett fel.
>> DAVID J. MALAN: OK, sant.
Så eftersom vi bara lagra positiva värden eller noll, då är det bra att
returnera ett negativt värde som en vaktpost värde, en speciell symbol.
Men du skriva om historien där, eftersom anledningen till att vi är bara
åter icke-negativa värden är att vi vill
har en sentinel värde.
Så mer specifikt, varför inte bara return false i fall av fel?
Yeah.
>> PUBLIK: Du har misslyckats att returnera ett heltal.
>> DAVID J. MALAN: Exakt.
Och det är här C får ganska begränsande.
Om du säger att du ska att returnera en int, har du
returnera en int.
Du kan inte få lust och börja återvända en bool eller en flottör eller en
sträng eller något liknande.
Nu, under tiden, JavaScript och PHP och några andra språk kan, i själva verket,
har du åter olika typer av värden.
Och det kan faktiskt vara till nytta, om du kunde återvända positiva Ints, nollor,
negativa Ints, eller falskt eller null även för att beteckna felet.
Men vi har inte så mångsidighet i C.
>> Så med dequeue, vad vi föreslå att göra är -
>> ROB BOWDEN: Du kan returnera false.
Det är bara det falska är hash definiera falskt till noll.
Så om du returnera false, du återvänder noll.
Och noll är en giltig sak i vår kö, medan negativ 1 inte om
falska råkade vara negativ 1.
Men du borde inte ens behöver veta det.
>> DAVID J. MALAN: Det är varför jag inte säga det.
>> ROB BOWDEN: Men det var inte sant att du inte kan returnera false.
>> DAVID J. MALAN: Visst.
Så dequeue, märker vi accepterar ogiltig som dess argument.
Och det beror på att vi inte är passerar något i.
Vi vill bara ta bort elementet längst fram i kön.
Så hur kan vi gå om att göra detta?
Tja, först, låt oss göra detta snabb sanity check.
Om köstorleken är 0, det finns inget arbete att göra.
Avkastning negativ 1.
Klar.
Så det är några rader i mitt program.
Så bara fyra rader kvar.
>> Så här jag väljer att dekrementera storleken.
Och nedräkning av storleken på ett effektivt sätt betyder att jag glömmer
något är där inne.
Men jag måste också uppdatera där framsida är siffrorna.
Så för att göra det, jag behöver att göra två saker.
Måste jag först komma ihåg vad numret är längst fram i kön,
eftersom jag behöver gå tillbaka det där.
Så jag vill inte av misstag glömmer om det och sedan skriva över den.
Jag kommer bara att komma ihåg i en int.
>> Och nu, jag vill uppdatera q.front skall q.front 1.
Så om detta var den första personen i linje, nu, jag vill göra plus 1 till
peka på nästa person i kön.
Men jag måste hantera det omslutande.
Och om kapaciteten är en global konstant, som kommer att tillåta mig att se till att
som jag pekar på den allra sista personen i linje, kommer modulooperationen föra
mig tillbaka till noll vid fram i kön.
Och som hanterar wraparound här.
Och då jag fortsätter att återvända n.
>> Nu, strängt taget, det gjorde jag inte måste deklarera n.
Jag behövde inte ta tag i den och förvara den temporärt, eftersom värdet är
fortfarande där.
Så jag kunde bara göra det rätta aritmetiska att returnera den förre chefen
i kön.
Men jag kände bara att det var mer tydlig att faktiskt ta tag i int, uttryckte det
i n, och sedan tillbaka till att för tydlighetens skull, men
inte är absolut nödvändigt.
Psst.
De är alla uttalas på mitt huvud.
>> ROB BOWDEN: Så första frågan Detta är ett binärt träd problem.
Så första frågan är, vi är med tanke på dessa siffror.
Och vi vill på något sätt infoga dem i dessa noder så att det är en
giltigt binärt sökträd.
Så en sak att komma ihåg om binära sökträd är att det inte är
bara det att den sak till vänster är mindre och man kan
höger är större.
Det måste vara att hela träd till vänster är mindre, och hela trädet
till höger är större.
>> Så om jag satte 34 här i toppen, och sedan Jag satte 20 här, så det är giltigt så
långt, eftersom 34 upp här.
20 går till vänster.
Så det är mindre.
Men jag kan inte sedan lägga 59 här, eftersom även om 59 är till höger om 20,
det är fortfarande till vänster 34.
Så med denna begränsning i åtanke, enklaste sättet troligen lösa detta
Problemet är att bara typ av dessa nummer -
så 20, 34, 36, 52, 59, 106.
Och sedan in dem från vänster till höger.
>> Så 20 går här.
34 går här.
36 går här.
52, 59, 106.
Och ni också kunde ha räknat ut med några koppla in och inse,
oh, vänta, jag har inte tillräckligt med siffror att fylla i det här borta.
Så jag måste reshift vad min rutt anmärkning kommer att bli.
Men märker att i de tre sista, om du läser från vänster till höger, är det i
stigande ordning.
>> Så nu vill vi förklara vad det struct kommer att vara för
noder i trädet.
Så vad vi behöver i ett binärt träd?
Så vi har ett värde av typen int, så vissa int värde.
Jag vet inte vad vi kallade det i lösningen -
int n.
Vi behöver en pekare till den vänstra underordnade och en pekare till det rätta barnet.
Så det kommer att se ut så här.
Och det kommer faktiskt se ut innan när gjorde den dubbelt bundna
lista grejer, så varsel -
Jag kommer att behöva rulla hela vägen tillbaka ner till problem 11.
>> Så märker det ser identisk med detta, utom vi råkar bara kalla dessa
olika namn.
Vi har fortfarande ett heltal värde och två pekare.
Det är bara det att i stället för att behandla pekare som pekar på nästa sak
och den tidigare sak, vi behandlar pekare att peka på ett vänster barn
och högra underordnade.
OK.
Så det är vår struct node.
Och nu, den enda funktionen måste vi genomföra detta är travers, som
vi vill gå över trädet, tryckning ut värdena för trädet i ordning.
>> Så ser här, skulle vi vill skriva ut ut 20, 34, 36, 52, 59, och 106.
Hur kan vi åstadkomma det?
Så det är ganska likartad.
Om du såg tidigare examen problemet att du ville skriva ut
hela träd med kommatecken emellan allt, var det faktiskt ännu
enklare än så.
Så här är lösningen.
Det var betydligt enklare om du gjorde det rekursivt.
Jag vet inte om någon försökt att göra det iterativt.
>> Men först, har vi vår bas fallet.
Tänk om roten är noll?
Då vi bara kommer att återvända.
Vi vill inte skriva ut någonting.
Annars kommer vi att korsa rekursivt ned.
Skriv ut hela vänstra underträd.
Så skriver du ut allt mindre än min nuvarande värde.
Och då kommer jag att skriva ut själv.
Och sedan ska jag recurse ner min Hela högra delträd, så allt
större än mitt värde.
Och detta kommer att skriva ut ut allt i ordning.
Frågor om hur det faktiskt åstadkommer det?
>> PUBLIK: Jag har en fråga på [OHÖRBAR].
>> ROB BOWDEN: Så ett sätt att närma sig någon rekursiv problem är att bara tänka
om det som du måste tänka om alla hörnfall.
Så anser att vi vill skriva ut hela trädet.
Så allt vi kommer att fokusera på är denna speciella nod -
36.
De rekursiva anrop, vi låtsas de fungerar bara.
Så här, detta rekursivt anrop till travers, vi utan att ens tänka
om det, bara traversera vänster tre, tänka sig att redan skriver ut 20
och 34 för oss.
Och sedan när vi så småningom rekursivt ringa travers på
rätt, som kommer att korrekt ut 52, 59 och 106 för oss.
>> Så med tanke på att detta kan skriva ut 20, 34, och den andra kan skriva ut 52, 59, 108,
allt vi behöver för att kunna göra är att skriva ut själv i mitten av det.
Så skriva ut allting framför oss.
Skriv själv, så den aktuella noden print 36, regelbunden printf och sedan
skriva ut allt efter oss.
>> DAVID J. MALAN: Det är där rekursion blir riktigt vacker.
Det är denna fantastiska steg i tro där du gör det minsta lite arbete.
Och sedan låta någon annan göra resten.
Och att någon annan är, ironiskt nog, du.
Så för allvarliga tomte poäng, om du rullar upp på frågorna -
>> ROB BOWDEN: På frågorna?
>> DAVID J. MALAN: Och ner lite till siffrorna, är det någon som vet var
dessa siffror ifrån?
>> ROB BOWDEN: Jag har bokstavligt talat ingen aning.
>> David J. MALAN: De visas genom hela testet.
>> PUBLIK: Är de samma siffror?
>> DAVID J. MALAN: Dessa siffror.
Lite påskägg.
Så för de av er tittar på nätet på hem, om du kan berätta för oss via e-post till
heads@CS50.net vilken betydelse av dessa återkommande sex nummer är
hela Quiz 1 kommer vi duscha dig med fantastisk uppmärksamhet vid den slutliga
föreläsning och en stressboll.
Trevligt, subtilt.
>> ROB Bowden: Några sista frågor vad som helst på frågesport?