Reproduktor 1: Dobře, takže to je CS50 To je konec týdne pět. A připomenout, že minule jsme začal hledat na chovatele dat struktury, které začaly řešit problémy, které začaly zavádět nové problémy, ale, kterého by mělo byl druh závitem, které jsme začal dělat z uzlu do uzlu. Takže to je samozřejmě singly provázaný seznam. A jednotlivě propojeny, Myslím, že je jen jeden závit mezi každý z těchto uzlů. Ukázalo se, že můžete dělat milovník věci, jako je dvojnásobně spojových seznamů kdy máte šipku se v obou směrech, což může pomoci s některými účinností. Ale tento problém vyřešil? Jaký problém se to vyřešit? Proč se staráme v pondělí? Proč, teoreticky, se staráme v pondělí? Co to dělá? 

Diváků: Můžeme dynamicky změnit jeho velikost. 

Reproduktor 1: OK, tak můžeme dynamicky změnit jeho velikost. Výborně vás oba. Takže můžete dynamicky měnit velikost této struktura dat, zatímco pole, Připomeňme, musíte vědět priori, kolik místa chcete a pokud budete potřebovat trochu více prostor, jste trochu smůlu. Musíte vytvořit zcela nové pole. Musíte přesunout všechny vaše data z jednoho na druhého, nakonec osvobodil starý pole pokud je to možné, a pak pokračujte. Která se právě cítí velmi nákladné a velmi neefektivní, a ve skutečnosti, že může být. Ale to není všechno dobré. Platíme cenu, co byl jeden z více zjevné ceny my zaplatit pomocí propojeného seznamu? 

Diváků: Musíme použít dvojitý prostor pro každou z nich. Reproduktor 1: Jo, takže potřebujeme nejméně dvakrát tolik prostoru. Ve skutečnosti, jsem si uvědomil, tento obrázek je dokonce i trochu zavádějící, protože na CS50 IDE v mnoha moderních počítače, ukazatel nebo adresa není ve skutečnosti čtyři bajty. Je to velmi často tito dny osm bajtů, které znamená, že spodní část nejvíce obdélníky tam ve skutečnosti jsou trochu dvakrát velký jako to, co jsem se vyvodit, což znamená, že používáte třikrát jako velký prostor, jak bychom mít jinak. Nyní ve stejné době, my jsme stále mluvil bytů, ne? My ne nutně mluvit megabyty nebo gigabyty, není-li těchto údajů struktury dostat velký. 

A tak dnes začneme uvažovat jak bychom mohli prozkoumat údaje efektivněji, pokud v Skutečnost, data dostane větší. Ale pojďme se pokusit se získat kanonická operace první že si můžete dělat na tyto druhy datových struktur. Takže něco jako připojený Seznam obecně podporuje operace, jako smazat, vložit a vyhledávání. A co mám na mysli, že? To prostě znamená, že obvykle, pokud lidé používáte spojový seznam, oni nebo někdo jiný zavedla funkce jako mazat, vkládat, a vyhledávání, takže můžete skutečně něco dělat užitečné se strukturou dat. Takže pojďme se rychle podívat na to, jak bychom mohli realizovat nějaký kód pro propojeném seznamu takto. 

Tak to je jen některé C kód, Ani kompletní program že jsem opravdu rychle rozdmýchala. Není to on-line v distribuci kód, protože to nebude ve skutečnosti spustit. Nevšimnout jsem jen s komentář řekl, dot dot tečka, je tu něco, tam, dot dot dot, něco, co tam. A ať to jen podívat na jaké jsou šťavnaté díly. Takže na lince tři, Připomínáme, že toto je nyní jsme navrhli deklarovat uzel poslední čas, jeden z těchto obdélníkových objektů. Má int, že budeme volat N, ale my jsme to mohli nazvat cokoliv, a pak struct uzel hvězdu zvanou další. A jen aby bylo jasno, že druhým linka, na lince šest, co to je? Co to dělá pro nás? Vzhledem k tomu, to určitě vypadá více mystický než naše obvyklé proměnné. 

Diváků: To dělá to pohybovat po jednom. 

Reproduktor 1: Tak to je pohybovat po jednom. A abych byl přesnější, to bude ukládat adresu uzlu, který je určen k sémanticky vedle ní, že jo? Takže to nebude nutně přesunout nic. Je to jen bude uložení hodnoty, což je bude adresa nějakého jiného uzlu, a to je důvod, proč jsme řekli struct uzel hvězda, hvězda označující ukazatel nebo adresa. OK, tak teď, pokud předpokládáme, že máme tento N které máme k dispozici, a pojďme Předpokládejme, že někdo jiný má vloženo spoustu celých čísel do propojeného seznamu. A to spojový seznam je ukázal na nějakým bodem proměnná s názvem seznam, který je prošel v zde jako parametr, jak mám jít o linky 14, kterým se provádí vyhledávání? Jinými slovy, když jsem se provádí funkce, jejíž účel života je vzít int a pak se začátek propojeného seznamu, že je ukazatel na spojový seznam. Jako první, kdo se myslím, že David Byl to náš dobrovolník v pondělí, ukazoval na celý spojový seznam, je to, jako bychom předáváte David se jako naši argumentaci zde. Jak můžeme jít o pojížděním tento seznam? No, to ukáže, že i přesto, ukazatele jsou relativně nové nyní na nás, to, co můžeme udělat relativně přímočaře. 

Chystám se jít dopředu a deklarovat dočasnou proměnnou, která konvencí se jen tak být nazýván ukazatel, nebo PTR, ale jste to mohli nazvat, co chcete. A já jdu na inicializovat že na začátek seznamu. Takže se můžete trochu myslet na to jak se mě učitel na druhý den, druh ukázal na někoho mezi našimi lidmi jako dobrovolníci. Takže jsem dočasné proměnné, které je jen ukazuje na stejnou věc že naše shodou okolností s názvem dobrovolník David byl také poukázat. Nyní, když je ukazatel Není null, protože odvolání že null je nějaký speciální hlídka hodnota vymezuje konec seznamu, takže zatímco já nejsem ukazuje na zem jako náš poslední dobrovolníka byl, pojďme do toho a proveďte následující. Pokud pointer-- a teď jsem trochu chci dělat to, co jsme dělali se studentem structure-- pokud ukazatel tečka další equals-- spíše, je-li ukazatel dot N se rovná se rovná proměnná N se Argument, že to už prošel v, pak chci jít dopředu a říkají, vrátí hodnotu true. Zjistil jsem, že číslo N vnitřek jeden z uzlů mého spojového seznamu. Ale tečka již pracuje v této souvislosti, protože ukazatel, PTR, je skutečně ukazatel, adresu, jsme vlastně možné nádherně použijte konečně kus syntaxe že druh značek intuitivní smysl a vlastně použít šipky tady, což znamená, že jít od že adresa na celé číslo tam v. Takže je to velmi podobné duch operátorem tečky, ale proto, že ukazatel není ukazatel a ne skutečný struct sám o sobě, jsme právě pomocí šipky. 

Takže v případě, že aktuální uzel, že I je dočasná proměnná, jsem ukázal na není N, co chci dělat? No, s mými lidských dobrovolnících že jsme zde měli na druhý den, když je moje první člověk není ten, který jsem chtějí, a možná druhý člověk není jediná, kterou chci, a třetí, jsem je třeba, aby fyzicky v pohybu. Jako jak mohu procházet seznamem? Když jsme měli celou řadu ti, právě udělal jako já a navíc plus. Ale v tomto případě, stačí dělat ukazovátko, dostane, ukazatel, další. Jinými slovy, další pole je stejně jako všechny levých rukou že naše lidská dobrovolníci v pondělí byly pomocí poukázat na nějakém jiném uzlu. Ti, kteří byli jejich další sousedé. 

Takže pokud chci krokovat tohoto seznamu, Nemůžu prostě já a navíc už, Místo toho musím říci, Já, ukazatel, se děje rovnat bez ohledu na další pole, Další pole je, další pole, po všech těch levé ruce že jsme měli na jevišti polohovací některých dalších hodnot. A když jsem si přes že celá iterace, a konečně, jsem narazila null nemít nalezeno N přesto, jen jsem return false. Takže znovu, všechno, co tu děláme, dle obrázku před chvílí, začíná poukazem na jednání začátek seznamu pravděpodobně. A pak jsem zkontrolovat, je hodnota Hledám rovná devět? Pokud ano, vraťte jsem pravda a já jsem udělal. Pokud ne, mohu aktualizovat svou ruku, AKA ukazatel na bod v místě příští Arrow, a pak umístění při příštím Arrow, a další. Já jsem prostě prochází tomto poli. 

