DAVID J. Malan: Dobře. Takže vítejte na vůbec první CS50 posmrtné na kvíz. Mysleli jsme, že slavnostně tato tradice v letošním roce. A to bude příležitost projít řešení kvízu. A budeme zrychlit nebo zpomalit na základě na zájmu těch, kteří zde. 

Takže jste asi tady, protože jste zajímalo, jak byste mohli mít nebo měla zodpovědět některé z těchto problémů. Tak proč bychom se podívat Zpočátku této sekci? Tak jak se řetězce. To vám dal tři různé verze programu, který byl nakonec chtěl získat řetězec od uživatele. Zda nebo ne to dělalo to bylo ponecháno na vás zjistit. 

A ptali jsme se v první otázce, 0, Předpokládám, že verze 1 je sestavil a popraven. Proč může program segfault? Na první pohled, nějaké návrhy , proč? Jo. 

DIVÁKŮ: Tak Vzpomínám si na to v Předchozí příklad při pohledu na char * s, a viděl scan S a vidět, protože je to ukazatel, jak to ovlivnilo to, co jste skenovat? Je to to nebo adresa s? 

DAVID J. Malan: OK. Dobrá. Takže v konečném důsledku, zdroj jakéhokoliv problému se pravděpodobně bude snižovat této proměnné s. A to je opravdu variabilní. Datový typ této proměnné je char *, což znamená, že to bude obsahovat adresu charakteru. A v tom spočívá pochopení. Bude obsahovat adresu znak nebo, obecněji, adresa prvního znaku v celý blok znaků. 

Ale úlovek je, že skenování s, účel život, je dána adresu a vzhledem Kód formátu, jako je% s, čtení řetězec do kusu Paměť na této adrese. Ale protože tam není rovnítko před že středník na první řádek kódu, protože to není ve skutečnosti alokovat paměť s malloc, protože ne ve skutečnosti alokovat pole nějaké velikosti, všechny děláte čte uživatele vstup z klávesnice do některé kompletní hodnota odpadky, které je s výchozím. Takže šance jsou vy budete segfault pokud že adresa není jen tak nestane být hodnota, kterou můžete, ve skutečnosti, napište. Tak špatné nerozdělit paměť tam. 

Takže v otázce č. 1, jsme se zeptali, Předpokládám, že verze 2 je sestavil a popraven. Proč může tento program segfault? Tak tohle je menší buggy. A je to opravdu jen jeden zřejmý způsob, kde můžete spustit segfault zde. A to je tematické. Kdykoliv jsme pomocí c v paměti, co se můžete udělat pro to, přimět segfault ve verzi 2? 

DIVÁKŮ: Pokud používáte tento vstup v řetězec, který je delší než 49 znaky. 

DAVID J. Malan: Přesně tak. Kdykoli vidíte něco pevné délky , pokud jde o pole, vaše radar by měl jít pryč, že by to mohlo být problematické, pokud si nejste kontrola hranice pole. A že je tu problém. Pořád pomocí scanf. Pořád pomocí% s, což znamená, že se snaží číst řetězec od uživatele. To bude číst do s, což v tomto bodě, je účinně adresa bloku paměti nebo je to ekvivalent. Je to název pole znaků v paměti. 

Ale přesně to, pokud budete číst řetězec to je delší než 49 znaků, 49 protože budete potřebovat prostor pro lomítkem 0, budete přetečení že vyrovnávací paměti. A můžete mít štěstí a být schopen napsat znak, 51. 52., 53.. Ale v určitém okamžiku, OS se chystá říct, no. To rozhodně není paměť budete dotýkat. A program bude segfault. 

Takže tam jsou heuristiky by měl být jakýkoli Čas máte pevnou délku, máte aby se ujistil, že jste kontrolu délky na co to je, že se snažíte číst do něj. 

DIVÁKŮ: Takže řešení, které byste mohli měli prohlášení kontrolu skutečně je délka větší nebo menší než? 

DAVID J. Malan: Přesně tak. Stačí mít podmínku , který říká, pokud - nebo spíše nemusíte nutně vědět, předem, kolik znaků uživatel bude psát, protože Máte kuře a vejce. Ne, dokud jste si ji s scanf můžete zjistit, jak dlouho to je. Ale v tomto okamžiku, to je příliš pozdě, proto, že jste již četli ji do některé blok paměti. Tak jako stranou, CS50 knihovna vyhýbá tento problém úplně, odvolání pomocí fgetc. A to přečte jeden znak v době, špičkách spolu s vědomím, že vás nemůže přetečení charakter, pokud budete číst jednu po druhé. 

Háček je s GetString odvolání je že máme neustále re-velikosti že kus paměti, který je jen bolest. Je to hodně řádků Kód k tomu, že. Takže jiný přístup by byl vlastně používat bratrance, takže mluvit, o scanf. K dispozici jsou varianty mnoho z nich funkce, které ve skutečnosti kontrolují Délka kolik znaků můžete číst maximálně. A vy jste mohli určit, nečtou více než 50 znaků. Tak, že by byl jiný přístup, ale méně vstřícný větších vstupů. 

Takže otázka 2 se ptá, předpokládám, že verze 3 je sestaven a proveden. Proč by to program, segfault? Takže tohle je vlastně stejný odpověď, i když to Vypadá trochu obsáhlejší. Budeme používat malloc, které se cítí jako dáváme sami sobě více možností. A pak jsme uvolnění, které paměti na konci. Je to stále jen 50 bajtů paměti. Tak bychom mohli ještě zkusit číst v 51, 52, 1000 bajtů. Bude to segfault pro přesně stejný důvod. 

Ale je tu další důvod, proč taky. Co jiného by mohlo malloc návrat vedle adresa bloku paměti? To by se mohl vrátit null. A protože nejsme kontrola to, že bychom mohli dělat něco hloupý jiného důvodu, což je to, že bychom mohli říkat scanf, přečtěte si vstup uživatele z klávesnice do 0 polohy, AKA null. A taky, bude určitě spustit segfault. Takže pro účely kvíz je, by se přijali jeden z těch, co pádný důvod. Jedním z nich je totožný. Jedním z nich je trochu složitější,. 

A konečně, s ohledem na programu je využití paměti, jak to verze 2 a Verze 3 se liší? Takže, co to stojí, viděli jsme zdánlivě nekonečnou zásobu možné odpovědi na to. A mezi odpověďmi lidí, co jsme byli doufal, že, ale přijali jsme další věci, byla nějaká zmínka o Skutečnost, že verze 2 se používá tzv. stack. Verze 3 je pomocí haldy. A funkčně, to není opravdu dělat vše, co velký rozdíl. Na konci dne, jsme stále jen dostat 50 bajtů paměti. 

Ale to byl jeden z možných odpovědí že jsme se dívali na. Ale uvidíte, jak vám vaše kvízy zpět z TFS, že jsme udělali přijmout jiné diskuse o jejich různorodé použití paměti, jakož. Ale stack a heap by bylo jednoduchá odpověď jít s. Jakékoliv dotazy? Dám vám Rob. 

ROB BOWDEN: Takže problém 4. To je ten, kdy jste museli vyplnit v počtu bajtů z všech Tyto různé typy používané. Takže první věc, kterou vidíme. Předpokládejme, že 32-bitovou architekturu, takhle CS50 spotřebiče. Takže jedna ze základních věcí, o 32-bitové architektury, která nám říká, přesně, jak velký ukazatel se děje být v architektuře. 

Takže hned, víme, že každý ukazatel Typ je 32-bitů nebo 4 bajty. Takže při pohledu na tuto tabulku uzel * je typu ukazatel. To bude 4 bajty. Struct uzel *, to je doslova totožný s uzlu hvězdy. A tak, že to bude 4 bajty. String, takže to nevypadá jako ukazatel ještě, ale typedef, řetězec je jen char *, které je typu ukazatel. Tak, že to bude 4 bajty. 

Takže tyto tři jsou všichni 4 bajty. Nyní, uzel a studentů jsou trochu složitější. Takže při pohledu na uzel a studentem, vidíme, uzel jako celé číslo a ukazatel. A student dva ukazatele uvnitř ní. Tak alespoň pro náš případ, způsob že jsme nakonec výpočet velikosti Tato struktura je jen sečíst vše že je uvnitř struct. 

Takže pro uzel, máme celé číslo, což je 4 bajty. Máme ukazatel, který má 4 bajty. A tak jeden uzel se děje aby se do 8 bajtů. A podobně pro studenta, máme ukazatel, který je 4 bajty a další ukazatel, který je 4 bajty. Takže, co se děje na konec up je 8 bajtů. Uzel a studentské Takže je 8 bajtů. A tito tři jsou všichni 4 bajty. Dotazy na to? Ano. 

DIVÁKŮ: Je to 64-bit architektura, by to dvojnásobek všichni z nich? 

ROB BOWDEN: To ne zdvojnásobit všechny z nich. Tak 64-bitové architektury, je, opět, změny, které zásadní věc, že Ukazatel je nyní 64 bitů. Jo. Takže ukazatel je 8 bajtů. Takže to, že se 4 byty se bude 8 bajtů. Student, který byl dva ukazatele, dobře, teď to bude být 8 bajtů, 8 bajtů. Bude to dělat 16 bajtů. 

Uzel, ale je stále ještě 4 byty. Takže tento ukazatel se děje být 8 bajtů. To je 4 bajty. Takže uzel se děje pouze na 12 bajtů. Jakékoliv další dotazy na tohle? Takže další jeden, jedná se o stavové kódy HTTP. A vy jste měl popsat okolnosti, za nichž je síla se vrátil k vám. jeden problém, který jsem slyšel některé studenty je to, že se snažili, aby Chyby být na straně klienta. Takže když se snažíme, aby žádost na serveru, něco, co jde špatně na naší straně. Ale obecně, tyto kódy jsou vracených serverem. Takže chceme-li zjistit, co se děje špatné nebo přímo na serveru, který způsobí, že tyto věci, které mají být vráceny. Tak proč by mohla a server vrací stavový kód 200? Jakékoliv myšlenky? 

Jo. Takže něco o úspěšném požadavek prošel. A oni jsou schopni se vrátit co jste chtěl. Takže je všechno v pořádku. Co o 302 nalezeno? Jo. 

Diváků: Server hledal za to, co jste požadovali. Ale to nemohl najít. Takže tam je chyba. 

ROB BOWDEN: Takže server byl hledá to, co jste chtěli. Tak právě hledáte tady, 302 nalezeno, to byl schopen ji najít. 

