DAVID J. Malan: Dobre. Takže vitajte na vôbec prvý CS50 posmrtné na kvíz. Mysleli sme, že slávnostne táto tradícia v tomto roku. A to bude príležitosť prejsť riešenie kvízu. A budeme zrýchliť alebo spomaliť na základe na záujme tých, ktorí tu. 

Takže ste asi tu, pretože ste zaujímalo, ako by ste mohli mať alebo mala odpovedať na niektoré z týchto problémov. Tak prečo by sme sa pozrieť Spočiatku tejto sekcii? Tak ako sa reťazca. To vám dal tri rôzne verzie programu, ktorý bol nakoniec chcel získať reťazec od užívateľa. Či alebo nie to robilo to bolo ponechané na vás zistiť. 

A pýtali sme sa v prvej otázke, 0, Predpokladám, že verzia 1 je zostavil a popravený. Prečo môže program segfault? Na prvý pohľad, nejaké návrhy , Prečo? Jo. 

DIVÁKOV: Tak Spomínam si na to v Predchádzajúci príklad pri pohľade na char * s, a videl scan S a vidieť, pretože je to ukazovateľ, ako to ovplyvnilo to, čo ste skenovať? Je to to alebo adresa s? 

DAVID J. Malan: OK. Dobrá. Takže v konečnom dôsledku, zdroj akéhokoľvek problému sa pravdepodobne bude znižovať tejto premennej s A to je naozaj variabilný. Dátový typ tejto premennej je char *, čo znamená, že to bude obsahovať adresu charakteru. A v tom spočíva pochopenie. Bude obsahovať adresu znak alebo, všeobecnejšie, adresa prvého znaku v celý blok znakov. 

Ale úlovok je, že skenovanie s, účel život, je daná adresu a vzhľadom Kód formátu, ako je% s, čítanie reťazec do kusa Pamäť na tejto adrese. Ale pretože tam nie je znamienko rovnosti pred že bodkočiarku na prvý riadok kódu, pretože to nie je v skutočnosti alokovať pamäť s malloc, pretože nie v skutočnosti alokovať pole nejaké veľkosti, všetky robíte číta užívateľa vstup z klávesnice do niektorej kompletnej hodnota odpadky, ktoré je s východiskovým. Takže šance sú vy budete segfault ak že adresa nie je len tak nestane byť hodnota, ktorú môžete, v skutočnosti, napíšte. Tak zlé neprerozdeliť pamäť tam. 

Takže v otázke č 1, sme sa spýtali, Predpokladám, že verzia 2 je zostavil a popravený. Prečo môže tento program segfault? Tak toto je menšia buggy. A je to naozaj len jeden zrejmý spôsob, kde môžete spustiť segfault tu. A to je tematické. Kedykoľvek sme pomocou c v pamäti, čo sa môžete urobiť pre to, prinútiť segfault vo verzii 2? 

DIVÁKOV: Ak používate tento vstup v reťazec, ktorý je dlhší ako 49 znaky. 

DAVID J. Malan: Presne tak. Kedykoľvek vidíte niečo pevnej dĺžky , Pokiaľ ide o pole, vaše radar by mal ísť preč, že by to mohlo byť problematické, ak si nie ste kontrola hranice poľa. A že je tu problém. Stále pomocou scanf. Stále pomocou% s, čo znamená, že sa snaží čítať reťazec od užívateľa. To bude čítať do s, čo v tomto bode, je účinne adresa bloku pamäti alebo je to ekvivalent. Je to názov poľa znakov v pamäti. 

Ale presne to, ak budete čítať reťazec to je dlhší ako 49 znakov, 49 pretože budete potrebovať priestor pre lomítkom 0, budete pretečeniu že vyrovnávacej pamäti. A môžete mať šťastie a byť schopný napísať znak, 51. 52., 53.. Ale v určitom okamihu, OS sa chystá povedať, no. To rozhodne nie je pamäť budete dotýkať. A program bude segfault. 

Takže tam sú heuristiky by mal byť akýkoľvek Čas máte pevnú dĺžku, máte aby sa ubezpečil, že ste kontrolu dĺžky na čo to je, že sa snažíte čítať do neho. 

DIVÁKOV: Takže riešenie, ktoré by ste mohli mali vyhlásenia kontrolu skutočne je dĺžka väčšia alebo menšie ako? 

DAVID J. Malan: Presne tak. Stačí mať podmienku , Ktorý hovorí, ak - alebo skôr nemusíte nutne vedieť, dopredu, koľko znakov užívateľ bude písať, pretože Máte kurča a vajcia. Nie, kým ste si ju s scanf môžete zistiť, ako dlho to je. Ale v tomto okamihu, to je príliš neskoro, preto, že ste už čítali ju do niektoré blok pamäte. Tak ako stranou, CS50 knižnica vyhýba tento problém úplne, odvolanie pomocou fgetc. A to prečíta jeden znak v čase, špičkách spolu s vedomím, že vás nemôže pretečeniu charakter, ak budete čítať jednu po druhej. 

Háčik je s GetString odvolanie je že máme neustále re-veľkosti že kus pamäti, ktorý je len bolesť. Je to veľa riadkov Kód k tomu, že. Takže iný prístup by bol vlastne používať bratranca, takže hovoriť, o scanf. K dispozícii sú varianty mnoho z nich funkcie, ktoré v skutočnosti kontrolujú Dĺžka koľko znakov môžete čítať maximálne. A vy ste mohli určiť, nečítajú viac ako 50 znakov. Tak, že by bol iný prístup, ale menej ústretový väčších vstupov. 

Takže otázka 2 sa pýta, predpokladám, že verzia 3 je zostavený a vykonaný. Prečo by to program, segfault? Takže toto je vlastne rovnaký odpoveď, aj keď to Vyzerá trochu obsiahlejší. Budeme používať malloc, ktoré sa cítia ako dávame sami sebe viac možností. A potom sme uvoľnenie, ktoré pamäte na konci. Je to stále len 50 bajtov pamäti. Tak by sme mohli ešte skúsiť čítať v 51, 52, 1000 bajtov. Bude to segfault pre presne rovnaký dôvod. 

Ale je tu ďalší dôvod, prečo taky. Čo iné by mohlo malloc návrat vedľa adresa bloku pamäti? To by sa mohol vrátiť null. A pretože nie sme kontrola to, že by sme mohli robiť niečo hlúpy iného dôvodu, čo je to, že by sme mohli hovoriť scanf, prečítajte si vstup užívateľa z klávesnice do 0 polohy, AKA null. A tiež, bude určite spustiť segfault. Takže na účely kvíz je, by sa prijali jeden z tých, čo pádny dôvod. Jedným z nich je totožný. Jedným z nich je trochu zložitejšie,. 

A konečne, s ohľadom na programe je využitie pamäte, ako to verzie 2 a Verzia 3 sa líšia? Takže, čo to stojí, videli sme zdanlivo nekonečnú zásobu možné odpovede na to. A medzi odpoveďami ľudí, čo sme boli dúfal, že, ale prijali sme ďalšie veci, bola nejaká zmienka o Skutočnosť, že verzia 2 sa používa tzv stack. Verzia 3 je pomocou haldy. A funkčne, to nie je naozaj robiť všetko, čo veľký rozdiel. Na konci dňa, sme stále len dostať 50 bajtov pamäti. 

Ale to bol jeden z možných odpovedí že sme sa pozerali na. Ale uvidíte, ako vám vaše kvízy späť z TFS, že sme urobili prijať iné diskusie o ich rôznorodé použitie pamäti, ako. Ale stack a heap by bolo jednoduchá odpoveď ísť s Akékoľvek otázky? Dám vám Rob. 

ROB BOWDEN: Takže problém 4. To je ten, kedy ste museli vyplniť v počte bajtov z všetkých Tieto rôzne typy používané. Takže prvá vec, ktorú vidíme. Predpokladajme, že 32-bitovú architektúru, takhle CS50 spotrebiča. Takže jedna zo základných vecí, o 32-bitovej architektúry, ktorá nám hovorí, presne, aký veľký ukazovateľ sa deje byť v architektúre. 

Takže hneď, vieme, že každý ukazovateľ Typ je 32-bitov alebo 4 bajty. Takže pri pohľade na túto tabuľku uzol * je typu ukazovateľ. To bude 4 bajty. Struct uzol *, to je doslova totožný s uzla hviezdy. A tak, že to bude 4 bajty. String, takže to nevyzerá ako ukazovateľ ešte, ale typedef, reťazec je len char *, ktoré je typu ukazovateľ. Tak, že to bude 4 bajty. 

Takže tieto tri sú všetci 4 bajty. Teraz, uzol a študentov sú trochu zložitejšie. Takže pri pohľade na uzol a študentom, vidíme, uzol ako celé číslo a ukazovateľ. A študent dva ukazovatele vnútri nej. Tak aspoň pre náš prípad, spôsob že sme nakoniec výpočet veľkosti Táto štruktúra je len sčítať všetko že je vnútri struct. 

Takže pre uzol, máme celé číslo, čo je 4 bajty. Máme ukazovateľ, ktorý má 4 bajty. A tak jeden uzol sa deje aby sa do 8 bajtov. A podobne pre študenta, máme ukazovateľ, ktorý je 4 bajty a ďalšie ukazovateľ, ktorý je 4 bajty. Takže, čo sa deje na koniec up je 8 bajtov. Uzol a študentské Takže je 8 bajtov. A títo traja sú všetci 4 bajty. Otázky na to? Áno. 

DIVÁKOV: Je to 64-bit architektúra, by to dvojnásobok všetci z nich? 

ROB BOWDEN: To nie zdvojnásobiť všetky z nich. Tak 64-bitovej architektúry, je, opäť, zmeny, ktoré zásadnú vec, že Ukazovateľ je teraz 64 bitov. Jo. Takže ukazovateľ je 8 bajtov. Takže to, že sa 4 byty sa bude 8 bajtov. Študent, ktorý bol dva ukazovatele, dobre, teraz to bude byť 8 bajtov, 8 bajtov. Bude to robiť 16 bajtov. 

Uzol, ale je stále ešte 4 byty. Takže tento ukazovateľ sa deje byť 8 bajtov. To je 4 bajty. Takže uzol sa deje len na 12 bajtov. Akékoľvek ďalšie otázky na toto? Takže ďalší jeden, jedná sa o stavové kódy HTTP. A vy ste mal opísať okolnosti, za ktorých je sila sa vrátil k vám. jeden problém, ktorý som počul niektorých študentov je to, že sa snažili, aby Chyby byť na strane klienta. Takže keď sa snažíme, aby žiadosť na serveri, niečo, čo ide zle na našej strane. Ale všeobecne, tieto kódy sú vrátených serverom. Takže ak chceme zistiť, čo sa deje zlé alebo priamo na serveri, ktorý spôsobí, že tieto veci, ktoré majú byť vrátené. Tak prečo by mohla a server vracia stavový kód 200? Akékoľvek myšlienky? 

Jo. Takže niečo o úspešnom požiadavka prešiel. A oni sú schopní sa vrátiť čo ste chcel. Takže je všetko v poriadku. Čo o 302 nájdených? Jo. 

Divákov: Server hľadal za to, čo ste požadovali. Ale to nemohol nájsť. Takže tam je chyba. 