Takže znovu, koho to zajímá? Stejně jako to, co je to složka pro? No, připomenout, že jsme zavedli pojem stohu, který je abstraktní datový typ, pokud je to není věc C, to není CS50 věc, je to abstraktní nápad, tato myšlenka stohování věci na vrcholu jednoho jiný , které mohou být prováděny v svazky různých způsobů. A jeden způsob, jak jsme navrhovali byl s pole, nebo s propojeného seznamu. A ukázalo se, že kanonicky, je stack podporuje nejméně dvě operace. A buzz slova jsou tlačit, aby tlačit něco do zásobníku, jako nový zásobník v jídelna, nebo pop, což znamená, že za účelem odstranění vrchní zásobník ze zásobníku v jídelně hala, a pak možná někteří další operace stejně. Tak jak můžeme definovat strukturu že jsme nyní volá hromadu? 

No, máme všichni jsou k dispozici požadované syntax máme k dispozici v C. říkám, Dejte mi definici typu pro struct uvnitř zásobníku, Já jsem chtěl říct, je pole, na celá řada čísel a potom velikost. Takže jinými slovy, když budu chtít k provedení tohoto v kódu, nech mě jít, a tak nějak kreslit, co to říká. Tak to říká, dej mi struktura, která má pole, a já nevím, co je kapacita, Je to prý nějaká konstanta, že jsem definována na jiném místě, a to je v pořádku. Předpokládejme však, že je to jen jeden, dva, tři, čtyři, pět. Takže kapacita je 5. Tento prvek uvnitř mé struktura bude volaná čísla. A pak jsem potřebovat jiné proměnné zřejmě volal formát, který původně jdu stanovit je inicializován na nulu. Pokud není nic v zásobník, velikost je nula, a to je hodnoty odpadkové v číslech. Nemám ponětí, co je tam ještě ne. 

Takže pokud chci, aby se zasadila něco do zásobníku, Předpokládám, že volání funkce Push, a Říkám tlačit 50, jako číslo 50, kde byste navrhli Kreslím to v tomto poli? K dispozici je pět různých možných odpovědí. Kam chcete tlačit číslo 50? V případě, že cílem zde, opět, zavolejte funkce Push, předat argument 50, kde mám dát? Pět possible-- 20% šance hádat správně. Ano? 

Diváků: Daleko vpravo. 

Reproduktor 1: Zcela vpravo. Tam je nyní 25% šance hádat správně. Tak, že by vlastně v pořádku. Podle konvence, řeknu s řadou, bychom obecně začít na levé straně, ale mohli bychom určitě začít na pravé straně. Takže spoiler by zde bylo, že jsem pravděpodobně bude čerpat ji na levé straně, stejně jako v normálním poli kde I začít chodit zleva doprava. Ale pokud můžete převrátit aritmetický, v pořádku. Je to prostě není konvenční. OK, musím udělat jednu další změna ačkoli. Teď, když jsem tlačil něco do zásobníku, co bude dál? 

Dobře, musím zvýšit velikost. Tak nech mě jít dopředu a jen je aktualizuje, který byl nulový. A místo toho teď, jdu aby v hodnotě jedna. A teď, že jsem tlačit další Číslo do zásobníku, stejně jako 51. No, musím udělat ještě jeden změna, která je až do velikosti dvě. A pak, že jsem tlačit ještě jeden Číslo do zásobníku, jako je 61, teď musím aktualizovat velikosti jeden čas, a získat hodnotu 3 jako velikost. A teď, že jsem zavolat pop. Nyní pop, podle konvence, nebere argument. Se zásobníkem, celý bod metafory zásobníku je to, že nemáte prostor pro uvážení jít dostat, že zásobník, můžete vše, co udělat je pop jeden z nejvrchnější zásobníku, jen proto, že. To je to, co tato datová struktura dělá. 

Takže touto logikou, kdybych říkat pop, co přijde? Tak 61. Takže to, co opravdu je počítač, dělat v paměti? Co můj kód musíte udělat? Co byste navrhli měníme na obrazovce? Co by se mělo změnit? Litovat? Tak jsme se zbavit 61. Tak jsem si rozhodně udělat. A mohu zbavit 61. A pak to, co ostatní Změna se má stát? Velikost má pravděpodobně vrátit se do dva. A tak to je v pořádku. Ale počkejte chvíli, velikost před chvílí byl tři. Pojďme se jen udělat rychlou kontrolu zdravý rozum. Jak to víme, že jsme chtěl se zbavit 61? Vzhledem k tomu, že jsme praskání. A tak jsem tuto druhou velikost majetku. 

Počkej, já jsem vzpomínal na dvě týden když jsme začali mluvit o pole, kam tohle místo nula, toto bylo umístění jednoho, toto bylo umístění dvě, to je umístění tří, čtyř, to vypadá jako vztah mezi velikostí a prvek, že chci odstranit z pole se zdá být jen to, co? Velikost minus jedna. A tak to je, jak jako lidé víme, že šedesát jedna je na prvním místě. Jak to, že počítač bude vědět? Když váš kód, kde na vás pravděpodobně chcete udělat velikost minus jedna, takže třemi minus jedna jsou dvě, a to znamená, že chceme zbavit 61. A pak můžeme skutečně aktualizovat tak, aby velikost velikost nyní jde ze tří na pouhé dva. A jen proto, aby pedantský, jdu navrhnout, že jsem udělal, že jo? Ty navrhované intuitivně správně bych měl zbavit 61. Ale nemám já druh nějak zbavili 61? Já jsem skutečně zapomněl že je to vlastně tam. A myslíte, že zpět do PSET4, pokud jste dočetli Článek o forenzní, PDF že jsme měli kluci číst, nebo si bude číst tento týden PSET4. Připomeňme, že je to vlastně relevantní k celá myšlenka počítačové forenzní. Co je počítač obvykle dělá, je to prostě zapomene, kde je něco, ale to není jít a podobně pokusit se poškrábat, nebo ovládání ty kousky s nul a jedniček nebo nějaký jiný náhodný vzor pokud vy sám to záměrně. Takže vaše intuice byla Dobře, pojďme se zbavit 61. Ale ve skutečnosti, my nemusíme obtěžovat. Potřebujeme jen zapomenout, že je to tam změnou našeho velikost. 

Teď je tu problém s zásobníku. Kdybych neustále tlačí věci do zásobníku, co je zřejmě bude dít jen v několik okamžiků čase? Budeme chybět prostor. A co budeme dělat? Jsme trochu v háji. Tato implementace neumožňuje us změnit velikost pole, protože použití Tato syntaxe, pokud jste Vzpomeňte si na dvou týdnů, poté, co jste prohlásil, velikost pole, jsme neviděli mechanismus přesto, kde můžete změnit velikost pole. A skutečně C nemá tuto funkci. Když řeknete, dej mi pět NTHS, jim říkají čísla, to je všechno, budete si to. Takže teď budeme dělat od pondělí, má schopnost vyjadřovat řešení i když, jen je třeba štípnout definice našeho stohu nebýt nějaký pevně pole, ale jen proto, aby uložit adresy. 

Nyní, proč je to? Teď jen musíme být pohodlné s skutečnost, že když můj program běží, Já pravděpodobně bude se zeptat člověka, kolik čísel chcete uložit? Takže vstup má přijít odněkud. Ale jakmile já vím, že číslo, pak mohu jen použít to, co funkci, čímž se získá mi kus paměti? Mohu použít malloc. A můžu říct, libovolný počet bajtů Chci zpátky na tyto NTHS. A vše, co mám skladovat v číslech variabilní tady uvnitř tohoto struct by mělo být to, co? Co je to vlastně jde do Čísla v tomto případě? Jo, ukazatel na první byte tohoto kusu paměti, nebo více specificky, adresa z první z těchto bajtů. Nezáleží na tom, jestli je to jedno byte nebo miliarda bajtů, Jen musím starat o první. Vzhledem k tomu, co malloc záruky a můj operační systém zaručuje, je to, že kus paměti I si, že to bude být souvislé. Je tu nebude mezery. Takže pokud jsem požádal o 50 bajtů nebo 1000 bajtů, oni jsou všichni bude zády k sobě k sobě. A tak dlouho, jak si vzpomínám, jak velký, jak moc jsem požádal o, všechno, co potřebuji vědět Je to první taková adresa. 