DIVÁKŮ: Omlouvám se. Nalezeno znamená, že oni si to. Promiňte. 

ROB BOWDEN: Tak 302 Found. Server je schopen najít to, co jste chtěli. 

DIVÁKŮ: Ale to není to zobrazení? 

ROB BOWDEN: rozdíl mezi to 302 a 200 je to, že ví, že to, co chcete. Ale není to přesně tam, kde jste se chtěl zeptat. Takže 302 je typický přesměrování. Takže jste si vyžádali stránku. Je to ví, oh, chci ti vrátit tohle. Ale to je na jinou adresu URL. Tak hele, vy vlastně chcete toto. 

DAVID J. Malan: Je to kus, který řekl: že jsme dali vy přesměrování funkce, která používá funkci záhlaví který, podle pořadí, vytisknout umístění, tlustého střeva, a pak URL, na které Chcete-li odmítnout uživatele. I když jste neviděli 302 výslovně se, že je to, co PHP by se mávnutím kouzelného proutku vložte jako záhlaví říká přesně to, co řekl Rob tam - nalezeno. Ale naleznete zde místo. 

ROB BOWDEN: OK. Takže to, co o 403 zakázán? 

DIVÁKŮ: Myslím, že to, že server je v podstatě říká, že klient nemůže získat přístup k domovské stránce. 

ROB BOWDEN: Takže ano. No, typická odpověď jsme byli čeká je něco jako, soubory nejsou náležitě chmodded. To je asi, za jakých okolností jste je viděli. Ale je tu důvod, že klient může být na štíru. Tam je vlastně další stavový kód - 401. Takže se jedná o velmi podobné. 

401 je neoprávněné. A 403 je zakázáno. A tak neoprávněnému vám exkluzivně dostat, pokud nejste přihlášeni Ale přihlášení může znamenat že jste oprávněni. Ale pokud jste již přihlášeni a můžete Stále nemáte oprávnění, pak můžete také získat zakázáno. Takže pokud jste přihlášeni a nemají povolení, zakázáno je také něco, co můžete dostat. 

DAVID J. Malan: A mechanismus , které tyto problémy jsou obvykle řeší na serveru přes to příkaz? Chmod, pokud je to vskutku oprávnění vydá na soubor nebo adresář. 

ROB BOWDEN: A 404 nebyla nalezena. Jo. Takže na rozdíl od 302, kde nebylo přesně kde se ptáte, ale ví, co chcete, to, to prostě musí žádný nápad, co chcete. A vy se nepožaduje něco platný. 418 Jsem konvice a poté 500 interní server. Tak proč můžete dostat, že? 

Takže segfault - Já vlastně nevím, třídění standard pro to. Ale pokud vaše PHP kódu něco špatně v tom, teoreticky, mohla by vlastně segfault, v tom případě, to 500 Interní chyba serveru, něco, co je se váš server je špatně konfigurace. Nebo je to chyba syntaxe v PHP kódu. Nebo se něco špatného děje. 

DAVID J. Malan: My jsme vidět segfault Mezi odpověďmi pár lidí. A technicky, mohlo by se to stalo. Ale, že by PHP, program napsal jiných lidí, ve skutečnosti segfaulted, který pouze tehdy, pokud tito lidé podělal a napsal buggy kód jejich interpret by PHP samo o sobě segfault. Takže i když je 500 jako segfault v duchu, je to téměř vždy Výsledkem je problém konfiguračního souboru s webovým serverem, nebo, jak řekl Rob, syntaktická chyba, jako jste vy neuzavřela cenovou nabídku. Nebo jste ztratili středník někde. 

DIVÁKŮ: Takže pro Shuttle pset, jsem že když jsem to udělal, když jsem kliknul prohlížeč, ale nic přišel, co oni volali bílá stránka. Ale bylo to proto, že z kódu. Myslím, že to bylo JavaScript, jo? 

ROB BOWDEN: Jo. 

DIVÁKŮ: Kéž by chyba ještě přijít? 

ROB BOWDEN: Takže byste se dostali to chyba, protože vše z pohledu webového serveru byl úplně v pořádku. Ale jste požadovali index.html. Požadovali jste shuttle.js a service.js. A to se podařilo úspěšně vrátit vám všem z těch věcí - 200. OK. Je to pouze tehdy, když se váš prohlížeč pokoušel interpretovat kód JavaScript, který je to jako, počkejte, to není platné k chybě JavaScript. Nějaké další otázky? Dobrá. 

DAVID J. Malan: Tak další až se číslo 11. A 11 byl nejděsivější pro mnoho lidí. Takže nejdůležitější věc na vědomí zde se, že je to skutečně o dvojnásobně spojový seznam. Ale to nebylo stejné jako minulý rok dvojnásobně spojový seznam problém, který vám nedal na námitku, že seznam by mohl ve skutečnosti být netříděný. 

A tak skutečnost, že seznam byl netříděného a skutečnost, že toto slovo bylo zdůrazněno, že měl sdělit , že je to ve skutečnosti zjednodušení z toho, co by jinak bylo náročnější problém a delší. Takže Běžnou chybou zde bylo dali Řešení loňský na jednom pager a pak už jen slepě kopírovat, který se jako odpověď, která je správná odpovědět na jinou otázku podobně v duchu. Ale jemnosti zde byly následující. 

Takže jedna, jsme uzel prohlásil a jsou definovány v obvyklým způsobem zde. Pak jsme definovaný seznam je globální ukazatel inicializován na hodnotu null. Pak se zdá, že je dvě funkce máme prototypy pro tu, vložka a odstranit. A pak tu máme nějaký ukázkový kód zde dělat spoustu vložení. A pak žádáme vás, abyste dokončit provedení vložky pod takovým tak, že se vloží do n seznamu v konstantním čase, rovněž zdůraznil, i když již existuje. 

Takže krása je možné vložit v konstantním čase, je, že to znamená, že budete muset vložit nový uzel, kde? Do přední části. Tak to eliminuje, naštěstí, alespoň jeden z případů, které dříve vyžadovaly ještě více řádků kódu, jako to udělal v loňském roce, a to i ve třídě, když jsme mluvil skrze tyhle věci s lidmi a s některými slovní pseudo kód. Takže řešení tady, pojďme přeskočit k tomu stačí mít vizuální kontakt obrazovce. 

Všimněte si, že děláme následující. A také si všimnout další zjednodušení bylo, že i když je to již existuje, tak to znamená, že i v případě, číslo již existuje, můžete jen slepě vložit další kopie toho. A to také mělo být zjednodušení, takže byste mohli zaměřit se na, opravdu, někteří více intelektuálně zajímavá část a není jen nějaký další kontrolu chyb s ohledem na omezený čas. 

Takže v tomto roztoku vzorku se přidělí ukazatel na levé straně stranu zde k uzlu. Nyní si uvědomit, že ukazatel, as Rob řekl, je pouze 32 bitů. A to není ve skutečnosti obsahovat adresa, dokud přiřadit mu adresu. A my, že na pravé straně strana přes malloc. Jako dobrý občan, můžeme zkontrolovat, že malloc není ve skutečnosti, null, takže nemáme náhodou vytvořit segfault zde. A kdykoliv použít malloc v životě, vám by měla být kontrola na null, jinak Máte jemné chybu. 

Pak jsme se inicializovat, že null by přiřazení n a předchozí a další. A v tomto případě tady, jsem inicializaci předchozí na hodnotu null, protože tento nový uzel bude nový začátku mého seznamu. Takže tam to bude nic před ním. A já chci, aby v podstatě připojit Stávající seznam do nového uzlu nastavení vedle rovná seznam sám. Ale já jsem to udělal jen zatím. Takže v případě, že seznam sám o sobě již existoval, a tam byl alespoň jeden uzel již na místě, pokud se jedná o seznam tady a já vložit nový uzel tady, jsem je třeba, aby se ujistil, že můj bývalý uzel body zpět do mého nového uzlu, , protože to je, opět, dvojnásobně spojový seznam. 

Takže děláme kontrolu zdravý rozum. Pokud seznam není null, pokud je již jeden nebo více uzlů, pak tam Dodávám, že zadní odkaz, abych tak řekl. A pak to poslední, co potřebujeme udělat, je aktualizovat globální seznam proměnných sám bodu do tohoto nového uzlu. Jo. 

DIVÁKŮ: Ve směru šipky [Neslyšitelný] se rovná null, dělá, že vypořádat se s seznamu, protože Seznam je null? 

DAVID J. Malan: Ne. To je prostě to, že jsem aktivně pozor, v tom, že pokud je to můj Původní seznam se možná některé další uzly tady a já jsem vkládání my nový uzel sem, tam se děje být nic sem. A chci zachytit ten nápad nastavením dříve null na nový uzel. A pravděpodobně, pokud můj kód je správný a neexistuje žádný jiný způsob, jak vložit jiné, než je tato funkce uzly, pravděpodobně, i když seznam již jeden nebo více uzlů v něm, pravděpodobně Seznam, první uzel, by měl předchozí ukazatel null sám. 

DIVÁKŮ: A jen následné-up. Důvod, proč dát ukazatel next rovná Seznam je děláte ukazatel Před seznamu v tom, že to ukazuje na další, myslím, že - Já ne - jen seznam? 

DAVID J. Malan: Přesně tak. A tak se pojďme skutečně zvážit dvě případů zde opravdu, i když Aby budeme uvažovat o nich není úplně stejný jako kód. Ale na vysoké úrovni, v případě, že představuje seznam, a to je 32-bit ukazatel, nejjednodušší scénář že je to null ve výchozím nastavení. A předpokládám Chci vložit Číslo 50 bylo první číslo. Takže budu pokračovat a přidělit uzel, který bude obsahovat tři pole - n, předchozí a další. 

Chystám se dát číslo 50 tady, protože to bude n. To bude další. A to bude předchozí. A tak co mám dělat v tomto případě? No, já jsem právě udělal linku 1 zde. Ukazatel n dostane n. Já pak řekl, předchozí by měl dostat null. Takže to bude mít hodnotu null. Pak budu říkat další se chystá do seznamu dostat. 

A to prostě funguje dobře. To je null. A tak říkám, nový uzel je vedle pole by měl dostat, co to je. Tak, že klade další null tam. A pak poslední věc, I to je zkontrolovat zde. Pokud seznam není rovna NULL, ale je roven null, takže jsme vynechat dohromady. A tak vše, co dělat dál, je seznam dostane ukazatel, který má za následek obrazově obrázek takhle. Takže to je jeden scénář. 