ROB BOWDEN: Takže server bol hľadá to, čo ste chceli. Tak práve hľadáte tu, 302 nájdených, to bol schopný ju nájsť. 

DIVÁKOV: Ospravedlňujem sa. Našiel znamená, že oni si to. Prepáčte. 

ROB BOWDEN: Tak 302 Found. Server je schopný nájsť to, čo ste chceli. 

DIVÁKOV: Ale to nie je to zobrazenie? 

ROB BOWDEN: rozdiel medzi to 302 a 200 je to, že vie, že to, čo chcete. Ale nie je to presne tam, kde ste sa chcel opýtať. Takže 302 je typický presmerovanie. Takže ste si vyžiadali stránku. Je to vie, oh, chcem ti vrátiť toto. Ale to je na inú adresu URL. Tak hele, vy vlastne chcete toto. 

DAVID J. Malan: Je to kus, ktorý povedal: že sme dali vy presmerovanie funkcia, ktorá používa funkciu záhlavia ktorý, podľa poradia, vytlačiť umiestnenie, hrubého čreva, a potom URL, na ktoré Ak chcete odmietnuť užívateľa. Aj keď ste nevideli 302 výslovne sa, že je to, čo PHP by sa mávnutím čarovného prútika vložte ako hlavičky hovorí presne to, čo povedal Rob tam - nájdených. Ale nájdete tu miesto. 

ROB BOWDEN: OK. Takže to, čo o 403 zakázaný? 

DIVÁKOV: Myslím, že to, že server je v podstate hovorí, že klient nemôže získať prístup k domovskej stránke. 

ROB BOWDEN: Takže áno. No, typická odpoveď sme boli čaká je niečo ako, súbory nie sú primerane chmodded. To je asi, za akých okolností ste ich videli. Ale je tu dôvod, že klient môže byť na Škorpiónovi. Tam je vlastne ďalší stavový kód - 401. Takže sa jedná o veľmi podobné. 

401 je neoprávnené. A 403 je zakázané. A tak neoprávnenému vám exkluzívne dostať, ak nie ste prihlásený Ale prihlásenie môže znamenať že ste oprávnení. Ale ak ste už prihlásení a môžete Stále nemáte oprávnenie, potom môžete tiež získať zakázané. Takže ak ste prihlásení a nemajú povolenie, zakázané je tiež niečo, čo môžete dostať. 

DAVID J. Malan: A mechanizmus , Ktoré tieto problémy sú zvyčajne rieši na serveri cez to príkaz? Chmod, ak je to vskutku oprávnenia vydá na súbor alebo adresár. 

ROB BOWDEN: A 404 nebola nájdená. Jo. Takže na rozdiel od 302, kde nebolo presne kde sa pýtate, ale vie, čo chcete, to, to jednoducho musí žiadny nápad, čo chcete. A vy sa nevyžaduje niečo platný. 418 Som kanvice a potom 500 interný server. Tak prečo môžete dostať, že? 

Takže segfault - Ja vlastne neviem, triedenie štandard pre to. Ale ak vaše PHP kódu niečo zle v tom, teoreticky, mohla by vlastne segfault, v tom prípade, to 500 Interná chyba servera, niečo, čo je sa váš server je zle konfigurácie. Alebo je to chyba syntaxe v PHP kódu. Alebo sa niečo zlé deje. 

DAVID J. Malan: My sme vidieť segfault Medzi odpoveďami pár ľudí. A technicky, mohlo by sa to stalo. Ale, že by PHP, program napísal iných ľudí, v skutočnosti segfaulted, ktorý len vtedy, ak títo ľudia podelal a napísal buggy kód ich interpret by PHP samo o sebe segfault. Takže aj keď je 500 ako segfault v duchu, je to takmer vždy Výsledkom je problém konfiguračného súboru s webovým serverom, alebo, ako povedal Rob, syntaktická chyba, ako ste vy neuzavrela cenovú ponuku. Alebo ste stratili bodkočiarku niekde. 

DIVÁKOV: Takže pre Shuttle pset, som že keď som to urobil, keď som klikol prehliadač, ale nič prišiel, čo oni volali biela stránka. Ale bolo to preto, že z kódu. Myslím, že to bolo JavaScript, jo? 

ROB BOWDEN: Jo. 

DIVÁKOV: Kiež by chyba ešte prísť? 

ROB BOWDEN: Takže by ste sa dostali to chyba, pretože všetko z pohľadu webového servera bol úplne v poriadku. Ale ste požadovali index.html. Požadovali ste shuttle.js a service.js. A to sa podarilo úspešne vrátiť vám všetkým z tých vecí - 200. OK. Je to len vtedy, keď sa váš prehliadač pokúšal interpretovať kód JavaScript, ktorý je to ako, počkajte, to nie je platné k chybe JavaScript. Nejaké ďalšie otázky? Dobrá. 

DAVID J. Malan: Tak ďalšie až sa číslo 11. A 11 bol najdesivejšie pre mnoho ľudí. Takže najdôležitejšia vec na vedomie tu sa, že je to skutočne o dvojnásobne spájať zoznam. Ale to nebolo rovnaké ako minulý rok dvojnásobne spájať zoznam problém, ktorý vám nedal na námietku, že zoznam by mohol v skutočnosti byť netriedený. 

A tak skutočnosť, že zoznam bol netriedeného a skutočnosť, že toto slovo bolo zdôraznené, že mal oznámiť , Že je to v skutočnosti zjednodušenie z toho, čo by inak bolo náročnejší problém a dlhšia. Takže Bežnou chybou tu bolo dali Riešenie minuloročný na jednom pager a potom už len slepo kopírovať, ktorý sa ako odpoveď, ktorá je správna odpovedať na inú otázku podobne v duchu. Ale jemnosti tu boli nasledujúce. 

Takže jedna, sme uzol vyhlásil a sú definované v obvyklým spôsobom tu. Potom sme definovaný zoznam je globálna ukazovateľ inicializovaný na hodnotu null. Potom sa zdá, že je dve funkcie máme prototypy pre tú, vložka a odstrániť. A potom tu máme nejaký ukážkový kód tu robiť veľa vloženie. A potom žiadame vás, aby ste dokončiť prevedenie vložky pod takým tak, že sa vloží do n zoznamu v konštantnom čase, tiež zdôraznil, aj keď už existuje. 

Takže krása je možné vložiť v konštantnom čase, je, že to znamená, že budete musieť vložiť nový uzol, kde? Do prednej časti. Tak to eliminuje, našťastie, aspoň jeden z prípadov, ktoré predtým vyžadovali ešte viac riadkov kódu, ako to urobil v minulom roku, a to aj v triede, keď sme hovoril skrze tieto veci s ľuďmi a s niektorými slovné pseudo kód. Takže riešenie tu, poďme preskočiť k tomu stačí mať vizuálny kontakt obrazovke. 

Všimnite si, že robíme nasledujúce. A tiež si všimnúť ďalšie zjednodušenie bolo, že aj keď je to už existuje, tak to znamená, že aj v prípade, číslo už existuje, môžete len slepo vložiť ďalšie kópie toho. A to tiež malo byť zjednodušenie, takže by ste mohli zamerať sa na, naozaj, niektorí viac intelektuálne zaujímavá časť a nie je len nejaký ďalší kontrolu chýb s ohľadom na obmedzený čas. 

Takže v tomto roztoku vzorky sa pridelí ukazovateľ na ľavej strane stranu tu k uzlu. Teraz si uvedomiť, že ukazovateľ, as Rob povedal, je iba 32 bitov. A to nie je v skutočnosti obsahovať adresa, kým priradiť mu adresu. A my, že na pravej strane strana cez malloc. Ako dobrý občan, môžeme skontrolovať, že malloc nie je v skutočnosti, null, takže nemáme náhodou vytvoriť segfault tu. A kedykoľvek použiť malloc v živote, vám by mala byť kontrola na null, inak Máte jemné chybu. 

Potom sme sa inicializovať, že null by priradenie n a predchádzajúcej a ďalšie. A v tomto prípade tu, som inicializáciu predchádzajúce na hodnotu null, pretože tento nový uzol bude nový začiatku môjho zoznamu. Takže tam to bude nič pred ním. A ja chcem, aby v podstate pripojiť Existujúci zoznam do nového uzla nastavenie vedľa rovná zoznam sám. Ale ja som to urobil len zatiaľ. Takže v prípade, že zoznam sám o sebe už existoval, a tam bol aspoň jeden uzol už na mieste, ak sa jedná o zoznam tu a ja vložiť nový uzol tu, som je potrebné, aby sa ubezpečil, že môj bývalý uzol body späť do môjho nového uzla, , Pretože to je, opäť, dvojnásobne spájať zoznam. 

Takže robíme kontrolu zdravý rozum. Ak zoznam nie je null, ak je už jeden alebo viac uzlov, potom tam Dodávam, že zadné odkaz, aby som tak povedal. A potom to posledné, čo potrebujeme urobiť, je aktualizovať globálna zoznam premenných sám bodu do tohto nového uzla. Jo. 

DIVÁKOV: V smere šípky [Nepočuteľné] sa rovná null, robí, že vysporiadať sa s zoznamu, pretože Zoznam je null? 

DAVID J. Malan: Nie. To je jednoducho to, že som aktívne pozor, v tom, že ak je to môj Pôvodný zoznam sa možno niektoré ďalšie uzly tu a ja som vkladanie my nový uzol sem, tam sa deje byť nič sem. A chcem zachytiť ten nápad nastavením skôr null na nový uzol. A pravdepodobne, ak môj kód je správny a neexistuje žiadny iný spôsob, ako vložiť iné, než je táto funkcia uzly, pravdepodobne, aj keď zoznam už jeden alebo viac uzlov v ňom, pravdepodobne Zoznam, prvý uzol, by mal predchádzajúci ukazovateľ null sám. 

DIVÁKOV: A len následné-up. Dôvod, prečo dať ukazovateľ next rovná Zoznam je robíte ukazovateľ Pred zoznamu v tom, že to ukazuje na ďalšie, myslím, že - Ja nie - len zoznam? 

DAVID J. Malan: Presne tak. A tak sa poďme skutočne zvážiť dve prípadov tu naozaj, aj keď Aby budeme uvažovať o nich nie je úplne rovnaký ako kód. Ale na vysokej úrovni, v prípade, že predstavuje zoznam, a to je 32-bit ukazovateľ, najjednoduchší scenár že je to null v predvolenom nastavení. A predpokladám Chcem vložiť Číslo 50 bolo prvé číslo. Takže budem pokračovať a prideliť uzol, ktorý bude obsahovať tri polia - n, predchádzajúce a ďalšie. 

Chystám sa dať číslo 50 tu, pretože to bude n To bude ďalší. A to bude predchádzajúce. A tak čo mám robiť v tomto prípade? No, ja som práve urobil linku 1 tu. Ukazovateľ n dostane n Ja potom povedal, predchádzajúce by mal dostať null. Takže to bude mať hodnotu null. Potom budem hovoriť ďalšie sa chystá do zoznamu dostať. 

A to jednoducho funguje dobre. To je null. A tak hovorím, nový uzol je vedľa poľa by mal dostať, čo to je. Tak, že kladie ďalšie null tam. A potom posledná vec, Aj to je skontrolovať tu. Ak zoznam nie je rovná NULL, ale je rovný null, takže sme vynechať dohromady. A tak všetko, čo robiť ďalej, je zoznam dostane ukazovateľ, ktorý má za následok obrazovo obrázok takhle. Takže to je jeden scenár. 

