>> David J. MALAN: Rendben.
Ezért örvendetes, hogy az első CS50 halál utáni egy kvíz.
Azt hittük, leleplez ezt a hagyományt ebben az évben.
És ez lesz lehetőség séta a
megoldások a teszt.
És mi gyorsítani vagy lassítani alapú kamat azok itt.
>> Szóval valószínűleg itt, mert te érdekel, hogyan lehet, vagy
kellett volna válaszolt néhány ezeket a problémákat.
Akkor miért nem nézzük az ebben a szakaszban az első?
Így egyre szálakat.
Ez adta meg a három különböző változatban program volt, végül,
azt jelentette, hogy egy stringet a felhasználó.
Függetlenül attól, hogy nem volt balra, hogy meghatározza.
>> És kérdezte Kérdés 0, Tegyük fel, hogy az 1-es verzió van
össze és kivégezték.
Miért lehet, hogy a program segfault?
Első pillantásra, olyan javaslatokat , hogy miért?
Igen.
>> Közönség: Így emlékszem, hogy láttam ezt korábbi példája nézi a
char * s, és látta, a vizsgálat az s és látta, mert ez egy mutató, hogyan
hatott, amit beszkennelt?
Ez s vagy címét s?
>> David J. MALAN: OK.
Jó.
Így végül a forrása minden probléma feltehetőleg fog csökkenteni
hogy a változó s.
És ez valóban egy változó.
Az adatok a fajta, amely változó char *, ami azt jelenti, hogy fog
tartalmazza a címét egy karaktert.
És ebben rejlik a betekintést.
Ez lesz, hogy tartalmazza a címét egy karakter, vagy általánosabban, a
címe az első karakter egy egész blokk karaktereket.
>> De a fogást, hogy vizsgálat s, célja az élet, kap egy címet, és mivel
formátumban kódot, mint% s, olvassa el a szöveget a darab
memóriát a címet.
De mivel nincs egyenlőségjel előtt hogy pontosvessző az első
kódsor, mert valójában nem kiosztani olyan memória
malloc, mert valójában nem osztja egy sor bizonyos méret, mind
csinálsz olvas a felhasználó billentyűzet a néhány teljes
szemét értéket, amely van, s alapból.
Így esély fogsz segfault ha hogy a cím nem csak azért történik,
hogy egy értéket, hogy lehet, valójában írni.
Olyan rossz, hogy nem osztja a memória is.
>> Így a szóban forgó 1, megkérdeztük, tegyük fel, hogy a 2-es verziója is
össze és kivégezték.
Miért lehet, hogy ez a program segfault?
Tehát ez egy kevésbé hibás.
És tényleg csak egy Nyilvánvaló módon, ahol lehet
kiváltó segfault itt.
És ez a tematikus.
Bármikor mi ac a memóriában, milyen tudna tenni, hogy rábírja a segfault
a 2-es verziója?
>> Közönség: Ha ezt a bemenet egy string, ami hosszabb, mint 49
karaktereket.
>> David J. MALAN: Pontosan.
Minden alkalommal, amikor valami fix hosszúságú amikor egy sor, a
radar ki kell aludnia, hogy ez lehet problémás, ha nem ellenőrzi a
határait tömb.
És ez itt a probléma.
Még mindig a scanf.
Még mindig a% s, ami azt jelenti, próbálkozzon olvasni egy string a felhasználó.
Ez lesz olvasható a s, ami ezen a ponton, a ténylegesen
címét egy darab memória vagy ez egyenértékű.
Ez a neve egy tömb karakterek memória.
>> De pontosan, hogy, ha elolvassa a szöveg ami hosszabb, mint 49 karakter, 49
mert szükség van hely a backslash 0, fogsz túlcsordulás
hogy a puffer.
És lehet, hogy szerencsés és képes levelet 51st karakter, 52., 53..
De egy bizonyos ponton, az operációs rendszer fog mondani, nem.
Ez biztosan nem a memória akkor szabad hozzányúlni.
És a program fog segfault.
>> Tehát, a heurisztikus legyen bármilyen idő megvan fix hosszúságú, akkor
hogy győződjön meg róla, ellenőrzi a hosszát bármit is akarsz
olvasni bele.
>> Közönség: Tehát megoldani, hogy, akkor volt egy nyilatkozatot ellenőrzése valóban
a hossza nagyobb, kisebb vagy kisebb, mint?
>> David J. MALAN: Abszolút.
Csak egy állapot , amely azt mondja, ha az -
vagy inkább nem feltétlenül tudja előre, hogy hány karakter a
felhasználó fog gépelni, mert a van tyúk és a tojás.
Nem, amíg nem olvastam azt a scanf lehet kitalálni, hogy mennyi ideig van.
De ezen a ponton, már túl késő, mert már elolvasta a
néhány blokk memória.
Tehát, mint egy félre, a CS50 könyvtár meghiúsítja ezt a kérdést teljesen, visszahívás
használatával fgetc.
És így szól az egyik karakter egy időben, tip-toeing mellett, tudva, hogy
nem overflow egy karaktert, ha olvassa egyesével.
>> A fogás a getstring visszahívás hogy van, hogy állandóan újra méret
hogy a darab memória, amely csak a fájdalom.
Ez egy nagy vonalak kódot csinálni.
Így egy másik megközelítés az lenne, hogy valójában egy unokatestvére, így
beszélni, a scanf.
Vannak változatai egy csomó ilyen funkciók valóban ellenőrizni a
hosszát, hogy hány karakter lehet, hogy olvassa el maximálisan.
És akkor adja meg, nem olvassa el több mint 50 karakter.
Szóval ez lenne a másik megközelítés, de kevésbé alkalmazkodó nagyobb bemenet.
>> Így a 2. kérdésre kéri, tegyük fel, hogy a változat 3. össze és kivégezték.
Miért lehet, hogy a program segfault?
Tehát ez tulajdonképpen ugyanaz válaszolni, még akkor is,
úgy néz ki, egy kicsit cifrább.
Mi a malloc, amely olyan, mint mi így magunknak több lehetőséget.
És akkor mi szabaddá, hogy memória a végén.
Ez még mindig csak 50 bájt memóriát.
Tehát még mindig próbálja olvasni 51, 52, 1000 bájt.
Meg fog segfault a pontosan ugyanezen okból.
>> De van egy másik oka is.
Mi mást malloc visszatérés mellett címét egy darab memória?
Lehet vissza null.
És mivel nem vagyunk ellenőrzése hogy mi lehet csinál valamit
hülye egy másik ok, ami az, hogy mi lehet mondani scanf olvassa
a felhasználó bemenet a billentyűzet a 0 helyen, AKA null.
És ez is biztosan kiváltó segfault.
Tehát a teszt célját, mi lenne elfogadták, vagy azok egy
indok.
Egy azonos.
Az egyik egy kicsit árnyaltabb.
>> Végül, tekintettel a program memória használatára, hogyan version 2 és
3-as verzió különböznek?
Tehát, amit érdemes, láttunk egy látszólag végtelen mennyiségű lehetséges
választ erre.
És az emberek választ, mi volt remélve, de elfogadta a többi
a dolgok, volt néhány említést a tény, hogy a 2-es verzióját használó
az úgynevezett stack.
3. verzió a kupac.
És funkcionálisan, ez nem igazán hogy minden, hogy sok a különbség.
Végén a nap, mi még mindig csak arra, hogy 50 byte memóriát.
>> De ez volt az egyik lehetséges válasz hogy kerestünk.
De látni fogod, ahogy kapsz vetélkedők vissza a TF, hogy mi
elfogadják egyéb viták a eltérő felhasználási memória is.
De a verem és a kupac lett volna egy egyszerű válasz, hogy menjen el.
Bármilyen kérdése?
Adok Rob.
>> ROB BOWDEN: Tehát a probléma 4..
Ez az, ahol meg kellett kitölteni a bájtok számát az összes
ezek a különböző típusú használt.
Tehát az első dolog, amit látni.
Tegyük fel, hogy egy 32-bites architektúrát, így CS50 készülék.
Tehát az egyik alapvető dolog 32-bites gépeken, hogy elmondja,
hogy pontosan mekkora a mutató megy hogy az építészet.
>> Így azonnal, mi tudjuk, hogy minden mutató típusú 32 bites vagy 4 bájt.
Így nézett az asztalnál, a node * egy mutató típusú.
Ez lesz a 4. bájt.
Struct node *, ez a szó szoros értelmében azonos node csillag.
És így lesz 4 bájt.
String, így nem néz ki, mint a pointer még, de a typedef, a
szöveg csak egy char *, amely egy mutató típusú.
Szóval ez lesz a 4. bájt.
>> Tehát ez a három mind a 4 bájt.
Most, csomópont és hallgatói is egy kicsit bonyolultabb.
Így nézett csomópont és hallgatói, látjuk csomópont, mint egy egész, és a mutatót.
És a diák két mutató belsejébe.
Így legalább a mi esetünkben itt, ahogy , hogy a végén a méret kiszámításához
A struktúra csak add fel mindent hogy van benne a struct.
>> Így a csomópont, van egy egész szám, amely 4 bájt.
Van egy mutató, amely 4 bájt.
És így egy csomópont lesz hogy akár 8 bájt.
És hasonlóképpen a hallgatói, van egy mutató, ami 4 byte és egy másik
mutató, hogy a 4 bájt.
Szóval ez lesz a vége fel, hogy 8 bájt.
Így csomópont és hallgatói 8 bájt.
És ez a három mind a 4 bájt.
Kérdések az, hogy?
Igen.
>> Közönség: Van-e egy 64 bites építészet, azt, hogy
dupla mindet?
>> ROB BOWDEN: Nem lenne megkétszereződik mindet.
Így a 64-bites architektúrát, akkor ismét, változás, hogy az alapvető dolog, hogy egy
mutató már 64 bit.
Igen.
Így a mutató 8 bájt.
Tehát ezek voltak 4 byte lesz 8 bájt.
Egy diák, ami két mutató, Nos, most ez fog
8 bájt 8 bájt.
Úgy megy, hogy 16 bájt.
>> De egy csomópont még mindig 4 bájt.
Tehát ez a mutató lesz hogy 8 bájt.
Ez a 4 bájt.
Így a csomópont csak akkor fog hogy 12 bájt.
Más kérdés, hogy az egyik?
Így a következő, ezek A HTTP státusz kódok.
És meg kellett leírni körülmények amely szerint ezek lehetnek
vissza az Ön számára.
az egyik probléma, hogy hallottam néhány diák van az, hogy megpróbálta a
hiba, hogy az ügyfél végén.
Tehát, amikor megpróbáljuk, hogy a kérelem a szerver, valami megy
rossz a mi oldalunkon.
De általában ezek a kódok hogy a kiszolgáló által visszaadott.
Tehát szeretné, hogy kitaláljuk, mi folyik rossz vagy jó a szerver
okozza ezeket a dolgokat vissza.
Miért lehet, hogy a kiszolgáló az status kód: 200?
Minden gondolat?
>> Igen.
Tehát valami a sikeres kérésére ment keresztül.
És ők tudják, hogy visszatérjen amit kért.
Szóval, minden rendben volt.
Mi a helyzet a 302 található?
Igen.
>> Közönség: A szerver keresett , amit kért.
De nem tudta megtalálni.
Tehát van egy hiba.
>> ROB BOWDEN: Tehát a kiszolgáló keres, amit akart.
Tehát csak keres itt, 302 találta, képes volt megtalálni.
>> Közönség: Sajnálom.
Talált azt jelenti, hogy nem találják.
Bocsánat.
>> ROB BOWDEN: Tehát a 302 ellenőrzés során talált.
A szerver képes megtalálni amit akart.
>> Közönség: De ez nem jeleníti meg?
>> ROB BOWDEN: A különbség ezt a 302, illetve 200, hogy
tudja, mit akar.
De ez nem pontosan hol meg akartam kérdezni.
Tehát 302 egy tipikus átirányítás.
Szóval kért oldalt.
Tudja, ó, azt akarom, vissza ezt.
De ez egy másik URL-t.
Tehát hé, hogy tényleg ezt akarod.
>> David J. MALAN: Ez egy darabot, hogy azt mondta hogy adott nektek egy átirányítás
funkció, amely használta a header függvényt ez viszont, kinyomtathatók helyszín,
vastagbél, majd az URL-t, amelyre azt szeretné, hogy utasítsák el a felhasználó.
Annak ellenére, hogy nem látta a 302 kifejezetten ott van, ez az, amit a PHP
varázslatos módon helyezze be a fejléc mondván, hogy pontosan mi Rob azt mondta, hogy -
található.
De megy itt helyette.
>> ROB BOWDEN: OK.
Szóval mi a 403 tiltott?
>> Közönség: Azt hiszem, hogy a szerver alapvetően azt mondja, hogy az ügyfél
nem fér hozzá a honlap.
>> ROB BOWDEN: Szóval igen.
Nos, a tipikus válasz voltunk vár olyasmi, mint a fájlok
nem chmodded megfelelően.
Ez valószínűleg milyen körülmények között látta őket.
De van egy oka annak, hogy az ügyfél lehet vétkes itt.
Itt tulajdonképpen egy státusz kód -
401.
Tehát ezek nagyon hasonlóak.
>> 401 engedélyezett.
És 403 tilos.
És így illetéktelen te kizárólag hogy ha nem vagy bejelentkezve,
De bejelentkezés jelenthet hogy Ön jogosult.
De ha már bejelentkezett, és még nincs engedélye, akkor
akkor is kap tiltott.
Tehát, ha be van jelentkezve, és nem engedélyt, tilos is
amit lehet kapni.
>> David J. MALAN: És az a mechanizmus, amelyek ezeket a problémákat általában
megoldani a szerver keresztül mi a parancs?
Chmod, ha ez valóban, a jogosultságok kérdés a fájl vagy könyvtár.
>> ROB BOWDEN: Akkor 404 nem található.
Igen.
Szóval, ellentétben a 302, ahol nem volt éppen ahol azt kérdezi, de tudja, hogy mit
akarod, ezt, csak éppen nem tudja, mit akar.
És te nem kér valami érvényes.
418 vagyok teáskanna, majd 500 belső szerver.
Szóval, miért is van ez?
>> Tehát segfault -
Igazából nem tudom, az osztályozás szabvány erre.
De ha a PHP kód volt valami rossz benne, elméletileg lehetett
ténylegesen segfault, amely esetben ez a 500 belső szerver hiba, amit
a hiba a szerver konfigurációt.
Vagy van egy szintaktikai hiba a PHP kódot.
Vagy valami rossz történik.
>> David J. MALAN: Mi nem látni segfault között, egy-két ember a válaszokat.
És technikailag, ez megtörténhet.
De ez lenne a PHP-t, a program írta más emberek, valójában
segfaulted, amely csak akkor, ha azok az emberek elrontottam és írt hibás kód
a tolmács lenne PHP maga segfault.
Így, bár a 500, mint a segfault lélekben, akkor szinte mindig a
eredmény egy konfigurációs fájl kérdés a web szerver vagy, mint Rob azt mondta,
szintaktikai hiba, mint te nem zárta be árajánlatot.
Vagy elvesztette a pontosvessző valahol.
>> Közönség: Tehát a Shuttle Pset, azt hiszem, ha én egyszer rákattintottam a
a böngésző, de semmi nem jött fel, amit az úgynevezett fehér oldal.
De ez azért volt, mert a kódot.
Azt hiszem, ez volt JavaScript, igaz?
>> ROB BOWDEN: Igen.
>> Közönség: Vajon ez a hiba Még mindig jön?
>> ROB BOWDEN: Szóval nem ütött ezt a hibát, mert mindent
a webszerver szemszögéből teljesen rendben van.
De kért index.html.
Azt kérte shuttle.js és service.js.
És képes volt sikeresen vissza Önnek minden olyan dolog -
200-at.
OK.
Ez csak akkor, ha a böngésző megpróbált értelmezni a JavaScript kód, amely
ez olyan, mint, várj, ez nem érvényes JavaScript hiba.
Van még kérdés?
Rendben van.
>> David J. MALAN: Így a következő up volt 11-es.
És a 11. volt a legijesztőbb egy csomó ember.
Tehát a legfontosabb dolog megjegyezni volt, hogy ez volt, sőt, körülbelül
kétszeresen láncolt lista.
De ez nem ugyanaz, mint a tavalyi kétszeresen láncolt lista a problémát,
amely nem adja meg a fenntartással, hogy A lista is, sőt, a rendezetlen.
>> Tehát az a tény, hogy a lista volt rendezetlen és az a tény, hogy ez a szó volt
kiemelte ott volt a célja, hogy közvetítse hogy ez valójában egy egyszerűsítés
egyébként, hogy mi volna egy nagyobb kihívást jelentő probléma
és egy hosszabb.
Tehát a leggyakoribb hiba az volt, hogy már fel tavalyi megoldást az egyik
lapozó és aztán csak vakon vettem le, mint a válasz, amely a jobb oldali
választ egy másik kérdés hasonló szellemben.
De a finomságok itt a következők voltak.
>> Tehát az egyik, van egy csomópont bejelentett és meghatározása a szokásos módon itt.
Aztán definiált lista egy globális mutató kezdeti értéke null.
Aztán úgy tűnik, van két funkció mi prototípusok itt, betét
és távolítsa el.
Aztán van néhány minta kódját itt csinál egy csomó betoldások.
És akkor kérjük, hogy töltse ki a végrehajtása betét alatt az ilyen
olyan módon, hogy az n beszúrja a listába állandó időben is hangsúlyozta,
még akkor is, ha már jelen van.
>> Tehát a szépség, hogy képes beszúrni állandó az idő, hogy ez azt jelenti,
hogy van, hogy be Az új csomópont, ahol?
Into az első.
Így megszünteti, szerencsére, legalábbis az egyik eset, hogy a használt igénylő
még több sornyi kódot, mint tette az elmúlt évben, és még az osztályban, amikor
Beszéltem keresztül ez a fajta dolog emberekkel és némi
verbális pszeudo kódot.
Tehát itt a megoldás, ugorjunk át az, hogy csak, hogy egy vizuális on
a képernyőn.
>> Figyeljük meg, hogy csinálunk a következő.
És azt is észre más egyszerűsítési az volt, hogy még akkor is, ha ez
már jelen van, így ez azt jelenti, akkor is, ha A szám már ott van, akkor
vakon be egy másik másolatát.
És ez is volt a célja, hogy egy egyszerűsítés, így lehet
összpontosít, tényleg, néhány a intellektuálisan érdekes rész és
nem csak néhány további hiba ellenőrzése tekintettel a korlátozott ideig.
>> Tehát ez a minta megoldás, kiosztani A mutató a bal oldali
másikra itt egy csomópont.
Most, rájönnek, hogy a mutató, mint Rob azt mondta, csak 32 bites.
És ez valójában nem tartalmaz egy címet, amíg meg nem
hozzá, hogy a címet.
És mi, hogy a jobb oldali oldalon keresztül malloc.
Mint egy jó állampolgár, akkor ellenőrizze, hogy malloc nem, sőt, null, úgy, hogy
nem véletlenül hoz létre a segfault itt.
És minden alkalommal, amikor a malloc az életben, akkor kell megnézni a null, nehogy
van egy bug.
>> Aztán inicializálni, hogy null által hozzárendelése n és az előző és a következő.
És ebben az esetben itt, inicializált megelőző null, mert ez az új
csomópont lesz az új elején a listámon.
Tehát ott lesz sem előtte.
És azt akarom, hogy alapvetően hozzáfűzni a meglévő listát az új csomópontot
beállítás mellett egyenlő a listára is.
De én nem vagyok kész csak még.
Tehát, ha maga a lista már létezett, és volt legalább egy csomópontot
már a helyén, ha ez a lista Itt és helyezzen be egy új csomópontot itt,
kell győződnie arról, hogy a korábbi csomópont rámutat hátra az új csomópontot,
mert ez megint kétszeresen láncolt lista.
>> Tehát mi a józan eszét csekket.
Ha a lista nem üres, ha nincs már egy vagy több csomópont van, akkor
Hozzáteszem, hogy vissza hivatkozás úgy mondjam.
És akkor az utolsó dolog, amire szükségünk tennie, hogy valóban frissíti a globális
változó lista maga pont az, hogy az új csomópontot.
Igen.
>> Közönség: A mutató nyíl [Hallhatatlan] egyenlő null, ez azt
foglalkozik a listán, mert a lista null?
>> David J. MALAN: Nem.
Ez egyszerűen nekem, hogy proaktív óvatos, az, hogy ha ez az én
eredeti listát és talán még néhány csomópont itt és én behelyezése a
Új csomópont ide, oda megy hogy semmi itt.
És szeretném megragadni, hogy az ötlet beállításával megelőző
null az új csomópontot.
És feltehetően, ha a kód helyes és nincs más módja annak, hogy be
csomópontok más, mint ez a funkció, Feltételezhető, hogy még akkor is ha a lista már
egy vagy több csomópont benne, feltehetően a listát, az első csomópont, volna egy
előző mutató null is.
>> Közönség: És csak a nyomon követést.
Az ok teszel mutató mellett egyenlő lista még van a mutató
előtt lista, hogy ez mutat a következő, azt hiszem -
Én nem -
csak listák?
>> David J. MALAN: Pontosan.
És így nézzük valóban úgy két esetben Itt tényleg, bár a
érdekében fogjuk tekintik őket, nem teljesen ugyanaz, mint a kódot.
De egy magas szinten, ha ez jelenti listát, és ez egy 32 bites
mutató, a legegyszerűbb forgatókönyv hogy ez null alapértelmezés szerint.
És tegyük fel, azt akarom, hogy helyezze be a szám 50 volt az első szám.
Szóval megyek előre, és osztja egy csomópont, ami megy, hogy tartalmazza
három területen -
n, az előző és a következő.
>> Megyek fel a számot 50 itt, mert ez lesz az n.
Ez lesz a következő.
És ez lesz az előző.
És mit tegyek ebben az esetben?
Nos, én már csak kész 1. sor itt.
Pointer n lesz n.
Én akkor azt mondja, a korábbi kéne null.
Tehát ez lesz null.
Majd fogok mondani legközelebb fog kapni listát.
>> És ez csak működik jól.
Ez null.
És azt mondom, az új csomópont következő mező kéne bármi is ez.
Tehát, hogy hozza egy null oda.
És akkor az utolsó dolog, Azt is ellenőrizze itt.
Ha a lista nem egyenlő a nulla, de a egyenlő nulla, ezért hagyja, hogy a
összesen.
És így minden, amit csinálni, lista lesz mutató, amely képileg eredményez
egy kép, mint ezt.
Tehát ez az egyik forgatókönyv.
>> És az egyik, hogy te kérdezett konkrétan az a helyzet, mint ez,
ahol már van egy node lista.
És ha megyek vissza az eredeti probléma megfogalmazását, a következő fogunk
be mondjuk 34, csak a A vita kedvéért.
Ezért fogok csak kényelmesen felhívni, hogy több mint itt.
Most malloced.
Tegyük fel, hogy én vagyok ellenőrzése null.
>> Most megyek inicializálása n, hogy 34..
És ez lesz az n.
Ez lesz a következő.
És ez lesz az előző.
Nézzük hogy biztos, hogy nem hogy ez visszafelé.
Előző előbb meghatározása.
Hadd erősít ez.
Ez a korábbi.
Ez a következő.
Annak ellenére, hogy ezek azonosak, maradjon is következetes.
>> Előző.
Ez a következő.
Szóval már csak malloced levelemet, ellenőrzött A null, célhoz kötött 34 a csomópontot.
Előző lesz null.
Annak érdekében, hogy ad nekem.
Következő lesz lista.
Tehát lista ez.
Tehát ez ugyanaz most is, mint ez a rajz nyíl, úgy, hogy pont egy
az azonos.
Aztán nézem ha a lista nem egyenlő null.
És ez most nem.
Majd fogok teendők előző kap mutató.
>> Tehát listára Előző lesz PTR.
Tehát ez az a hatása, hogy grafikus nyíl itt.
És ez kezd egy kicsit hullámos, a vonalak.
És akkor végül, azt frissíteni listát, hogy pont a mutató.
Tehát most ez arra mutat, hogy ez a fickó.
És most nézzük egy gyors józanság csekket.
>> Itt a lista, amely az a globális változót.
Az első csomópont, sőt, 34, mivel Én követő nyíl.
És ez helyes, mert azt akarom, hogy helyezze elején a lista
minden új csomópont.
A következő mezőben arra késztet, hogy ez a fickó.
Ha folyamatosan megy, elütöttem a következő null.
Tehát nincs több lista.
Ha hit korábbi, kapok vissza, ahol várják.
>> Tehát van még néhány mutató, Nyilvánvaló, hogy manipulálni.
De az a tény, hogy azt mondták, hogy nem ez az állandó idő azt jelenti, hogy csak
van egy véges számú dolog akkor tehetnek meg.
És mi ez a szám?
Lehet, hogy egy lépéssel.
Lehet, hogy kettő.
Lehet, hogy 1000 a lépéseket.
De ez véges, ami azt jelenti, hogy nem Van-e valamilyen loop folyik
itt, nem rekurzió, nincs hurok.
Ez csak most, hogy kódolt vonalak A kód, mint mi ebben a mintában.
>> Így a következő probléma 12 megkért minket, hogy teljes körű végrehajtása a Remove
alább oly módon, hogy eltávolítja n a listából lineáris időben.
Szóval van egy kicsit több kígyózik szobában most.
Lehet, hogy azt feltételezik, hogy n, ha van a listán, jelen lesz
nem több, mint egyszer.
És ez is azt jelentette, hogy a teszt-alapú egyszerűsítő feltételezéssel élünk, így
hogy ha megtalálja a 50-valahol szerepel a listán, akkor nem is
kell aggódnia, továbbra is ismételget, akik minden lehetséges
másolata 50, ami csak száll a néhány minutia korlátozott ideig.
>> Tehát remove, ez határozottan nagyobb kihívást jelent, és több
kódot írni.
De első pillantásra, őszintén szólva, ez talán néz elsöprő és mint valami
nincs mód, akkor lehetett volna felér egy kvíz.
De ha arra összpontosítunk, hogy az egyes lépések, remélem, hogy lesz hirtelen
sztrájk van, hogy minden ilyen egyéni lépéseket tesz nyilvánvaló értelme
visszatekintve.
Szóval vessünk egy pillantást.
>> Tehát először is inicializálni pointer hogy felsorolni is.
Mert azt akarom, lineáris idő, azt jelenti, Megyek egy kis hurok.
És egy közös utat végighaladni a csomópontok listáját szerkezet vagy bármilyen
a szerkezet is, hogy iteratív a mutató az első adatok
szerkezete és aztán csak elkezd frissítése , és járni az utat
az adatstruktúra révén.
Így fogok tenni, hogy pontosan.
>> Bár a mutató, az ideiglenes változó, nem egyenlő nulla, nézzük
megy előre, és ellenőrizze.
Volt szerencsém?
Az n mező a csomópont vagyok jelenleg néztem egyenlő a
szám, amit keresek?
És ha igen, csináljunk valamit.
Nos, észre ezt, ha a feltétel körülveszi az egész
következő sornyi kódot.
Ez az egyetlen dolog, amit érdekel - találni egy számot adott.
Szóval nincs más, ami egyszerűsíti dolgok fogalmilag egy kicsit.
>> De most rájöttem, és lehet, hogy csak rájött erre gondolkodás után
ez egy kicsit, ott van valójában két eset van.
Az egyik az, ahol a csomópont a kezdve a lista, amely a
kicsit bosszantó, mert ez a speciális eset, mert meg kell foglalkozni
ezt a dolgot, ami az egyetlen anomália.
Mindenütt a listán, ez ugyanaz a dolog.
Van egy korábbi csomópont és a következő csomópont, az előző csomópont, a következő csomópont.
De ez a fickó egy kicsit különleges ha ő az elején.
>> Tehát, ha a mutató megegyezik a lista is, így ha én vagyok az elején
a listát, és azt találtam n, meg kell hogy csinál egy pár dolgot.
Az egyik, hogy meg kell változtatni lista pont a következő mezőre, 50..
Tehát tegyük fel, hogy próbálom eltávolítani 34..
Szóval ez a srác kell mennie el csak egy pillanatra.
>> Így fogok mondani, lista lesz melletti mutatóra.
Nos, ez a mutató.
Következő mutat itt.
Tehát ez megváltoztatja ezt a nyílra Most, hogy pont ez a fickó itt.
Ne feledd, mi átmeneti változót.
Tehát mi nem árva olyan csomópontok, mert én is ezt a fickót én
végrehajtása remove.
Tehát most, ha a lista önmagában nem null, Azt kell rögzíteni egy kis valamit.
>> Meg kell bizonyosodni arról, hogy ezt a nyilat, amelyet korábban mutat
50-34, ez van, hogy menjen el, mert ha próbálok megszabadulni
34, 50, jobb nem tarthatnak fenn olyan fajta vissza hivatkozik rá, mint a
nyíl javasolta.
Szóval én csak tettem ezt a sort.
Így aztán kész vagyok.
Ez az ügy valójában nagyon egyszerű.
Szeletelés le a fejét a lista viszonylag egyszerű.
>> Sajnos, ez zavaró más blokk.
Tehát most, meg kell vizsgálni az ügyet ahol van valami a közepén.
De ez nem túl szörnyű, kivéve szintaxis, mint ez.
Tehát, ha én nem vagyok az elején a lista, én vagyok valahol a közepén.
És ez a vonal itt azt mondja, a Start Bármilyen node te meg.
Ugrás az előző csomópont következő mezőre és pont, hogy a mutató.
>> Csináljuk ezt képileg.
Az egyre bonyolultabb.
Tehát, ha van egy korábbi mezők itt - csináljuk - következő mezők itt.
Megyek, hogy egyszerűsítse a mutatók inkább mint felhívni egy csomó
dolog oda-vissza crisscrossing egymást.
És most, mondjuk, hogy ez 1, 2, 3. a vita kedvéért, még
bár ez nem sorakoznak a A szóban forgó probléma.
>> Tehát itt az én láncolt lista.
Próbálom, hogy távolítsa el a két jelen adott változata a történetnek.
Úgyhogy frissítve mutató mutatva ezzel a fickóval.
Szóval ez a PTR.
Ő mutat itt.
Ez a lista, amely létezik világszerte, mint korábban.
És ő mutat itt nem számít, mit.
És most, próbálom eltávolítani kettő.
>> Tehát, ha a mutató mutat itt vagyok fogja követni, úgy tűnik, a
előző mutató, amely helyére teszi meg 1.
Én akkor akartam mondani, hogy a következő mező, amely elvezet át ezt a
doboz itt fog egyenlő mutató a következő.
Szóval, ha ez a mutató, ez a következő.
Ez azt jelenti, hogy a nyíl igények hogy pont ez a fickó.
>> Tehát mi ezt a vonalat a kódot csak tett egy kicsit ezt.
És most, ez néz ki, mint egy lépés a helyes irányba.
Mi alapvetően szeretnénk nyissz 2 out A középső 1 és 3.
Így van értelme, hogy azt akarjuk, hogy út ez a mutató körül.
Tehát ez a következő sor annak ellenőrzése, hogy a mutató következő nem nulla, ott
Valóban valaki jobbra, 2, azt jelenti, hogy mi is a teendő
Egy kis nyissz itt.
>> Szóval most kell, hogy kövesse ezt a mutatót és frissíti a korábbi mutatót
ez a fickó, hogy csinál egy kicsit a Kerülő itt a lényeg itt.
És most, vizuálisan ez szép.
Ez egy kicsit zavaros, hogy van senki sem mutatott a 2. már.
2. mutat a bal oldalon.
És 2. jobbra mutató.
De ő tehet, amit akar, mert a úgy szól, hogy felszabadult.
És nem számít, milyen ezek az értékek már.
>> Mi a fontos az, hogy a többi fiúk routing felett
és alatta most.
És valóban, ez az, amit csinálni.
Mi ingyenes mutató, ami azt jelenti, hogy megmondja a operációs rendszer, akkor várjuk
vissza ezt.
És akkor végül visszatérünk.
Else implicit, ha nem tért vissza még,
megvan, hogy keresd.
Tehát mutató értéke mutató mellett csak azt jelenti, mozog ez a fickó.
Mozgás ez a fickó itt.
Mozgás ez a fickó itt, ha, sőt, mi nem találja a számot
keresünk még.
>> Tehát őszintén szólva, úgy néz ki, teljesen elsöprő, azt hiszem, az első
Dióhéjban, különösen akkor, ha küszködött ezzel az kvízt aztán majd meglátjuk,
valami ilyesmi.
És pat magad a hátán.
Nos, nincs mód arra, hogy van jön ki, hogy a kvíz.
De én azt állítják, akkor ha törik le ezekbe az egyéni
esetekben és csak gyalog rajta óvatosan, bár, igaz, alatt
stresszes körülmények között.
>> Szerencsére a kép készült Mindent boldogabb.
Lehet rajzolni ezt tetszőleges számú módon.
Önnek nem kell tennie a crisscrossing dolog itt.
Lehet csinálni egyenes hasonló sor.
De a lényege ezt a problémát, Általában az volt, hogy észre, hogy a
képet a végén kell meg egy kicsit valami ilyesmi, mert a
állandó alkalommal azt sugallta, hogy tartsa a zavarás és zavarás és zavarás a
új csomópontokat az elején a listán.
Bármilyen kérdése?
Talán a legnagyobb kihívást a minden bizonnyal a kódolás kérdésekre.
>> Közönség: Szóval lista hasonló fej az előző példákban.
>> David J. MALAN: Pontosan, pontosan.
Csak egy másik nevet egy globális változót.
Világszerte mi?
>> ROB BOWDEN: OK.
Tehát ez az egyik, ahol kellett írni a bekezdést.
Vannak, akik azt írta esszék ezt a kérdést.
De akkor csak meg kell használni ezeket a kifejezéseket a hat arra, hogy mi történik, ha
megpróbál kapcsolatba lépni facebook.com.
Szóval, én csak beszélek a folyamat használja ezeket a kifejezéseket.
Tehát mi a böngésző, akkor írja facebook.com és nyomja meg az Entert.
Így a böngészőt fog építeni egy HTTP kérés, hogy ez fog küldeni
valamilyen folyamat Facebook Facebook, hogy válaszoljon nekünk a
HTML az oldalon.
>> Tehát mi az a folyamat, amely a HTTP kérés
valóban kap a Facebook?
Tehát először meg kell fordítani Facebook.com.
Tehát most adott nevet Facebook.com, ahol valójában nem a HTTP kérés
kell menni?
Tehát meg kell fordítani Facebook.com hogy az IP-cím, amely egyedülállóan
megállapítja, hogy milyen gép valójában szeretné küldeni ezt a kérést.
A laptop van IP-címe.
Bármi, ami csatlakozik az internethez van IP-címe.
>> Tehát DNS, Domain Name System, azaz mi fog kezelni a fordítás
A facebook.com az IP címet, ha valóban szeretne kapcsolatba lépni.
Tehát mi a kapcsolatot a DNS-kiszolgálók és mondjuk, mi facebook.com?
Azt mondja, ó, ez az IP-címet 190,212 valami, valami, valami.
Rendben van.
Most már tudom, mi a gép Szeretném felvenni a kapcsolatot.
>> Szóval, akkor küldje el a HTTP-kérelem át, hogy az a gép.
Szóval, hogyan jut el, hogy a gép?
Nos, a kérést megy router a router Pattogó.
Ne feledje, a példában az osztályban, ahol a mi valóban látta az út, hogy a
csomagokat vett, amikor megpróbáltuk kommunikálni.
Láttuk, hogy átugorjuk az Atlanti-óceán Ocean egy ponton, vagy bármi.
>> Így az utolsó kifejezés port.
Szóval ez már a számítógépen.
Egyszerre több dolgok jelenlegi kommunikál az interneten.
Szóval lehet futás, mondjuk, a Skype.
Én lehet, hogy a böngésző nyitva.
Talán van valami, ami torrenting fájlokat.
Szóval ezek a dolgok kommunikál a
internet valamilyen módon.
>> Tehát, ha a számítógép kap néhány adatot az interneten, hogy hogyan csinálja
tudom, mi alkalmazás valójában szeretné, ha az adatokat?
Honnan tudja, hogy az adott adatok célja a
torrenting alkalmazás szemben A böngésző?
Tehát ez a célja a portokat, hogy az összes ilyen alkalmazások
azt állította, a port a számítógépen.
Tehát a böngésző azt mondja, hé, Hallgatom porton 1000.
És a torrenting program azt mondja, Hallgatom porton 3000.
És a Skype azt mondja, én vagyok a port 4000.
>> Tehát, ha egy kis tartozó adatokat hogy egy ilyen alkalmazás, az adatok
van ellátva, amely port valójában kell küldeni mentén.
Tehát ez azt mondja, jaj, tartozom a port 1000.
Tudom, hogy akkor kell, hogy továbbítsa ezt az mentén a böngésző.
Tehát az oka, hogy fontos itt az, hogy a webszerverek általában
hallgatni 80-as porton.
Tehát, amikor kapcsolatba Facebook.com vagyok kommunikál néhány gépen.
De azt kell mondanom, melyik port, hogy a gépet akarok kommunikálni.
És webszerverek általában hallgat 80-as porton.
>> Ha azt akarták, tudták beállítani fel, így felsorolja, mint a 7000-es port.
És aztán egy web böngésző, tudtam manuálisan Facebook.com: 7000
elküldi a kérelmet, hogy 7000-es port Facebook webszervert.
>> David J. MALAN: És ebben az esetben is, bár mi nem követeli meg, hogy az emberek
említem ezt, ebben az esetben, milyen port azt a kérést valóban megy?
Próbálja újra.
Pontosan.
Nem keres, de a finomság hogy ott van, sem az utolsó.
>> ROB BOWDEN: Tehát a HTTPS, mivel ez hallgatta kifejezetten a
titkosított, akkor a port 4430.
>> Közönség: és e-mailek 25, nem igaz?
>> David J. MALAN: kiutazó e-mailek, 25, igen.
>> ROB BOWDEN: Én nem is tudom, a legtöbb a - mind az alsó is általában
fenntartva dolgokat.
Azt hiszem, minden alatt 1024 fenntartva.
>> Közönség: Miért mondod 3 volt a rossz számot?
>> ROB BOWDEN: Mivel egy IP-címet, van négy csoportok számjegy.
És ők 0 és 255 között.
Tehát egy közös 192.168.2.1 helyi hálózati IP-címet.
Figyeljük meg az összes ilyen kevesebb, mint 255..
Tehát, amikor elkezdtem, 300, hogy a nem lehetett volna
volt az egyik számot.
>> David J. MALAN: De buta klip a - volt CSI, ahol volt egy
szám, amely túl nagy volt az IP-cím.
>> ROB BOWDEN: bármilyen kérdése van ez?
A következő, tehát a teljes változás topic, de itt van ez a PHP tömb
A házak a quad.
És van egy rendezetlen listát.
És szeretnénk kinyomtatni lista elemeit csak tartalmazza a ház nevét.
Tehát van egy foreach ciklus.
Úgy emlékszem, a szintaxis foreach tömb elem a tömbben.
Így az egyes iteráció a hurok ház lesz, hogy az egyik
értékek a tömb belsejébe.
>> Az első iteráció, house lesz Cabot House.
Egy második iteráció, ház legyen Courier Ház és így tovább.
Tehát minden quad, mint a ház, mi csak fog nyomtatni -
akkor is lehetett volna visszhangozta -
A lista elemet, majd a ház nevét majd zárja be a lista elemet.
A kapcsos zárójelek opcionális itt.
>> És akkor azt is elmondta, a kérdés magát, ne feledje, hogy zárja be a
rendezetlen lista tag.
Tehát szükségünk van a kilépéshez a PHP módba annak érdekében, hogy erre a célra.
Vagy volna visszhangzott a zárja rendezetlen lista tag.
>> David J. MALAN: Szintén jó itt lenne volna, hogy egy régi iskola
loop egy $ i = 0 0. és a számít a kitaláljuk, a hossza a sugár.
Teljesen finom is, csak Egy kicsit wordier.
>> Közönség: Tehát, ha akartál [Hallhatatlan] tennél -
Nem emlékszem, mi a hurok [hallható] is.
Szeretne $ quad konzol i?
>> David J. MALAN: Pontosan.
Igen, pontosan.
>> ROB BOWDEN: Van még valami?
>> David J. MALAN: Rendben.
Kompromisszumokat.
Tehát voltak fürtök válaszok lehetséges minden egyes ilyen.
Mi tényleg csak keres valami ellenállhatatlan egy fejjel és
a hátránya.
És a 16-kérdezte érvényesítése felhasználók input kliens-oldali, mint a JavaScript,
helyett a szerver oldali, mint a PHP.
Tehát mi egy fejjel Ennek kliens-oldali?
>> Nos, az egyik dolog, amit javasolt hogy csökkentse késleltetést, mert
nem kell bajlódnia a kapcsolatot a szerver, amely eltarthat néhány
ezredmásodperc, vagy akár egy pár másodpercig elkerülve azt, és csak a
érvényesítése a felhasználók hozzájárulása kliensoldali by kiváltó egy on-be felvezető és
Csak ellenőrzöm, ugye írja valamit a név?
Vajon be valami az e-mail cím?
Vajon válasszon egy kollégiumi a A legördülő menüből?
>> Adhat nekik azonnali visszajelzést a gigahertz számítógép
vagy bármi más van, ami valójában az asztalon.
Szóval, ez csak a jobb felhasználói tapasztal általában.
De egy hátránya ennek kliensoldali érvényesítése, ha ez nem is
Ennek szerver oldali érvényesítésre, legtöbb valaki jön ki a CS50 tudja
hogy ha csak küldeni kívánt adatokat a szerveren tetszőleges számú módon.
Őszintén szólva, a legtöbb minden böngésző, akkor kattintson körül a beállításokat, és csak
kapcsolja ki a JavaScript, amely, ezért ki minden formáját
érvényesítés.
>> De azt is lehet, hogy emlékeztetnek arra, hogy még én is volt néhány misztikus dolgok az osztályban a
telnet és valóban úgy tesz, mintha egy böngészőt küldött get
kéri, hogy a szerveren.
És ez természetesen nem tetszőleges JavaScript.
Ez csak nekem parancsokat gépelünk egy billentyűzet.
Szóval tényleg, minden programozó belül elég kényelem az interneten, és HTTP
lehet küldeni bármilyen adatot akar venni a szerveren ellenőrzés nélkül.
És ha a szerver nem is ellenőrzi, nem adnak nekem egy név,
ez valójában egy érvényes e-mail címet nem úgy döntenek, egy kollégiumi, lehet, hogy végül
behelyezése hamis, vagy csak üres adat be az adatbázisba, ami valószínűleg
nem lesz egy jó dolog, ha te feltételezve, hogy ott van.
>> Tehát ez egy bosszantó valóság.
De általában, a kliens-oldali érvényesítés nagyszerű.
De ez azt jelenti, kétszer annyi munkát.
Annak ellenére, hogy léteznek különböző könyvtárak, JavaScript könyvtárak
Például, hogy ezt sok, sokkal kevesebb a fejfájás.
És akkor újra néhány kód szerver-oldali, kliens-oldalon.
De nem veszik észre, hogy általában további munkát.
Igen.
>> Közönség: Tehát, ha mi csak szerint kevésbé biztonságos -
>> DAVID J. MALAN: [nevet]
Huh.
Ezek mindig a nehezebb is határozni.
>> ROB BOWDEN: Ez lenne elfogadták.
>> David J. MALAN: Mi?
>> ROB BOWDEN: hoztam létre ezt a problémát.
Ez azt elfogadták.
>> David J. MALAN: Igen.
>> Közönség: Cool.
>> ROB BOWDEN: De nem fogadta el Az első -
Nos, mi kerestünk egy valami olyasmit, hogy nem kell
kommunikálni a szerverrel.
Nem fogadja el, csak gyorsabb.
>> Közönség: Mi a helyzet nem újratölti az oldalt?
>> ROB BOWDEN: Igen.
Ez egy elfogadott válasz.
>> David J. MALAN: bármi, ahol úgy éreztük, volt valószínűbb, mint nem valószínű
hogy tudja, mit mondván, amely egy kemény
sorban felhívni néha.
Egy láncolt lista helyett egy tömb, hogy fenntartsák a
rendezett lista az egész.
Így egy fejjel gyakran idézik a kapcsolt listák motivált az egész
bevezetése volt, kapsz dinamizmus.
Ezek nőhet.
Ők is csökken.
Szóval nem kell ugrik át karika hogy valóban létre több memóriát
egy tömb.
Vagy nem kell, hogy csak azt mondják, bocs, a felhasználó.
A tömb tele van.
Tehát dinamikus növekedése a listán.
A hátránya, bár a kapcsolt listák?
>> Közönség: Ez lineáris.
Keresés a láncolt lista lineáris ahelyett, hogy mit jelentkezzen be
>> David J. MALAN: Pontosan.
Keresés a láncolt lista lineáris, még akkor is, ha ez sorrendje, mert akkor
csak az alábbi zsemlemorzsa, ezek mutatók, a kezdetektől a lista
a végére.
Nem lehet kihasználhatják véletlenszerű hozzáférés, és Így, bináris keresés, akkor is, ha ez
sorrendje, amit lehetett köze egy tömb.
És van még egy költség.
Igen.
>> Közönség: Memória hatékony?
>> David J. MALAN: Igen.
Nos, én nem feltétlenül mondjuk nem hatékony.
De ez nem költsége is több memóriát, mert szükség van 32 bit minden
node a további mutató, a legalábbis egy egyszeresen láncolt lista.
Nos, ha csak a tárolás egész számok és te hozzá a mutatót, ami
valójában milyen nem triviális.
Ez megduplázza a memória.
De a valóságban, ha tárolása láncolt lista a struktúrákat, amelyek rendelkeznek
8 bájt, 16 byte, még mint, hogy talán kevésbé
A marginális költség.
De ez a költség mégis.
Tehát bármelyik ezek volna volt, finom, mint a hátrányai.
>> 18..
PHP helyett C írni parancssori programot.
Tehát itt, ez gyakran gyorsabb használni a nyelv, mint a PHP vagy Ruby és Python.
Csak gyors megnyitásához egy szövegszerkesztő.
Van még sok más funkciót áll az Ön rendelkezésére.
A PHP a konyhai mosogató funkciók, míg a C, akkor
nagyon, nagyon kevés.
Tény, hogy a srácok az tudja, a nehezebb utat hogy nincs hash táblákat.
Nem is kapcsolódik listákat.
Ha azt szeretné azokat, akkor a végre rájuk.
>> Tehát az egyik fejjel PHP vagy tényleg olyan értelmezett nyelv a gyorsaság
, amivel lehet írni a kódot.
De egy hátránya, láttuk ezt, amikor hamar felkorbácsolta a misspeller
végrehajtás előadás a PHP, az , hogy használ egy értelmezett nyelv
általában lassabb.
És láttuk, hogy bizonyíthatóan egy növekedése idő 0,3 másodperc és 3
másodperc, mert az értelmezés hogy valóban megtörténik.
>> A másik fejjel volt, hogy nem kell lefordítani.
Tehát ez is gyorsítja a fejlődést egyébként, mert nem kell
két lépést, hogy egy program futtatása.
Csak egy.
És ez elég lenyűgöző is.
Egy SQL adatbázis helyett CSV fájl az adatok tárolására.
Tehát SQL adatbázist használják pset7.
CSV fájlokat, nem használt sokat.
De használta közvetett módon pset7 mint jól beszél a Yahoo Finance.
>> De CSV olyan, mint egy Excel-fájlt, de szuper egyszerű, ahol az oszlopok
csak demarked vesszővel belül az egyébként szöveges fájl.
És egy SQL adatbázis egy kicsit vonzóbb.
Ez egy fordított, mert a dolgokat mint kiválasztani és beszúrni és törölni.
És kapsz, feltehetően indexek MySQL és más adatbázisok, mint például
Oracle, épít az Ön számára a memóriában, ami azt jelenti, hogy válassza valószínűleg nem
lesz lineáris fentről lefelé.
Ez tényleg lesz valami mint a bináris keresés, vagy valami
hasonló szellemben.
Így ők általában gyorsabb.
>> De egy hátránya, hogy ez csak több munkát.
Ez több erőfeszítést.
Meg kell értenie adatbázisok.
Meg kell beállítani.
Szüksége van egy szerver fut hogy az adatbázis.
Meg kell értened, hogyan kell beállítani azt.
Tehát ezek csak ezek a féle kompromisszumokat.
Mivel a CSV fájlt, akkor hozza létre a gedit.
És te jó menni.
Nincs komplexitás túl.
>> Egy trie helyett hash tábla külön láncolási tárolni a
szótár szavak emlékeztető A pset5.
Tehát egy megpróbál fejjel, elméletben legalábbis az, ami?
Állandó idő, legalábbis ha hashelés az egyes egyéni
betűk egy szó, mint te Lehet, hogy a pset5.
Ez lehet öt hash, hat hash kódok ha van öt vagy hat
betűk a szó.
És ez nagyon jó.
És ha van egy felső határa, hogyan Hosszú a szavaidat lehet, hogy ez
Valóban aszimptotikusan konstans id.
>> Mivel hash tábla külön láncolás, a probléma az, hogy az ott
fajta adatstruktúra az, hogy a teljesítményét algoritmusok általában
számától függ a dolog már az adatszerkezet.
És ez minden bizonnyal a helyzet láncok, ahol a több dolgot tesz
egy hash tábla, a hosszabb azok láncok megy, ami azt jelenti, a legrosszabb
esetben a dolog, lehet, hogy keres ez egészen a végén egy
azoknak a láncok, amely hatékonyan hárul valami lineáris.
>> Most a gyakorlatban lehetett teljesen a helyzet, hogy a hash tábla
láncok gyorsabb, mint a megfelelő trie végrehajtását.
De ez különböző okok miatt, többek között amelyek a próbálkozás egy csomó
memória is, sőt, lassan a dolgok le, mert akkor nem kap szép
előnyei úgynevezett caching, ahol a dolgokat, amelyek közel vannak egymáshoz
memóriában lehet elérni gyakran gyorsabban.
És néha akkor is elér Egy igazán jó hash függvényt.
Akkor is, ha a hulladék egy kicsit memória, lehet, hogy valóban képes lesz
a dolgok gyors, és nem olyan rossz, mint lineárisan.
>> Tehát röviden, nem volt feltétlenül ezekkel egy vagy akár két
konkrét dolgokat kerestünk.
Tényleg valami meggyőző mint inflációt növelő és csökkentő
általában elkapta a szemét.
>> ROB BOWDEN: Tehát a fejjel, mi nem fogadja el a saját "gyorsabb". Ön
kellett mondani valamit róla.
Akkor is, ha azt mondta elméletileg gyorsabb, tudtuk, hogy ilyen ismert
hogy ez 0 1.
És hash tábla, elméletben, nem 0 1.
Említése semmit runtime általában neked a pontokat.
De a "gyorsabb", a legtöbb megoldások a nagy fórumon, hogy volt próbálkozás volt
objektíven lassabb megoldások amelyek hash táblákat.
Így gyorsabban és önmagában nem igazán igaz.
>> David J. MALAN: Dom de dom dom.
Valószínűleg én vagyok az egyetlen, aki rájön, ez az, hogy hogyan kéne
kell kiejteni, nem igaz?
>> ROB BOWDEN: Én valóban nem tudom.
>> David J. MALAN: Ez történt értelme a fejemben.
>> ROB BOWDEN: csinálom ezt.
OK.
Tehát ez az, ahol meg kellett rajzolni A diagram hasonló lehet, hogy
láttam a korábbi vizsgák.
Tehát nézzük csak nézd meg ezt.
Tehát a HTML csomópont, van két a gyermekek, a fej és a test.
Tehát ág - fej és a test.
A fej egy címet tag.
Tehát van egy címet.
>> Most, az egyetlen dolog, amit egy csomó ember elfelejtettem, hogy ezeket a szöveges csomópontok
elemei ezt a fát.
Tehát itt történni felhívni őket ovális hogy megkülönböztessék őket a következő
csomópontok.
De figyeljük meg itt is van felső, középső és alsó, majd a végén, hogy
Szöveg csomópontok.
Tehát megfeledkezve azokról kissé Egy gyakori hiba.
>> A test három gyermek - a három divs.
Tehát div, div, div, majd a szöveget csomópont gyermekei azok divs.
Ez nagyjából azt az, hogy a kérdések.
>> David J. MALAN És érdemes megjegyezni, még akkor is, ha nem laknak ezeken a
részleteket az időt töltünk a JavaScript, hogy a sorrend nem, a
Sőt, az anyag technikailag.
Tehát, ha a fej megelőzi test a HTML, akkor meg kell jelennie a
maradt a test az aktuális DOM.
Ez az övé, általában, csak hogy tudd, úgynevezett dokumentum annak érdekében, ahol a
nem mindegy.
És ha te megvalósítása elemző, egy programot, amely beolvassa HTML épületben
fel a fa a memóriában, hogy őszinte legyek, ez az, ösztönösen talán, amit
ezt egyébként - fentről lefelé, balról jobbra.
>> ROB BOWDEN: Kérdések, hogy?
Ha én a következő?
>> David J. MALAN: Persze.
>> ROB BOWDEN: OK.
Tehát ez a puffertúlcsordulást támadás kérdés.
A legfontosabb dolog, hogy ismerje itt, Nos, hogy lehet, hogy egy támadó trükk
a program futtatását tetszőleges kódot?
Tehát argv1, az első parancssor érv, hogy ezt a programot, amely lehet
tetszőlegesen hosszú.
De itt mi használ memcpy másolni argv1, ami itt található.
Mi halad, mint az érvelés.
És ez így tart a nevet bárban.
>> Szóval memcpying bar ebbe a puffer c.
Hány bájt vagyunk másol?
Hát de sok bájt sáv történik használja, a hossza az érvet.
De c mindössze 12 bájt széles.
Tehát, ha azt írja be a parancssori argumentum , ami hosszabb, mint 12 bájt, vagyunk
fog túlcsordulás ezt különös puffer.
Most, hogy lehet, hogy egy támadó becsapni a beprogramozni végrehajtása tetszőleges kód?
>> Úgy emlékszem, hogy itt Fő hívja foo.
És így aztán fő meghívja ize.
Nézzük felhívni a.
Tehát a verem.
És a legfontosabb egy verem keret az alján.
Egy bizonyos ponton, fő meghívja ize.
Nos, azonnal, fő meghívja ize.
És így foo kap saját verem keret.
>> Nos, egy bizonyos ponton, ize megy vissza.
És elment foo visszatér, tudnunk kell, hogy a milyen kódsor belsejében fő is
volt ahhoz, hogy tudja, hol kellene folytatódik fő.
Nevezhetjük foo egy egész csomó különböző helyeken.
Honnan tudjuk, hogy hol, hogy visszatérjen?
Nos, meg kell tárolni valahol.
>> Tehát valahol jobb itt, tárolunk ahol vissza kell egyszer
foo visszatér.
És ez a feladó címét.
Szóval, hogy ellenfele lehet kihasználni erre az a tény, hogy a
ez a puffer c tároljuk, nézzük azt mondják, itt van c.
Tehát van 12 bájt c.
Ez kb.
És ez az izé a stack gyűrűt.
Tehát, ha a rosszindulatú felhasználó belép több bájt, mint 12, vagy írjon be egy parancsot
argumentum, ami hosszabb, mint 12 karaktert, majd megyünk
túlcsordul a puffert.
>> Tudjuk tartani fog.
És egy bizonyos ponton, megyünk messzire elég, hogy kezdjük
felülírja ezt a feladó címét.
Tehát, ha azt írja felül a feladó címét, ez azt jelenti, hogy amikor az ize
vissza, most visszatér, ahol a rosszindulatú felhasználó mondja azt, hogy az
milyen értéket lépett, bármilyen karakter a felhasználó által megadott.
És így, ha a rosszindulatú felhasználó, hogy különösen okos, tudja, hogy ez a
vissza a valahol a printDef funkciót, vagy valahol a malloc
funkció, akárhonnan önkényes.
>> De még ennél is ügyes az, mi van, ha ő a felhasználó visszatér ide.
És akkor elkezd végrehajtása ezeket sornyi kódot.
Tehát ezen a ponton, a felhasználó megadhatja amit akar ebbe a régióba.
És teljes ellenőrzése át a programot.
Kérdések az, hogy?
Így a következő kérdés befejeződött a újraírását foo oly módon,
, hogy ez már nem sebezhető.
>> Szóval van egy pár módon Ön képes lett volna erre.
Még mindig csak c- hogy a hossz 12.
Ön megváltoztatná az részeként a megoldás.
Azt is hozzátette, egy csekket, hogy a biztos, bár nem null.
Bár akkor nem kell hogy teljes hitelt.
Szóval először ellenőrzi a karakterlánc hossza bar.
Ha ez nagyobb, mint 12, akkor valójában nem ezt a példányt.
Tehát ez az egyik módja a rögzítés is.
>> Egy másik módja a rögzítés ez helyett miután c csak a hossz 12, megvan
lehetnek hosszú strlen (bar).
Egy másik módja a rögzítés van hogy valójában csak vissza.
Tehát, ha épp most ütött megszabadulni az összes ezt, ha éppen törölte az összes
sornyi kódot, akkor ütött a teljes hitelt, mivel ezt a funkciót
valójában nem elérni semmit.
Ez másolása a parancssorba érvelést néhány tömb
helyi verem keret.
És akkor a dolog visszatér.
És bármi is megvalósult elment.
Így vissza is elegendő módja a teljes hitelt.
>> David J. MALAN: Nem egészen jegyében a kérdés, de elfogadható a per
spec mégis.
>> ROB BOWDEN: Kérdések sem, hogy?
Az egyetlen dolog, amit legalább szükséges, hogy összeállítása kódot.
Tehát annak ellenére, hogy technikailag meg nem veszélyeztetett, ha a kódot nem
össze, azt nem fogadja el, hogy.
Nem kérdés?
OK.
>> David J. MALAN: Akarsz mondani ezt a címet?
>> ROB BOWDEN: Nem.
>> David J. MALAN: Tehát ez, ez volt, vagy jó hír, vagy rossz hír.
Ez szó szerint ugyanaz a probléma mint az első teszt.
És ez szinte azonos problémát pset1.
De szándékosan egyszerűsített, hogy egyszerűbb piramis, az egyik, hogy lehet
megoldható egy kissé egyszerűbb iteráció.
És tényleg, mi voltunk kilyukadni itt nem annyira a logika,
mert valószínűleg, ez a pont, akkor kényelmesebb, mint te
A héten az egyik a hurkok vagy miért hurkok, de tényleg ugratni egymástól, hogy
te egy kicsit kényelmes a elképzelést, hogy a PHP nem csak arról, hogy mi
programozás.
Azt is lehet használni, mint egy nyelv írni parancssori programokat.
>> És valóban, ez az, amit akartunk felhívni a figyelmet.
Ez egy parancssori PHP program.
Tehát C kód van, míg a helyes C-ben nem javítja a PHP.
De a kód valóban ugyanaz.
Ha összehasonlítjuk a megoldásokat Quiz 0 ellen kvíz 1., rájössz, hogy
ez csaknem azonos, kivéve Néhány dollár jeleket, és a
nincs adat típusát.
Különösen, ha veszünk egy pillantást ide, látni fogod, hogy mi léptetjük, ebben a
esetben az 1-től egészen 7.
>> Tudtuk volna, hogy 0. index.
De néha, azt hiszem, ez csak mentálisan könnyebb gondolni a dolgokat
1-7.
Ha szeretne egy blokk, akkor két blokkok, aztán három, majd
pont, pont, pont hét.
Mi j inicializálása 1 majd számítok fel i.
És itt minden egyébként azonos.
De figyelemre méltó a egy-két dolgot.
Adunk a két vonal, az első Egy, goofily nevezték a kocsma
éles bumm.
És ez csak megadja az elérési utat, a mappát, amelyben a program lehet
úgy találta, hogy a használni kívánt értelmezni ezt a fájlt.
>> És akkor a vonal után, hogy a Persze, azt be PHP módba.
És a sort a legalján azt jelenti, exit PHP módot.
És ez működik, az általános, a értelmezett nyelvekhez.
Elég bosszantó, ha levelet program nevű fájlt foo.php.
És akkor a felhasználóknak, hogy csak emlékszem, OK, futtatni ezt a programot, azt
kell beírni: "php tér foo.php." Kedves A bosszantó, ha semmi mást.
És az is kiderül, hogy a programban PHP-ben íródott, ami nem minden
Világítási, hogy a felhasználó számára.
>> Szóval lehet eltávolítani a. Php összesen emlékszem az előadás.
És tudod valójában csinál. / Foo ha már chmodded meg azáltal, hogy
futtatható.
Tehát chmod a + x ize volna ezt.
És ha még hozzá a kocsma itt.
De tényleg, a probléma kilyukadni kinyomtatásával valami ilyesmi.
HTML, nem C-kód természetesen, csak néhány PHP.
Így Milo majd visszatért a probléma 25.
És 25, akkor kaptak a következő csontváz-kód, ami egy
nagyon egyszerű weboldal.
És a szaftos rész HTML-bölcs volt, meg itt, ahol van a test belsejébe
olyan formában, amely egyedi azonosítója bemenet amelynek belsejében két bemenet volt, az egyik
egy ötlet a név, egy egy ötlet gombot.
>> Az első típus a szöveget, a második típusú be.
És így adtam neked, valójában több összetevőket, mint szükséges, csak így
nektek volt lehetőség, amellyel megoldani ezt a problémát.
Nem feltétlenül kell, az összes ilyen azonosítók.
De ez lehetővé teszi, hogy megoldani azt különböző módokon.
És fel a csúcsra, észreveszi, hogy A cél az volt, hogy kiváltó
ablak, mint ez -
Helló, Milo! -
felbukkan a böngésző segítségével A szuper egyszerű, ha a
nem csúnya, riasztási funkciót.
És így, végül is ez a lényeg, fogalmilag valahogy hallgatta
beadványok az űrlap kliensoldali , És nem a szerver oldali, valahogy
válaszol, hogy a beadvány megragadta az érték, amit a felhasználó beírt
az, hogy a név mezőben, majd jeleníti meg a szervezetben a riasztás.
>> Tehát az egyik mód, akkor ezt a jQuery, ami úgy néz ki, egy kicsit
szintaktikailag zavarba ejtő az elején.
Ezt megteheti a tiszta DOM kód - document.getelement ID.
De vessünk egy pillantást a verzió.
Nekem van egy pár fontos vonalak először.
Tehát az egyik, hogy van ez a vonal, ami megegyezik azzal, amit látott
ben, azt hiszem, form2.html az osztály 9. hét.
És ez is csak azt mondom, végre az alábbi kódot, amikor
A dokumentum készen áll.
Mivel ez fontos, csak azért, mert HTML oldalak olvas felülről
lefelé, balról jobbra.
>> És ezért, ha megpróbál tenni valami kódot itt néhány DOM
elem, néhány HTML tag, ami le Itt csinálod túl hamar,
mert ez már nem is beolvasott a memóriába.
Tehát ezt mondta document.ready vonal, azt mondjuk,
itt van egy kis kódot, a böngésző.
De ne hajtsa végre ezt, amíg az egész dokumentum készen áll, azaz a DOM
fa létezik a memóriában.
Ez egy kicsit több, egyszerű, ha szintaktikailag a
kicsit más, amikor azt mondom, fogd A HTML elem, amelynek egyedi
azonosító bemenet.
Ez az, amit a hash tag jelöli, az egyedi azonosító.
És akkor hívlak. Be.
>> Tehát. Be itt van egy függvény, egyébként ismert módszer, ami
belsejében a tárgyat a bal oldali oldalon van, hogy nem kiemelni.
Tehát, ha úgy gondolja, a bemenetek, mint egy tárgy a memóriában -, és valóban az is.
Ez egy csomópont egy fa -
. Be eszközöket, amikor ez a forma az azonosító benyújtják, végre
a következő kódot.
Nem érdekel, hogy mi a neve a függvény Én végrehajtása.
Tehát itt vagyok használ, mint korábban, mi úgynevezett lambda funkcióból, vagy olyan
névtelen funkciót.
Ez egyáltalán nem intellektuálisan érdekes, azon kívül, hogy nincs neve,
ami rendben van, ha te csak valaha is hívni egyszer.
És belül ott valóban kezelni benyújtása az űrlapot.
Először, hogy egy változót nevű értéket.
És akkor mi a hatása ennek a kiemelt része, most itt?
Mit jelent, amelyek egy magas nekem?
>> Közönség: Ez lesz az érték, amit a a felhasználó nem a HTML alább.
Ez lesz, hogy az ID, majd megállapítja az értékét.
>> David J. MALAN: Pontosan.
Ez megragadja a csomópont, melynek egyedi azonosító nevet.
Ez az érték lesz benne, amely van, feltehetően, hogy a felhasználó mit
gépelt saját maga.
És akkor tárolja, hogy a nevű változó értékét.
Mellesleg, akkor is előfordulhat, hogy tette ezt egy kicsit másképp.
Teljesen elfogadható csinál valamit hazugság var értékét kapja
document.getElementById.
És ez az oka annak, hogy ez egy kicsit unalmas, hogy nem használja jQuery.
"Name". Értéket.
Így teljesen elfogadható.
Különböző módon teheti meg. jQuery csak inkább egy kicsit tömör és
határozottan népszerűbb programozók körében.
>> Most csinálok egy kis józanság ellenőrizni, mert a probléma
adatok azt egyértelműen azt mondta, ha a a felhasználó még nem írt ő
név, nem mutatnak figyelmeztetéseket.
De lehet ellenőrizni, hogy az csak a ellenőrzi az üres karakterlánc a
idézet, idézet vége, ha van semmi valójában van.
De ha ez nem egyenlő az idézet, idézet vége, Szeretném felhívni figyelmeztetéseket.
És az érdekes része az, hogy mi a Plusz operátor, amely
mit JavaScript?
Összefűzni.
Szóval, ez olyan, mint phps dot operátor.
Ugyanez a gondolat, kicsit más szintaxist.
És én csak létre a húr, amely láttad a képernyőn lövés -
Helló, így és így.
>> És akkor az utolsó részlet is ezt.
Miért return false belül Ennek névtelen funkciót?
>> Közönség: Nincs értéket.
Te tedd formában.
Csak azt mondja, ha az érték nem egyenlő üres, akkor csináld.
Volt egy üres előterjesztés.
>> David J. MALAN: OK.
Óvatosan mégis.
Nincs itt senki más.
És return false kívül A ha a körülmények.
Szóval ez a kiemelt sor, return false, végrehajtja nem számít, milyen, amikor
Az űrlap elküldése.
Mit jelent a visszatérő téves belsejében ennek eseménykezelő, ahogy hívják,
a szóban forgó esemény lenni benyújtás?
>> Közönség: Mert csak egyszer.
>> David J. MALAN: csak egyszer.
Nem egészen.
Igen?
>> Közönség: Megakadályozza az űrlap benyújtása az alapértelmezett viselkedés,
ami, hogy az oldal újratöltése.
>> David J. MALAN: Pontosan.
Szóval túlterhelése a kifejezést be itt, mert én csak azt mondom, a forma
benyújtják.
De ahogy azt sugallják, hogy ez valójában nem nyújtottak be az igaz HTTP utat.
Amikor a Küldés gombra kattint, mert a mi onSubmit handler, mi elfogó
hogy űrlapküldés hogy úgy mondjam.
Mi akkor tesszük a dolgunkat JavaScript kódot.
De én szándékosan vissza hamis, mert amit nem akarok, hogy megtörténjen a
pillanattal később is az egész űrlap magát, be kell nyújtani a weben
szerver kulcs-érték párból változtatásával az URL-t, hogy valami hasonló
q = a macskák, vagy bármi mi, például, az osztályban.
Nem akarom, hogy ez megtörténjen, mert a nincs szerver hallgat erre a
formában benyújtott.
Ez tisztán történik JavaScript kódot.
És ezért én nem is egy akció attribútumot formám, mert
nem kívánják, hogy ez mindig megy a szerver.
>> Szóval ez benyújtják.
De elfognak a formában benyújtása és megakadályozza az alapértelmezett
viselkedés, amely a ténylegesen menj végig a szerver.
>> Közönség: Tehát tartása kliens oldali.
>> David J. MALAN: Keeping ez kliens oldali.
Pontosan így van.
Következik az én oh MySQL.
>> ROB BOWDEN: OK.
Tehát ez az első kérdés az volt, általában durva az emberek.
Bár a későbbiekben is jobban ment.
Szóval kellett választani a helyes adatokat típusok mindkét oszlop.
És mindkét van némi dolgokat róluk, hogy
hogy a választás nehéz.
Tehát int nem érvényes írja be a számot.
Ennek az az oka, hogy egy 12 számjegyű számla szám, egy int nem elég nagy, hogy
tárolja a teljes szám.
Tehát egy érvényes választás lett volna a nagy int, ha történetesen tudja.
Egy másik választás lehetett volna a char területen hossz 12.
Tehát bármelyik ezek működött volna.
Int. nem.
>> Nos, az egyensúly, gondoljon vissza pset7.
Tehát kimondottan tízes tárolja a részvények értéke, vagy -
>> David J. MALAN: Cash.
>> ROB BOWDEN: Cash.
Szoktuk decimális tárolására összegének készpénz, hogy a felhasználó jelenleg.
Tehát az ok, hogy van Mert ne feledjük, úszók.
Van lebegőpontos precíziós.
Nem pontosan tárolja a készpénz értékek, mint szeretnénk itt.
Tehát decimális pontosan képes tárolni valamit, mondjuk, két tizedesjegy pontossággal.
Ezért egyensúlyt, azt akarjuk, hogy decimális, és nem lebegnek.
>> David J. MALAN: És azt is, is, bár lehetett volna okos más
összefüggésekben gondolkodni, lehet, hogy ez az esélye egy int.
Én csak nyomon követni dolgokat fillérekért.
Mivel kifejezetten megmutatta az alapértelmezett értékét, hogy 100.00, hogy
azt jelenti, hogy lehet, hogy csak egy int.
És egy másik finomság is számmal az volt, hogy ez nem azt jelentette,
hogy egy trükkös kérdés.
De emlékeztetni arra, hogy egy int a MySQL, , mint a C-ben, legalábbis a
készülék, 32-bit.
És bár mi nem várom el, hogy pontosan tudja, hány számjegy
azt jelenti, nem emlékszem, hogy a legnagyobb számban Ön képviseli potenciálisan
egy 32 bites szám nagyjából mi?
>> Mi több nem mindig azt mondják?
2 A 32, amely a mi durván?
Nem tudni pontosan.
De nagyjából hasznos az életben.
Ez nagyjából 4 milliárd.
Így már azt mondta, hogy egy párszor.
Tudom, hogy azt mondta, hogy egy párszor.
És ez nagyjából 4 milliárd.
És ez egy jó szabály A hüvelykujj tudni.
Ha 8 bites, 256 a mágikus szám.
Ha van 32 bit, 4 milliárd ide vagy oda.
Tehát, ha csak annyit írj le 4 milliárd, látni fogod, hogy ez kevesebb számjegyet tartalmaz, mint
12, ami azt jelenti, hogy ez nyilvánvalóan nem elég kifejező, hogy rögzítse egy
12 jegyű számlaszám.
>> ROB BOWDEN: OK.
Tehát a másik is jobban ment.
Tehát tegyük fel, hogy a bank ró egy $ 20 havonta
díj minden tekintetben.
Milyen SQL lekérdezést tudott a bank levonni 20 $ minden számít, akkor is, ha
eredményez némi negatív egyenleg?
Tehát alapvetően négy főbb kérdések -
be, válassza ki, frissítés és törlés.
Szóval, mit gondolunk mi vagyunk fogja használni itt?
Frissítése.
>> Szóval vessünk egy pillantást.
Tehát itt vagyunk frissítjük.
Mit táblázat vagyunk frissítése számlákat?
Tehát frissítése számlák.
És akkor a szintaxis azt mondja, hogy mi A számlák vagyunk frissítése?
Nos, mi beállítást egyenlege megegyezik a aktuális értékét mérleg mínusz 20.
Szóval ez frissíteni fogja az összes sort számlák, kivonva
20 $ az egyensúlyt.
>> David J. MALAN: Az egyik leggyakoribb hiba itt, bár néha megbocsátotta,
az volt, hogy valóban van egy php kódot hívja a lekérdezés funkciót vagy üzembe
idézőjelbe mindent, ami nem kell ott lenni.
>> ROB BOWDEN: Ne feledje, hogy a MySQL egy külön nyelvet a PHP.
Azt történetesen írásban MySQL PHP.
És PHP majd kiküldi át a MySQL szerver.
De nem kell a PHP-ben annak érdekében, hogy kommunikál a MySQL szerver.
>> David J. MALAN: Pontosan.
Tehát nem változók dollár jeleket kell lennie ebben az összefüggésben.
Ez csak nem az összes matematikai az adatbázisban is.
>> ROB BOWDEN: OK.
Így a következő alkalommal.
Ez a következő?
Igen.
Tehát mi SQL query tudott a bank letölteni a számlaszámok a
leggazdagabb ügyfelek, akiknek egyenlegek nagyobb, mint 1000?
Tehát, hogy a négy fő típusa megyünk akar itt?
Válassza ki a.
Tehát szeretnénk kiválasztani.
Mit akar választani?
Mit oszlopot akarunk kiválasztani?
Fogunk kifejezetten akarja kiválasztásához szám.
De ha azt mondta csillag, mi azt is elfogadta, hogy.
>> Tehát válasszon számot, amit asztalra?
Fiókok.
És akkor a feltétel akarunk?
Ahol egyenlege nagyobb, mint 1000.
Azt is elfogadták a nagyobb kisebb vagy azzal egyenlő.
Az utolsó.
Milyen SQL lekérdezést tudott a bank szoros, azaz törölje minden fiók
az egyensúlyt a $ 0?
Tehát, hogy a négy vagyunk szeretne majd használni?
Törlése.
Így a szintaxis ez?
Törlés mi asztalra?
Fiókok.
És akkor az a feltétel, amely szeretnénk törölni -
ahol az egyensúlyt egyenlő nulla.
Így törli az összes sort számla ahol az egyenleg nulla.
Kérdések ezek közül bármelyik?
Szeretné sorba?
>> David J. MALAN: Sor útmutatót.
Tehát ez az egy, amit kaptál egy kissé ismerős szerkezet, feltártuk a
bit osztály mellett a struktúrákat, amely egy adat
struktúra kapcsolódó lélekben.
A különbség, bár a sorban hogy mi volt, hogy valahogy emlékszik, hogy ki
volt az első a sorban, nagy rész, hogy mi is, hogy több
hatékony felhasználása a memóriát, legalább ha mi is használ egy tömböt.
>> Mivel a visszahívás, ha van egy sor, ha Például, ez az elülső
a sor, ha kapok a sorban van, majd valaki kap a sorban
mögöttem, a hátam mögött, a hátam mögött, és a egy ember kilép a sorból, akkor
lehetne, mint láttuk néhány emberi önkéntesek az osztályban, mindenkit
elmozdulás ezen a módon.
De általában, miután mindenki do valami nem a legjobb idő
a programban, mert ez azt jelenti, hogy algoritmus fut, amit
aszimptotikus futási ideje?
Ez lineáris.
>> És úgy érzem, hogy hülyeség.
Ha a következő személyt a sorban a következő aki állítólag bemegy a
tárolni, nem mind együtt mozogni.
Csak hagyd, hogy a személyt leszakasztott ha eljön az ideje, például.
Így tudjuk menteni egy kis időt ott.
És így kell csinálni, hogy mégis, azt jelenti, hogy a feje a sor, illetve a
első a sorban fog fokozatosan egyre mélyebbre és mélyebbre
a tömb, és végül esetleg tulajdonképpen a kerületi ha mi használ
tömb tárolja az embereket ezen a sorban.
Így szinte gondolni a array, mint egy körkörös adat
struktúrát ebben az értelemben.
>> Szóval valahogy meg kell nyomon követni a mérete, vagy tényleg a vége
és akkor, ahol az elején van.
Ezért azt javasoljuk, hogy a deklarált egy ilyen sor, amelyben
q, csak egy levelet.
Ezután azt javasoljuk, hogy az első legyen nullára inicializálunk, és hogy a méret
inicializálni nullára.
>> Tehát most, nincs semmi belül, hogy a sorban.
És szeretnénk, ha a teljes végrehajtása Enqueue alábbi
oly módon, hogy a funkció még n végén q, majd igazat ad vissza.
De ha q tele vagy negatív, a függvény helyett return false.
És adott neked egy pár A feltételezések.
De ők nem igazán funkcionálisan lényeges, csak, hogy bool létezik,
mert technikailag bool nem léteznek C, ha tartalmazza a
bizonyos header fájlt.
Tehát csak győződjön meg róla, nem volt ez egy trükk
kérdése a fajta dolog.
>> Tehát Enqueue javasoltuk a mintában megoldások megvalósítása az alábbiak szerint.
Egy, először ellenőrzi a könnyű, Az alacsonyan lógó gyümölcsöket.
Ha a sor nem teljes, vagy a szám, akarsz beszúrni kevésbé
mint nulla, ami azt mondta, a meghatározása a problémát meg
nem szabad megengedni, mert csak szeretnénk nem negatív értéket, akkor kell
csak vissza hamis azonnal.
Szóval néhány viszonylag egyszerű hibaellenőrzéshez.
Ha mégis szeretne hozzáadni, hogy a tényleges szám, meg kellett csinálni egy kis
gondolok itt.
És ez az, ahol ez egy kicsit idegesítő szellemileg, mert meg kell
kitalálni, hogyan kell kezelni a körbefutó.
>> De a csíra, a gondolat, hogy itt ez a érdekes számunkra, hogy a körbefutó
gyakran azzal jár, moduláris aritmetika és A mod operátor, a százalék oldalon,
ahol lehet menni egy nagyobb értéket vissza nullára, majd egy és két és
három, majd visszafordult nullára, egy és kettő és három és így tovább
újra és újra.
Így, ahogyan azt javasoljuk, ezt a hogy mi szeretnénk index a
array hívott számok, ahol az egész hazugság.
De oda, először akarok függetlenül a méret a sorban van, de
majd hozzá, hogy bármilyen előtt a lista.
És a hatása, hogy az, hogy nekünk a megfelelő helyzetben a sorban, és
Nem feltételezhetjük, hogy az első ember a sorban van az elején, amelyet ő vagy
ő egyáltalán lehet, ha is változó mindenkinek.
De mi csak létre a munka magunknak, ha volt
az adott utat.
>> Így tudjuk tartani, hogy viszonylag egyszerű.
Mi kell emlékezni, hogy mi csak hozzá egy int a sorban.
És akkor most vissza igaz.
Eközben dequeue, megkérdeztük hogy tegye a következőket.
Végrehajtása, azt oly módon, hogy dequeues, hogy eltávolítja, és visszatér,
az int elejénél sorban.
Eltávolításához int, elegendő elfelejteni.
Nem kell, hogy felülírja a kicsit.
Tehát még mindig valóban ott van.
Csakúgy, mint az adatok a merevlemezen, mi csak figyelmen kívül hagyja azt a tényt,
hogy ez most van.
És ha q üres, mi kell helyett vissza a negatív 1.
Tehát ez úgy érzi, önkényes.
Miért vissza negatív 1 ahelyett, hogy hamis?
Igen.
>> Közönség: Q tárolja pozitív értékeket.
Mivel csak tárolni pozitív értékeket A q, negatív hiba.
>> David J. MALAN: OK, igaz.
Tehát azért, mert mi csak tárolja a pozitív értékek vagy nulla, akkor ez rendben van, hogy
vissza a negatív érték a sentinel érték, egy speciális szimbólum.
De te újraírása történelem ott, mert az ok, mi csak
vissza nem negatív értékeket azért van, mert azt akarjuk, hogy
egy őrszem értéket.
Így pontosabban, miért nem return false hiba esetén?
Igen.
>> Közönség: Már nem vissza az egész.
>> David J. MALAN: Pontosan.
És ez az, ahol C kap nagyon korlátozó.
Ha azt mondod, hogy mész vissza int, megvan
vissza az int.
Nem lehet kapni divatos és indítsa visszatérő a bool vagy úszó vagy a
szöveg, vagy valami ilyesmi.
Nos, eközben, JavaScript és a PHP és a Néhány más nyelvvel is, sőt,
voltál visszatérő más típusú értékeket.
És az is lehet hasznos, ahol a akkor visszatérhet a pozitív ints, nulla,
negatív ints, vagy hamis vagy null még jelent hibát.
De nem kell, hogy sokoldalúság C.
>> Tehát dequeue, amit javaslatot tennie, hogy -
>> ROB BOWDEN: Visszatérhet hamis.
Csak annyi, hogy hamis hash határozza meg hamis nullára.
Tehát, ha return false, akkor vissza nullára.
És nulla érvényes dolog a sorban, míg a negatív 1 nem, ha
hamis történetesen negatív 1..
De ne is tudniuk kell, hogy az.
>> David J. MALAN: Ez miért nem mondtam el.
>> ROB BOWDEN: De ez nem volt igaz hogy nem tud visszatérni hamis.
>> David J. MALAN: Persze.
Tehát dequeue, észre elfogadjuk semmisnek érvelését.
És ez azért van, mert nem vagyunk múló valami be
Csak azt akarjuk, hogy távolítsa el az elemet az első a sorban.
Tehát hogyan tudnánk járni ezt?
Nos, először is, nézzük ezt gyors józanság ellenőrzés.
Ha a sor mérete 0, van nincs tennivaló.
Vissza negatív 1..
Kész.
Szóval ez a néhány sor a programom.
Tehát csak négy sor marad.
>> Tehát itt úgy döntök, hogy csökkentse a méret.
És a csökkentés méretét hatékonyan azt jelenti, hogy én vagyok elfelejtve
valami van ott.
De azt is meg kell frissíteni, ahol a az első a számok.
Tehát erre, szükségem két dolgot.
Először meg kell emlékezni, amit a számot van az első a sorban,
mert vissza kell azt a dolgot.
Szóval nem akarom, hogy véletlenül elfelejt róla, és aztán írja felül azt.
Én csak fog emlékezni egy int.
>> És most, azt akarom, hogy frissíteni q.front kell q.front +1.
Tehát, ha ez volt az első, aki vonal, most azt akarom, plusz 1
pont a következő személyt a sorban.
De azt kell kezelni, hogy a körbefutó.
És ha a kapacitás globális állandó, hogy fog, hogy engedje meg, hogy megbizonyosodjon arról,
én pont az utolsó ember vonal, a modulo művelet hozni
vissza nullára a első a sorban.
És, hogy kezeli a wraparound itt.
És akkor én jár vissza n.
>> Nos, szigorúan véve, én nem kell jelenteniük n.
Nem kell megragadni, és tárolja azt ideiglenesen, mert az érték
még mindig ott van.
Így is csak a helyes számtani vissza a korábbi vezetője
a sor.
De én csak úgy éreztem, hogy ez több volt, tiszta hogy valóban megragad a int, tedd
n, majd vissza, hogy az egyértelműség kedvéért, hanem
nem feltétlenül szükséges.
Psszt.
Mind kiejthető a fejemben.
>> ROB BOWDEN: Tehát az első kérdés a bináris fa problémát.
Tehát az első kérdés az, hogy mi mivel ezeket a számokat.
És azt akarjuk, hogy valahogy be őket ezek a csomópontok oly módon, hogy ez egy
érvényes bináris kereső fa.
Tehát az egy dolog, hogy emlékezzen a bináris kereső fák, hogy nem
csak, hogy a dolog, hogy a bal oldali kevésbé, és a dolog, hogy
A jobb oldali nagyobb.
Meg kell, hogy az egész fa a bal oldalon van kevesebb, és az egész fát
a jobb nagyobb.
>> Tehát, ha tettem 34 itt a tetején, majd a Tettem 20 van, így ez érvényes olyan
messze, mert a 34 itt.
20 megy a bal oldalon.
Szóval ez kevesebb.
De nem tudom, majd tegye 59 itt, mert 59 bár a jobb oldalon a 20,
ez még mindig a bal oldalon a 34.
Tehát az, hogy kényszer szem előtt tartva, a legegyszerűbb módja talán megoldásában
a probléma az, hogy csak egyfajta Az ezeket a számokat -
így 20, 34, 36, 52, 59, 106.
Majd helyezze azokat balról jobbra.
>> Tehát 20 megy itt.
34. megy itt.
36. megy itt.
52., 59., 106..
És azt is lehetett volna alakított ki néhány dugulás és megvalósítása,
Ó, várj, nincs elég számok hogy töltse ki ezt itt.
Szóval kell reshift mi a útvonal megjegyzés lesz.
De észre, hogy az utolsó három, ha olvassa el balról jobbra, akkor a
növekvő sorrendben.
>> Tehát most, szeretnénk, hogy állapítsa meg, mi a struct lesz a
csomópontok a fán.
Szóval, mi kell egy bináris fa?
Tehát van egy érték típusú int, így néhány int értéket.
Nem tudom, mi az úgynevezett ez a megoldás -
int n.
Szükségünk van egy mutatót a bal fia és egy hivatkozást a jobb fia.
Így fog kinézni.
És azt fogja nézni, mielőtt mikor a kétszeresen kapcsolt
lista cucc, így felhívás -
Megyek kell görgetni a út vissza a probléma 11.
>> Így észre, hogy ugyanúgy néz ki, hogy ezt, kivéve, mi egyszerűen csak hívja ezeket a
különböző nevek alatt.
Még mindig van egy egész érték és a két mutató.
Csak, hogy ahelyett, kezelése mutatók, mint rámutatva, hogy a következő dolog
és a korábbi dolog, mi kezeljük a mutatókat, hogy pont a bal fia
és a jobb gyerek.
OK.
Szóval ez a mi struct csomópontot.
És most, az egyetlen funkciója meg kell végrehajtani ezt Traverse, amely
azt akarjuk, hogy menjen át a fa, a nyomtatás ki az értékeket a fa a sorrendben.
>> Így keresnek itt, mi szeretne nyomtatni ki 20, 34, 36, 52, 59 és 106.
Hogyan elérni ezt?
Tehát ez elég hasonló.
Ha látta a múltban vizsga a probléma , amit akart, hogy nyomtassa ki
az egész fa vesszővel között Minden volt, valójában még
könnyebb, mint ezt.
Tehát itt a megoldás.
Ez jelentősen megkönnyíti ha nem is rekurzívan.
Nem tudom, ha valaki kísérletet csinálni iteratív.
>> De először is, mi az alapeset.
Mi van, ha a gyökér null?
Majd mi csak úgy vissza.
Nem akarunk nyomtatni semmit.
Else megyünk áthalad rekurzívan lefelé.
Nyomtassa ki az egész bal részfa.
Tehát bármit kinyomtathat kevesebb mint az aktuális érték.
És akkor fogom nyomtatni magamnak.
És akkor fogom recurse le a teljes jobb részfa, így minden
nagyobb, mint az érték.
És ez fog nyomtatni meg mindent annak érdekében.
Kérdések az, hogy ez a valóban véghez, hogy az?
>> Közönség: Van egy kérdésem A [hallható].
>> ROB BOWDEN: Tehát az egyik módja a közeledő minden rekurzív probléma az, hogy csak azt gondolom,
róla, mint meg kell gondolni, az összes sarokba esetben.
Ezért úgy vélik, hogy szeretnénk nyomtassa ki ezt az egész fát.
Szóval fogunk összpontosítani ez a különleges csomópont -
36..
A rekurzív hívások, úgy teszünk, mintha azokat csak a munka.
Tehát itt ez a rekurzív hívás Traverse, akkor gondolkodás nélkül
róla, csak vándorol a bal három, képzeljük el, hogy már kiírja 20
és 34. számunkra.
És amikor végül rekurzívan hívja áthalad a
van, hogy helyesen nyomtatni 52., 59., és 106. számunkra.
>> Tehát, mivel ez lehet nyomtatni 20, 34 és a másik lehet nyomtatni 52, 59, 108,
Csak azt kell tudni tennie, hogy a nyomtatási magunkat a közepén, hogy a.
Tehát nyomtassa ki mindent elénk.
Print magunkat, így a jelenlegi csomópont nyomtatási 36., a rendszeres printf, majd
nyomtat mindent utánunk.
>> David J. MALAN: Ez az a pont, ahol a rekurzió lesz igazán szép.
Ez a csodálatos ugrás a hit, ahol a te a legapróbb kis munka.
És akkor legyen valaki mást a többit.
És az a valaki az, ironikusan, te.
Tehát komoly brownie pont, ha görgeti fel a kérdést -
>> ROB BOWDEN: A kérdés?
>> David J. MALAN És le egy kicsit, hogy A számok, Tudja valaki, hol
ezek a számok érkeznek?
>> ROB BOWDEN: Én szó szerint fogalmam sincs.
>> David J. MALAN: Úgy tűnik, az egész teszt.
>> Közönség: Vajon ugyanazokat a számokat?
>> David J. MALAN: Azok a számok.
Egy kis húsvéti tojás.
Tehát azoknak, néz online otthon, ha meg tudod mondani nekünk e-mailben, hogy
heads@CS50.net mi a jelentősége Ezeknek a visszatérő hat a számok
egész Quiz 1, akkor zuhanyzó Önnek csodálatos figyelmet a végső
előadás és a stressz labdát.
Szép, finom.
>> ROB BOWDEN: Minden utolsó kérdése semmit a kvíz?