A ten, který jste se ptal konkrétně je situace, jako je tato, kde již máme seznam jeden-uzlu. A když jsem se vrátit do původní Problém prohlášení, další sejdeme vložit řekněme je 34, jen pro saké diskuse. Takže budu jen pohodlně kreslit, které sem. Právě jsem malloced. Předpokládejme, že jsem kontrolu na null. 

Teď jdu k inicializaci n být 34. A to bude n. To bude další. A to bude předchozí. Pojďme se ujistěte se, že jsem to neudělal si to pozpátku. Předchozí je na prvním místě v definici. Dovolte mi, abych tento problém odstranit. Je to předchozí. To je vedle. I přesto, že jsou shodné, pojďme si to konzistentní. 

Předchozí. To je vedle. Tak jsem právě malloced mé vědomí, kontrolovat NULL, přiřadí 34 do uzlu. Předchozí dostane null. Tak, že mi to dává. Další dostane seznam. Takže seznam je to. Takže je to teď stejné jako čerpání této šipka, takže se upozornit na jeden ve stejném. A pak jsem kontrolu, zda seznam není rovno null. A není to tentokrát. Pak jdu udělat seznam předchozí dostane ukazatel. 

Takže seznam Předchozí dostane PTR. Tak to má za následek uvedení grafický šipka zde. A to je už trochu vlnité, linky. A pak, konečně, jsem aktualizovat seznam poukázat na ukazatel. Takže teď to ukazuje na toho chlapa. A teď, pojďme dělat rychlé Kontrola zdravý rozum. 

Zde je seznam, který je globální proměnná. První uzel je, ve skutečnosti, 34, protože Já jsem po tu šipku. A to je správné, protože chci, aby vložit na začátku seznamu všechny nové uzly. Jeho další pole mě vede k této chlapa. Pokud jsem dál, jsem narazila další je null. Takže to nic víc seznamu. Pokud jsem narazila předchozí, jsem si tam, kde jsem čekat. 

Takže stále existuje několik rad, samozřejmě, manipulovat. Ale skutečnost, že vám bylo řečeno, k tomu to v konstantním čase vás znamená pouze to, mají konečný počet věcí máte dovoleno dělat. A co je to za číslo? To by mohl být jeden krok. Mohlo by to být dva. Mohlo by to být 1000 kroků. Ale to je konečný, což znamená, že nemůžete mají nějaký druh zacyklení děje tady, no rekurze, žádné smyčky. Je to prostě musím být tvrdý-kódované linky kódu, jak máme v tomto vzorku. 

Takže další problém 12 nás požádala, abychom dokončení implementace vyřazení pod takovým způsobem, že se odstraňuje n ze seznamu v lineárním čase. Takže budete muset trochu více manévrovací prostor nyní. Můžete předpokládat, že n, je-li přítomna v seznamu, bude přítomen ne více než jednou. A to také má být test založený na zjednodušující předpoklad, aby že pokud najdete číslo 50 někde v seznamu, nemáte také mají na starosti i nadále iteraci, hledá všechny možné kopie z 50, což by právě přecházejí do nějaké drobné detaily, v omezeném čase. 

Takže s remove, tenhle byl určitě náročnější a více Kód psát. Ale na první pohled, upřímně řečeno, to by mohlo vypadat ohromující a jako něco, neexistuje žádný způsob, jak byste mohli mít přijít s na kvíz. Ale pokud se zaměříme na jednotlivé kroky, Doufejme, že to najednou Připadá vám, že každý z těchto jednotlivých kroky je zřejmý smysl ve zpětném pohledu. Takže pojďme se podívat. 

Tak za prvé, my inicializovat ukazatel být seznam sám. Protože chci lineární čas, to znamená Budu mít nějaké smyčky. A obyčejný způsob, jak iterovat přes uzly ve struktuře seznamu nebo jakékoliv struktury iterativně je, aby se ukazatel na přední části dat struktura a pak jen spustit aktualizaci to a jít svou cestou prostřednictvím datové struktury. Takže budu dělat přesně to. 

Zatímco ukazatel, můj dočasné proměnné, není rovno null, pojďme jděte do toho a zkontrolovat. Měl jsem štěstí? Je n pole v uzlu jsem v současné době při pohledu na rovný číslo jsem hledal? A pokud ano, pojďme něco udělat. Teď, všimněte si to, pokud podmínka obklopuje celý Následující řádky kódu. To je jediné, co mě zajímá - najít číslo v otázce. Takže neexistuje žádný jiný, který zjednodušuje věci koncepčně trochu. 

Ale teď jsem si uvědomil, a můžete mít jen si to uvědomil po myšlení je to přes trochu, je tu vlastně dvě případů zde. Jedním z nich je, pokud je uzel v začátku seznamu, který je trochu nepříjemné, protože to je zvláštní případ, protože se budete muset vypořádat s tou věcí, která je pouze anomálie. Všude jinde v seznamu, je to totéž. K dispozici je předchozí uzel a další uzel, uzel předchozí, další uzel. Ale ten chlap je trochu zvláštní v případě, že je na začátku. 

Takže v případě, že ukazatel se rovná seznam sama o sobě, takže když jsem na začátku roku seznam a našel jsem n, musím udělat pár věcí. Za prvé, musím do seznamu změnit poukazují na další pole, 50 let. Takže předpokládám, že se snažím odebrat 34. Takže ten chlap musí jít pryč jen chvíli. 

Takže jsem chtěl říct, seznam dostane ukazatel další. No, to je ukazatel. Dále se ukazuje sem. Tak to se mění na tuto šipku vpravo nyní poukázat na toho chlapa tady. Nyní, pamatujte, že máme dočasné proměnné. Takže jsme se osiřelé všechny uzly, protože jsem také toho chlapa v mém realizace remove. Takže teď, pokud seznam sám o sobě není null, Musím opravit něco. 

Musím se ujistit, že tato šipka, který je již ukazuje 50 až 34, to má jít pryč, protože když se snažím zbavit z 34, 50 měl lepší ponechat v platnosti veškerá druh zpět odkaz na to, jak arrow navrhl. Tak jsem to udělal čáru. Tak jsem udělal. Tento případ je vlastně docela snadné. Odsekne hlavu seznamu je poměrně jednoduché. 

Bohužel, tam je to nepříjemné jiný blok. Takže teď, musím vzít v úvahu případ tam, kde je něco uprostřed. Ale není to příliš hrozné, s výjimkou pro syntaxi jako je tato. Takže pokud nejsem na začátku roku Seznam, jsem někde uprostřed. A tento řádek je zde říká, začátek na co uzlu jste na. Přejít na další pole z předchozího uzlu a ukazují, že na ukazatel. 

Pojďme to obrazně. To bylo stále složitější. Takže pokud mám předchozí pole zde - pojďme na to - další pole zde. Chystám se zjednodušit své ukazatele, spíše než kreslit spoustu věci tam a zpět brázdí navzájem. A teď, řekněme, že je to 1, 2, 3 kvůli diskusi, a to i i když to není vyrovnaná se problém se jedná. 

Takže tady je moje spojový seznam. Snažím se odstranit dva v tomto zejména verze příběhu. Takže jsem aktualizováno ukazatel se ukázal na toho chlapa. Tak tohle je PTR. On ukázal zde. Toto je seznam, který existuje na celém světě jako předtím. A on ukázal tu bez ohledu na to, co. A teď se snažím odstranit dva. 

Takže pokud je ukazatel ukazuje zde, jsem bude následovat, zdá se, předchozí ukazatel, který mi dává na 1. Já jsem pak chtěl říct, že příští pole, což mě přivádí na to box tady, bude rovná ukazatel další. Takže pokud tento ukazatel, je to hned vedle. To znamená, že to musí šipka poukázat na toho chlapa. 

Tak co, že řádek kódu má jen udělat, je trochu z toho. A teď to vypadá, jako krok správným směrem. V podstatě Chceme odstřihnout 2 out do středu 1 a 3. Takže je logické, že chceme trasy tohoto ukazatele kolem něj. Takže to další řádek je kontrola, zda ukazatel další není null, je tu opravdu někdo na pravé straně 2, to znamená, že musíme také udělat trochu odstřihnout zde. 

Takže teď je třeba dodržovat tento ukazatel a aktualizovat předchozí ukazatel na ten chlap udělat trochu obejít zde bod zde. A teď, vizuálně je to pěkné. Je to trochu chaotický v tom, že tam je nikdo ukázal na 2 už. 2 ukazuje doleva. A 2 se ukazuje na pravé straně. Ale on může dělat, co chce, protože je to asi, aby se osvobodil. A nezáleží na tom, co tyto hodnoty jsou už. 

Co je důležité je, že zbývající kluci jsou směrování výše a pod ním teď. A vskutku, to je to, co dělat dál. Jsme bez ukazatel, což znamená, řekneme operační systém, jste vítáni kultivovat to. A pak se konečně vrátíme. Else implicitně, pokud se se ještě nevrátil, musíme hledat dál. Takže ukazatel se rovná ukazatel vedle právě znamená pohybovat toho chlapa tady. Přesunout toho chlapa tady. Přesunout toho chlapa tady, jestli ve skutečnosti, jsme nenašli číslo hledáme ještě. 

Takže upřímně řečeno, vypadá to naprosto ohromující, myslím, že na první pohled pohled, a to zejména pokud jste se snažil s tím během testu pak zjistit, něco takového. A ty pat si na záda. No, neexistuje způsob, jak bych mohl mít přijít s tím na kvíz. Ale řekl bych, můžete, pokud porušíte že se do nich jednotlivé případech a pouze pěšky přes něj opatrně, i když, pravda, pod stresující situace. 

Naštěstí, vyrobený obrázek vše šťastnější. Ty by mohly čerpat na tuto libovolný počet způsobů. Nemusíte dělat křížem krážem věc zde. Dalo by se to udělat s rovnou linky, jako je tento. Ale podstata tohoto problému, v Obecně platí, že bylo si uvědomit, že obrázek na konci by mělo vypadat trochu něco takového, protože konstantní čas znamenal, že budete mít rušení a rušení a rušení nové uzly na začátku seznamu. Jakékoliv dotazy? Asi nejnáročnější jistě kódování otázky. 

DIVÁKŮ: Takže je seznam podobný hlavu v předchozích příkladech. 

DAVID J. Malan: Přesně tak, přesně tak. Jen jiný název pro globální proměnná. Na celém světě, co? 