A ten, ktorý ste sa pýtal konkrétne je situácia, ako je táto, kde už máme zoznam jeden-uzla. A keď som sa vrátiť do pôvodnej Problém vyhlásenie, ďalšie zídeme vložiť povedzme je 34, len pre saké diskusie. Takže budem len pohodlne kresliť, ktoré sem. Práve som malloced. Predpokladajme, že som kontrolu na null. 

Teraz idem k inicializácii n byť 34. A to bude n To bude ďalší. A to bude predchádzajúce. Poďme sa uistite sa, že som to neurobil si to pospiatky. Predchádzajúce je na prvom mieste v definícii. Dovoľte mi, aby som tento problém odstrániť. Je to predchádzajúce. To je vedľa. Aj napriek tomu, že sú zhodné, poďme si to konzistentné. 

Predchádzajúce. To je vedľa. Tak som práve malloced moje vedomie, kontrolovať NULL, priradí 34 do uzla. Predchádzajúca dostane null. Tak, že mi to dáva. Ďalšie dostane zoznam. Takže zoznam je to. Takže je to teraz rovnaké ako čerpanie tejto šípka, takže sa upozorniť na jeden v rovnakom. A potom som kontrolu, či zoznam nie je rovné null. A nie je to tentoraz. Potom idem urobiť zoznam predchádzajúce dostane ukazovateľ. 

Takže zoznam Predchádzajúca dostane PTR. Tak to má za následok uvedenie grafický šípka tu. A to je už trochu vlnité, linky. A potom, konečne, som aktualizovať zoznam poukázať na ukazovateľ. Takže teraz to ukazuje na toho chlapa. A teraz, poďme robiť rýchle Kontrola zdravý rozum. 

Tu je zoznam, ktorý je globálna premenná. Prvý uzol je, v skutočnosti, 34, pretože Ja som po tú šípku. A to je správne, pretože chcem, aby vložiť na začiatku zoznamu všetky nové uzly. Jeho ďalšie pole ma vedie k tejto chlapa. Ak som ďalej, som narazila ďalšie je null. Takže to nič viac zoznamu. Ak som narazila predchádzajúce, som si tam, kde som čakať. 

Takže stále existuje niekoľko rád, samozrejme, manipulovať. Ale skutočnosť, že vám bolo povedané, k tomu to v konštantnom čase vás znamená iba to, majú konečný počet vecí máte dovolené robiť. A čo je to za číslo? To by mohol byť jeden krok. Mohlo by to byť dva. Mohlo by to byť 1000 krokov. Ale to je konečný, čo znamená, že nemôžete majú nejaký druh zacykleniu deje tu, no rekurzia, žiadne slučky. Je to proste musím byť tvrdý-kódované linky kódu, ako máme v tejto vzorke. 

Takže ďalší problém 12 nás požiadala, aby sme dokončení implementácie vyradenie pod takým spôsobom, že sa odstraňuje n zo zoznamu v lineárnom čase. Takže budete musieť trochu viac manévrovací priestor teraz. Môžete predpokladať, že n, ak je prítomná v zozname, bude prítomný nie viac ako raz. A to tiež má byť test založený na zjednodušujúce predpoklad, aby že ak nájdete číslo 50 niekde v zozname, nemáte tiež majú na starosti aj naďalej iterácii, hľadá všetky možné kópie z 50, čo by práve prechádzajú do nejaké drobné detaily, v obmedzenom čase. 

Takže s remove, tento bol určite náročnejšie a viac Kód písať. Ale na prvý pohľad, úprimne povedané, to by mohlo vyzerať ohromujúci a ako niečo, neexistuje žiadny spôsob, ako by ste mohli mať prísť s na kvíz. Ale ak sa zameriame na jednotlivé kroky, Dúfajme, že to naraz Pripadá vám, že každý z týchto jednotlivých kroky je zrejmý zmysel v spätnom pohľade. Takže poďme sa pozrieť. 

Tak za prvé, my inicializovať ukazovateľ byť zoznam sám. Pretože chcem lineárny čas, to znamená Budem mať nejaké slučky. A obyčajný spôsob, ako iterovat cez uzly v štruktúre zoznamu alebo akékoľvek štruktúry iteratívne je, aby sa ukazovateľ na prednej časti dát štruktúra a potom len spustiť aktualizáciu to a ísť svojou cestou prostredníctvom dátovej štruktúry. Takže budem robiť presne to. 

Zatiaľ čo ukazovateľ, môj dočasné premenné, nie je rovné null, poďme choďte do toho a skontrolovať. Mal som šťastie? Je n polia v uzle som v súčasnej dobe pri pohľade na rovný číslo som hľadal? A ak áno, poďme niečo urobiť. Teraz, všimnite si to, ak podmienka obklopuje celý Nasledujúce riadky kódu. To je jediné, čo ma zaujíma - nájsť číslo v otázke. Takže neexistuje žiadny iný, ktorý zjednodušuje veci koncepčne trochu. 

Ale teraz som si uvedomil, a môžete mať len si to uvedomil po myslenie je to cez trochu, je tu vlastne dve prípadov tu. Jedným z nich je, ak je uzol v začiatku zoznamu, ktorý je trochu nepríjemné, pretože to je zvláštny prípad, pretože sa budete musieť vysporiadať s tou vecou, ​​ktorá je len anomálie. Všade inde v zozname, je to to isté. K dispozícii je predchádzajúca uzol a ďalšie uzol, uzol predchádzajúce, ďalšie uzol. Ale ten chlap je trochu zvláštne v prípade, že je na začiatku. 

Takže v prípade, že ukazovateľ sa rovná zoznam sama o sebe, takže keď som na začiatku roka zoznam a našiel som n, musím urobiť pár vecí. Po prvé, musím do zoznamu zmeniť poukazujú na ďalšie pole, 50 rokov. Takže predpokladám, že sa snažím odobrať 34. Takže ten chlap musí ísť preč len chvíľu. 

Takže som chcel povedať, zoznam dostane ukazovateľ ďalšie. No, to je ukazovateľ. Ďalej sa ukazuje sem. Tak to sa mení na túto šípku vpravo teraz poukázať na toho chlapa tu. Teraz, pamätajte, že máme dočasné premenné. Takže sme sa osirelé všetky uzly, pretože som tiež toho chlapa v mojom realizácia remove. Takže teraz, ak zoznam sám o sebe nie je null, Musím opraviť niečo. 

Musím sa uistiť, že táto šípka, ktorý je už ukazuje 50 až 34, to má ísť preč, pretože keď sa snažím zbaviť z 34, 50 mal lepší ponechať druh späť odkaz na to, ako arrow navrhol. Tak som to urobil čiaru. Tak som urobil. Tento prípad je vlastne celkom jednoduché. Odsekne hlavu zoznamu je pomerne jednoduché. 

Bohužiaľ, tam je to nepríjemné iný blok. Takže teraz, musím vziať do úvahy prípad tam, kde je niečo uprostred. Ale nie je to príliš hrozné, s výnimkou pre syntax ako je táto. Takže ak nie som na začiatku roka Zoznam, som niekde uprostred. A tento riadok je tu hovorí, začiatok na čo uzla ste na. Prejsť na ďalšie pole z predchádzajúceho uzla a ukazujú, že na ukazovateľ. 

Poďme to obrazne. To bolo stále zložitejšie. Takže ak mám predchádzajúce pole tu - poďme na to - ďalšie pole tu. Chystám sa zjednodušiť svoje ukazovatele, skôr ako kresliť veľa veci tam a späť brázdia navzájom. A teraz, povedzme, že je to 1, 2, 3 kvôli diskusiu, a to aj aj keď to nie je vyrovnaný so problém sa jedná. 

Takže tu je moja spájať zoznam. Snažím sa odstrániť dva v tomto najmä verzie príbehu. Takže som aktualizované ukazovateľ sa ukázal na toho chlapa. Tak toto je PTR. On ukázal tu. Toto je zoznam, ktorý existuje na celom svete ako predtým. A on ukázal tú bez ohľadu na to, čo. A teraz sa snažím odstrániť dva. 

Takže ak je ukazovateľ ukazuje tu, som bude nasledovať, zdá sa, predchádzajúci ukazovateľ, ktorý mi dáva na 1. Ja som potom chcel povedať, že budúci pole, čo ma privádza na to box tu, bude rovná ukazovateľ ďalšie. Takže ak tento ukazovateľ, je to hneď vedľa. To znamená, že to musí šípka poukázať na toho chlapa. 

Tak čo, že riadok kódu má len urobiť, je trochu z toho. A teraz to vyzerá, ako krok správnym smerom. V podstate Chceme odstrihnúť 2 out do stredu 1 a 3. Takže je logické, že chceme trasy tohto ukazovateľa okolo neho. Takže to ďalší riadok je kontrola, či ukazovateľ ďalšie nie je null, je tu naozaj niekto na pravej strane 2, to znamená, že musíme tiež urobiť trochu odstrihnúť tu. 

Takže teraz je potrebné dodržiavať tento ukazovateľ a aktualizovať predchádzajúce ukazovateľ na ten chlap urobiť trochu obísť tu bod tu. A teraz, vizuálne je to pekné. Je to trochu chaotický v tom, že tam je nikto ukázal na 2 už. 2 ukazuje doľava. A 2 sa ukazuje na pravej strane. Ale on môže robiť, čo chce, pretože je to asi, aby sa oslobodil. A nezáleží na tom, čo tieto hodnoty sú už. 

Čo je dôležité je, že zostávajúce chlapci sú smerovanie vyššie a pod ním teraz. A vskutku, to je to, čo robiť ďalej. Sme bez ukazovateľ, čo znamená, povieme operačný systém, ste vítaní kultivovať to. A potom sa konečne vrátime. Else implicitne, ak sa sa ešte nevrátil, musíme hľadať ďalej. Takže ukazovateľ sa rovná ukazovateľ vedľa práve znamená pohybovať toho chlapa tu. Presunúť toho chlapa tu. Presunúť toho chlapa tu, či v skutočnosti, sme nenašli číslo hľadáme ešte. 

Takže úprimne povedané, vyzerá to úplne ohromujúci, myslím, že na prvý pohľad pohľad, a to najmä ak ste sa snažil s tým počas testu potom zistiť, niečo také. A ty pat si na chrbát. No, neexistuje spôsob, ako by som mohol mať prísť s tým na kvíz. Ale povedal by som, môžete, ak porušíte že sa do nich jednotlivé prípadoch a len pešo cez neho opatrne, aj keď, pravda, pod stresujúce situácie. 

Našťastie, vyrobený obrázok všetko šťastnejší. Tie by mohli čerpať na túto ľubovoľný počet spôsobov. Nemusíte robiť krížom krážom vec tu. Dalo by sa to urobiť s rovnou linky, ako je tento. Ale podstata tohto problému, v Všeobecne platí, že bolo si uvedomiť, že obrázok na konci by malo vyzerať trochu niečo také, pretože konštantný čas znamenal, že budete mať rušenie a rušenie a rušenie nové uzly na začiatku zoznamu. Akékoľvek otázky? Asi najnáročnejšie určite kódovanie otázky. 