Takže teď máme možnost v kódu. Ačkoli, že to bude trvat nás více času psát toto nahoru, jsme nyní mohli přerozdělit, že paměť Jen uložení jinou adresu zde Chceme-li větší, nebo dokonce menší kus paměti. Takže tady na kompromis. Teď jsme si dynamiku. Stále máme contiguousness jsem tvrdil. Vzhledem k tomu, malloc bude nám sousedící kus paměti. Ale toto je bude bolest v krk pro nás, programátor, skutečně kód nahoru. Je to prostě víc práce. Potřebujeme kód podobný tomu, co jsem byl bouchání se před chvílí. Velmi proveditelné, ale přidává složitost. A tak developer čas, programátor Doba je dalším zdrojem že bychom mohli muset strávit nějaký čas, aby se nové funkce. A pak samozřejmě je zde fronta. Nebudeme jít do toho člověk v hodně detailu. Ale je to velmi podobné duchu. Mohl bych implementovat fronty, a její odpovídající operace, Přidat do seznamu nebo dequeue, jako je přidat nebo odebrat, je to jen milovník způsob, jak říct to, Přidat do seznamu nebo dequeue takto. Mohu jen dát sám struct má celou řadu celou řadu, že opět, má to znovu velikost, ale proč teď potřebuji sledovat přední fronty? Nepotřeboval jsem vědět přední mého stacku. No, když jsem znovu pro queue-- Pojďme se jen těžko kódovat to jak mít jako pět celá čísla v potenciálně zde. Takže to je nula, jedna, dva, tři, čtyři. To bude znovu zavolal čísla. A to se bude nazývat velikost. 

Proč není dostačující mít jen velikost? Dobře, pojďme stiskněte tytéž čísla na. Tak jsem pushed-- I enqueued, nebo tlačil. Teď budu Zařadí 50, a poté 51, a pak 61, a dot dot dot. Tak to je Enqueue. I enqueued 50, pak 51, pak 61. A to vypadá totožně do komína tak daleko, kromě Já třeba, aby se jednu změnu. Musím aktualizovat této velikosti, takže jdu od nuly do jednoho na dva až tři nyní. Jak mohu dequeue? Co se stane s dequeue? Kdo by měl přijít z tohoto seznamu jako první pokud je to linka na Apple Store? Tak 50. Takže je to trochu složitější tentokrát. Vzhledem k tomu, naposledy to byl výborný snadné prostě velikost minus jedna, I dostat na konci svého pole účinně kde čísla jsou, odebere 61. Ale já nechci, aby odstranit 61. Chci se 50, který Byl tam v 5:00 hodin na line up pro Nový iPhone nebo kdoví co ještě. A tak, jak se zbavit 50, I Nemůžete prostě to udělat, ne? Můžu vyškrtnout 50. Ale my jsme řekli jen nemusí být tak anální jak na zelené louce, nebo skrýt data. Můžeme jen zapomněl, kde to je. 

Ale když změním velikost nyní dva, je to dostatečné informace vědět, co se děje v mém frontě? Opravdu ne. Stejně jako moje velikost je dva, ale kde se fronta začíná, zejména pokud Stále mám ta stejná čísla v paměti. 50, 51, 61 |. Tak jsem třeba mít na paměti, Nyní, kdy je přední. A tak, jak jsem navrhla nahoru tam budeme právě volal Nth přední, jejichž původní hodnota by měla být co? Zero, jen začátek seznamu. Ale teď kromě dekrementování velikost, právě jsme zvýšit přední. A teď je tu další problém. Takže jakmile jsem se jít dál. Předpokládejme, že se jedná o počet jako je 121, 124, a pak se, sakra, Jsem z vesmíru. Ale počkejte, já nejsem. Takže v tomto bodě příběhu, Předpokládejme, že velikost je jeden, dva, tři, čtyři, tak předpokládat, že velikost je čtyři, přední je jedna, takže 51 je na přední straně. Chci dát jiné číslo zde, ale, sakra, já jsem z vesmíru. Ale já nejsem, že jo? Tam, kde jsem mohl dát nějaké další hodnoty, jako je 171? Jo, mohl bych jen tak vrátit se tam, že jo? A pak vyškrtnout na 50, nebo prostě jej přepsat s 171. A pokud jste přemýšlel, proč náš počet se dostal tak náhodný, Tito jsou obyčejně přijata počítač přírodovědné předměty na Harvardu po CS50. Ale to byl dobrý optimalizace, protože teď jsem to plýtvání místem. Stále mám na paměti, jak velká ta věc je totální. Je to celkem pěti. Protože nechci, aby zahájit přepisování 51. Takže teď jsem ještě z vesmíru, takže stejný problém jako předtím. Ale můžete vidět, jak teď v kódu, budete pravděpodobně muset trochu psát více složitost, aby se to stalo. A ve skutečnosti to, co operátor v C pravděpodobně umožňuje budete magicky udělat kruhovitost? Jo, operátor modulo, znak procenta. Takže to, co je paráda asi fronty, i když jsme udržet kreslení pole jak tyto, jako rovných čar, pokud jste trochu přemýšlet o tom, jak zakřivení kolem jako kruh, pak stačí intuitivně to trochu funguje mentálně Myslím si, že trochu víc čistě. Ty by se ještě musí zavést že mentální model v kódu. Takže není tak těžké, nakonec, implementovat, ale stále ztratit size-- poněkud, schopnost změnit velikost, pokud to uděláme. 

Musíme se zbavit pole, my jej nahradit jediným ukazatelem, a pak se někde v mém kódu mám Příjem volání, jakou funkci skutečně vytvořit pole volaných čísel? Malloc, nebo nějaký podobný funkce, přesně tak. Jakékoliv dotazy týkající komínů nebo frontách. To jo? Dobrá otázka. Co modulo byste použili zde. Takže obecně, při použití mod, měli byste to udělat s velikostí Celá struktura dat. Takže něco jako pět nebo kapacity, je-li to je konstantní, je pravděpodobně zapojen. Ale jen to, modulo pět asi není dostačující, protože musíme vědět my zábal kolem zde nebo zde nebo zde. Takže vy jste pravděpodobně také bude chtít zapojit velikost věci, nebo přední proměnné stejně. Takže je to právě tento poměrně prostý aritmetický výraz, ale modulo bude klíčovou složkou. 

Tak krátký film chcete-li. Animace, že některé lidé na jiné vysoké škole dal dohromady, že máme přizpůsobené pro tuto diskusi. To zahrnuje Jack Učení fakta o frontách a statistiky. 

FILM: Kdysi dávno, tam byl chlápek jménem Jack. Když došlo k tomu, že přátelé, Jack neměl talent. Takže Jack šel mluvit s nejpopulárnější kluk věděl. On šel do Lou a zeptal se, co mám dělat? Lou viděl, že jeho přítel byl opravdu zoufalý. No, on začal, jen podívejte se, jak jste oblečen. Nemáte žádné šaty s jiným pohledem? Ano, řekl Jack. Jsem si jistý, ano. Pojď do mého domu a Ukážu vám je. A tak šli pryč, aby Jack. A Jack ukázal na políčko lou kde on držel všechny své košile, a jeho kalhoty, a jeho ponožky. Řekl Lou, vidím, že máte Všechny vaše oblečení v hromadu. Proč jste nosit nějaké jiní jednou za čas? 

Řekl Jack, dobře, když jsem odstranit oblečení a ponožky, I umýt je a dal je pryč v krabici. Pak přijde příští ráno, a já si hop. Chodím do boxu a získat moje oblečení z vrcholu. Lou rychle si uvědomil, problém s Jackem. Pořád oblečení, CD, a knihy v zásobníku. Když se dostal na něco ke čtení nebo opotřebení, že by si vybrat horní knihu nebo spodní prádlo. Pak, když byl hotov, by dal to zpátky. Back to půjde, na vrcholu zásobníku. Vím, že řešení, řekl vítězný Loud. Musíte se naučit začít používat frontu. Lou vzal Jackovy šaty a pověsil je do skříně. A když vyprázdnil krabice, prostě hodil. 