ROB BOWDEN: OK. Takže to je ten, kde se musel napsat odstavec. Někteří lidé psali eseje na tuto otázku. Ale stačí použít těchto šest termíny popsat, co se stane, když zkuste kontaktovat facebook.com. Tak jsem si jen promluvit prostřednictvím procesu s využitím všech těchto podmínek. Takže v našem prohlížeči, napíšeme facebook.com a stiskněte klávesu Enter. Takže náš prohlížeč se děje na výstavbu HTTP požadovat, že to bude posílat prostřednictvím nějakého procesu na Facebook pro Facebook reagovat na nás s HTML své stránky. 

Takže to, co je proces který požadavek HTTP skutečně dostane na Facebook? Takže nejprve musíme překládat Facebook.com. Tak právě dal název Facebook.com, kde vlastně dělá HTTP požadavku je třeba jít? Takže musíme přeložit Facebook.com na IP adresu, která jednoznačně určuje, co stroj vlastně chcete poslat tuto žádost. Váš notebook má IP adresu. Cokoliv, připojení k internetu má IP adresu. 

Takže DNS, Domain Name System, která je co se děje zvládnout překlad od facebook.com na IP adresu, která vlastně chcete kontaktovat. Tak jsme se kontaktovat DNS servery a řekněme, co je facebook.com? To říká, oh, to je IP adresa 190,212 něco, něco, něco. Dobrá. Teď vím, co stroj Chci kontaktovat. 

Takže pak pošlete svůj požadavek HTTP se k tomuto zařízení. Tak jak to dostat do toho stroje? No, žádost jde od na routeru odrážení. Vzpomeňte si na příklad ve třídě, kde jsme vlastně viděli cestu, která pakety se, když jsme se snažili komunikovat. Viděli jsme, že skok přes Atlantik Ocean na jednom místě, nebo cokoliv jiného. 

Takže poslední termín portu. Tak to je nyní na vašem počítači. Můžete mít více věcí v současné době komunikaci s internetem. Takže můžu být spuštěn, řekněme, Skype. Mohl bych mít webový prohlížeč otevřený. Možná jsem něco, co torrenting soubory. Takže všechny tyto věci jsou komunikaci s internet nějakým způsobem. 

Takže když váš počítač přijme nějaká data z internetu, jak se to vědět, co vlastně aplikace chce údaje? Jak to, zda tento konkrétní Data jsou určena pro torrenting aplikace na rozdíl od na webovém prohlížeči? Takže to je účel portů v tom, že Všechny tyto aplikace mají prohlásil port na vašem počítači. Takže váš webový prohlížeč říká, hej, Poslouchám na portu 1000. A váš torrenting programu říká, Poslouchám na portu 3000. A Skype říká, jsem pomocí portu 4000. 

Takže když vám některá data, která patří do jedné z těchto aplikací, dat je označen port, který je ve skutečnosti by měly být zaslány spolu se. Tak to říká, oh, já patřím na portu 1000. Vím, že pak musím, aby předal toto po mé webovém prohlížeči. Takže důvod, proč je to relevantní je, že webové servery mají tendenci naslouchat na portu 80. Takže když jsem se kontaktovat Facebook.com, jsem komunikaci s nějakým strojem. Ale musím říci, jaký port, který Stroj chci komunikovat. A webové servery mají tendenci být naslouchá na portu 80. 

Kdyby chtěli, mohli by ho nastavit tak, že uvádí jako na portu 7000. A pak ve webovém prohlížeči, mohl bych ručně zadat Facebook.com: 7000 k poslat požadavek na portu 7000 webového serveru Facebooku. 

DAVID J. Malan: A v tomto případě, a to i i když jsme neměli požadovat, aby lidé zmínit to, v tomto případě, jaký port by žádost skutečně jít na? Zkuste to znovu. Přesně tak. Nehledám, ale jemnost že tam nic jako poslední. 

ROB BOWDEN: Tak HTTPS, protože je to speciálně pro poslech zašifrované, je to na portu 4430. 

Diváků: A e-maily jsou 25, že jo? 

DAVID J. Malan: Odchozí e-maily, 25, jo. 

ROB BOWDEN: Já ani nevím, většina - všechny ty nižší bývají vyhrazeno pro věci. Myslím, že všechno pod 1024 je vyhrazeno. 

DIVÁKŮ: Proč říkáte, 3. Byl špatné číslo? 

ROB BOWDEN: Protože IP adresy, tam čtyři seskupení číslic. A oni jsou od 0 do 255.. Takže 192.168.2.1 je společný lokální sítě IP adresy. Všimněte si, všechny z nich jsou menší než 255.. Takže když jsem začal s 300, že nemohl mít jedním z čísel. 

DAVID J. Malan: Ale to hloupé klip od - byl to CSI, kde měli číslo, které je příliš velké pro IP adresu. 

ROB BOWDEN: Případné dotazy na to? Příští, takže úplná změna téma, ale máme to PHP pole pro domy na čtyřkolce. A máme neuspořádané seznam. A chceme vytisknout každé položky seznamu Jen obsahující název domu. Takže máme smyčky foreach. Takže pamatujte, že syntaxe je foreach pole jako položka v poli. Takže prostřednictvím každé opakování smyčky, Dům bude trvat na jedné z hodnoty uvnitř tohoto pole. 

Na první iterace, dům bude Cabot dům. Na druhé iterace, dům bude být Courier dům a tak dále. Takže pro každou čtveřici jako dům, jsme jen jít do tisku - jste také mohli ozvěnou - položku seznamu a pak název domu je a zavřete položku seznamu. Složené závorky jsou zde volitelná. 

A pak jsme také řekl v otázce sama o sobě, nezapomeňte zavřít Jednoduchý seznam zobrazí značka. Takže musíme opustit režim PHP aby se to udělat. Nebo bychom mohli ozvěnou zavřít neuspořádaný seznam tag. 

DAVID J. Malan: Také zde by pokuta byli použít starou školu smyčka s $ i = 0 0 a použitím se počítá na zjistit délku paprsku. Taky úplně v pohodě, jen trochu wordier. 

DIVÁKŮ: Takže pokud jste se chystali [Neslyšitelné], by vy - Já zapomněl, co smyčka [neslyšitelné] je. Chtěli byste $ quad držák i? 

DAVID J. Malan: Přesně tak. Jo, přesně tak. 

ROB BOWDEN: Ještě něco? 

DAVID J. Malan: Dobře. Trade-off. Takže tam byly hrozny odpovědí možné, pro každou z nich. Byli jsme opravdu jen hledáte něco přesvědčivé pro vzhůru a nevýhoda. A číslo 16 zeptal, ověřování uživatelů " Vstup na straně klienta, jako u JavaScriptu, místo na straně serveru, jako u PHP. Takže to, co je vzhůru z dělá na straně klienta? 

No, jedna z věcí, které jsme navrhli, je že snížit latenci, protože vám Nemusíte se obtěžovat kontaktování Server, který může trvat několik milisekund nebo dokonce pár sekund vyloučením, že i jen ověřování vstupu na straně klienta uživatelů tím, spuštění obslužné rutiny on-předložit a jen kontrolovat, se jim napište něco pro jméno? Líbilo se jim něco psát in pro e-mailovou adresu? Líbilo se vybrat kolej z Rozevírací nabídka? 

Můžete jim dát okamžitou zpětnou vazbu pomocí počítače gigahertz nebo co mají, že je vlastně na svém stole. Takže je to jen lepší uživatelské zažít obvykle. Ale Nevýhodou dělá na straně klienta ověření, pokud si to bez toho, dělá server-side validaci je, že Nejvíce někdo přichází z CS50 ví že můžete jen odesílat data, která chcete na serveru libovolný počet způsobů. Upřímně řečeno, ve většině libovolném prohlížeči, můžete klikněte kolem v nastavení a jen vypnout JavaScript, která by proto, zakázat jakoukoli formu validace. 

Ale vy jste také mohli připomenout, že i já dělal nějaké tajemné věci ve třídě pomocí telnet a dokonce předstírá, že bude prohlížeč zasláním get požadavky na server. A to rozhodně není pomocí libovolného JavaScript. To je jen můj zadáním příkazů na klávesnici. Takže opravdu, každý programátor v dostatečně komfort s webem a HTTP mohl poslat co dat on nebo ona chce k serveru bez ověření. A pokud váš server není také kontrola, to se mi dát jméno, je to vlastně platnou e-mailovou adresu, dělal si vyberou koleji, můžete skončit nahoru vkládání falešné, nebo jen prázdné údaje do databáze, což pravděpodobně se nebude dobrá věc, pokud jste za předpokladu, že tam byl. 

Tak to je nepříjemné reality. Ale obecně, na straně klienta validace je skvělá. Ale to znamená, že dvakrát tolik práce. Ačkoli tam přece existují různé knihovny, JavaScript knihovny pro instance, které tvoří tolik, mnohem menší bolesti hlavy. A můžete znovu použít některé z kódu server-side, na straně klienta. Ale uvědomit, že to je typicky další práce. Jo. 

DIVÁKŮ: Takže kdybychom řekl méně bezpečné - 

DAVID J. Malan: [směje se] Fuj. Ti jsou vždy těžší ty se rozhodnout. 

ROB BOWDEN: To by byly přijaty. 

DAVID J. Malan: Co? 

ROB BOWDEN: Vytvořil jsem tento problém. To by byly přijaty. 

DAVID J. Malan: Jo. 

DIVÁKŮ: Cool. 

ROB BOWDEN: Ale my jsme nepřijali pro první - dobře, to, co jsme hledali, je něco jako vy nemusíte komunikaci se serverem. Nepřijali jsme prostě rychlejší. 

DIVÁKŮ: Co ne znovu načíst stránku? 

ROB BOWDEN: Ano. To byla přijata odpověď. 

DAVID J. Malan: Cokoliv, kde jsme cítili, to bylo více pravděpodobné než nepravděpodobné, že jste věděl, že to, co bylo říká, což je těžké vedení k tomu někdy. Místo pomocí propojeného seznamu z pole k udržení řazeny seznam celých čísel. Takže vzhůru se často citují se spojené seznamy, které motivovaly jejich celek úvod byl dostanete dynamiku. Mohou dorůst. Mohou zmenšit. Takže nemusíte se proskočit obručí skutečně vytvořit více paměti s řadou. Nebo nemusíte jen říci, je mi líto, uživatel. Pole je vyplněno. Takže dynamický růst seznamu. Nevýhodou však spojových seznamů? 

DIVÁKŮ: Je to lineární. Vyhledávání na Google seznamu je lineární místo toho, co se přihlásíte 