DIVÁKOV: Takže je zoznam podobný hlavu v predchádzajúcich príkladoch. 

DAVID J. Malan: Presne tak, presne tak. Len iný názov pre globálna premenná. Na celom svete, čo? 

ROB BOWDEN: OK. Takže to je ten, kde sa musel napísať odsek. Niektorí ľudia písali eseje na túto otázku. Ale stačí použiť týchto šesť termíny popísať, čo sa stane, keď skúste kontaktovať facebook.com. Tak som si len pohovoriť prostredníctvom procesu s využitím všetkých týchto podmienok. Takže v našom prehliadači, napíšeme facebook.com a stlačte klávesu Enter. Takže náš prehliadač sa deje na výstavbu HTTP požadovať, že to bude posielať prostredníctvom nejakého procesu na Facebook pre Facebook reagovať na nás s HTML svojej stránky. 

Takže to, čo je proces ktorý požiadavku HTTP skutočne dostane na Facebook? Takže najprv musíme prekladať Facebook.com. Tak práve dal názov Facebook.com, kde vlastne robí HTTP požiadavky treba ísť? Takže musíme preložiť Facebook.com na IP adresu, ktorá jednoznačne určuje, čo stroj vlastne chcete poslať túto žiadosť. Váš notebook má IP adresu. Čokoľvek, pripojenie k internetu má IP adresu. 

Takže DNS, Domain Name System, ktorá je čo sa deje zvládnuť preklad od facebook.com na IP adresu, ktorá vlastne chcete kontaktovať. Tak sme sa kontaktovať DNS servery a povedzme, čo je facebook.com? To hovorí, oh, to je IP adresa 190,212 niečo, niečo, niečo. Dobrá. Teraz viem, čo stroj Chcem kontaktovať. 

Takže potom pošlite svoju požiadavku HTTP sa k tomuto zariadeniu. Tak ako to dostať do toho stroja? No, žiadosť ide od na routeru odrážanie. Spomeňte si na príklad v triede, kde sme vlastne videli cestu, ktorá pakety sa, keď sme sa snažili komunikovať. Videli sme, že skok cez Atlantik Ocean na jednom mieste, alebo čokoľvek iného. 

Takže posledný termín portu. Tak to je teraz na vašom počítači. Môžete mať viac vecí v súčasnej dobe komunikáciu s internetom. Takže môžem byť spustený, povedzme, Skype. Mohol by som mať webový prehliadač otvorený. Možno som niečo, čo torrenting súbory. Takže všetky tieto veci sú komunikáciu s internet nejakým spôsobom. 

Takže keď váš počítač prijme nejaké dáta z internetu, ako sa to vedieť, čo vlastne aplikácie chce údaje? Ako to, či tento konkrétny Dáta sú určené pre torrenting aplikácie na rozdiel od na webovom prehliadači? Takže to je účel portov v tom, že Všetky tieto aplikácie majú vyhlásil port na vašom počítači. Takže váš webový prehliadač hovorí, hej, Počúvam na porte 1000. A váš torrenting programu hovorí, Počúvam na porte 3000. A Skype hovorí, som pomocou portu 4000. 

Takže keď vám niektoré dáta, ktorá patrí do jednej z týchto aplikácií, dát je označený port, ktorý je v skutočnosti by mali byť zaslané spolu so. Tak to hovorí, oh, ja patrím na porte 1000. Viem, že potom musím, aby postúpil toto po mojej webovom prehliadači. Takže dôvod, prečo je to relevantné je, že webové servery majú tendenciu načúvať na porte 80. Takže keď som sa kontaktovať Facebook.com, som komunikáciu s nejakým strojom. Ale musím povedať, aký port, ktorý Stroj chcem komunikovať. A webové servery majú tendenciu byť načúva na porte 80. 

Keby chceli, mohli by ho nastaviť tak, že uvádza ako na porte 7000. A potom vo webovom prehliadači, mohol by som ručne zadať Facebook.com: 7000 k poslať požiadavku na porte 7000 webového servera Facebooku. 

DAVID J. Malan: A v tomto prípade, a to aj aj keď sme nemali požadovať, aby ľudia spomenúť to, v tomto prípade, aký port by žiadosť skutočne ísť na? Skúste to znova. Presne tak. Nehľadám, ale jemnosť že tam nič ako posledný. 

ROB BOWDEN: Tak HTTPS, pretože je to špeciálne pre počúvanie zašifrované, je to na porte 4430. 

Divákov: A e-maily sú 25, že jo? 

DAVID J. Malan: Odchádzajúce e-maily, 25, jo. 

ROB BOWDEN: Ja ani neviem, väčšina - Všetky tie nižšia bývajú vyhradené pre veci. Myslím, že všetko pod 1024 je vyhradené. 

DIVÁKOV: Prečo hovoríte, 3. Bol zlé číslo? 

ROB BOWDEN: Pretože IP adresy, tam štyri zoskupenia číslic. A oni sú od 0 do 255.. Takže 192.168.2.1 je spoločný lokálnej siete IP adresy. Všimnite si, všetky z nich sú menšie ako 255.. Takže keď som začal s 300, že nemohol mať jedným z čísiel. 

DAVID J. Malan: Ale to hlúpe klip od - bol to CSI, kde mali číslo, ktoré je príliš veľké pre IP adresu. 

ROB BOWDEN: Prípadné otázky na to? Budúci, takže úplná zmena tému, ale máme to PHP polia pre domy na štvorkolke. A máme neusporiadané zoznam. A chceme vytlačiť každej položky zoznamu Len obsahujúci názov domu. Takže máme slučky foreach. Takže pamätajte, že syntax je foreach pole ako položka v poli. Takže prostredníctvom každej opakovanie slučky, Dom bude trvať na jednej z hodnoty vnútri tohto poľa. 

Na prvý iterácie, dom bude Cabot dom. Na druhej iterácie, dom bude byť Courier dom a tak ďalej. Takže pre každú štvoricu ako dom, sme len ísť do tlače - ste tiež mohli ozvenou - položku zoznamu a potom názov domu je a zatvorte položku zoznamu. Zložené zátvorky sú tu voliteľná. 

A potom sme tiež povedal v otázke sama o sebe, nezabudnite zavrieť Jednoduchý zoznam zobrazí značka. Takže musíme opustiť režim PHP aby sa to urobiť. Alebo by sme mohli ozvenou zavrieť neusporiadaný zoznam tag. 

DAVID J. Malan: Tiež tu by pokuta boli použiť starú školu slučka s $ i = 0 0 a použitím sa počíta na zistiť dĺžku lúča. Taky úplne v pohode, len trochu wordier. 

DIVÁKOV: Takže ak ste sa chystali [Nepočuteľné], by vy - Ja zabudol, čo slučka [nepočuteľné] je. Chceli by ste $ quad držiak aj? 

DAVID J. Malan: Presne tak. Jo, presne tak. 

ROB BOWDEN: Ešte niečo? 

DAVID J. Malan: Dobre. Trade-off. Takže tam boli hrozno odpovedí možné, pre každú z nich. Boli sme naozaj len hľadáte niečo presvedčivé pre nahor a nevýhoda. A číslo 16 spýtal, overovanie používateľov " Vstup na strane klienta, ako u JavaScriptu, miesto na strane servera, ako u PHP. Takže to, čo je hore z robí na strane klienta? 

No, jedna z vecí, ktoré sme navrhli, je že znížiť latenciu, pretože vám Nemusíte sa obťažovať kontaktovanie Server, ktorý môže trvať niekoľko milisekúnd alebo dokonca pár sekúnd vylúčením, že aj len overovanie vstupu na strane klienta používateľov tým, spustenie obslužné rutiny on-predložiť a len kontrolovať, sa im napíšte niečo pre meno? Páčilo sa im niečo písať in pre e-mailovú adresu? Páčilo sa vybrať koľaj z Výberová ponuka? 

Môžete im dať okamžitú spätnú väzbu pomocou počítača gigahertz alebo čo majú, že je vlastne na svojom stole. Takže je to len lepšie užívateľské zažiť zvyčajne. Ale Nevýhodou robí na strane klienta overenie, ak si to bez toho, robí server-side validáciu je, že Najviac niekto prichádza z CS50 vie že môžete len odosielať dáta, ktoré chcete na serveri ľubovoľný počet spôsobov. Úprimne povedané, vo väčšine ľubovoľnom prehliadači, môžete kliknite okolo v nastavení a len vypnúť JavaScript, ktorá by preto, zakázať akúkoľvek formu validácia. 

Ale vy ste tiež mohli pripomenúť, že aj ja robil nejaké tajomné veci v triede pomocou telnet a dokonca predstiera, že bude prehliadač zaslaním get požiadavky na server. A to rozhodne nie je pomocou ľubovoľného JavaScript. To je len môj zadaním príkazov na klávesnici. Takže naozaj, každý programátor v dostatočne komfort s webom a HTTP mohol poslať čo dát on alebo ona chce k serveru bez overenia. A ak váš server nie je tiež kontrola, to sa mi dať meno, je to vlastne platnú e-mailovú adresu, robil si vyberú koľaji, môžete skončiť hore vkladanie falošné, alebo len prázdne údaje do databázy, čo pravdepodobne sa nebude dobrá vec, ak ste za predpokladu, že tam bol. 

Tak to je nepríjemné reality. Ale všeobecne, na strane klienta validácia je skvelá. Ale to znamená, že dvakrát toľko práce. Hoci tam predsa existujú rôzne knižnice, JavaScript knižnice pre inštancie, ktoré tvoria toľko, oveľa menšie bolesti hlavy. A môžete znova použiť niektoré z kódu server-side, na strane klienta. Ale uvedomiť, že to je typicky ďalšie práce. Jo. 

DIVÁKOV: Takže keby sme povedal menej bezpečné - 

DAVID J. Malan: [smeje sa] Fuj. Tí sú vždy ťažšie tie sa rozhodnúť. 

ROB BOWDEN: To by boli prijaté. 

DAVID J. Malan: Čo? 

ROB BOWDEN: Vytvoril som tento problém. To by boli prijaté. 

DAVID J. Malan: Jo. 

DIVÁKOV: Cool. 

ROB BOWDEN: Ale my sme neprijali pre prvý - dobre, to, čo sme hľadali, je niečo ako vy nemusíte komunikáciu so serverom. Neprijali sme jednoducho rýchlejší. 

DIVÁKOV: Čo nie znova načítať stránku? 

ROB BOWDEN: Áno. To bola prijatá odpoveď. 

DAVID J. Malan: Čokoľvek, kde sme cítili, to bolo viac pravdepodobné ako nepravdepodobné, že ste vedel, že to, čo bolo hovorí, čo je ťažké vedenie k tomu niekedy. Miesto pomocou prepojeného zoznamu z poľa k udržaniu radené zoznam celých čísel. Takže hor sa často citujú sa spojené zoznamy, ktoré motivovali ich celok úvod bol dostanete dynamiku. Môžu dorásť. Môžu zmenšiť. Takže nemusíte sa preskočiť obručou skutočne vytvoriť viac pamäte s radom. Alebo nemusíte len povedať, je mi ľúto, užívateľ. Pole je vyplnené. Takže dynamický rast zoznamu. Nevýhodou však spojových zoznamov? 