Pak řekl, nyní Jack, na konci roku den, dát své oblečení na levé straně když dal je pryč. Pak se zítra ráno, když vás vidět slunce, dostat své šaty Na pravé straně, od konce řádku. Copak nevidíš? řekl Lou. Bude to tak hezké. Budete nosit všechno jednou Než budete nosit něco dvakrát. A se vším v frontách v jeho skříni a policí, Jack začal cítit docela jistý sám sebou. Všechny díky Lou a Jeho úžasné fronta. Reproduktor 1: Dobře, to je rozkošný. Takže to, co se ve skutečnosti děje Na pod pokličku teď? Že máme ukazatele, že máme malloc, že máme schopnost vytvářet kusy paměti pro sebe dynamicky. Takže tohle je obrázek jsme zahlédl jen druhý den. My jsme opravdu přebývat na to, ale tento obrázek má se děje pod odsavač několik týdnů. A tak to znamená, jen obdélník, který jsme vyvodit, paměti počítače. A možná váš počítač, nebo CS50 ID, má gigabajt paměti nebo RAM nebo dva gigabajty nebo čtyři. Je to opravdu nezáleží. Váš operační systém Windows nebo Mac OS či Linux, v podstatě umožňuje program myslet si, že má přístup na celý rozsah paměť počítače, i když byste mohli být spuštěn více programů najednou. Takže ve skutečnosti, že ve skutečnosti nefunguje. Ale je to trochu iluze věnovat všechny své programy. Takže pokud jste měli dva koncerty RAM, toto je, jak se počítač může myslet na to. 

Nyní náhodně, jeden z nich věci, jeden z těchto segmentů paměti, se nazývá zásobník. A skutečně kdykoliv tak daleko v psaní kódu že jste volal funkce, například main. Připomeňme si, že kdykoli jsem Paměť Drawn počítače, Vždycky jsem tomu nějak polovina z obdélníku zde a neobtěžují mluvit o tom, co je výše. Protože když je hlavní volal, tvrdím, že jste si to plátek paměti že jde sem dolů. A pokud hlavní volal funkce jako odkládací prostor, dobře odkládací jde zde. A ukázalo se, že je to kde je to končí. Na takzvaný stoh vnitřní paměti vašeho počítače. Nyní se na konci dne, to je jen adresy. Je to jako bajt nula, byte jednoho, byte 2000000000. Ale jestli si myslíte, že o tom jako je obdélníkový objekt, všechno děláme každý Doba říkáme funkce vrstvení nový řez paměti. Dáváme tuto funkci plátek ze své vlastní paměti pro práci s. 

A teď připomínají, že je to důležité. Vzhledem k tomu, kdybychom se něco jako odkládací prostor a dvě lokální proměnné, jako je A a B a změníme tyto hodnoty z jedné a dvou na dva a jeden, odvolání že když se vrátí swapu, je to, jako by tento plátek paměti je prostě pryč. Ve skutečnosti, je to stále tam forenzně. A něco je ještě ve skutečnosti tam. Ale koncepčně, je to, jako i když je to úplně pryč. A tak hlavní nezná žádnou z prací která byla provedena v této funkci odkládacího pokud je to vlastně prošel v těch Argumenty ukazatelem nebo odkazem. Nyní, základní řešení k tomuto problému s swapu je kolem věci podle adresy. Ale ukazuje se, taky, co je se děje nad tuto část obdélníku celou dobu je Ještě je tu více paměti tam nahoře. A když dynamicky alokovat paměť, ať už je to uvnitř getString, který jsme dělali pro vás v CS50 knihovna, nebo jestli vy zavolat a zeptat se malloc operační systém pro kus paměť, nepochází ze zásobníku. To pochází z jiného místa v paměti počítače Tomu se říká haldy. A to není nic jiného. Je to stejné RAM. Je to stejná paměť. Je to jen RAM, který se děje tam místo tady dole. 

A tak co to znamená? No, pokud má počítač konečné množství paměti a zásobník se vyrůstal, takže mluvit, a haldy, podle k této šipky, roste dolů. Jinými slovy, každý Čas volání malloc, jste dána plátek paměti shora, pak možná o něco nižší, a pak trochu nižší, pokaždé, když budete volat malloc, haldy, je to použití, je druh roste, roste blíž a blíž k čemu? Stoh. Takže to zdá jako dobrý nápad? Mám na mysli, pokud to není opravdu jasné, co jiného můžete dělat, když jen mají omezené množství paměti. Ale to je určitě špatné. Tyto dva šípy jsou na Rychlokurz jeden o druhého. 

A ukázalo se, že špatný člověk, lidí, kteří jsou velmi dobré s programováním, a snaží se proniknout do počítačů, můžete využít tuto skutečnost. Ve skutečnosti, uvažujme trochu úryvek. Takže toto je příklad si můžete přečíst o podrobněji na Wikipedii. Budeme bod, který u článku, pokud zvědavý. Ale je tu útok obecně známý jako přetečení vyrovnávací paměti, že existuje tak dlouho, jak u lidí měli schopnost manipulovat paměť počítače, a to zejména v C. Tak to je velmi libovolný program ale pojďme ji přečíst zdola nahoru. Hlavní do argc char hvězdy argv. Takže je to program, který bere argumenty příkazového řádku. A všechny hlavní dělá zřejmě je výzva funkce, říkají F pro jednoduchost. A to projde v čem? Argv jednoho. Tak to přechází do F cokoliv slovo je, že uživatel zadaný do příkazového řádku po vyrobení Název programu vůbec. Takže stejně jako Caesar nebo Vigenère, který můžete připomenout děláte s argv. 

Takže to, co je F? F se v řetězci jako jeho jediný argument AKA char hvězda, stejná věc, jako řetězec. A je to jen svévolně bar v tomto příkladu. A pak char c 12, jen v Laicky řečeno, co je char c držák 12 dělá pro nás? Co to dělá? Přidělování paměti, konkrétně 12 bytů pro 12 znaků. Přesně tak. A pak poslední řádek, zamíchat a kopírování, pravděpodobně jste ještě neviděli. To je řetězec kopie funkce, jejíž účel života je zkopírovat svůj druhý argument do první argument, ale pouze do určitý počet bajtů. Takže třetí argument říká, kolik bajtů byste měli kopírovat? Délka tyče, bez ohledu na uživatel zadal. A obsahu bar, tento řetězec, jsou zkopírovány do paměti ukázal na při ° C 

Takže to vypadá trochu hloupé, a to je. Je to nepřirozený příklad, ale je to zástupce třídy vektorů útoku, způsob, jak útočit program. Všechno je v pořádku a dobré, pokud uživatel Typy ve slovech, která je 11 znaků nebo méně, plus zpětné lomítko nula. Co když uživatel zadá ve více než 11 nebo 12 nebo 20 nebo 50 znaků? Co je tento program bude dělat? Potenciálně seg chyba. Jde to slepě kopírovat vše, co v baru nahoru k jeho délce, což je doslova všechno, co v baru, do adresního ukázal na C. Ale ° C má jen preventivně uveden jako 12 bajtů. Ale není další kontrolu. Není-li podmínkách. Neexistuje kontrola tady žádná chyba. 

A tak to, co je tento program chystá udělat, je jen slepě kopírovat jednu věc na druhou. A tak, když čerpáme to jako obrázek, tady je jen tříska paměťového prostoru. Tak si všimnout na dně, jsme mají lokální proměnné bar. Tak, aby ukazatel, který to bude store-- spíše to, že místní argumentu, který je bude ukládat řetězec bar. A pak si všimnout jen nad ní ve stohu, protože pokaždé, když se ptáte pro paměť na zásobníku, to jde trochu nad ní obrazově, Všimněte si, že máme 12 bajtů tam. V levém horním z nich je C držák nula a vpravo dole nich je C držák 11. To je jen, jak se počítače chystá položit ji ven. Takže jen intuitivně, pokud bar má více než 12 znaků celkem, včetně zpětné lomítko nula, kde je 12 nebo C držák 12 jít? Nebo spíš, kde je 12. znak nebo 13. znak, sté postava jít skončit na obrázku? Nad nebo pod? 