DAVID J. Malan: Přesně tak. Vyhledávání na Google seznamu je lineární, i když je to dále, protože můžete jen postupujte podle následujících strouhanky, tyto ukazatele, od začátku seznamu až do konce. Nemůžete využít náhodný přístup a, tak, binární vyhledávání, i když je to dále, že byste mohli co dělat s matici. A je tu i další náklady. Jo. 

DIVÁKŮ: Memory neefektivní? 

DAVID J. Malan: Jo. No, já bych to nutně říkají neefektivní. Ale to stát více paměti, protože budete potřebovat 32 bitů pro každý uzel pro další ukazatele, na alespoň pro jednotlivě propojeného seznamu. Nyní, když jste jen ukládání celých čísel a přidáváte ukazatel, který je ve skutečnosti druh non-triviální. Je to zdvojnásobení množství paměti. Ale ve skutečnosti, pokud jste ukládání spojový seznam struktur, které by mohly mít 8 bajtů, 16 bajtů, ještě než to, že je to možná méně z mezní náklady. Ale je to nákladově nicméně. Takže jeden z těch by si Byl v pořádku, stinné stránky. 

18. Použití PHP namísto C psát příkazového řádku programu. Tak tady je to často rychlejší použít jazyk, jako je PHP nebo Ruby nebo Python. Prostě rychle otevřít do textového editoru. Máte mnoho dalších funkcí Vám k dispozici. PHP má kuchyňský dřez funkcí, zatímco v C, je mají velmi, velmi málo. Ve skutečnosti, kluci vědí tvrdě že nemáte hash tabulky. Nemáte spojeny seznamy. Chcete-li ti, musíte jim realizovat sami. 

Takže jeden vzhůru PHP nebo opravdu nějaký interpretovaný jazyk je rychlost pomocí kterého můžete psát kód. Ale nevýhoda, viděl jsme se, když jsem rychle se šlehačkou a misspeller implementace v přednášce pomocí PHP, je že použití interpretovaný jazyk je obvykle pomalejší. A my jsme viděli, že prokazatelně se zvýšení v době od 0,3 sekund až 3 sekund, a to z důvodu výkladu že ve skutečnosti děje. 

Dalším dnem bylo to, že vám nemusíte kompilovat. Tak to také urychluje vývoj mimochodem, protože nemáte dva kroky k běhu programu. Stačí mít jeden. A tak to je docela přesvědčivé stejně. Namísto použití SQL databáze CSV soubor pro ukládání dat. Tak SQL databáze se používá pro pset7. Soubory CSV jste nepoužili moc. Ale vy jste ji použil nepřímo pset7 jako i tím, že mluví do Yahoo Finance. 

Ale CSV je, stejně jako soubor aplikace Excel, ale super jednoduché, kde sloupce jsou jen demarked čárkami uvnitř z jinak textového souboru. A pomocí SQL databáze je trochu více přesvědčivé. Je to obráceně, protože se věci jako vybrat a vložit a odstranit. A vám, podle všeho indexy, které MySQL a další databáze, jako je Oracle, vybudovat pro vás v paměti, které znamená, že váš výběr je pravděpodobně bude lineární shora dolů. Je to opravdu bude něco jako binární vyhledávání nebo něco podobně v duchu. Takže jsou obecně rychlejší. 

Ale nevýhodou je, že je to jen více práce. Je to více úsilí. Musíte pochopit databází. Musíte nastavit. Musíte server spustit že databáze. Musíte pochopit, jak ji nakonfigurovat. Takže to jsou jen ty druhy kompromisů. Vzhledem k tomu, CSV, můžete vytvořit s gedit. A máte dobré jít. Neexistuje žádný složitosti dál. 

Použití trie místo hash tabulky s oddělenou řetězení pro uložení slovník slov připomínajících z pset5. Proto se snaží vzhůru, teoreticky nejméně, je to, co? Konstantní čas, alespoň pokud jste hash na každém jednotlivci písmena ve slovech, jako jste vy, může mít pro pset5. To by mohlo být pět hash, šest hash v případě, že je pět nebo šest písmen ve slově. A to je docela dobré. A v případě, že je horní mez na tom, jak dlouho vaše slova mohou být, to je opravdu asymptoticky konstantní čas. 

Vzhledem k tomu, hash tabulka s odděleným řetězení, problém tam s tím druh datové struktury je to, že výkon svých algoritmů obvykle závisí na mnoha faktorech již v datové struktuře. A to je určitě případ řetězy, přičemž více věcí si dát do hash tabulky, už ti řetězy jít, což znamená, že v nejhorším případ, věc, kterou by mohl mít zájem o je úplně na konci jednoho z těchto řetězců, které účinně přejde do něčeho lineární. 

Nyní, v praxi by se zcela být v případě, že hash tabulky s řetězce je rychlejší než odpovídající Implementace trie. Ale to z různých důvodů, mezi , které se snaží využít celou řadu paměti, že může ve skutečnosti pomalé věci dolů, protože nemusíte dostat pěkný Výhody něco, co nazývá ukládání do vyrovnávací paměti, kde věci, které jsou blízko u sebe v paměti lze přistupovat často rychleji. A někdy můžete přijít s opravdu dobrý hašovací funkce. I když budete muset ztrácet trochu paměť, můžete skutečně být schopen najít věci rychle, a ne stejně špatný jako lineárně. 

Takže ve zkratce, nebylo nutně s některou z těchto jednoho nebo i dva konkrétní věci, které jsme hledali. Opravdu nic přesvědčivý jako proinflační a protiinflační obecně zachytil naši pozornost. 

ROB BOWDEN: Tak na druhou stranu, my jsme nepřijímá sama o sobě "rychleji." Vy musel říkat něco o tom. Dokonce i když jste řekl teoreticky rychlejší, věděli jsme, že tak nějak pochopil, že je to 0 z 1.. A hash tabulka, v teorii, není 0 1.. Za zmínku něco o běhu obecně Máš body. Ale "rychleji", většina řešení na velká deska, která se snaží byly objektivně pomalejší než řešení které byly hash tabulky. Tak rychleji a sama o sobě Není to pravda. 

DAVID J. Malan: Dom de dom dom. Jsem asi jediný, kdo si uvědomuje, to je, jak to má se prohlásil, že jo? 

ROB BOWDEN: Měl jsem vlastně ani ponětí. 

DAVID J. Malan: Je vyrobena pocit v mé hlavě. 

ROB BOWDEN: Dělám tuhle. OK. Takže to je ten, kde jste museli čerpat diagram podobný byste mohli viděli na posledních zkouškách. Takže pojďme se jen podívat na to. Takže z uzlu HTML, máme dvě děti, hlava a tělo. Tak jsme se rozdělit - hlavu a tělo. Hlava má název značky. Takže máme titul. 

Teď, jedna věc, kterou mnoho lidí zapomněl je, že tyto textové uzly prvky v rámci tohoto stromu. Tak jsme tady náhodou je nakreslit jako ovály odlišit je od nich druhy uzlů. Ale Oznámení také zde máme vrchol, střední a dolní skončí na textové uzly. Tak zapomínám které bylo poněkud společného chyby. 

Tělo má tři děti - Tyto tři divs. Takže div, div, div a pak text uzel děti těchto divs. To je docela hodně to na tom, že otázky. 

DAVID J. Malan: A je třeba poznamenat, i když nebydlí na těchto Podrobnosti v době, kdy jsme strávili na JavaScript, který příkaz dělá, v Skutečnost, záležitost technicky. Takže pokud hlava je před tělem v HTML, pak by se měla objevit na vlevo těla ve skutečném DOM. To mu je, obecně, jen FYI, něco, co nazývá aby dokument, kde to záleží. A pokud jste byli se provádí analyzátor, program, který čte HTML v budově do stromu v paměti, abych byl upřímný, to je intuitivně pravděpodobně to, co jste dělat tak jako tak - shora dolů, zleva doprava. 

ROB BOWDEN: Dotazy na to? Mám udělat další? 

DAVID J. Malan: Jistě. 

ROB BOWDEN: OK. Tak tohle je přetečení vyrovnávací paměti Útok otázka. Hlavní věc, kterou si uvědomit, tady je, dobře, jak by mohl protivník trik tento program do provádění libovolný kód? Takže argv1, první příkazového řádku argument tohoto programu, které může být libovolně dlouho. Ale tady jsme pomocí memcpy kopírovat argv1, který je zde bar. Jsme předáním jako argument. A tak je to s na jméno baru. 

Takže jsme memcpying bar do této vyrovnávací paměti c. Kolik bajtů jsme kopírování? No však mnoho bytů bar se stane používat, délku tohoto argumentu. Ale c je pouze 12 bajtů široký. Takže pokud bychom zadejte argument příkazového řádku to je delší než 12 bajtů, jsme bude přetékat to zejména vyrovnávací paměti. Nyní, jak by protivník trik naprogramovat do provedení libovolného kódu? 

Takže nezapomeňte, že zde Hlavní volá foo. A tak tedy hlavní výzvy foo. Pojďme nakreslit to. Takže máme stack. A hlavní je rámeček zásobníku ve spodní části. Na nějakém místě, hlavní výzvy foo. No, okamžitě, hlavní výzvy foo. A tak foo dostane svůj vlastní rámeček zásobníku. 

Nyní, v určitém okamžiku, foo se chystá na návrat. A šel foo vrátí, musíme vědět, na co řádek kódu uvnitř hlavní my bylo, aby věděli, kde bychom měli pokračovat v main. Můžeme volat foo z celku spoustu různých místech. Jak můžeme vědět, kam se vrátit? No, musíme uložit, že někde. 

Takže někde přímo tady, uložíme kde bychom se měli vrátit k jednou foo vrací. A to je zpáteční adresa. Tak jak by mohl protivník využít to je skutečnost, že Tato vyrovnávací paměť c je uložena, pojďme říci, tady je cca. Takže máme 12 bajtů pro C. To je cca. A to je Foo stack kroužek. Takže v případě, že uživatel se zlými úmysly zadá více bajtů, než 12 let nebo je zadejte příkaz linka argument, že je delší než 12 znaky, pak budeme přetečení této vyrovnávací paměti. 

Můžeme jít dál. A v určitém okamžiku, můžeme jít daleko natolik, že začneme přepsání této zpáteční adresu. Takže jakmile jsme se přepsat návratovou adresu, to znamená, že při foo se vrací, vracíme se tam, kde uživatel se zlými úmysly se říká, to by bez ohledu na hodnotu vstoupila, bez ohledu na znaky uživatel zadal. A tak v případě, že uživatel se zlými úmysly je, že obzvláště chytrý, může mít tato návrat někam do printDef funkce nebo někde v malloc funkce, prostě kdekoliv libovolný. 