DIVÁKOV: Je to lineárna. Vyhľadávanie na Google zozname je lineárna namiesto toho, čo sa prihlásite 

DAVID J. Malan: Presne tak. Vyhľadávanie na Google zozname je lineárna, aj keď je to ďalej, pretože môžete len postupujte podľa nasledujúcich strúhanky, tieto ukazovatele, od začiatku zoznamu až do konca. Nemôžete využiť náhodný prístup a, tak, binárne vyhľadávanie, aj keď je to ďalej, že by ste mohli čo robiť s maticu. A je tu aj ďalšie náklady. Jo. 

DIVÁKOV: Memory neefektívne? 

DAVID J. Malan: Jo. No, ja by som to nutne hovoria neefektívne. Ale to stáť viac pamäte, pretože budete potrebovať 32 bitov pre každý uzol pre ďalšie ukazovatele, na aspoň pre jednotlivo prepojeného zoznamu. Teraz, keď ste len ukladanie celých čísel a pridávate ukazovateľ, ktorý je v skutočnosti druh non-triviálne. Je to zdvojnásobenie množstva pamäte. Ale v skutočnosti, ak ste ukladanie spájať zoznam štruktúr, ktoré by mohli mať 8 bajtov, 16 bajtov, ešte ako to, že je to možno menej z medzné náklady. Ale je to nákladovo však. Takže jeden z tých by si Bol v poriadku, tienisté stránky. 

18. Použitie PHP namiesto C písať príkazového riadku programu. Tak tu je to často rýchlejší použiť jazyk, ako je PHP alebo Ruby alebo Python. Jednoducho rýchlo otvoriť do textového editora. Máte mnoho ďalších funkcií Vám k dispozícii. PHP má kuchynský drez funkcií, zatiaľ čo v C, je majú veľmi, veľmi málo. V skutočnosti, chlapci vedia tvrdo že nemáte hash tabuľky. Nemáte spojené zoznamy. Ak chcete tí, musíte im realizovať sami. 

Takže jeden hore PHP alebo naozaj nejaký interpretovaný jazyk je rýchlosť pomocou ktorého môžete písať kód. Ale nevýhoda, videl sme sa, keď som rýchlo sa šľahačkou a misspeller implementácia v prednáške pomocou PHP, je že použitie interpretovaný jazyk je zvyčajne pomalší. A my sme videli, že preukázateľne sa zvýšenie v čase od 0,3 sekúnd až 3 sekúnd, a to z dôvodu výkladu že v skutočnosti deje. 

Ďalším dňom bolo to, že vám nemusíte kompilovať. Tak to tiež urýchľuje vývoj mimochodom, pretože nemáte dva kroky k behu programu. Stačí mať jeden. A tak to je celkom presvedčivé rovnako. Namiesto použitia SQL databázy CSV súbor pre ukladanie dát. Tak SQL databázy sa používa pre pset7. Súbory CSV ste nepoužili moc. Ale vy ste ju použil nepriamo pset7 ako aj tým, že hovorí do Yahoo Finance. 

Ale CSV je, rovnako ako súbor programu Excel, ale super jednoduché, kde stĺpce sú len demarked čiarkami vnútri z inak textového súboru. A pomocou SQL databázy je trochu viac presvedčivé. Je to obrátene, pretože sa veci ako vybrať a vložiť a odstrániť. A vám, podľa všetkého indexy, ktoré MySQL a ďalšie databázy, ako je Oracle, vybudovať pre vás v pamäti, ktoré znamená, že váš výber je pravdepodobne bude lineárny zhora nadol. Je to naozaj bude niečo ako binárne vyhľadávanie alebo niečo podobne v duchu. Takže sú všeobecne rýchlejšie. 

Ale nevýhodou je, že je to len viac práce. Je to viac úsilia. Musíte pochopiť databáz. Musíte nastaviť. Musíte server spustiť že databáza. Musíte pochopiť, ako ju nakonfigurovať. Takže to sú len tie druhy kompromisov. Vzhľadom k tomu, CSV, môžete vytvoriť s gedit. A máte dobré ísť. Neexistuje žiadny zložitosti ďalej. 

Použitie trie miesto hash tabuľky s oddelenou reťazenie pre uloženie slovník slov pripomínajúcich z pset5. Preto sa snaží nahor, teoreticky najmenej, je to, čo? Konštantný čas, aspoň pokiaľ ste hash na každom jednotlivcovi písmená v slovách, ako ste vy, môže mať pre pset5. To by mohlo byť päť hash, šesť hash v prípade, že je päť alebo šesť písmen v slove. A to je celkom dobré. A v prípade, že je horná hranica na tom, ako dlho vaše slová môžu byť, to je naozaj asymptoticky konštantný čas. 

Vzhľadom k tomu, hash tabuľka s oddeleným reťazenie, problém tam s tým druh dátové štruktúry je to, že výkon svojich algoritmov zvyčajne závisí na mnohých faktoroch už v dátovej štruktúre. A to je určite prípad reťaze, pričom viac vecí si dať do hash tabuľky, už ti reťaze ísť, čo znamená, že v najhoršom prípad, vec, ktorú by mohol mať záujem o je úplne na konci jedného z týchto reťazcov, ktoré účinne prejde do niečoho lineárne. 

Teraz, v praxi by sa úplne byť v prípade, že hash tabuľky s reťazca je rýchlejší ako zodpovedajúca Implementácia trie. Ale to z rôznych dôvodov, medzi , Ktoré sa snažia využiť celý rad pamäti, že môže v skutočnosti pomalé veci dole, pretože nemusíte dostať pekný Výhody niečo, čo nazýva ukladanie do vyrovnávacej pamäte, kde veci, ktoré sú blízko pri sebe v pamäti možno pristupovať často rýchlejšie. A niekedy môžete prísť s naozaj dobrý hašovacej funkcie. I keď budete musieť strácať trochu pamäť, môžete skutočne byť schopný nájsť veci rýchlo, a nie rovnako zlý ako lineárne. 

Takže v skratke, nebolo nutne s niektorou z týchto jedného alebo aj dva konkrétne veci, ktoré sme hľadali. Naozaj nič presvedčivý ako inflačné a protiinflačnej všeobecne zachytil našu pozornosť. 

ROB BOWDEN: Tak na druhú stranu, my sme neprijíma sama o sebe "rýchlejšie." Vy musel hovoriť niečo o tom. Dokonca aj keď ste povedal teoreticky rýchlejší, vedeli sme, že tak nejako pochopil, že je to 0 z 1.. A hash tabuľka, v teórii, nie je 0 1.. Za zmienku niečo o behu všeobecne Máš body. Ale "rýchlejšie", väčšina riešení na veľká doska, ktorá sa snaží boli objektívne pomalší ako riešenie ktoré boli hash tabuľky. Tak rýchlejšie a sama o sebe Nie je to pravda. 

DAVID J. Malan: Dom de dom dom. Som asi jediný, kto si uvedomuje, to je, ako to má sa vyhlásil, že jo? 

ROB BOWDEN: Mal som vlastne ani poňatia. 

DAVID J. Malan: Je vyrobená pocit v mojej hlave. 

ROB BOWDEN: Robím túto. OK. Takže to je ten, kde ste museli čerpať diagram podobný by ste mohli videli na posledných skúškach. Takže poďme sa len pozrieť na to. Takže z uzla HTML, máme dve deti, hlava a telo. Tak sme sa rozdeliť - hlavu a telo. Hlava má názov značky. Takže máme titul. 

Teraz, jedna vec, ktorú mnoho ľudí zabudol je, že tieto textové uzly prvky v rámci tohto stromu. Tak sme tu náhodou je nakresliť ako ovály odlíšiť ich od nich druhy uzlov. Ale Oznámenie tiež tu máme vrchol, strednej a dolnej skončí na textové uzly. Tak zabúdam ktoré bolo trochu spoločného chyby. 

Telo má tri deti - Tieto tri divs. Takže div, div, div a potom text uzol deti týchto divs. To je docela veľa to na tom, že otázky. 

DAVID J. Malan: A je potrebné poznamenať, aj keď nebýva na týchto Podrobnosti v čase, keď sme strávili na JavaScript, ktorý príkaz robí, v Skutočnosť, záležitosť technicky. Takže ak hlava je pred telom v HTML, potom by sa mala objaviť na vľavo tela v skutočnom DOM. To mu je, všeobecne, len FYI, niečo, čo nazýva aby dokument, kde to záleží. A ak ste boli sa vykonáva analyzátor, program, ktorý číta HTML v budove do stromu v pamäti, aby som bol úprimný, to je intuitívne pravdepodobne to, čo ste robiť tak ako tak - zhora nadol, zľava doprava. 

ROB BOWDEN: Otázky na to? Mám urobiť ďalší? 

DAVID J. Malan: Iste. 

ROB BOWDEN: OK. Tak toto je pretečeniu vyrovnávacej pamäti Útok otázka. Hlavná vec, ktorú si uvedomiť, tu je, dobre, ako by mohol protivník trik tento program do realizácie ľubovoľný kód? Takže argv1, prvý príkazového riadku argument tohto programu, ktoré môže byť ľubovoľne dlho. Ale tu sme pomocou memcpy kopírovať argv1, ktorý je tu bar. Sme odovzdaním ako argument. A tak je to s na meno bare. 

Takže sme memcpying bar do tejto vyrovnávacej pamäti c Koľko bajtov sme kopírovanie? No však veľa bytov bar sa stane používať, dĺžku tohto argumentu. Ale c je iba 12 bajtov široký. Takže ak by sme zadajte argument príkazového riadku to je dlhšie ako 12 bajtov, sme bude pretekať to najmä vyrovnávacej pamäti. Teraz, ako by protivník trik naprogramovať do vykonania ľubovoľného kódu? 

Takže nezabudnite, že tu Hlavné volá foo. A tak teda hlavné výzvy foo. Poďme nakresliť to. Takže máme stack. A hlavné je rámik zásobníka v spodnej časti. Na nejakom mieste, hlavné výzvy foo. No, okamžite, hlavné výzvy foo. A tak foo dostane svoj vlastný rámik zásobníka. 

Teraz, v určitom okamihu, foo sa chystá na návrat. A šiel foo vráti, musíme vedieť, na čo riadok kódu vnútri hlavné my bolo, aby vedeli, kde by sme mali pokračovať v main. Môžeme volať foo z celku veľa rôznych miestach. Ako môžeme vedieť, kam sa vrátiť? No, musíme uložiť, že niekde. 

Takže niekde priamo tu, uložíme kde by sme sa mali vrátiť k raz foo vracia. A to je spiatočná adresa. Tak ako by mohol protivník využiť to je skutočnosť, že Táto vyrovnávacia pamäť c je uložená, poďme povedať, tu je cca. Takže máme 12 bajtov pre C. To je cca. A to je Foo stack krúžok. Takže v prípade, že používateľ sa zlými úmyslami zadá viac bajtov, ako 12 rokov alebo je zadajte príkaz linka argument, že je dlhší ako 12 znaky, potom budeme pretečeniu tejto vyrovnávacej pamäti. 