Správně, protože i když stoh sám roste vzhůru, jakmile jste dal věci do to, že z konstrukčních důvodů, klade paměť od shora dolů. Takže pokud máte více než 12 bajtů, budete začít přepsat bar. Tak to je chyba, ale je to není opravdu velký problém. Ale je to velký problém, protože tam je více věcí se děje v paměti. Takže tady je návod, jak bychom mohli dal ahoj, aby bylo jasné. Pokud jsem napsal v ahoj na příkazovém řádku. H-E-L-L-O backslash nula, končí v rámci tyto 12 bajtů, a my jsme výborný bezpečí. Vše je v pořádku. Ale pokud píšu něco déle, případně je to chystá vplížit do baru prostoru. Ale ještě horší, to dopadá out celou tu dobu, i když jsme se nikdy nemluvil o to, zásobník se používá pro jiné věci. Není to jen lokální proměnné. 

C je velmi nízká úroveň jazyka. A to tak nějak tajně používá zásobník také mít na paměti, když se Funkce je volána, co je adresa z předchozí funkce, tak to může skočit zpět na tuto funkci. Takže když hlavní výzvy výměně, mezi věci tlačil do fronty nejsou jen swapy lokální proměnné, nebo její argumenty, také tajně tlačil do zásobníku, jak je znázorněno červeným řezu zde, je adresa hlavního fyzicky v paměti počítače, tak, že když je odkládací provádí, počítač ví, že je třeba se vrátit k hlavnímu a dokončit provedení hlavní funkci. Takže toto je nyní nebezpečné, protože pokud uživatel zadá v dobře více než ahoj, taková, že vstup uživatele clobbers nebo přepíše že červené úsek, logicky v případě, že počítač je prostě jít slepě předpokládat, že byty v tomto červeném plátek jsou adresa, na kterou by měl vrátit, co v případě, že protivník je dost chytrý, nebo štěstí dát posloupnost bytů tam, že vypadá jako adresa, ale je to adresa kódu že on nebo ona chce počítač provádět místo main? 

Jinými slovy, jestli to, co se Uživatel je psaní na výzvy, Není to jen něco, neškodný jako Dobrý den, ale je to vlastně kód, který je rovnocenný vymazat všechny soubory tohoto uživatele? Nebo e-mailem své heslo ke mně? Nebo začít protokolování jejich kláves, že jo? Existuje způsob, pojďme stanovit dnes, že by mohli zadejte není jen ahoj world nebo jejich jméno, mohli v podstatě předat kódů, nuly a ty, že je počítač chyby jak pro kód a adresu. Takže i když poněkud abstraktně, v případě, že uživatel zadá v dostatečném sporného kódu že budeme zobecnit zde A. A je útok nebo protivníci. Takže jen špatné věci. My se nestarají o čísla nebo nuly, nebo ty, dnes, takže můžete skončit přepisování, že červená část, Všimněte si, že pořadí bajtů. O 835 C nula osmi nula. A teď, když na Wikipedii článek zde navrhla, pokud si nyní skutečně začít označování bajtů v počítače paměť, co článek Wikipedie navrhující je, že to, co v případě, že adresa tohoto levém horním bytu je 80 C 0 3508. 

Jinými slovy, pokud je špatný chlap je dost chytrý s jeho nebo její kód skutečně vložit číslo, které zde odpovídá na adresu kódu on nebo ona injekčně do počítače, která dokáže oklamat počítač do něco dělat. Odstranění souborů, posílání e-mailů věci, čichání svůj provoz, doslova něco mohlo být vstřikuje do počítače. A tak přetečení vyrovnávací paměti útok ve svém jádru je jen hloupá, hloupá Prvořadým z pole, který neměl kontrolovat jeho hranice. A to je to, co je super nebezpečný a zároveň velmi výkonný v C je, že jsme skutečně mají přístup k kdekoli v paměti. Je to na nás, programátoři, kteří píší původní kód zkontrolovat délku zašít některého polí, že jsme manipulovali. Tak, aby bylo jasné, co je to oprava? Pokud bychom se vrátit k tomu kód, měl bych to nejen změnit délku tyče, co jinak bych měl zkontrolovat? Co jiného bych měl dělat, aby zabránit zcela tento útok? Nechci, aby jen slepě říct že byste měli zkopírovat tolik bajtů jako je délka tyče. Chci říci, kopírování as mnoho bajtů jako jsou v barech až do přidělené paměť, nebo 12 maximálně. Tak jsem potřebovat nějaký, pokud stav která dělá zkontrolujte délku tyče, ale pokud překročí 12, jen jsme pevný kód 12 jako maximální možné vzdálenosti. V opačném případě takzvaný vyrovnávací paměti overflow útoku se může stát. V dolní části těchto snímků, pokud jste zvědaví číst více je skutečný původní článek pokud byste chtěli, aby se podívat. 

Ale teď, mezi cenami Zde zaplatil byl neefektivní. Takže to byla rychlá nízká úroveň pohled na to, co Problémy mohou vznikat nyní, že jsme mají přístup do paměti počítače. Ale další problém, který jsme Už narazil v pondělí byl jen neefektivnost propojeného seznamu. Jsme zpátky do lineárního času. Máme již nemají souvislou řadu. Nemáme náhodný přístup. Nemůžeme použít hranatou závorku notace. Máme doslova muset použít while jako ten, který jsem napsal před chvílí. Ale v pondělí, jsme tvrdili, že můžeme vplížit zpět do říše účinnosti dosažení něco, co je logaritmický možná, nebo nejlepší přesto, možná i něco, co je tzv časová konstanta. Tak jak můžeme udělat, že při použití tyto nové nástroje, tyto adresy, těchto ukazatelů, a řezání závitů věci vlastní? No, předpokládám, že tady, to jsou banda čísel, které chceme uložit v struktura a vyhledávání dat efektivně. Můžeme zcela přetočit do týdne dva, hodit je do pole, a vyhledávání je pomocí binárního vyhledávání. Rozděl a panuj. A ve skutečnosti jste napsal binární vyhledávání v PSET3, kde jste zavedli program find. Ale víte co. Tam je trochu více chytrý způsob, jak toho dosáhnout. Je to trochu víc sofistikované a to možná nám umožňuje vidět, proč binární Vyhledávání je tak mnohem rychlejší. Za prvé, pojďme představit pojem stromu. Které, i když v reality stromy druh rostou jako to, ve světě počítačů věda, že druh rostou směrem dolů jako rodinný strom, kde máte vaši prarodiče nebo prarodiče nebo kdoví co ještě na vrcholu, patriarcha a matriarch rodiny, jen jeden tzv kořen, uzel, níže které jsou jeho děti, pod kterou jsou jeho děti, nebo jeho potomci obecněji. A někdo visí spodní rodiny tree, vedle být nejmladší v rodině, může být jen také obecně volal listy stromu. 

Tak to je jen banda slov a definic pro něco, co se nazývá strom v počítači věda, podobně jako rodokmenu. Ale je tu milovník inkarnací stromů, z nichž jedna se nazývá binární vyhledávací strom. A můžete druh vtipálek kromě toho, co tahle věc dělá. No, je to binární v jakém smyslu? Odkud binární pochází tady? Litovat? To není ani tak nebo. Je to spíše, že každý z uzlů nemá více než dvě děti, protože zde vidíme. Obecně platí, že tree-- a vaši rodiče a prarodiče může mít tolik dětí, nebo vnoučata, jak se ve skutečnosti chtějí, a tak například tam máme tři děti z toho pravého uzlu, ale v binárním stromu, uzel má nula, jedna nebo dvě děti maximálně. A to je pěkná vlastnost, protože pokud je limitován dvěma, budeme moci si trochu log základnu dvou akce děje nakonec. Takže máme něco logaritmické. Ale o tom více za chvíli. Vyhledávací strom znamená, že čísla jsou uspořádány tak, že levá dítěte hodnota je větší než kořene. A jeho právo dítě větší než kořene. Jinými slovy, pokud budete mít některý z uzly, kruhy v tomto obrázku, a dívá se na její levé straně Dítě a jeho právo dítěte, První by měla být nižší než, druhá by měla být větší než. Takže zdravý rozum zkontrolovat 55. Je to nechal dítě je 33. To je méně než. 55, jeho právo dítě je 77. To je větší než. A to je rekurzivní definice. Mohli bychom zkontrolovat každý jeden z těch, uzly a stejný vzor by se držet. 