Ale i další chytré je to, co v případě, že má uživatel vrátit k právě zde. A pak začnete provádění to jako řádky kódu. Takže v tomto bodě, může uživatel zadat co chce v této oblasti. A on má úplnou kontrolu na programu. Dotazy na to? Takže další otázka je kompletní reimplementace foo takovým způsobem, že už to není zranitelná. 

Takže tam je několik způsobů, jak jsi to mohl udělat. Máme stále c pouze jsou délky 12. Dalo by se změnily v tomto jako součást vašeho řešení. Také jsme přidali kontrolu, aby se , že bar není null. I když nepotřeboval že pro plnou úvěru. Takže jsme kontrolu první délka řetězce baru. Pokud je větší než 12, pak nejsou ve skutečnosti dělat kopie. Takže to je jeden ze způsobů, kterým se to. 

Další způsob, kterým se to je místo s c se pouze v délce 12, má to být délka strlen (bar). Další způsob, kterým se to je skutečně jen vrátit. Takže pokud jste se právě zbavili všech to, pokud jste právě odstraněny všechny řádků kódu, by jste se dostali plné uznání, protože tuto funkci není ve skutečnosti dosáhnout nic. Je to kopírování příkazového řádku Argument do nějakého pole v její místní stack frame. A pak, co se vrací. A co to dokonalý, je pryč. Takže návrat byl také dostatečné způsob, jak dostat všechny zásluhy. 

DAVID J. Malan: Ne tak docela duch otázka, ale přijatelné za spec nicméně. 

ROB BOWDEN: Dotazy týkající se něco z toho? Jedna věc, která vám alespoň potřebné k sestavování kódu. Takže i když technicky nejste zranitelná, pokud váš kód není sestavit, jsme neměli přijmout. Žádné otázky? OK. 

DAVID J. Malan: Chcete říci, tento titul? 

ROB BOWDEN: Ne 

DAVID J. Malan: Tak v tomhle, to byl buď dobrá zpráva nebo špatná zpráva. To je doslova stejný problém jako první kvíz. A to je skoro stejný problém, pset1. Ale to bylo záměrně zjednodušen, aby se jednodušší pyramida, který může být řešena s mírně jednodušší iterace. A opravdu, co jsme se dostat na zde nebylo tolik logiky, protože pravděpodobně v tomto okamžiku, že jste mnohem pohodlnější, než jste byli v týdnu jedné s pro smyčky nebo proč smyček, ale opravdu dráždit sebe, že jste trochu pohodlnější s Představa, že PHP není jen o tom, co programování. To může ve skutečnosti být použit jako jazyk psát programy příkazového řádku. 

A vskutku, to je to, co se snažíme upozornit na. To je PHP programu pro příkazovou řádku. Takže C kód zde, zatímco správná v C, není správné pro PHP. Ale kód je ve skutečnosti stejné. Pokud porovnáte řešení pro Quiz 0 proti Quiz 1, zjistíte, že je to téměř totožné, s výjimkou Některé dolaru a pro absence datového typu. Zejména, pokud se podíváme tady, uvidíte, že jsme iteraci, v tomto případ od 1 do až 7. 

Mohli jsme to udělal 0 index. Ale někdy si myslím, že je to jen mentálně jednodušší přemýšlet o věcech, 1-7. Chcete-li jeden blok, a pak dva bloky, pak tři, pak tečka, tečka, tečka sedm. Máme j je inicializován na hodnotu 1 a pak se počítá až na i.. A vše je zde jinak identické. Ale stojí za zmínku, jsou pár věcí. Dáme vám tyto dva řádky, to první jeden, goofily pojmenovaný jako shebang pro ostrou ránou. A to právě určuje cestu, složka, ve které může být program zjistili, že chcete použít interpretovat tento soubor. 

A pak vedení po tom, o Samozřejmě, že znamená, že vstup do režimu PHP. A linka na samém dně znamená, že režim exit PHP. A to funguje obecně, s interpretovat jazyků. Je to docela nepříjemné, pokud píšete Program v souboru s názvem foo.php. A pak uživatelé mají jen pamatujte, OK, pro spuštění tohoto programu, jsem muset zadat "php prostor foo.php." Druh nepříjemné když už nic jiného. A to také ukazuje, že váš program je napsán v PHP, který není vše že osvětlení pro uživatele. 

Takže můžete odstranit. Php úplně pamatujete z přednášky. A můžete skutečně udělat. / Foo, pokud jste chmodded to tím, že to spustitelný soubor. Takže chmod + x foo by udělal to. A pokud jste také přidat cirkus zde. Ale ve skutečnosti, problém byl dostat na vytisknout něco takového. No HTML, ne C-kódu jistě, jen některé PHP. Takže Milo pak se vrátil do problému 25. A v roce 25, jste dostali z následujících kostra kód, který byl docela jednoduché webové stránky. A šťavnaté část HTML-moudrý byl dole tady, kde máme uvnitř těla forma, která má unikátní ID vstupů uvnitř které je dva vstupy, jeden s myšlenkou jméno, jeden s myšlenkou tlačítka. 

První byl typ textu, Druhá typu předložit. A tak jsme vám dali, ve skutečnosti, více složky, než jste potřebovali, jen tak vy jste měli možnosti, s nimiž k vyřešení tohoto problému. Nemusíte nezbytně potřebují všechny tyto ID. Ale to vám umožní řešit to různými způsoby. A až na vrchol, všimněte si, že Cílem bylo vyvolat Okno takhle - Dobrý den, Milo! - vyskočí v prohlížeči pomocí super jednoduché, pokud Není ošklivá, funkce upozornění. A tak nakonec, to se scvrkává koncepčně nějak poslouchat podání formuláře na straně klienta , Ne na straně serveru, tak nějak odpovědi na toto podání podle chytil hodnotu, která uživatel zadaný do pole Název a poté jeho zobrazení v těle výstrahy. 

Takže jeden způsob, jak to můžete udělat, je se jQuery, která vypadá trochu syntakticky matoucí na první pohled. Můžete to udělat s čistým DOM kódu - document.getelement podle ID. Ale pojďme se podívat na tuto verzi. Mám pár důležitých první linie. Takže jeden, máme tento řádek, který je totožný s tím, co jste mohli vidět v, věřím, form2.html z třídy v týdnu 9. A to je jen říkám, provést Následující kód při Dokument je nyní připraven. To je důležité nejen proto, HTML stránky se čtou shora dole, zleva doprava. 

A proto, pokud se pokusíte udělat něco v kódu, až tady na nějakou DOM prvek, některé značky HTML, která je dole zde, že jste to děláte příliš brzy, , protože to nemá ani byly načteny do paměti. Takže tím, že říká toto document.ready linka, říkáme, tady je nějaký kód, prohlížeč. Ale ne spustit, dokud celý Dokument je nyní připraven, že je DOM strom existuje v paměti. To je trochu víc jednoduché, pokud syntakticky trochu jiná, kde říkám, grab prvek HTML, jehož jedinečný identifikátor vstupy. To je to, co značka hash označuje, jedinečný identifikátor. A pak volám. Odeslat. 

Tak. Předloží zde je funkce, jinak známý jako metoda, která je uvnitř objektu na levé straně straně tam, že jsem neměl zvýraznit. Takže pokud si myslíte, vstupů jako objekt v paměti - a opravdu to je. Je to uzel na stromě - . Předloží znamená, že když je tato forma se toto číslo je předložen, provést Následující kód. Nezajímá mě, co název Funkce je mi provádění. Tak tady jsem pomocí, stejně jako dříve, to, co je tzv. funkce lambda nebo anonymní funkce. Je to vůbec intelektuálně zajímavé, jiné, než je to nemá jméno, což je v pořádku, pokud jste jen kdy bude jednou zavolat. A uvnitř jsem tam vlastně zvládnout předložení formuláře. Poprvé jsem deklarovat proměnnou tzv. hodnota. A co pak je účinek tohoto zvýrazněna část tady? Co to udělat na na vysoké úrovni pro mě? 

DIVÁKŮ: Dostane hodnotu, která uživatel neměl v následující HTML. Dostane to ID a poté najde hodnotu něj. 

DAVID J. Malan: Přesně tak. Je to chytne uzel, jehož jedinečný Identifikátor je název. To dostane hodnotu v něm, které je pravděpodobně to, co uživatel napsal jej nebo sebe. A pak se ukládá, aby do proměnné s názvem hodnotu. Jako stranou, mohli byste mít také udělat to trochu jinak. Zcela přijatelné tím, že dělá něco, co lež var hodnota dostane document.getElementById. A to je důvod, proč je to trochu zdlouhavý, že nebude používat jQuery. "Jméno". Hodnota. Takže naprosto přijatelné. Různé způsoby, jak to udělat. jQuery jen má tendenci být trochu stručnější a určitě více populární mezi programátory. 

Teď dělám trochu zdravého rozumu zkontrolovat, protože v problému prohlášení jsme výslovně řekl, pokud uživatel ještě napsaný jeho nebo její jméno, nevykazují upozornění. Ale můžete zkontrolovat tím, že právě kontrolu na prázdný řetězec pro quote-konec citátu v případě, že je nic ve skutečnosti neexistuje. Ale pokud to není rovná citátem-konec citátu, Chci volat upozornění. A zajímavá část je, že jsme pomocí operátoru navíc, které co dělá v JavaScriptu? Zřetězit. Takže je to jako Phps operátor tečka. Stejný nápad, mírně odlišná syntaxe. A já jsem jen vytvořit řetězec, který jste viděli na snímku obrazovky - Ahoj, tak a tak. 

A pak poslední detail je to. Proč bych se vrátit false vnitřek této anonymní funkce? 

DIVÁKŮ: Není hodnotu. Můžete dát ve formě. Je to jen říká, pokud hodnota není rovná prázdné, pak to udělat. Tam byla prázdná v tomto podání. 

DAVID J. Malan: OK. Opatrní. K dispozici je zde nikdo jiný. A to return false je mimo ze pokud podmínky. Tak tohle zvýrazní linii, vrátí false, provádí bez ohledu na to, kdy Formulář je předkládán. Co vrací false uvnitř tohoto Obslužná rutina události, jak se tomu říká, událost v otázce že podání? 

DIVÁKŮ: Vzhledem k tomu, stane jen jednou. 

DAVID J. Malan: stane jen jednou. Ne tak docela. Jo? 