Môžeme ísť ďalej. A v určitom okamihu, môžeme ísť ďaleko natoľko, že začneme prepísanie tejto spiatočnú adresu. Takže akonáhle sme sa prepísať návratovú adresu, to znamená, že pri foo sa vracia, vraciame sa tam, kde užívateľ sa zlými úmyslami sa hovorí, to by bez ohľadu na hodnotu vstúpila, bez ohľadu na znaky užívateľ zadal. A tak v prípade, že používateľ sa zlými úmyslami je, že obzvlášť šikovný, môže mať táto návrat niekam do printDef funkcie alebo niekde v malloc funkcie, proste kdekoľvek ľubovoľný. 

Ale aj ďalšie chytré je to, čo v prípade, že má užívateľ vrátiť k práve tu. A potom začnete vykonávanie to ako riadky kódu. Takže v tomto bode, môže užívateľ zadať čo chce v tejto oblasti. A on má úplnú kontrolu na programe. Otázky na to? Takže ďalšia otázka je kompletný reimplementáciu foo takým spôsobom, že už to nie je zraniteľná. 

Takže tam je niekoľko spôsobov, ako si to mohol urobiť. Máme stále c iba sú dĺžky 12. Dalo by sa zmenili v tomto ako súčasť vášho riešenia. Tiež sme pridali kontrolu, aby sa , Že bar nie je null. Aj keď nepotreboval že pre plnú úveru. Takže sme kontrolu prvej dĺžka reťazca baru. Ak je väčší ako 12, potom nie sú v skutočnosti robiť kópie. Takže to je jeden zo spôsobov, ktorým sa to. 

Ďalší spôsob, ktorým sa to je miesto s c sa len v dĺžke 12, má to byť dĺžka strlen (bar). Ďalší spôsob, ktorým sa to je skutočne len vrátiť. Takže ak ste sa práve zbavili všetkých to, ak ste práve odstránené všetky riadkov kódu, by ste sa dostali plné uznanie, pretože túto funkciu nie je v skutočnosti dosiahnuť nič. Je to kopírovanie príkazového riadku Argument do nejakého poľa v jej miestna stack frame. A potom, čo sa vracia. A čo to dokonalý, je preč. Takže návrat bol tiež dostatočné spôsob, ako dostať všetky zásluhy. 

DAVID J. Malan: Nie tak celkom duch otázka, ale prijateľné za spec však. 

ROB BOWDEN: Otázky týkajúce sa niečo z toho? Jedna vec, ktorá vám aspoň potrebné na zostavenie kódu. Takže aj keď technicky nie ste zraniteľná, ak váš kód nie je zostaviť, sme nemali prijať. Žiadne otázky? OK. 

DAVID J. Malan: Chcete povedať, tento titul? 

ROB BOWDEN: Nie 

DAVID J. Malan: Tak v tomto, to bol buď dobrá správa alebo zlá správa. To je doslova rovnaký problém ako prvý kvíz. A to je skoro rovnaký problém, pset1. Ale to bolo zámerne zjednodušený, aby sa jednoduchšie pyramída, ktorý môže byť riešená s mierne jednoduchšie iterácie. A naozaj, čo sme sa dostať na tu nebolo toľko logiky, pretože pravdepodobne v tomto okamihu, že ste oveľa pohodlnejšie, než ste boli v týždni jednej s pre slučky alebo prečo slučiek, ale naozaj dráždiť seba, že ste trochu pohodlnejšie s Predstava, že PHP nie je len o tom, čo programovania. To môže v skutočnosti byť použitý ako jazyk písať programy príkazového riadku. 

A vskutku, to je to, čo sa snažíme upozorniť na. To je PHP programu pre príkazový riadok. Takže C kód tu, zatiaľ čo správna v C, nie je správne pre PHP. Ale kód je v skutočnosti rovnaké. Ak porovnáte riešenie pre Quiz 0 proti Quiz 1, zistíte, že je to takmer totožné, s výnimkou Niektoré dolára a pre absencia dátového typu. Najmä, ak sa pozrieme tu, uvidíte, že sme iterácii, v tomto prípad od 1 do až 7. 

Mohli sme to urobil 0 index. Ale niekedy si myslím, že je to len mentálne jednoduchšie premýšľať o veciach, 1-7. Ak chcete jeden blok, a potom dva bloky, potom tri, potom bodka, bodka, bodka sedem. Máme j je inicializovaný na hodnotu 1 a potom sa počíta až na i. A všetko je tu inak identické. Ale stojí za zmienku, sú pár vecí. Dáme vám tieto dva riadky, to prvé jeden, goofily pomenovaný ako shebang pre ostrú ranou. A to práve určuje cestu, zložka, v ktorej môže byť program zistili, že chcete použiť interpretovať tento súbor. 

A potom vedenie po tom, o Samozrejme, že znamená, že vstup do režimu PHP. A linka na samom dne znamená, že režim exit PHP. A to funguje všeobecne, s interpretovať jazykov. Je to docela nepríjemné, ak píšete Program v súbore s názvom foo.php. A potom užívatelia majú len pamätajte, OK, pre spustenie tohto programu, som musieť zadať "php priestor foo.php." Druh nepríjemné keď už nič iné. A to tiež ukazuje, že váš program je napísaný v PHP, ktorý nie je všetko že osvetlenie pre užívateľa. 

Takže môžete odstrániť. Php úplne pamätáte z prednášky. A môžete skutočne urobiť. / Foo, ak ste chmodded to tým, že to spustiteľný súbor. Takže chmod + x foo by urobil to. A ak ste tiež pridať cirkus tu. Ale v skutočnosti, problém bol dostať na vytlačiť niečo také. No HTML, nie C-kódu iste, len niektoré PHP. Takže Milo potom sa vrátil do problému 25. A v roku 25, ste dostali z nasledujúcich kostra kód, ktorý bol celkom jednoduché webové stránky. A šťavnaté časť HTML-múdry bol dole tu, kde máme vo vnútri tela forma, ktorá má unikátne ID vstupov vnútri ktorej je dva vstupy, jeden s myšlienkou meno, jeden s myšlienkou tlačidla. 

Prvý bol typ textu, Druhá typu predložiť. A tak sme vám dali, v skutočnosti, viac zložky, než ste potrebovali, len tak vy ste mali možnosti, s ktorými k vyriešeniu tohto problému. Nemusíte nevyhnutne potrebujú všetky tieto ID. Ale to vám umožní riešiť to rôznymi spôsobmi. A až na vrchol, všimnite si, že Cieľom bolo vyvolať Okno takhle - Dobrý deň, Milo! - vyskočí v prehliadači pomocou super jednoduché, ak Nie je škaredá, funkcia upozornenia. A tak nakoniec, to sa scvrkáva koncepčne nejako počúvať podanie formulára na strane klienta , Nie na strane servera, tak nejako odpovede na toto podanie podľa chytil hodnotu, ktorá používateľ zadaný do poľa Názov a potom jeho zobrazenie v tele výstrahy. 

Takže jeden spôsob, ako to môžete urobiť, je sa jQuery, ktorá vyzerá trochu syntakticky mätúce na prvý pohľad. Môžete to urobiť s čistým DOM kódu - document.getelement podľa ID. Ale poďme sa pozrieť na túto verziu. Mám pár dôležitých prvej línie. Takže jeden, máme tento riadok, ktorý je totožný s tým, čo ste mohli vidieť v, verím, form2.html z triedy v týždni 9. A to je len hovorím, vykonať Nasledujúci kód pri Dokument je teraz pripravený. To je dôležité nielen preto, HTML stránky sa čítajú zhora dole, zľava doprava. 

A preto, ak sa pokúsite urobiť niečo v kóde, až tu na nejakú DOM prvok, niektoré značky HTML, ktorá je dole tu, že ste to robíte príliš skoro, , Pretože to nemá ani boli načítané do pamäte. Takže tým, že hovorí toto document.ready linka, hovoríme, tu je nejaký kód, prehliadač. Ale nie spustiť, kým celý Dokument je teraz pripravený, že je DOM strom existuje v pamäti. To je trochu viac jednoduché, ak syntakticky trochu iná, kde hovorím, grab prvok HTML, ktorého jedinečný identifikátor vstupy. To je to, čo značka hash označuje, jedinečný identifikátor. A potom volám. Odoslať. 

Tak. Predloží tu je funkcia, inak známy ako metóda, ktorá je vnútri objektu na ľavej strane strane tam, že som nemal zvýrazniť. Takže ak si myslíte, vstupov ako objekt v pamäti - a naozaj to je. Je to uzol na strome - . Predloží znamená, že keď je táto forma sa toto číslo je predložený, vykonať Nasledujúci kód. Nezaujíma ma, čo názov Funkcia je mi vykonávania. Tak tu som pomocou, rovnako ako predtým, to, čo je tzv. funkcia lambda alebo anonymné funkcie. Je to vôbec intelektuálne zaujímavé, iné, než je to nemá meno, čo je v poriadku, ak ste len kedy bude raz zavolať. A vnútri som tam vlastne zvládnuť predloženie formulára. Prvýkrát som deklarovať premennú tzv hodnota. A čo potom je účinok tohto zvýraznená časť tu? Čo to urobiť na na vysokej úrovni pre mňa? 

DIVÁKOV: Dostane hodnotu, ktorá užívateľ nemal v nasledujúcej HTML. Dostane to ID a potom nájde hodnotu neho. 

DAVID J. Malan: Presne tak. Je to chytí uzol, ktorého jedinečný Identifikátor je názov. To dostane hodnotu v ňom, ktoré je pravdepodobne to, čo používateľ napísal ho alebo seba. A potom sa ukladá, aby do premennej s názvom hodnotu. Ako stranou, mohli by ste mať tiež urobiť to trochu inak. Úplne prijateľné tým, že robí niečo, čo lož var hodnota dostane document.getElementById. A to je dôvod, prečo je to trochu zdĺhavý, že nebude používať jQuery. "Meno". Hodnota. Takže úplne prijateľné. Rôzne spôsoby, ako to urobiť. jQuery len má tendenciu byť trochu stručnejší a určite viac populárne medzi programátormi. 

Teraz robím trochu zdravého rozumu skontrolovať, pretože v probléme vyhlásenie sme výslovne povedal, ak užívateľ ešte napísaný jeho alebo jej meno, nevykazujú upozornenia. Ale môžete skontrolovať tým, že práve kontrolu na prázdny reťazec pre quote-koniec citátu v prípade, že je nič v skutočnosti neexistuje. Ale ak to nie je rovná citátom-koniec citátu, Chcem volať upozornenia. A zaujímavá časť je, že sme pomocou operátora navyše, ktoré čo robí v JavaScripte? Zřetězit. Takže je to ako Phps operátor bodka. Rovnaký nápad, mierne odlišná syntaxe. A ja som len vytvoriť reťazec, ktorý ste videli na snímke obrazovky - Ahoj, tak a tak. 

A potom posledný detail je to. Prečo by som sa vrátiť false vnútro tejto anonymné funkcie? 

DIVÁKOV: Nie je hodnotu. Môžete dať vo forme. Je to len hovorí, ak hodnota nie je rovná prázdne, potom to urobiť. Tam bola prázdna v tomto podaní. 

DAVID J. Malan: OK. Opatrní. K dispozícii je tu nikto iný. A to return false je mimo ze ak podmienky. Tak toto zvýrazní líniu, vráti false, vykonáva bez ohľadu na to, kedy Formulár je predkladaný. Čo vracia false vnútri tohto Obslužná rutina udalosti, ako sa tomu hovorí, udalosť v otázke že podanie? 