Takže to, co je milé v binární vyhledávací strom, je že jeden, můžeme jej realizovat s struct, stejně jako tato. A i když jsme házení spousta staveb na dosah, oni jsou poněkud intuitivní teď nadějně. Syntaxe je stále tajemný pro jistotu, ale obsah uzlu v této context-- a držíme pomocí uzlu slovo, ať už je to obdélník na obrazovku nebo do kruhu, je to jen nějaký obecný kontejner, V tomto případě stromu, jako je ta jsme viděli, potřebujeme číslo v každém z uzlů a pak jsem třeba dva ukazatelů ukazujících do levého dítě a pravé dítě, v tomto pořadí. Tak to je to, jak bychom mohli nářadí, které v Struct. A jak bych mohl realizovat ji v kódu? Dobře, pojďme se rychle podívejte se na tento malý příklad. Není to funkční, ale já jsem zkopírovat a vložit tuto strukturu. A když je moje funkce pro binární vyhledávací strom se nazývá hledání, a to trvá dva argumenty, celé číslo N a ukazatel do uzlu, takže ukazatel na stromu nebo ukazatel ke kořeni stromu, Jak mám jít o hledání N? No, v první, protože jsem jednání s ukazateli, Budu dělat kontrolu zdravý rozum. Pokud strom rovná rovná null, je N v této větvi nebo není v této větvi? To nemůže být, že jo? Jestliže jsem v minulosti null, tam nic není. Já bych mohl také právě slepě říkají return false. Pokud mi nic, rozhodně nemůžu najít libovolný počet N. Takže co jiného bych mohl zjistit teď? Chystám se říct i jinak, pokud N je menší než to, co je v uzlu stromu že jsem byla předána hodnota n. Jinými slovy, pokud je číslo nejsem hledá, N, je menší, než uzel že jsem při pohledu na. A uzel se dívám u se nazývá strom, a vyvolat z předchozího příkladu se dostat na hodnotu v ukazateli, Používám notaci se šipkou. Takže pokud N je menší než stromu šipky N, chci koncepčně jít doleva. Jak mohu express vyhledávání odešel? Aby bylo jasno, zda se jedná obraz v otázce, a byl jsem prošel, že nejvyšší šipka, která je směrem dolů. To je můj strom ukazatel. Já jsem ukázal na kořen stromu. A já hledám řekněme, pro číslo 44, libovolně. Je menší než 44, nebo větší než 55 zřejmě? Takže je to méně než. A tak, pokud podmínka platí. Tak koncepčně, co chci hledat další, když jsem hledal 44? To jo? 

Přesně tak, chci vyhledávat levé dítě, nebo doleva sub-strom obrázku. A ve skutečnosti, dovolte mi, abych prostřednictvím obrázek tady dole jen na chvíli, protože Nemůžu poškrábání to. Pokud začnu tady na 55, a Vím, že hodnota 44 Já jsem hledal je levá, je to druh jako se trhá telefonní seznam v polopenze nebo trhání strom na polovinu. Já už muset starat o Celá tato polovina stromu. A přesto, zvědavě v termínech struktura, tohle tady, že začíná 33, které samo o sobě je binární vyhledávací strom. Řekl jsem to slovo rekurzivní dříve, protože ve skutečnosti to je datová struktura, která podle definice je rekurzivní. Možná budete mít strom, který je tento velký, ale každý z jejích dětí představuje strom jen trochu menší. Namísto toho, že děda nebo babička, teď je to jen máma nebo-- Nemůžu say-- není máma nebo táta, to by bylo divné. Místo toho tam dvě děti by byl jako bratr a sourozenci. Nová generace rodinného stromu. Ale strukturálně, je to stejný nápad. A ukázalo se, že mám funkci s nimiž mohu vyhledávat binární vyhledávání strom. Nazývá se vyhledávání. I hledat N ve stromu Šipka doleva else if N je větší než hodnota že jsem v současné době. 55 v příběhu před chvílí. Mám funkci nazvanou Hledání, který mohu jen projít N a to rekurzivně vyhledávání sub-strom a právě návrat co to odpověď. Jinak mám nějaké finální základní případ tady. 

Jaká je konečná případ? Strom je buď nulový. Hodnota jsem buď hledal je menší než, nebo větší než nebo rovna to. A mohl bych říct, rovná rovni, ale logicky je to což odpovídá jen říkám, že tady jinde. Takže pravda je, jak jsem se něco najít. Tak doufejme, že to je ještě přesvědčivější příklad než stupidní funkce sigma jsme udělali několik přednášek zpět, kde to bylo stejně snadné používat smyčku spočítat všechna čísla od jedničky N. Zde s datovou strukturu který sám o sobě je rekurzivně definované a rekurzivně vyvodit, teď jsme mají schopnost vyjádřit sebe V kódu, který sám o sobě je rekurzivní. Tak to je přesně stejný kód zde. 

Takže to, co další problémy můžeme vyřešit? Tak rychlý krůček od stromy na chvilku. Zde je, řekněme, pod německou vlajkou. A je tu jednoznačně vzor tohoto parametru. A je tu spousta Vlajky na světě, který jsou tak jednoduché, jak je to z hlediska jejich barev a vzorů. Ale předpokládejme, že tento je uložen jako GIF, nebo JPEG, nebo bitmapové, nebo ping, jakýkoli grafický formát souboru , se kterým jste se seznámili, z nichž některé jsme hrát s v PSET4. To se zdá jako velice užitečné pro ukládání Černý pixel, černý pixel, černý pixel, tečka, tečka, tečka, celá parta černé pixely pro první scanline, nebo řádku, pak celá parta stejné, pak se celý svazek of stejné, a pak Celá banda červených pixelů, červené pixely, červené pixely, potom celý banda žlutých pixelů, žlutá, že jo? 

Je tu takový neefektivnost sem. Jak byste intuitivně stlačit pod německou vlajkou pokud se provádí jako soubor? Jako jaké informace nemůžeme obtěžovat ukládání na disk v pořadí snížit naši velikost souboru z podobně megabajt na kilobyte, něco menší? V čem spočívá redundance zde musí být jasné? Co jsi to mohl udělat? To jo? Přesně tak. Proč raději než vzpomenout barva každého pixelu zašít stejně jako to děláte v PSET4 s formátem bitmapový obrázek, proč si prostě představují vlevo sloupec obrazových bodů, například banda černých pixelů, parta červené a banda žluté, a pak už jen nějak zakódovat idea Opakujte tento 100 krát nebo zopakovat tento 1,000 časů? V případě, 100 nebo 1000, je jen číslo, takže si může dostat pryč jen s jedním číslem namísto stovek nebo tisíců dodatečných pixelů. A opravdu, to je, jak jsme by mohlo stlačit pod německou vlajkou. A A teď, co o francouzskou vlajkou? A trochu jakýsi mentální cvičení, které vlajka mohou být komprimovány více na disku? Německé vlajky nebo francouzská vlajky, vezmeme-li tento přístup? Německá vlajka, protože tam je více horizontální redundance. A podle návrhu, mnozí grafický soubor formáty skutečně pracovat jako rozkladové řádky horizontálně. Mohly by fungovat vertikálně, jen lidstvo Před lety se rozhodli, že budeme obecně myslet na věci, řady řádkem namísto řádku po řádce. Takže opravdu, pokud jste byli se podívat na soubor velikost německou vlajkou a francouzštině flag, tak dlouho, dokud je rozlišení stejné, stejnou šířku a výška, tahle Zde bude větší, protože muset opakovat sami třikrát. Musíte zadat modrá, opakování sami, bílá, opakovat sami, červená, opakovat se. Nemůžete prostě jít all cesta doprava. A jako stranou, aby se zrušte komprese je všude, pokud se jedná o Čtyři rámy z video-- vás by mohl připomenout, že filmu nebo video je obecně jako je 29 nebo 30 snímků za sekundu. Je to jako malé flip knihy, kde vás Jen viz obrázek, obrázek, image, image, image prostě super rychlý, takže to vypadá, herci na obrazovce se pohybují. Zde je bumble včela na Vrchol kytice. A i když to by mohlo být trochu těžké vidět na první pohled, Jediná věc, pohybující se v tento film je včela. 