DIVÁKŮ: Zabraňuje formulář od předložení výchozí chování, které by na stránku znovu načíst. 

DAVID J. Malan: Přesně tak. Takže jsem přetížení termín předložení tady, protože já říkám, forma je byl předložen. Ale jak si navrhnout, že to ve skutečnosti není byla předložena v pravém způsobem HTTP. Po klepnutí na tlačítko Odeslat, protože naše onSubmit handler, budeme zastavovat že podací formulář, abych tak řekl. Jsme pak dělá naše věc s kódem JavaScript. Ale já jsem záměrně vrací false, protože to, co nechci, aby se to stalo zlomek vteřiny později, je pro celý formulář sama o sobě, která bude předložena na webu server s klíče a hodnoty, změnou URL musí být něco jako q = kočky nebo co jsme udělali, Například, ve třídě. Nechci, aby se to stalo, protože není server naslouchání na to vytvořit podání. Je to čistě provedeno v kódu JavaScript. A to je důvod, proč jsem neměl ani akce atribut na mé formě, protože jsem nemají v úmyslu, aby to někdy jít na server. 

Takže je to být předloženy. Ale my zachycení tohoto formuláře podání a prevenci výchozí chování, což je ve skutečnosti jít celou cestu k serveru. 

DIVÁKŮ: Takže udržet to na straně klienta. 

DAVID J. Malan: Vedení je na straně klienta. Přesně tak. Další na řadě byl můj oh MySQL. 

ROB BOWDEN: OK. Takže tato první otázka byla obecně hrubý k lidem. I když ty později šel lépe. Takže jste měli vybrat správnou údaje typy na obou těchto sloupců. A jak z nich mají některé věci o nich, že aby volba obtížné. Takže int nebyl platný typ pro čísla. Důvodem je 12-místné číslo účtu číslo, int není dostatečně velká, aby uložení celkem číslic. Takže volba je možná by byl velký int, pokud jste náhodou víte, že. Další možností by mohlo být char pole o délce 12. Takže jeden z těch by to fungovalo. Int, že ne. 

Nyní, rovnováha, si vzpomenu na pset7. Tak jsme se speciálně používá desetinné číslo na uložit hodnotu akcií, nebo - 

DAVID J. Malan: Cash. 

ROB BOWDEN: Cash. Použili jsme desítkové uložit částku hotovosti, které má v současné době uživatel. Takže důvod, proč to děláme, je protože, pamatujte, že plave. K dispozici je s plovoucí desetinnou čárkou v přesnosti. Nelze přesně uložit hotovost hodnoty, jako je chceme zde. Takže desítkové je schopen přesně sklad něco, řekněme, dvě desetinná místa. To je důvod, proč bilance, chceme ho být desetinné, a ne plavat. 

DAVID J. Malan: A taky, taky, i když to by mohlo být chytrý v jiných souvislostech přemýšlet, možná to Je to šance pro int. Budu jen sledovat věci haléře. Protože jsme explicitně ukázal výchozí hodnota je 100,00, že znamená, že to může být jen int. A další jemnost také s řadou bylo, že to nebylo myšleno být chyták. Ale vzpomínám, že int v MySQL, stejně jako v C, alespoň v zařízení, je 32-bit. A i když neočekáváme, že vám přesně vědět, kolik číslic, které prostředky, si připomenout, že největší počet můžete představovat potenciálně 32-bitové číslo je zhruba to, co? 

Jaké číslo si vždycky říct? 2 až 32, což je to, co zhruba? Nemusíte přesně vědět. Ale asi je užitečné v životě. Je to zhruba 4 miliardy. Tak jsme řekli, že za několik minut. Vím, že jsem řekl, že za několik minut. A to je zhruba 4 miliardy. A to je dobré pravidlo palce vědět. Pokud máte 8 bitů, 256 je magické číslo. Pokud máte 32 bitů, 4 miliard dávat nebo brát. Takže pokud jste právě napsat 4000000000, uvidíte, že je to méně číslic než 12, což znamená, že je zjevně dost expresivita zachytit Číslo účtu 12-místné. 

ROB BOWDEN: OK. Takže ty ostatní šlo lépe. Takže předpokládám, že banka ukládá 20 dolarů měsíčně udržovací poplatek na všech účtech. S tím, co SQL dotazu by banka odečíst 20 dolarů z každého počtu, a to i v případě, to má za následek některé negativní bilancí? Takže v podstatě existují čtyři Hlavními typy dotazů - vložit, vyberte, aktualizovat a mazat. Takže to, co si myslíme, že jsme bude tady používat? Aktualizovat. 

Takže pojďme se podívat. Tak tady jsme aktualizaci. Co tabulce jsme aktualizaci účtů? Tak aktualizace účtů. A pak syntaxe říká, co v účtech jsme aktualizaci? No, my jsme nastavení vyvážení rovnající se aktuální hodnota zůstatku minus 20. Takže to bude aktualizovat všechny řádky účtů, odečtením 20 dolarů z rovnováhy. 

DAVID J. Malan: Častou chybou tady, i když jsme někdy odpustil to, bylo skutečně PHP kód zde volání funkce dotazu nebo uvedení uvozovky kolem všeho, co Nepotřeboval, aby se tam. 

ROB BOWDEN: Nezapomeňte, že MySQL je oddělený jazyk od PHP. Jsme stalo, že se psaní MySQL v PHP. A PHP se to pak posílá se k MySQL serveru. Ale nemusíte PHP, aby se komunikovat se serverem MySQL. 

DAVID J. Malan: Přesně tak. Takže žádné proměnné se znaky dolaru by měla být v tomto kontextu. To může jen dělat vše z matematiky v databázi samotné. 

ROB BOWDEN: OK. Takže ten příští. Je to další? Jo. Takže s tím, co SQL dotazu by banka načtení čísla účtů svých Nejbohatší zákazníci, které se zůstatky větší než 1000? Tak který z těchto čtyř hlavních typů budeme chtít tu? Vyberte. Takže chceme vybrat. Co chceme vybrat? Co sloupec chceme vybrat? Budeme se konkrétně chcete vyberte číslo. Ale pokud jste řekl, hvězda, jsme Také připustil, že. 

Takže zvolte číslo z jakého stolu? Účty. A pak stav chceme? Kde zůstatek větší než 1000. Jsme rovněž přijala větší než nebo rovno. Poslední. S tím, co SQL dotazu by banka zavřít, tj. odstranit každý účet, který má bilanci 0 dolarů? Tak který z těch čtyř jsme chtít používat? Odstranit. Takže syntaxe, že? Odstranit z jakého stolu? Účty. A pak se podmínka, která chceme odstranit - kde zůstatek se rovná nule. Takže odstranit všechny řádky z účtů tehdy, je nulová. Otázky týkající se některého z nich? Chcete fronty? 

DAVID J. Malan: průvodce fronty. Takže v tomto jednom, vám dal nám poněkud seznámit struktura, která jsme zkoumali A bit ve třídě vedle of struktur, který byl údaje Struktura příbuzný v duchu. Rozdíl však s frontě že jsme museli nějak vzpomenout, kdo byl v přední části fronty, ve velkých část tak, aby jsme mohli udělat víc efektivní využití paměti, alespoň pokud jsme pomocí pole. 

Vzhledem k tomu, odvolání, pokud máme pole, pokud Například, to je přední část fronta, když jsem si do fronty zde, a pak někdo dostane v souladu za mnou, za mnou, za mnou, a jeden člověk vystoupí z řady, si mohli, jak jsme viděli některé z našich člověka dobrovolníci ve třídě, mají všichni posunout tímto způsobem. Ale obecně, když všichni dělat něco, co není nejlepší využití času v programu, protože to znamená, že vaše algoritmus běží v tom, co asymptotická doba chodu? Je to lineární. 

A mám pocit, že je trochu hloupé. Pokud je další člověk v řadě je další člověk, který má jít do obchod, nemají všichni mají se pohybují společně. Jen ať ten člověk se rval až přijde čas, například. Takže můžeme si trochu času ušetřit tam. A tak k tomu, že i když to znamená, že že hlava fronty nebo přední fronty se chystá postupně pohybovat hlouběji a hlouběji do pole a případně by mohly ve skutečnosti se zalomí kolem, pokud jsme pomocí pole pro uložení lidi v této frontě. Takže můžete téměř myslet pole jako kruhová údaje struktura v tomto smyslu. 

Takže si nějak muset sledovat velikost, nebo opravdu konec to a pak, kde je počátek toho je. Takže navrhujeme, že deklarujete jedna taková fronta, volání to q, jen jedno písmeno. Pak navrhujeme, aby přední být inicializován na nulu, a to, že velikost být inicializován na nulu. 

Takže teď, nic uvnitř této fronty. A žádáme vás, abyste dokončit provádění Zařadí níže takovým způsobem, že funkce přidá n na Konec q a potom vrátí hodnotu true. Ale pokud q je plná, nebo negativní, Funkce by měla raději vrátit false. A ti dal nám pár předpokladů. Ale to není opravdu funkčně relevantní, jen to bool existuje, protože, technicky, bool není existují v C, pokud obsahují jisté hlavičkový soubor. Takže to byla jen se tam, že byly ne je to jen trik Otázka takové věci. 

Tak enqueue, jsme navrhli ve vzorku řešení, realizovat následujícím způsobem. Jednou jsme nejprve zkontrolujte snadnost, na nízko visící ovoce. Pokud je fronta plná nebo číslo, které se snažíte vložit je méně než nula, které jsme si řekli v Specifikace problému by nemělo být dovoleno, protože chceme jen non-záporné hodnoty, pak byste měli jen vrátit okamžitě false. Takže některé poměrně snadné Kontrola chyb. Pokud však budete chtít přidat, že skutečná číslo, co musel udělat trochu na mysli. A to je místo, kde je to trochu nepříjemné psychicky, protože budete muset přijít na to, jak zacházet s wraparound. 

Ale zárodek myšlenky zde, že je na zájem pro nás je, že ovinovací často znamená, modulární aritmetika a mod operátor, procento straně, kde můžete jít z větší hodnoty zpět na nulu, a pak jeden a dva a tři a pak zpět kolem nuly, jedna a dvě a tři a tak dále znovu a znovu. Takže způsob, jak navrhujeme dělat to je že my chceme, aby index do Pole s názvem čísla, kde naše celá čísla lhát. Ale tam dostat, nejprve chci udělat bez ohledu na velikost fronty, ale je přidejte se, že bez ohledu na Přední část seznamu je. A efekt, který je nám dát na pravá pozice ve frontě a Nepředpokládejte, že první osoba v souladu je na začátku, kterému ona absolutně mohlo být, pokud bychom byl také posun každého. Ale my jsme jen vytvořit práci pro sebe, kdybychom se že konkrétní cesta. 