DIVÁKOV: Vzhľadom k tomu, stane len raz. 

DAVID J. Malan: stane len raz. Nie tak celkom. Jo? 

DIVÁKOV: Zabraňuje formulár od predloženie predvolené správanie, ktoré by na stránku znova načítať. 

DAVID J. Malan: Presne tak. Takže som preťaženiu termín predloženia tu, pretože ja hovorím, forma je bol predložený. Ale ako si navrhnúť, že to v skutočnosti nie je bola predložená v pravom spôsobom HTTP. Po kliknutí na tlačidlo Odoslať, pretože naše onSubmit handler, budeme zastavovať že podacie formulár, aby som tak povedal. Sme potom robí naša vec s kódom JavaScript. Ale ja som zámerne vracia false, pretože to, čo nechcem, aby sa to stalo zlomok sekundy neskôr, je pre celý formulár sama o sebe, ktorá bude predložená na webe server s kľúče a hodnoty, zmenou URL musí byť niečo ako q = mačky alebo čo sme urobili, Napríklad, v triede. Nechcem, aby sa to stalo, pretože nie je server načúvanie na to vytvoriť podanie. Je to čisto vykonané v kóde JavaScript. A to je dôvod, prečo som nemal ani akcie atribút na mojej forme, pretože som nemajú v úmysle, aby to niekedy ísť na server. 

Takže je to byť predložené. Ale my zachytenie tohto formulára podanie a prevenciu predvolené správanie, čo je v skutočnosti ísť celú cestu k serveru. 

DIVÁKOV: Takže udržať to na strane klienta. 

DAVID J. Malan: Vedenie je na strane klienta. Presne tak. Ďalší na rade bol môj oh MySQL. 

ROB BOWDEN: OK. Takže táto prvá otázka bola všeobecne hrubý k ľuďom. Aj keď tie neskôr išiel lepšie. Takže ste mali vybrať správnu údaje typy na oboch týchto stĺpcov. A ako z nich majú niektoré veci o nich, že aby voľba ťažké. Takže int nebol platný typ pre čísla. Dôvodom je 12-miestne číslo účtu číslo, int nie je dostatočne veľká, aby uloženie celkom číslic. Takže voľba je možná by bol veľký int, ak ste náhodou viete, že. Ďalšou možnosťou by mohlo byť char pole o dĺžke 12. Takže jeden z tých by to fungovalo. Int, že nie. 

Teraz, rovnováha, si spomeniem na pset7. Tak sme sa špeciálne používa desatinné číslo na uložiť hodnotu akcií, alebo - 

DAVID J. Malan: Cash. 

ROB BOWDEN: Cash. Použili sme desiatkovej uložiť čiastku hotovosti, ktoré má v súčasnej dobe užívateľ. Takže dôvod, prečo to robíme, je pretože, pamätajte, že pláva. K dispozícii je s plávajúcou desatinnou čiarkou v presnosti. Nemožno presne uložiť hotovosť hodnoty, ako ich chceme tu. Takže desiatkovej je schopný presne sklad niečo, povedzme, dve desatinné miesta. To je dôvod, prečo bilancia, chceme ho byť desatinné, a nie plávať. 

DAVID J. Malan: A taky, taky, aj keď to by mohlo byť šikovný v iných súvislostiach premýšľať, možno to Je to šanca pre int. Budem len sledovať veci haliere. Pretože sme explicitne ukázal predvolené hodnota je 100,00, že znamená, že to môže byť len int. A ďalšie jemnosť tiež s radom bolo, že to nebolo myslené byť chyták. Ale spomínam, že int v MySQL, rovnako ako v C, aspoň v zariadenie, je 32-bit. A aj keď neočakávame, že vám presne vedieť, koľko číslic, ktoré prostriedky, si pripomenúť, že najväčší počet môžete predstavovať potenciálne 32-bitové číslo je zhruba to, čo? 

Aké číslo si vždy povedať? 2 až 32, čo je to, čo zhruba? Nemusíte presne vedieť. Ale asi je užitočné v živote. Je to zhruba 4 miliardy. Tak sme povedali, že za niekoľko minút. Viem, že som povedal, že za niekoľko minút. A to je zhruba 4 miliardy. A to je dobré pravidlo palca vedieť. Ak máte 8 bitov, 256 je magické číslo. Ak máte 32 bitov, 4 miliárd dávať alebo brať. Takže ak ste práve napísať 4000000000, uvidíte, že je to menej číslic ako 12, čo znamená, že je zjavne dosť expresivita zachytiť Číslo účtu 12-miestne. 

ROB BOWDEN: OK. Takže tie ostatné šlo lepšie. Takže predpokladám, že banka ukladá 20 dolárov mesačne udržiavací poplatok na všetkých účtoch. S tým, čo SQL dotazu by banka odpočítať 20 dolárov z každého počtu, a to aj v prípade, to má za následok niektoré negatívne bilanciou? Takže v podstate existujú štyri Hlavnými typmi otázok - vložiť, vyberte, aktualizovať a mazať. Takže to, čo si myslíme, že sme bude tu používať? Aktualizovať. 

Takže poďme sa pozrieť. Tak tu sme aktualizáciu. Čo tabuľke sme aktualizáciu účtov? Tak aktualizácie účtov. A potom syntaxe hovorí, čo v účtoch sme aktualizáciu? No, my sme nastavenie vyváženia rovnajúcu sa aktuálna hodnota zostatku mínus 20. Takže to bude aktualizovať všetky riadky účtov, odpočítaním 20 dolárov z rovnováhy. 

DAVID J. Malan: Častou chybou tu, aj keď sme niekedy odpustil to, bolo skutočne PHP kód tu volanie funkcie dotazu alebo uvedenie úvodzovky okolo všetkého, čo Nepotreboval, aby sa tam. 

ROB BOWDEN: Nezabudnite, že MySQL je oddelený jazyk od PHP. Sme stalo, že sa písanie MySQL v PHP. A PHP sa to potom posiela sa k MySQL serveru. Ale nemusíte PHP, aby sa komunikovať so serverom MySQL. 

DAVID J. Malan: Presne tak. Takže žiadne premenné sa znaky dolára by mala byť v tomto kontexte. To môže len robiť všetko z matematiky v databáze samotné. 

ROB BOWDEN: OK. Takže ten budúci. Je to ďalší? Jo. Takže s tým, čo SQL dotazu by banka načítanie čísla účtov svojich Najbohatší zákazníci, ktoré sa zostatky väčšie ako 1000? Tak ktorý z týchto štyroch hlavných typov budeme chcieť tú? Vyberte. Takže chceme vybrať. Čo chceme vybrať? Čo stĺpec chceme vybrať? Budeme sa konkrétne chcete vyberte číslo. Ale ak ste povedal, hviezda, sme Tiež pripustil, že. 

Takže zvoľte číslo z akého stola? Účty. A potom stav chceme? Kde zostatok väčší ako 1000. Sme tiež prijala väčšie alebo rovné. Posledná. S tým, čo SQL dotazu by banka zavrieť, tj odstrániť každý účet, ktorý má bilanciu 0 dolárov? Tak ktorý z tých štyroch sme chcieť používať? Odstrániť. Takže syntaxe, že? Odstrániť z akého stola? Účty. A potom sa podmienka, ktorá chceme odstrániť - kde zostatok sa rovná nule. Takže odstrániť všetky riadky z účtov vtedy, je nulová. Otázky týkajúce sa niektorého z nich? Chcete fronty? 

DAVID J. Malan: sprievodca fronty. Takže v tomto jednom, vám dal nám trochu zoznámiť štruktúra, ktorá sme skúmali A bit v triede vedľa of štruktúr, ktorý bol údaje Štruktúra príbuzný v duchu. Rozdiel však s fronte že sme museli nejako spomenúť, kto bol v prednej časti fronty, vo veľkých časť tak, aby sme mohli urobiť viac efektívne využitie pamäte, aspoň ak sme pomocou poľa. 

Vzhľadom k tomu, odvolanie, ak máme pole, ak Napríklad, to je predná časť front, keď som si do fronty tu, a potom niekto dostane v súlade za mnou, za mnou, za mnou, a jeden človek vystúpi z radu, si mohli, ako sme videli niektoré z našich človeka dobrovoľníci v triede, majú všetci posunúť týmto spôsobom. Ale všeobecne, keď všetci robiť niečo, čo nie je najlepšie využitie času v programe, pretože to znamená, že vaše algoritmus beží v tom, čo Asymptotická doba chodu? Je to lineárne. 

A mám pocit, že je trochu hlúpe. Ak je ďalší človek v rade je ďalší človek, ktorý má ísť do obchod, nemajú všetci majú sa pohybujú spoločne. Len nech ten človek sa trhal až príde čas, napríklad. Takže môžeme si trochu času ušetriť tam. A tak k tomu, že aj keď to znamená, že že hlava fronty alebo predné fronty sa chystá postupne pohybovať hlbšie a hlbšie do poľa a prípadne by mohli v skutočnosti sa zalomia okolo, ak sme pomocou pole pre uloženie ľudí v tejto fronte. Takže môžete takmer myslieť pole ako kruhová údaje štruktúra v tomto zmysle. 

Takže si nejako musieť sledovať veľkosť, alebo naozaj koniec to a potom, kde je počiatok toho je. Takže navrhujeme, že deklarujete jedna taká fronta, volanie to q, len jedno písmeno. Potom navrhujeme, aby predné byť inicializovaný na nulu, a to, že veľkosť byť inicializovaný na nulu. 

Takže teraz, nič vnútri tejto fronty. A žiadame vás, aby ste dokončiť vykonávanie Zaradí nižšie takým spôsobom, že funkcia pridá n na Koniec q a potom vráti hodnotu true. Ale ak q je plná, alebo negatívne, Funkcia by mala radšej vrátiť false. A ti dal nám pár predpokladov. Ale to nie je naozaj funkčne relevantné, len to bool existuje, pretože, technicky, bool nie je existujú v C, ak obsahujú isté hlavičkový súbor. Takže to bola len sa tam, že boli nie je to len trik Otázka také veci. 

Tak enqueue, sme navrhli vo vzorke riešenie, realizovať nasledujúcim spôsobom. Raz sme najprv skontrolujte jednoduchosť, na nízko visiace ovocie. Ak je fronta plná alebo číslo, ktoré sa snažíte vložiť je menej ako nula, ktoré sme si povedali v Špecifikácie problému by nemalo byť dovolené, pretože chceme len non-záporné hodnoty, potom by ste mali len vrátiť okamžite false. Takže niektoré pomerne jednoduché Kontrola chýb. Ak však budete chcieť pridať, že skutočná číslo, čo musel urobiť trochu na mysli. A to je miesto, kde je to trochu nepríjemné psychicky, pretože budete musieť prísť na to, ako zaobchádzať s wraparound. 