Co je němý o skladování Video nekomprimované? Je to druh odpadu pro ukládání videa jako čtyři téměř identické obrazy, které se liší pouze v případě, kdy je včela. Můžete zahodit většinu těchto informací a pamatovat si jen, například, první snímek a poslední snímek, klíčové snímky, pokud jste někdy slyšel slovo, a jen uložit do prostřední kde včela je. A nemusíte se ukládat všechny růžové, a modré, a zelené hodnoty stejně. Tak tohle je jen říct, že komprese je všude. Jedná se o techniku ​​často používáme nebo považuje za samozřejmost v těchto dnech. 

Ale jak si komprimovat text? Jak se vám jít o kompresi textu? No, každý ze znaků v ASCII je jeden bajt, nebo osm bitů. A to je trochu hloupá, že jo? Vzhledem k tomu, budete pravděpodobně typu A a E a I a O a U hodně častěji než jako W nebo Q nebo Z, v závislosti na jazyk, ve kterém píšete určitě. A proč jsme s použitím osm bitů pro každé písmeno, včetně nejméně populární dopisy, že jo? Proč ne použít méně bitů pro Super populární dopisy, jako E, věci, které hádat nejprve v Wheel of Fortune, a používat více bitů pro méně populární dopisy? Proč? Protože jsme jen tak používat méně často. 

No, to ukáže, že tam mají Byl pokusy, jak toho dosáhnout. A pokud si vzpomínáte ze stupně škola nebo vysoká škola, Morseova abeceda. Morseova abeceda má tečky a pomlčky, které mohou být přenášeny po drátě as zvuky nebo signály nějakého druhu. Ale Morseova abeceda je super čistý. Je to trochu binárního systému že máte tečky nebo čárky. Ale když vidíte, například, dvě tečky. Nebo pokud si myslíte, zpět na provozovatele kteří chodí jako píp, píp, pípnutí, pípnutí, bít trochu spoušť který vysílá signál, pokud vás, příjemce, obdrží dvě tečky, jakou zprávu jste obdrželi? Zcela libovolné. 

I? I? Nebo co about-- nebo já? Možná to bylo jen dva E má pravdu? Takže tam je to problém z decodability s Morse kód, přičemž pokud se osoba zasílání zprávy ve skutečnosti se zastaví, takže si můžete třídit podle vidět nebo slyšet mezery mezi písmeny, že to není dostačující jen Poslat proudu nul a jedniček, nebo tečky a čárky, protože tam je dvojznačnost. E je jediná tečka, takže pokud vás viz dvě tečky nebo slyšet dvě tečky, Možná je to dva E je nebo možná je to jedna I. Takže potřebujeme systém, který je málo chytřejší než to. Takže muž jménem Huffman let Před přišli s přesně tohle. Takže jsme jen tak vzít rychlý pohled na to, jak stromy jsou pro projednávanou. Předpokládejme, že je to nějaký hloupý zpráva, kterou chcete odeslat, složený z pouhých A, B, C je D'S a E je, ale je tu spousta redundance sem. Není to znamená být angličtina. To není šifrována. Je to jen hloupá zpráva se spoustou opakování. Takže pokud jste opravdu počítat se všechny A to, B je, je C, D's, a E je, tady je frekvence. 20% z dopisů jsou A je 45% z dopisů jsou E je, a další tři frekvence. Počítali jsme tam ručně a právě udělal matematický. 

Tak to dopadá, že Huffman, před nějakým časem, si uvědomil, že, víte, co, když jsem začít stavět strom nebo les stromů, chcete-li, takto, mohu udělat následující. Chystám se dát uzlu ke každému z dopisů, které jsem záleží a budu ukládat uvnitř tohoto uzlu frekvence jako pohyblivé řádové čárce hodnota, nebo můžete použít N, taky, ale my budeme stačí použít float zde. A algoritmus, který navrhl je, že jste tento les jednoho uzlu stromy, takže extra krátké stromy, a začnete je spojují s nové skupiny, nové rodiče, chcete-li. A to tím, že volbě dvě nejmenší frekvencí najednou. Tak jsem vzal 10% a 10%. I vytvořit nový uzel. A já říkám nového uzlu 20%. 

Kteří dva uzly I kombinovat dál? Je to trochu nejasné. Takže tam je několik případů roh zvážit, ale udržet věci dost, Budu volit 20% - I nyní ignorovat děti. Budu volit 20% a 15% a kreslit dva nové hrany. A nyní, kdy jsou dvě uzly mám logicky kombinovat? Ignorovat všechny děti, jsou všechny vnoučata, stačí se podívat na kořeny teď. Kteří dva uzly mám svázat dohromady? Bod dva a 0.35. Dovolte mi tedy kreslit dva nové hrany. A pak jsem se dostal jen jeden vlevo. Tak tady je to strom. A to byl vypracován záměrně vypadat trochu hezká, ale všimněte si, že hrany mají Také byl označen nulou a jedničkou. Takže všechny levého okraje jsou nulové libovolně, ale důsledně. Všechny hrany jsou ty správné. 

A tak to, co Hoffman Navrhuje se, Chcete-li reprezentovat B, spíše než představují počet 66 as ASCII, který je osm celé bitů, Víš co, jen obchod vzor nula, nula, nula, nula, protože to je cesta z mého stromu, pana Huffmanův strom, na listu z kořene. Pokud chcete uložit E, naproti tomu nemají poslat osm bitů, které představují E. Místo toho, co poslat vzor bitů? One. A co je příjemné na tom je, že E je nejpopulárnější dopis, a používáte Nejkratší kód pro ni. Příští Nejoblíbenější dopis vypadá, že byl A. A tak, kolik bitů udělal navrhují použití za to? Nula, jedna. 

A protože je implementováno jak tohoto stromu, prozatím dovolte mi, abych stanoví, že je žádná nejasnost jako v Morse kód, protože všechny dopisy vám záleží jsou na konci těchto hran. Tak to je jen jeden Aplikace stromu. To je-- a budu mávat moje ruka se na to, jak na Vás může provádět toto jako struktura C. Potřebujeme jen kombinovat symbol, jako char, a frekvence doleva a doprava. Ale pojďme se podívat na dva Konečné příklady, které budete dostat docela obeznámeni s po kvíz nula problém nastavit pět. 

Takže tam je datová struktura známý jako stolu mřížky. A hash tabulka je druh ochladí se tím, že korečky. A předpokládám, že tam je čtyři kbelíky tady, pouhé čtyři mezery. Zde je balíček karet, a je zde klubu, rýč, klub, diamanty, klub, diamanty, klub, diamanty, clubs-- takže to je náhodné. Hearts, hearts-- takže jsem bucketizing veškeré vstupy sem. A A potřebuje hash table podívat se na váš vstup, a pak ji do určité položte na základě toho, co vidíte. Je to algoritmus. A já jsem byl s použitím super jednoduché vizuální algoritmus. Nejtěžší část, která byla si vzpomněl, jaké obrázky byly. A pak je tu celkem čtyři věci. 

Nyní komíny rostly, což je záměrná návrh věc tady. Ale co jiného bych mohl udělat? Takže vlastně tady máme banda staré školy zkoušky knih. Předpokládejme, že banda Jména studenti jsou tady. Tady to větší hash tabulky. Namísto čtyř věder, Jsem, řekněme 26. A my jsme nechtěli jít půjčit 26 ze zemí mimo [? Annenberg?], Tak tady je pěti které reprezentují A až Z. A pokud já viz studentem, jehož jméno začíná na A, Chystám se dát jeho nebo její kvíz tam. Pokud někdo začne s C, tam, Je-- skutečnosti, nechtěl udělat. B jede sem. Tak jsem dostal A a B a C a teď tady je další student. Ale pokud to hash tabulka implementován s matici Jsem typ šroubované v tomto bodě, že jo? Tak nějak jsem potřebujete, aby to někde. 