Takže můžeme udržet relativně jednoduché. Nechceme mít na paměti, že jsme jen přidal int do fronty. A pak jsme se jen vrátit true. Mezitím, v dequeue, jsme se zeptali můžete provést následující kroky. Provést to takovým způsobem, že dequeues, že se odstraňuje a vrátí, int na přední straně fronty. Chcete-li odstranit int, postačí na to zapomenout. Nemusíte přepsat svým dílem. Takže je to pořád vlastně tam. Stejně jako dat na pevném disku, jsme prostě ignorovat skutečnost, že je to teď. A pokud q je prázdná, měli bychom místo toho vrátí negativní 1. Tak to cítí libovolný. Proč návrat Negativní 1 místo falešný? Jo. 

DIVÁKŮ: Q je ukládání kladné hodnoty. Vzhledem k tomu, uložit pouze kladné hodnoty v q, negativní je chyba. 

DAVID J. Malan: OK, to je pravda. Takže protože jsme jen ukládání pozitivní hodnoty nebo nula, pak je to v pořádku, aby vrátí zápornou hodnotu jako strážce hodnota, speciální symbol. Ale vy jste přepisování historie tam, protože důvod, proč jsme jen vrací non-záporné hodnoty je proto, že chceme, aby mít hodnotu sentinel. Takže konkrétně, proč ne jen return false v případě chyby? Jo. 

DIVÁKŮ: jsi selhal vrátí celočíselnou hodnotu. 

DAVID J. Malan: Přesně tak. A to je místo, kde C dostane docela omezující. Pokud říkáte, že jdete vrátit int, máte vrátit int. Nemůžete dostat fantazie a začít vracet bool nebo float nebo string nebo něco takového. Nyní, mezitím, JavaScript a PHP, a některé jiné jazyky mohou, ve skutečnosti, jste se vrátil jiný typy hodnot. A to může ve skutečnosti být užitečné, pokud můžete vrátit pozitivní INT, nuly, negativní ints, nebo false nebo null ještě znamenat chybu. Ale my nemáme, že Všestrannost v C. 

Takže s dequeue, co jsme navrhnout, aby udělat, je - 

ROB BOWDEN: Můžete se vrátit false. Je to jen, že falešná je hash definovat false na nulu. Takže pokud jste se vrátit false, budete vracet nulu. A nula je platný věc v naší frontě, vzhledem k tomu, negativní 1 není-li false stalo negativní 1. Ale neměli byste ani potřebují vědět, že. 

DAVID J. Malan: To je proč jsem to neřekl. 

ROB BOWDEN: Ale to není pravda že se nemůžete vrátit false. 

DAVID J. Malan: Jistě. Takže dequeue, všimněte si, přijímáme ztrátu jako svůj argument. A to proto, že nejsme kolem nic palců Chceme jen odstranit prvek na přední straně fronty. Takže, jak můžeme jít asi dělá? No, za prvé, pojďme na to Rychlá kontrola zdravý rozum. Pokud je velikost fronty je 0, je tu žádná práce je třeba udělat. Návrat negativní 1. Hotovo. Tak to je pár řádků o mém programu. Takže jen čtyři řádky zůstanou. 

Tak tady jsem se rozhodl decrement velikosti. A účinně snižující velikost Znamená to, že jsem zapomněl něco, co je tam. Ale já jsem také aktualizovat, pokud přední čísla jsou. Takže k tomu, že musím udělat dvě věci. Nejprve musím mít na paměti, jaké číslo je na přední straně fronty, protože musím vrátit tu věc. Takže nechci, aby náhodou zapomněl o tom a pak jej přepsat. Jdu si vzpomenout na int. 

A teď, chci aktualizovat q.front být q.front +1. Takže jestli to byl první osoba v linka, teď chci udělat, plus 1 na poukazují na další osoby v souladu. Ale musím zvládnout, že wraparound. A pokud kapacita je globální konstanta, že to bude mi dovolte, abych se ujistil, jak jsem se poukázat na poslední osobou v linka, operace modulo přinese mě zpátky na nulu přední fronty. A to zpracovává wraparound zde. A pak jsem se přistoupit k návratu n. 

Nyní, přesněji řečeno, já ne musí prohlásit n. Nemusel jsem se chytit ji a uložte jej dočasně, protože hodnota je ještě tam. Takže jsem mohl jen udělat správnou aritmetické pro návrat bývalého šéfa fronty. Ale já prostě cítil, že to bylo více zřejmé, skutečně chytit int, dát v roce n, a pak se vrátit, že z důvodů přehlednosti, ale není nezbytně nutné. Psst. Jsou to všechno vyslovitelné v mé hlavě. 

ROB BOWDEN: Takže první otázka je binární strom problém. Takže první otázka je, že jsme vzhledem tato čísla. A my chceme, aby nějak vložit do Tyto uzly tak, že je platí binární vyhledávací strom. Takže jedna věc k zapamatování binární vyhledávací stromy, je, že to není jen to, co na levé straně je menší, a to na právo je větší. Je třeba, aby se stát, že celý strom vlevo je menší, a celý strom na pravé straně je větší. 

Takže když jsem dal 34 tady nahoře, a pak Dal jsem 20 tady, tak to platí, aby daleko, protože 34 až tady. 20 bude na levé straně. Tak to je méně. Ale nemůžu pak dal 59 tady, protože 59, i když je na pravé straně 20, je to pořád na levé straně 34. Tak s tímto omezením na mysli, Nejjednodušší způsob, jak zřejmě řešení tohoto Problém je jen trochu z těchto čísel - tak 20, 34, 36, 52, 59, 106. A pak vložíte zleva doprava. 

Takže 20 jde zde. 34 jde zde. 36 jde zde. 52, 59, 106. A také by přišel na to, s některé připojením a realizaci, oh, počkej, já nemám dost čísel vyplnit to ve více než tady. Takže musím reshift, co my trasa poznámka bude. Ale všimněte si, že v posledních třech, pokud budete číst zleva doprava, je v zvyšuje objednávky. 

Takže teď, chceme deklarovat, co struct bude pro Uzly tohoto stromu. Takže to, co potřebujeme v binárním stromu? Takže máme hodnotu typu int, takže některé int hodnota. Já nevím, co jsme nazvali se v roztoku - int n. Potřebujeme ukazatel na levé straně dítěte a ukazatel na pravé dítě. Takže to bude vypadat takto. A to bude ve skutečnosti vypadat před když se dvakrát vázaná Seznam věcí, tak Oznámení - Budu muset procházet všechny Cesta zpět dolů do problému 11. 

Takže všimnete, že vypadá stejně jako to, kromě nás jen tak zavolat těchto různá jména. Stále máme celé číslo hodnota a dva ukazatele. Je to jen, že místo léčení ukazatele jako směřující k další věci a předchozí věc, my léčbě ukazatelé poukázat na levé dítě a právo dítě. OK. Tak to je naše struct uzel. A teď, jediná funkce je třeba realizovat, je to traverza, která Chceme jít přes strom, tisk z hodnot stromu v pořadí. 

Takže hledáte tady, bychom chtěli vytisknout z 20, 34, 36, 52, 59, a 106. Jak jsme toho dosáhli? Takže je to dost podobné. Pokud jste viděli v minulém zkoušku problém že jste chtěli vytisknout Celý strom s čárkami mezi všechno, to bylo vlastně ještě jednodušší, než to. Takže tady je řešení. To bylo výrazně jednodušší pokud jste to udělal rekurzivně. Nevím, jestli někdo pokusil na to iterativně. 

Ale nejdřív, máme základní případ. Co v případě, že kořen je null? Pak jsme jen tak vrátit. Nechceme tisknout cokoli. Jinak budeme procházet rekurzivně dolů. Vytisknout celý levý podstrom. Takže tisknout vše méně než mé současné hodnoty. A pak budu tisknout sám. A pak budu recurse se my Celá pravá podstrom, takže vše větší než moje hodnoty. A to se bude tisknout se vše v pořádku. Otázky o tom, jak to ve skutečnosti dosáhne, že? 

DIVÁKŮ: Mám otázku na [neslyšitelné]. 

ROB BOWDEN: Takže jeden způsob, jak se blíží každá rekurzivní problém je jen, že o to, jako bys měl myslet o všech případech rohu. Takže za to, že chceme, aby vytisknout celý tento strom. Takže vše, co se zaměříme na Je to zvláštní uzel - 36. V rekurzivní volání, předstíráme ty prostě fungovat. Tak tady to rekurzivní volání traverza, my bez přemýšlení o tom, jen posuvné levé tři, představte si, že už se vytiskne 20 a 34 pro nás. A pak, když jsme se nakonec rekurzivně volejte posuv na pravdu, že bude správně tisknout 52, 59, a 106 pro nás. 

Takže za předpokladu, že to může tisknout 20, 34, a ostatní lze tisknout 52, 59, 108, všichni musíme být schopni udělat, je vytisknout sami ve středu, která. Takže vytisknout vše, co před námi. Vytisknout sami, takže aktuální uzel pro tisk 36, pravidelné printf, a pak tisknout vše, co po nás. 

DAVID J. Malan: To je místo, kde rekurze dostane opravdu krásné. Je to úžasný skok víry, kde budete dělat nejmenší kousek práce. A pak se nechat někoho jiný se postará o zbytek. A že někdo jiný Je ironií osudu, můžete. Takže pro závažné body za snaživost, pokud stiskněte navigační tlačítko nahoru na otázky - 

ROB BOWDEN: Na otázky? 

DAVID J. Malan: A trochu dolů na čísla, nevíte někdo, kde Tato čísla pocházejí z? 

ROB BOWDEN: Mám doslova tušení. 

DAVID J. Malan: Objevují celé kvíz. 

DIVÁKŮ: Jsou stejná čísla? 

DAVID J. Malan: Tato čísla. Trochu velikonoční vajíčko. Takže pro ty z vás, sledovat on-line na domů, pokud nám můžete říci, prostřednictvím e-mailu na heads@CS50.net co význam na tyto opakované šest čísel jsou celé Quiz 1, budeme sprchovat vás s úžasnou pozornost na finále přednáška a stres míček. Pěkné, jemné. 

ROB Bowden: Nějaké poslední otázky o něco na ten kvíz?