Ale zárodok myšlienky tu, že je na záujem pre nás je, že ovinovacie často znamená, modulárny aritmetika a mod operátor, percento strane, kde môžete ísť z väčšej hodnoty späť na nulu, a potom jeden a dva a tri a potom späť okolo nuly, jedna a dve a tri a tak ďalej znova a znova. Takže spôsob, ako navrhujeme robiť to je že my chceme, aby index do Pole s názvom čísla, kde naše celé čísla klamať. Ale tam dostať, najprv chcem urobiť bez ohľadu na veľkosť frontu, ale je pridajte sa, že bez ohľadu na Predná časť zoznamu je. A efekt, ktorý je nám dať na pravá pozície vo fronte a Predpokladajte, že prvá osoba v súlade je na začiatku, ktorému ona absolútne mohlo byť, ak by sme bol tiež posun každého. Ale my sme len vytvoriť prácu pre seba, keby sme sa že konkrétna cesta. 

Takže môžeme udržať relatívne jednoduché. Nechceme mať na pamäti, že sme len pridal int do fronty. A potom sme sa len vrátiť true. Medzitým, v dequeue, sme sa opýtali môžete vykonať nasledujúce kroky. Vykonať to takým spôsobom, že dequeues, že sa odstraňuje a vráti, int na prednej strane frontu. Ak chcete odstrániť int, postačí na to zabudnúť. Nemusíte prepísať svojím dielom. Takže je to stále vlastne tam. Rovnako ako dát na pevnom disku, sme jednoducho ignorovať skutočnosť, že je to teraz. A ak q je prázdna, mali by sme namiesto toho vráti negatívny 1. Tak to cíti ľubovoľný. Prečo návrat Negatívny 1 miesto falošný? Jo. 

DIVÁKOV: Q je ukladanie kladné hodnoty. Vzhľadom k tomu, uložiť len kladné hodnoty v q, negatívne je chyba. 

DAVID J. Malan: OK, to je pravda. Takže pretože sme len ukladanie pozitívne hodnoty alebo nula, potom je to v poriadku, aby vráti zápornú hodnotu ako strážca hodnota, špeciálny symbol. Ale vy ste prepisovanie histórie tam, pretože dôvod, prečo sme len vracia non-záporné hodnoty je preto, že chceme, aby mať hodnotu sentinel. Takže konkrétne, prečo nie len return false v prípade chyby? Jo. 

DIVÁKOV: si zlyhal vráti celočíselnú hodnotu. 

DAVID J. Malan: Presne tak. A to je miesto, kde C dostane docela obmedzujúce. Ak hovoríte, že idete vrátiť int, máte vrátiť int. Nemôžete dostať fantázie a začať vracať bool alebo float alebo string alebo niečo také. Teraz, medzitým, JavaScript a PHP, a niektoré iné jazyky môžu, v skutočnosti, ste sa vrátil iný typy hodnôt. A to môže v skutočnosti byť užitočné, ak môžete vrátiť pozitívny INT, nuly, negatívne ints, alebo false alebo null ešte znamenať chybu. Ale my nemáme, že Všestrannosť v C. 

Takže s dequeue, čo sme navrhnúť, aby urobiť, je - 

ROB BOWDEN: Môžete sa vrátiť false. Je to len, že falošná je hash definovať false na nulu. Takže ak ste sa vrátiť false, budete vracať nulu. A nula je platný vec v našej fronte, vzhľadom k tomu, negatívne 1 ak nie je false stalo negatívny 1. Ale nemali by ste ani potrebujú vedieť, že. 

DAVID J. Malan: To je prečo som to nepovedal. 

ROB BOWDEN: Ale to nie je pravda že sa nemôžete vrátiť false. 

DAVID J. Malan: Iste. Takže dequeue, všimnite si, prijímame stratu ako svoj argument. A to preto, že nie sme okolo nič palcov Chceme len odstrániť prvok na prednej strane frontu. Takže, ako môžeme ísť asi robí? No, za prvé, poďme na to Rýchla kontrola zdravý rozum. Ak je veľkosť frontu je 0, je tu žiadna práce je potrebné urobiť. Návrat negatívny 1. Hotovo. Tak to je pár riadkov o mojom programe. Takže len štyri riadky zostanú. 

Tak tu som sa rozhodol decrement veľkosti. A účinne znižujúce veľkosť Znamená to, že som zabudol niečo, čo je tam. Ale ja som tiež aktualizovať, ak predné čísla sú. Takže na to, že musím urobiť dve veci. Najprv musím mať na pamäti, aké číslo je na prednej strane frontu, pretože musím vrátiť tú vec. Takže nechcem, aby náhodou zabudol o tom a potom ho prepísať. Idem si spomenúť na int. 

A teraz, chcem aktualizovať q.front byť q.front +1. Takže či to bol prvá osoba v linka, teraz chcem urobiť, plus 1 na poukazujú na ďalšie osoby v súlade. Ale musím zvládnuť, že wraparound. A ak kapacita je globálna konštanta, že to bude mi dovoľte, aby som sa uistil, ako som sa poukázať na poslednú osobou v linka, operácia modulo prinesie ma späť na nulu predné fronty. A to spracováva wraparound tu. A potom som sa pristúpiť k návratu n 

Teraz, presnejšie povedané, ja nie musí vyhlásiť n Nemusel som sa chytiť ju a uložte ho dočasne, pretože hodnota je ešte tam. Takže som mohol len urobiť správnu aritmetické pre návrat bývalého šéfa fronty. Ale ja jednoducho cítil, že to bolo viac zrejmé, skutočne chytiť int, dať v roku n, a potom sa vrátiť, že z dôvodov prehľadnosti, ale nie je nevyhnutne nutné. Psst. Sú to všetko vysloviteľné v mojej hlave. 

ROB BOWDEN: Takže prvá otázka je binárny strom problém. Takže prvá otázka je, že sme vzhľadom tieto čísla. A my chceme, aby nejako vložiť do Tieto uzly tak, že je platí binárny vyhľadávací strom. Takže jedna vec na zapamätanie binárne vyhľadávacie stromy, je, že to nie je len to, čo na ľavej strane je menšie, a to na právo je väčšie. Je potrebné, aby sa stať, že celý strom vľavo je menšia, a celý strom na pravej strane je väčšia. 

Takže keď som dal 34 tu hore, a potom Dal som 20 tu, tak to platí, aby ďaleko, pretože 34 až tu. 20 bude na ľavej strane. Tak to je menej. Ale nemôžem potom dal 59 tu, pretože 59, aj keď je na pravej strane 20, je to stále na ľavej strane 34. Tak s týmto obmedzením na mysli, Najjednoduchší spôsob, ako zrejme riešenie tohto Problém je len trochu z týchto čísel - tak 20, 34, 36, 52, 59, 106. A potom vložíte zľava doprava. 

Takže 20 ide tu. 34 ide tu. 36 ide tu. 52, 59, 106. A tiež by prišiel na to, s niektoré pripojením a realizáciu, oh, počkaj, ja nemám dosť čísel vyplniť to vo viac ako tu. Takže musím reshift, čo môj trasa poznámka bude. Ale všimnite si, že v posledných troch, ak budete čítať zľava doprava, je v zvyšuje objednávky. 

Takže teraz, chceme deklarovať, čo struct bude pre Uzly tohto stromu. Takže to, čo potrebujeme v binárnom stromu? Takže máme hodnotu typu int, takže niektoré int hodnota. Ja neviem, čo sme nazvali sa v roztoku - int n Potrebujeme ukazovateľ na ľavej strane dieťaťa a ukazovateľ na pravej dieťa. Takže to bude vyzerať takto. A to bude v skutočnosti vyzerať pred keď sa dvakrát viazaná Zoznam vecí, tak Oznámenie - Budem musieť prechádzať všetky Cesta späť dole do problému 11. 

Takže všimnete, že vyzerá rovnako ako to, okrem nás len tak zavolať týchto rôzne mená. Stále máme celé číslo hodnota a dva ukazovatele. Je to len, že miesto liečenia ukazovatele ako smerujúca k ďalšej veci a predchádzajúca vec, my liečbe ukazovatele poukázať na ľavej dieťa a právo dieťa. OK. Tak to je naša struct uzol. A teraz, jediná funkcia je potrebné realizovať, je to traverza, ktorá Chceme ísť cez strom, tlač z hodnôt stromu v poradí. 

Takže hľadáte tu, by sme chceli vytlačiť z 20, 34, 36, 52, 59, a 106. Ako sme to dosiahli? Takže je to dosť podobné. Ak ste videli v minulom skúšku problém že ste chceli vytlačiť Celý strom s čiarkami medzi všetko, to bolo vlastne ešte jednoduchšie, než to. Takže tu je riešenie. To bolo výrazne jednoduchšie ak ste to urobil rekurzívne. Neviem, či niekto pokúsil na to iteratívne. 

Ale najprv, máme základný prípad. Čo v prípade, že koreň je null? Potom sme len tak vrátiť. Nechceme tlačiť čokoľvek. Inak budeme prechádzať rekurzívne dole. Vytlačiť celý ľavý podstrom. Takže tlačiť všetko menej ako mojej súčasnej hodnoty. A potom budem tlačiť sám. A potom budem recurse sa my Celá pravá podstrom, takže všetko väčšie ako moje hodnoty. A to sa bude tlačiť sa všetko v poriadku. Otázky o tom, ako to v skutočnosti dosiahne, že? 

DIVÁKOV: Mám otázku na [nepočuteľné]. 

ROB BOWDEN: Takže jeden spôsob, ako sa blíži každá rekurzívne problém je len, že o to, ako by si mal myslieť o všetkých prípadoch rohu. Takže za to, že chceme, aby vytlačiť celý tento strom. Takže všetko, čo sa zameriame na Je to zvláštne uzol - 36. V rekurzívne volanie, predstierame tie jednoducho fungovať. Tak tu to rekurzívne volanie traverza, my bez premýšľania o tom, len posuvné ľavej tri, predstavte si, že už sa vytlačí 20 a 34 pre nás. A potom, keď sme sa nakoniec rekurzívne volajte posuv na pravdu, že bude správne tlačiť 52, 59, a 106 pre nás. 

Takže za predpokladu, že to môže tlačiť 20, 34, a ostatné je možné tlačiť 52, 59, 108, všetci musíme byť schopní urobiť, je vytlačiť sami v stredu, ktorá. Takže vytlačiť všetko, čo pred nami. Vytlačiť sami, takže aktuálny uzol pre tlač 36, pravidelné printf, a potom tlačiť všetko, čo po nás. 

DAVID J. Malan: To je miesto, kde rekurzia dostane naozaj krásne. Je to úžasný skok viery, kde budete robiť najmenší kúsok práce. A potom sa nechať niekoho iný sa postará o zvyšok. A že niekto iný Je iróniou osudu, môžete. Takže pre závažné body za snaživosť, ak stlačte navigačné tlačidlo nahor na otázky - 

ROB BOWDEN: Na otázky? 

DAVID J. Malan: A trochu dole na čísla, neviete niekto, kde Tieto čísla pochádzajú z? 

ROB BOWDEN: Mám doslova tušenie. 

DAVID J. Malan: Objavujú celé kvíz. 

DIVÁKOV: Sú rovnaké čísla? 

DAVID J. Malan: Tieto čísla. Trochu veľkonočné vajíčko. Takže pre tých z vás, sledovať on-line na domov, ak nám môžete povedať, prostredníctvom e-mailu na heads@CS50.net čo význam na tieto opakované šesť čísel sú celé Quiz 1, budeme sprchovať vás s úžasnou pozornosť na finále prednáška a stres loptičku. Pekné, jemné. 

ROB Bowden: Nejaké posledné otázky o niečo na ten kvíz?