Takže jeden způsob, jak mohu řešit to, všechno vpravo, A je zaneprázdněn, B je zaneprázdněn, C je zaneprázdněn. Chystám se ho dát do D. Takže na První, mám náhodný okamžitý přístup ke každé z lopatek pro studenty. Ale teď je to trochu přenesl do něčeho lineární, protože když chci hledat někoho, Název jehož začíná, já podívejte se sem. Ale pokud to není A Student Hledám, Tak nějak jsem musel spustit kontrolu kbelíky, protože to, co jsem udělal Bylo to trochu lineárně zkoumat strukturu dat. Hloupá způsob jak říci, stačí se podívat za první dostupné otvoru, a dal jako plán B, abych tak řekl, nebo plán D v tomto případě je hodnota V tomto místě namísto. Je to jen proto, aby, pokud jste dostal 26 míst a žádní studenti s názvem Q nebo Z, nebo něco podobného že přinejmenším používáte prostor. 

Ale my jsme již viděli více Chytrá řešení tady, že jo? Co byste dělali, místo Máte-li ke kolizi? Pokud se dva lidé mají název A, co by byli chytřejší a více intuitivní řešení než jen Uvedení kde D má být? Proč nemůžu prostě jít mimo [? Annenberg?], jako je malloc, jiného uzlu, dát to tady, a pak dal, že student zde. Tak, že jsem v podstatě mají nějaký pole, nebo možná více elegantně, jak jsme Začínáme vidět propojeného seznamu. 

A tak hash tabulky je struktura které by mohly vypadat přesně takhle, ale chytře, jste něco jako samostatný řetězení, přičemž hash tabulky docela jednoduše je pole, každý z jejíž prvky není číslo, je sám o sobě spojen seznam. Tak, že máte super rychlý přístup rozhodování o tom, kde se vaše hash hodnotu. Podobně jako u příkladu karty, Udělal jsem mimořádně rychlé rozhodování. Hearts jde tady, diamanty jde zde. Já taky, A tady jde, D jde tady, B jde zde. Takže super rychlé look-ups, a pokud jste náhodou narazit na případu kde jste dostal kolize, dva lidé se stejným názvem, no a pak stačí začít spojovat dohromady. A možná si udržet je seřazena abecedně, možná ne. Ale aspoň teď máme dynamiku. Takže na jedné straně máme velmi rychlé konstantní čas, a druh lineárního času zapojit, pokud těchto spojových seznamů začne být trochu dlouho. 

Takže tento druh hloupý, geeky vtip před lety. Na CS50 hack-a-Thon, Když studenti check in, některé TF nebo CA každý rok si myslí, že je to legrační, aby se znamení jako je tento, kde jde jen znamená, že pokud vaše jméno začíná s A, jít touto cestou. Pokud se spustí Vaše jméno s B, jděte tohle-- OK, je to legrační možná později v semestru. Ale je tu další způsob, jak toho dosáhnout, taky. Vrať se k tomu. 

Takže je tu tato struktura. A to je náš poslední struktura pro dnešek, což je něco, co nazývá trie. T-R-I-E, která z nějakého důvodu je krátká pro vyhledávání, ale je to jen trie. Takže Trie je další zajímavá amalgám z mnoha těchto nápadů. Je to strom, který jsme viděli dříve. Není to strom binárního vyhledávání. Je to strom s libovolným počtem dětí, ale každý z dětí v trie je pole. Pole velikosti, řekněme, 26 nebo možná 27 Chcete-li podpořit pomlčkou jména nebo apostrofy v názvech lidí. 

A tak to je datová struktura. A když se podíváte z vrcholu dolů, jako když podívejte se na horním uzlu tam, M, je ukazující na nejvíce vlevo věc tam, který je potom A, X, W, E, L, L. To je jen datová struktura, která libovolně je ukládání jmen lidí. A Maxwell je uložen právě tímto cesta z pole na pole do pole. Ale co je to úžasné asi trie je že, vzhledem k tomu, Google seznamu a dokonce pole, to nejlepší, co jsem kdy dostal, je lineární čas nebo logaritmické čas hledáte někdo up. V této datové struktuře trie, pokud je to můj datová struktura má jedno jméno v něm a já jsem hledal Maxwella, já jsem že ho docela rychle najít. Já se jen podívat na M-A-X-W-E-L-L. Jestliže Tato datová struktura, naopak pokud N je milion, jestli je milión jména v této datové struktury, Maxwell se ještě bude zjistitelný po právě M-A-X-W-E-L-L, kroky. A David-- D-A-V-I-D kroky. Jinými slovy tím, že stavební datová struktura, která je dostal přičemž všechny z těchto polí, vše samy podporují náhodný přístup, Můžu začít vzhlédl lidí'S název pomocí množství času, který je úměrný ne číslo věcí v datové struktury, jako milion existující jmen. Množství času to trvá mi najít M-A-X-W-E-L-L v této datové struktury je úměrný není na velikost datové struktury, ale k délce názvu. A Realisticky Jména díváme nahoru se nikdy nebude blázen dlouho. Možná, že někdo má 10 znak jméno, název 20 znaků. Je to určitě konečný, že jo? Tam je člověk na Zemi, který má nejdelší název, ale to jméno je konstantní hodnota délky, ne? To se nemění v žádném smyslu. Takže tímto způsobem, máme dosáhla datovou strukturu že je konstantní doba look-up. Je to trvat řadu kroků v závislosti na délce vstupu, ale ne množství názvu v datové struktuře. Takže pokud budeme zdvojnásobit počet jmen v příštím roce z miliardy do dvou miliard, nález Maxwell bude trvat přesně stejný počet sedmi stupních ho najít. A tak se zdá k dosáhli náš svatý grál doby chodu. 

Takže pár rychlých oznámení. Kvíz nula se blíží. Více o tom na internetových stránkách Course během příštích pár dní. Pondělní lecture-- je to svátek tady na Harvardu v pondělí. Není to v New Haven, takže bereme třídu do New Havenu pro přednášku v pondělí. Vše bude natočen a sledovat živě jako obvykle, ale pojďme skončit dnes s 30 druhého klipu zvané "hluboké myšlenky" podle Daven Farnham, který byl inspirován v loňském roce v sobotu Night Live "hluboké myšlenky" Jack Handy, který by nyní měla smysl. 

FILM: A teď, "Hluboké Myšlenky "od Daven Farnham. Hash tabulky. 

Reproduktor 1: Dobře, to je pro teď. Uvidíme se příští týden. 

DOUG: Chcete-li jej vidět v akci. Takže pojďme se podívat na právě teď. Takže tady máme netříděného pole. 

IAN: Doug, můžete jít dopředu a restart to jen na jednu sekundu, prosím. Dobře, kamery jsou rolovací, tak akce vždy, když budete připraveni, Doug, OK? DOUG: Dobře, takže to, co jsme zde je netříděný pole. A já jsem barevné všech prvků červeně, což znamená, že to je, ve skutečnosti, netříděný. Takže připomenout, že první věc, kterou děláme je třídíme na levé polovině pole. Pak jsme třídit právo polovina pole. A ya-da, da-ya, ya-da, jsme je spojit dohromady. A máme úplně setříděné pole. Tak to je, jak sloučit nějak funguje. 

IAN: Whoa, hej, hej, střih, střih, střih, řez. Doug, nemůžeš ya-da, ya-da, ya-da, si cestu přes sloučení druhu. 

DOUG: Jen jsem udělal. To je v pořádku. Jsme dobré jít. Pojďme se jen držet válcování. Tak jako tak, 

IAN: Musíte vysvětlit to ve větší míře, než to. To je prostě nestačí. DOUG: Ian, my ne je třeba se vrátit do jednoho. To je v pořádku. Takže tak jako tak, pokud budeme pokračovat s merge-- Ian jsme v polovině natáčení. 

IAN: Já vím. A my nemůžeme jen ya-da, ya-da, ya-da, celý proces. Musíte vysvětlit, jak Obě strany si spojil. 

DOUG: Ale máme už vysvětlil, jak dva sides-- 

IAN: Právě jste zobrazeny jim merge pole. DOUG: Znají proces. Jsou v pořádku. Šli jsme přes to desetkrát. 

IAN: Právě jsi přeskočil hned nad ním. Vracíme se do jednoho, vy nemůžeš ya-da, ya-da přes ni. Dobře, zpátky do jednoho. 

DOUG: Musím se vrátit přes všechny snímky? Můj bože. Je to jako již pošesté, Ian. To je v pořádku. 

IAN: Dobře. Jste připraveni? Skvělý. Akce.