[Přehrávání hudby] David J. Malan: Dobře. To je CS50. To je týden pět pokračuje, a my nějaké dobré zprávy a špatné zprávy. Takže dobrá zpráva je, že CS50 zahajuje tento pátek. Máte-li zájem se k nám připojit, zamiřte do obvyklé adrese zde. Ještě lepší zpráva, ne přednáška letos v pondělí 13.. O něco méně lepší zprávy, kvíz nula je příští středu. Více informací může být naleznete na této adrese zde. A v příštích pár dní budeme vyplňovat prázdná místa s ohledem na pokojích že budeme mít vyhrazena. Lepší zprávou je, že tam budu být přezkum samozřejmě celé Zasedání letos Pondělí ve večerních hodinách. Zůstaňte naladěni na kurzu je Internetové stránky pro umístění a podrobnosti. Sekce, a to i když se jedná o dovolená, zobrazí se také setkat také. Nejlepší novinky, přednáška příští pátek. Tak to je tradice nám mají podle osnov. Jen--, že to bude úžasné. Uvidíte věci, jako je datové struktury konstantní časové a hashovací tabulky a stromy a snaží se. A budeme mluvit o problémech narozenin. Celá parta věcí čeká příští pátek. OK. Tak či onak. Takže připomenout, že jsme byli se zaměřením na obrázku o tom, co je vnitřní paměti našeho počítače. Takže je paměť RAM, nebo tam, kde programy existuje, když jste jim běží. Pokud poklepete na ikonu spustit nějaký program, nebo poklepejte na icon otevřít některé soubory, je nabitá z vašeho pevného disk nebo jednotku SSD do paměti RAM, Random Access Memory, kde žije, dokud se nevypne napájení, víko notebooku se zavře, nebo ukončení programu. 

Nyní, paměť, z které pravděpodobně máte 1 GB v těchto dnech, 2 GB, nebo dokonce mnohem více, je obecně stanoveno pro daný program v tomto druhu pravoúhlého konceptuální model čímž máme zásobníku ve spodní části a spoustu dalších věcí, na vrcholu. Jde o to, na samém vrcholu jsme viděli na obrázku dříve, ale nikdy nemluvil o je takzvaný textu segmentu. Text segment je jen ozdobný způsob, jak říkat nuly a ty, které vytvořte aktuální zkompilovaný program. 

Takže když poklepete Microsoft Word v počítači Mac nebo PC, nebo při spuštění tečka lomítko Mario na Linux počítač v okně vašeho terminálu, nuly a ty, které se skládají Word a Mario jsou dočasně uloženy v paměti RAM počítače v takzvané Text segmentu pro konkrétní program. Pod tím jde inicializován a neinicializovaná údaje. To je věc jako globální proměnné, že jsme nepoužívá mnoho, ale občas máme měl globální proměnné nebo staticky definované řetězce, které je pevný kódované slova jako "ahoj" které nejsou přijata od uživatele , které jsou pevně do svého programu. 

Nyní, se ve spodní části jsme mají takzvaný stack. A stack, dosud jsme byli použitím, jaké druhy účely? Co zásobník se používá? Jo? 

Diváků: Funkce. 

David J. Malan: Pro funkce? V jakém smyslu pro funkce? 

Diváků: Při volání funkce, argumenty jsou zkopírovány do zásobníku. 

David J. Malan: Přesně tak. Při volání funkce, její argumenty jsou zkopírovány do zásobníku. Takže nějaké X nebo Y či či B je že jste přechází do funkce jsou dočasně kladen na takzvaný zásobník, stejně jako jeden z Annenberg jídelna podnosy, a také věci, jako lokální proměnné. Pokud váš foo funkce nebo odkládacího funkce mají lokální proměnné, jako je teplota, ti dva skončit na zásobníku. Nyní budeme moc nemluvila o ně, ale tyto proměnné prostředí v dolní části jsme viděli před chvílí, když Byl jsem futzing na klávesnici jeden den a začal jsem přístup k věci jako argv 100 nebo argv 1000, Jen elements-- jsem zapomněl numbers-- ale, že neměli být přístupné mnou. Začali jsme vidět některé funky symboly na obrazovce. Byly to takzvané proměnné prostředí jako globální nastavení pro můj programu nebo pro svůj počítač, ne nesouvisí s poslední chyba, že jsme se bavili, Shellshock, že to bylo trápí poměrně málo počítačů. 

Nyní konečně, v dnešní zaměření budeme nakonec mít na haldě. Jedná se o další kus paměti. A v podstatě vše paměť je samé. Je to stejný hardware. Jsme jen trochu léčení různých klastrů bajtů pro různé účely. Haldy bude také tam, kde proměnné a paměti, které požadujete z operačního systému jsou dočasně uloženy. 

Ale je to trochu problém zde, stejně jako obraz znamená. Máme druh má dva lodě se srazit. Protože pokud budete používat více a více ze zásobníku, a jak vidíme dnes kupředu, pokud budete používat více a více haldy, jistě špatné věci se může stát. A skutečně, můžeme vyvolat, že úmyslně nebo neúmyslně. Takže cliffhanger posledního čas byl tento program, které neměly sloužit nějaký funkční účel jiný než ukázat jak jste jako zloduch může skutečně trvat Výhodou chyb v něčí programu a převzít program nebo dokonce Celý počítačový systém nebo server. Takže stačí, aby se podíval krátce vás Všimněte si, že nejdůležitější na dně se v příkazovém řádku argumenty, dle argv. A to je volání funkce f, v podstatě bezejmenná funkce nazvaná f, a to předáním argv [1]. 

Takže bez ohledu na slovo, že uživatel zadá na řádku za jménem tohoto programu, a pak libovolná funkce nahoru top, f, se v řetězci, AKA char *, jak jsme začali diskutovat, a to jen nazývá "bar". Ale my jsme to mohli nazvat cokoliv. A pak prohlašuje, uvnitř f, pole znaků volal C-- 12 těchto znaků. 

Nyní, podle příběhu, který jsem říkal před chvílí, kdy v paměti je c, nebo jsou ty 12 znaků skončí? Jen aby bylo jasno. Jo? 

Diváků: Na zásobníku. 

David J. Malan: Na zásobníku. Takže c je lokální proměnná. Ptáme se na 12 znaků nebo 12 bajtů. Ti, kteří se skončí na takzvané zásobníku. Teď konečně je to jiná funkce to je vlastně docela užitečné, ale my jsme opravdu použít to sami, strncopy. To znamená, že řetězec kopii, ale pouze n dopisy, n znaků. Tak n znaky budou kopírovat z baru do cca. A kolik? Délka tyče. Takže jinými slovy, že jeden řádek, strncopy, bude kopírovat účinně bar do cca. 

Nyní, jen trochu předvídat Ponaučení z tohoto příběhu, to, co je zde potenciálně problematické? I když jsme zkontrolovat délku tyče a její předání do strncopy, Jaký je váš gut říkáš, je stále zlomený o tomto programu? Jo? 

Diváků: Nezahrnuje prostor pro nulový znak. David J. Malan: Nezahrnuje prostor pro nulový znak. Potenciálně, na rozdíl od v běžná minulá praxe my ani mít tolik jako plus 1 na ubytovat, že znakem null. Ale je to ještě horší, než to. Co jiného jsme nedaří dělat? Jo? 

Diváků: [neslyšitelné] David J. Malan: Perfect. Jsme pevně dáno 12 dost libovolně. To není tak moc problém, ale skutečnost, že jsme ani kontrolovat, zda Délka tyče je menší než 12, v tom případě to bude bezpečné, aby to do paměti volal c, že ​​jsme přiděleny. Ve skutečnosti, pokud je jako bar 20 znaků, Zobrazí se tato funkce se kopírování 20 znaků z baru do C, čímž se přičemž alespoň 8 bajtů že by nemělo být. To je důsledek tady. 

Takže ve zkratce, rozbité programu. Není tak velký problém. Možná, že máte chybu segmentace. Všichni jsme měli chyby v programech. My všichni mohou mít chyby programů právě teď. Ale co je důsledek? No, tady je zvětšené verze že obraz paměti mého počítače. Jedná se o spodní část mého stacku. A skutečně, na samém dně je to, co je volal rodič rutina zásobník, ozdobný způsob, jak říct, že je to hlavní. Tak, že ten, kdo nazývá funkce f, že mluvíme o. Tak tohle je dno zásobníku. Zpáteční adresa je něco nového. Je to vždy tam, vždy v tomto obrázku. Právě jsme se nikdy obrátil pozornost k tomu. Vzhledem k tomu, že ukáže, že způsob, jakým funguje, je c , že když jeden volání funkce druhého, nejen že tvrzení, podle které Funkce tlačil do fronty, nejen že funkce je místní proměnné tlačil do fronty, něco jako zpáteční adresa získá také dát do zásobníku. Konkrétně, pokud hlavní volá foo, hlavní je vlastní adresu v paměti, vůl něco, efektivně dostane dát do zásobníku tak, že je-li f provádí spuštěním ví, kam skočit zpět do textu segmentu, aby mohl pokračovat provádění. 

Takže když jsme tady koncepčně, V hlavní, pak f volána. Jak se f vědět, kdo na ruční ovládání zpět? No, tento malý strouhanka v červené tady, volal zpáteční adresa, to prostě kontroly, co je to zpáteční adresa? Oh, nech mě skočit zpět na hlavní zde. A to je trochu jako zjednodušující, protože nul a jedniček Pro Main jsou technicky tady v tech segmentu. Ale to je nápad. f prostě musí vědět, co tam, kde řízení nakonec se vrátí. 

Ale způsob, jakým počítače již dlouho stanoveno věci jako lokální proměnné a argumenty jako je tato. Takže v horní části obrázku v modrá je stack frame pro f, takže vše na paměti, že f konkrétně je používáte. Tak tedy, všimněte si, že Bar je na tomto obrázku. Bar byl jeho argument. A tvrdí, že argumenty Funkce tlačil do zásobníku. A c, samozřejmě, je Také na tomto obrázku. 

A jen pro Značky účely, Všimněte si, v levém horním rohu je to, co by c držáku 0 a pak mírně vpravo dolů je c držák 11. Takže jinými slovy, ktere si lze predstavit že tam je mřížka z bytů tam, z nichž první je vlevo nahoře, dole, z nichž je poslední z těchto 12 bytů. 

Ale teď se snaží rychle vpřed. Co se má stát, pokud jsme se projít v řetězci baru, který je delší než c? A my nejsme kontrole, zda je to opravdu déle než 12 let. Která část obrázku bude přepsány po bajtech 0, 1, 2, 3, dot dot dot, 11, a pak se špatný, 12, 13 až 19? Co se bude dít tady, pokud vyvodit z objednání že držák c 0 je na vrcholu c držák 11 je trochu dolů k pořádku? Jo? 

DIVÁKŮ: No, to se děje přepsat char * bar. 

David J. Malan: Jo, vypadá to, že budete přepsat char * bar. A co je horší, pokud jste poslali opravdu dlouho řetězec, můžete dokonce přepsat, co? Zpáteční adresa. Což je opět stejně jako strouhanka říci programu, kde se vrátit, když f se provádí volána. 

Takže to, co protivníci obvykle do je v případě, že narazí na program , že jsou zvědaví, zda je využívání, buggy takovým způsobem, že on nebo ona může mít Výhodou této chybě, většinou se jim nedostává to hned napoprvé. Prostě začít vysílat, například, náhodné řetězce do svého programu, zda na klávesnici, nebo řečeno, že pravděpodobně napsat malý program, jen automaticky generovat řetězce, a začít bušit na programu odeslání v mnoha různých vstupů v různých délkách. 

Jakmile vaše zhroucení programu, to je úžasná věc. Protože to znamená, že nebo ona zjistila, co je asi opravdu chyba. A pak se můžete dostat chytřejší a začít soustředit úžeji o tom, jak využít tuto chybu. Konkrétně, co se on nebo ona by mohla udělat, je poslat, v nejlepším případě, ahoj. Žádný velký problém. Je to řetězec, který je dostatečně krátký. Ale co když on nebo ona pošle, a my zobecnit jako, Útok code-- tak nulami a ty, které se dělat věci, jako rm-rf, že odstraní vše z pevného disku nebo rozesílání spamu nebo nějak napadnout počítač? 

Takže v případě, každý z nich písmena A právě představuje koncepčně, útok, útok, útok, útok, nějaký špatný kód že někdo jiný napsal, ale pokud tato osoba je dost chytrý, nejen zahrnovat všechny z těch RM-RFS, ale také mít jeho nebo její poslední pár bajtů je číslo, které odpovídá na adresu jeho nebo její vlastní útok kód že on nebo ona prošla v několika tím, že ji na výzvu, můžete efektivně trik počítač do všímat, když je f provádí provádění, oh, to je čas, abych se skákat zpět na červenou zpáteční adresu. Ale protože on nebo ona má nějak překrývaly, že zpáteční adresu s vlastním číslem, a oni jsou dost chytří na to aby jste nakonfigurovali, že číslo, které chcete odkazovat, jako vy viz v super nahoru levá tam koutek, skutečná adresa počítače Vzpomínka na některé jejich útoku kódu, špatný člověk může oklamat počítač k vykonání své vlastní kód. 

A ten kód znovu, může to být cokoliv. To je obecně nazýván shell kód, který je právě způsob, jak říct, že to není obecně něco tak jednoduchého jako rm-rf. Je to vlastně něco jako Bash, nebo skutečný program, který mu dává nebo její programové řízení k provedení cokoli jiného, ​​co chtějí. Takže ve zkratce, to vše pochází z prosté skutečnosti, že tato chyba se netýkala kontrolu hranice svého pole. A proto, že na cestě počítače práce je to, že použít zásobník z efektivně, koncepčně, Spodní nahoru, ale pak se prvky zatlačíte do zásobníku roste shora dolů, To je neuvěřitelně problematické. Nyní existují způsoby, jak obejít to. A upřímně řečeno, tam jsou jazyky s níž se tento problém vyřešit. Java je imunní, například, k této konkrétní otázce. Vzhledem k tomu, že vám nedávají odkazy. Oni vám nedávají přímé adresy paměti. Tak s tímto výkonem, že máme na nic sahat do paměti chceme, je sice velké riziko. 

Takže dávat pozor. Pokud je, upřímně řečeno, v měsících nebo let přijít, kdykoliv budete číst o nějakém zneužívání programu nebo serveru, Pokud jste někdy vidět náznak něčeho jako útok přetečení vyrovnávací paměti, nebo přetečení zásobníku je jiný typ útoku, podobně jako v duchu, stejně jako inspiruje webové stránky jméno, pokud ho znáte, je to všechno mluví jen o přetékání velikost nějakého znaku pole nebo některá pole obecněji. Jakékoliv dotazy, pak, o tom myslíte? Nezkoušejte to doma. 

V pořádku. Takže malloc dosud byla naše nová přítel v tom, že můžeme přidělit paměť že nemusí nutně vědět, předem, že chceme, abychom nemuseli mít na pevný kód do našich čísla programů, jako je 12 let. Jakmile uživatel nám říká, kolik Data on nebo ona chce na vstup, můžeme malloc tolik paměti. 

Takže malloc to dopadá, na míry jsme se ji používat, výslovně naposledy, a pak vy jste se používat pro getString nevědomky pro několik týdnů, všechny paměti malloc je pochází z takzvaného haldy. A to je důvod, proč getString, například, může alokovat paměť dynamicky aniž by věděl, co jste bude psát v předstihu, předat zpět ukazatel na paměti, že, a že paměť je stále na vás, aby, i po getString vrátí. Protože odvolání po tom všem Zásobník je neustále jít nahoru a dolů, nahoru a dolů. A jakmile to jde dolů, to znamená, že jakýkoli paměť tato funkce použita, neměl být používán někým jiným. Je to hodnoty odpadky teď. 

Ale hromada je tady. A co je hezké o malloc je to, že když malloc přiděluje paměť tady, to není ovlivněn, protože z větší části tím, že v zásobníku. A tak nějaká funkce přístup paměť, která byla malloc'd, ani funkce jako je getString, i poté, co se vrátí. 

Nyní hovořit malloc je zdarma. A skutečně, na pravidlo, které je třeba začít přijetí je nějaký, některý, nějaký čas používat malloc musíte sami používat zdarma, případně, na stejném ukazateli. Celou tu dobu jsme se psát buggy, buggy kód, z mnoha důvodů. Ale jeden z nich byl pomocí knihovny CS50, které sama o sobě je záměrně buggy, to nevrací paměť. Pokaždé, když jsem volal getString během posledních několika týdnů ptáme se provozní systém, Linux, pro paměť. A vy jste ani jednou ho dal zpátky. A to není, v praxe, dobrá věc. 

A Valgrind, jeden z nástroje zavedené v pset 4, je především o který vám pomůže nyní najít chyby, jako že. Ale naštěstí pro pset 4 nepotřebujete pouze v CS50 knihovnu nebo getString. Takže nějaké chyby spojené s pamětí jsou nakonec bude váš vlastní. 

Takže malloc je více než jen vhodné pro tento účel. Můžeme vlastně teď řešit zásadně odlišné problémy, a zásadně řešit problémy více efektivně, jako za týden nula slibu. Až potud je to sexy struktura dat jsme měli. A datové struktury jsem na mysli způsob konceptualizace paměti způsobem, který přesahuje jen říkám, to je int, to je char. Můžeme začít clusteru věci dohromady. 

Takže pole vypadal takto. A co je klíčem k Pole je, že vám dává back-to-back kusy paměti, z nichž každá bude stejného typu, int, int, int, int nebo char, char, char, char. Ale je tu několik stinné stránky. To například, je pole o velikosti šest. Představte si, že vyplnění tohoto pole se šesti čísla a potom, z jakéhokoli důvodu, Vaše uživatelské chce dát jste sedmina číslo. Kde si dát? 

Jaké je řešení, pokud máte vytvořil řadu na zásobníku, Například, pouze s týden dvě notace, že jsme uvedli, hranatých závorek s číslem uvnitř? No, máš šest Čísla v těchto krabicích. Co by vaše instinkty být? Kam byste chtěli dát? 

Diváků: [neslyšitelné] 

David J. Malan: Sorry? 

Diváků: Dejte ji na konci. 

David J. Malan: Dejte ji na konci. Tak jen něco málo přes doprava, mimo tento box. Což by bylo hezké, ale je to Ukazuje se, můžete to udělat. Protože pokud jste nepožádal pro tento kus paměti, mohlo by to být náhodou, že tento se používá nějaké jiné proměnné úplně. Vzpomeňte si týden nebo tak, když jsme položili z Zamyla a DaviN a Gabe je jmény v paměti. Byli doslova zády k sobě k sobě. Takže nemůžeme být nutně věřím, že cokoliv je tady je k dispozici pro mě použití. 

Takže co jiného můžete dělat? No, jakmile si uvědomil, vás Potřebujete pole o velikosti sedm, můžete jen vytvořit pole o velikosti sedm pak použijte cyklu for nebo while, zkopírujte jej do nového pole, a pak nějak prostě zbavit Toto pole nebo prostě přestaňte jej používat. Ale to není příliš efektivní. Stručně řečeno, pole nenechte dynamicky měnit velikost. 

Takže na jedné straně se dostanete náhodný přístup, což je úžasné. Vzhledem k tomu, že nám umožňuje dělat věci, jako rozděl a panuj, binární vyhledávání, všichni máme mluvil o na obrazovce zde. Ale ty barvy se do kouta. Jakmile stisknete konec tvého pole, co musíte udělat velmi drahý provoz nebo napsat spoustu kódu aby se vypořádat s tímto problémem. 

Co když místo toho jsme měli něco jako seznam, nebo spojový seznam se konkrétně jedná? Co když místo toho, aby obdélníky zády k sobě k sobě, máme obdélníky, které opustí malý trochu manévrovací prostor mezi nimi? A i když jsem se vyvodit tento obrazu nebo přizpůsobit tento obrázek z jednoho z textů, zde se vrátí do zády k sobě velmi spořádaně, ve skutečnosti, jeden z těchto obdélníků by mohl být tady v paměti. Jedním z nich by mohl být tady. Jedním z nich by mohla být tady, sem, a tak dále. 

Ale co když jsme vycházeli, v tomto případě, šipky to nějak propojit je obdélníky dohromady? Skutečně jsme viděli technický ztělesnění šipkou. Co jsme v poslední dny, že pod kapotou, vyjadřující šipky? Ukazatel, že jo? 

Co když místo jen uložení čísla, jako 9, 17, 22, 26, 34, co kdybychom neukládá pouze číslo, ale ukazatel u každé takové číslo? Tak, že podobně jako byste závit jehlu přes spoustu látky, nějak vázání věci společně, podobně mohou jsme se s ukazateli, jako je inkarnoval šipkami zde druh tkát spolu tyto jednotlivé obdélníky tím, že účinně pomocí ukazatele vedle každého čísla, které poukazuje na některé další číslo, které poukazuje na zase nějaký další číslo? Takže jinými slovy, to, co Pokud bychom skutečně chtěli realizovat něco takového? Tak bohužel, tyto obdélníky Aspoň že ten s 9, 17, 22, a tak dále, to jsou již pěkné náměstí s jednotlivými čísly. Spodní, obdélník pod 9, například, představuje to, co by mělo být ukazatel, 32 bitů. Teď jsem ještě neví jakýkoliv datový typ v jazyce C, které vám umožní nejen int ale ukazatel úplně. 

Takže jaké je řešení, pokud chceme vymyslet vlastní odpověď na to? Jo? 

Diváků: [neslyšitelné] 

David J. Malan: Co je to? 

Diváků: Nová struktura. 

David J. Malan: Jo, tak proč Co kdybychom vytvořit novou strukturu, nebo C, struct? Viděli jsme structs dříve, pokud krátce, kde jsme se zabývali strukturou studentů takhle, který měl jméno a domu. V pset 3 útěk, kterou jste použili celý banda structs-- GRect a GOvals že Stanford vytvořen klastr informace dohromady. Tak co, vezmeme-li stejný nápad klíčová slova "typedef" a "struct", a pak nějaký student-specifické věci, a vyvíjet se to do následujících: typedef struct node-- a uzel je jen velmi obecný produkt počítačové vědy termín pro něco, co v datové struktuře, Kontejner v datové struktuře. Uzel Tvrdím, bude mít int n, naprosto jednoduché, a pak se trochu záhadně, Tento druhý řádek, struct uzel * další. Ale méně z technického hlediska, co je to druhý řádek kódu uvnitř složených závorek? Jo? 

Diváků: [neslyšitelné] David J. Malan: ukazatel do jiného uzlu. Takže sice syntaxe trochu záhadné. Ale pokud budete číst doslova, Další je název proměnné. Jaký je její datový typ? Je to trochu upovídaný tentokrát, ale to je typu struct uzel *. Kdykoliv jsme viděli něco hvězdu, která znamená, že je ukazatel na tento typ dat. Takže další je zřejmě ukazatel na struct uzel. 

A teď, co je uzel struct? Dobře si všimněte, vidíš ty, Stejná slova v pravém horním rohu. A skutečně, můžete také vidět slovo "Uzel" tady dole v levém dolním rohu. A to je vlastně jen pohodlí. Všimněte si, že v naší definici studenta je tu slovo "žák" pouze jednou. A to proto, že student Objekt nebyl zcela evidentní. Není nic uvnitř studenta že je třeba, aby ukazoval na jiný student, persay. To by bylo trochu divný v reálném světě. 

Ale s uzlem ve spojen seznam, my chceme uzel jako referenční k podobným předmětem. A tak zjistíte zde změna není jen to, co je uvnitř složených závorek. Ale přidat slovo "uzel" v horní části, jakož i přidáním na dno namísto "studenta." A to je jen technický detail tak, že, opět Vaše datová struktura může být samo-referenční, takže uzel může ukazovat na jiného takového uzlu. 

Takže to, co je v konečném důsledku bude znamenat pro nás? No, jeden, tohle dovnitř je obsah našeho uzlu. To, co tady, vpravo nahoře, je tak že opět můžeme odkazovat na sebe. A pak vnější věci, i když uzel je nový termín, Možná, že je to stále stejně jako studenti, a co byl pod kapotou v SPL. 

Takže pokud bychom se chtěli začít provádění tohoto propojeného seznamu, Jak bychom mohli přeložit něco takového se kód? No, řekněme, viz Příklad programu, který ve skutečnosti používá spojový seznam. Mezi dnešní distribuční kódu je program, nazvaný seznam nula. A když jsem spustit tento jsem vytvořil super jednoduché GUI, Graphical User Interface, ale je to opravdu jen printf. A teď jsem vzhledem k tomu sám pár nabídku options-- Delete, Insert, vyhledávání, a Traverse. A ukončete. To jsou jen běžné operace datové struktury známé jako seznam odkazů. 

Nyní, Delete se chystá Vymazání čísla ze seznamu. Vložte jde přidat číslo v seznamu. Vyhledávání bude vypadat na číslo v seznamu. A traverz je jen ozdobný způsob, jak říkat, projít seznamu vytisknout, ale to je vše. Neměňte ho žádným způsobem. 

Takže zkusme to. Pojďme dál a typ 2. A pak budu vložte číslo, řekněme 9. Enter. A teď můj program je prostě naprogramován tak, aby říct, seznam je nyní devět. Teď, když jsem se do toho pusťte a Vložte si znovu, ať mě jít napřed a oddálení a zadejte 17. Teď můj seznam je 9, pak 17. Pokud se mi vložit znovu, pojďme přeskočit jeden. Namísto 22, podle obrázku máme se při pohledu na tu, dovolte mi, abych náskok a vložte 26 další. Takže budu psát 26. Tento seznam je, jak jsem očekávat. Ale teď, jen aby zjistil, jestli tento kód bude flexibilní, dovolte mi, abych se typ 22, který alespoň koncepčně, když jsme Udržet tento řazeny, což je opravdu bude dalším cílem právě teď, by měl jít mezi 17 a 26 let. Tak jsem stiskněte klávesu Enter. Ve skutečnosti, to funguje. A tak teď mi dovolte vložit Poslední, na obrázku, 34. 

V pořádku. Takže teď mi dovolte stanoví, že Odstranit a Traverse a hledání dělat, ve skutečnosti, pracovat. Ve skutečnosti, když se mi spustit vyhledávání, pojďme vyhledat číslo 22, Enter. Bylo zjištěno 22. Takže to je to, co tento Program Seznam Zero dělá. 

Ale co se vlastně děje na který implementuje to? No, nejdřív bych mohl mít, a skutečně Musím, soubor s názvem list0.h. A někde tam je to linka, typedef struct uzel, pak mám složené závorky, int n, a pak struct-- co bylo definice? Struct uzel další. Takže potřebujeme hvězdu. Teď technicky jsme se dostali do zvyk kreslení zde. Můžete vidět učebnice a on-line odkazy na to tam. Je to funkčně ekvivalentní. Ve skutečnosti, je to trochu typické. Ale budu v souladu s čím jsme minule a to. A pak konečně, budu to dělat. 

Takže v hlavičkovém souboru někde v list0.h dnes je tato definice struct, a možná některé další věci. Zatím v list0c tu bude pár věcí. Ale budeme jen start a ne dokončit. List0.h je soubor chci zařadit do mého C soubor. A pak se v určitém okamžiku jsem bude mít int, hlavní, neplatné. A pak budu mít některé úkolů je tady. Taky budu mít prototyp, jako neplatné, vyhledávání, int, n, jejichž smyslem života je hledat elementu. A pak se tady tvrdí, v Dnešní kód, void, hledání, int n, ne středník, ale otevřené složené závorky. A teď chci nějak vyhledávání prvku v tomto seznamu. Ale nemáme dost informace na obrazovce ještě. Nemám vlastně představovaly samotný seznam. Takže jeden způsob, jak bychom mohli realizovat spojový seznam v programu je, že jsem trochu udělat něco jako prohlásit, spojový seznam tady. Pro jednoduchost budu dělat tento globální, i když v Obecně neměli dělat to příliš mnoho. Ale to bude zjednodušení tento příklad. Tak jsem chtěl deklarovat spojový seznam tady. Nyní, jak by to dělal? 

Zde je obrázek propojeného seznamu. A já opravdu nemám vědět, v okamžiku, kdy jak Chystám se jít o zastupování tolik věcí, které se jen jeden proměnná v paměti. Ale vzpomínám na okamžik. Celou tu dobu jsme měli řetězce, které pak odhalil, že je pole pro znaky, které pak odhalen být jen ukazatel na první znak v poli znaků , který je ukončen nulovým znakem. Takže podle této logiky, a s tím obrázek druh setí své myšlenky, K čemu nám vlastně napsat v naší kód představuje spojový seznam? Kolik z těchto informací potřebujeme zachytit v C kódu, řekli byste? Jo? 

Diváků: Potřebujeme ukazatel na uzel. David J. Malan: ukazatel na uzel. Zejména, který uzel by byl váš instinkty se udržet ukazatel? 

Diváků: první uzel. 

David J. Malan: Ano, asi jen ten první. A všimněte si, první Uzel je odlišný tvar. Je to jen poloviční velikost struct, protože je to opravdu jen ukazatel. Takže to, co můžete opravdu udělat, je vyhlásit spojový seznam být typu uzlu *. A řekněme první nazvat a inicializovat ji na hodnotu null. Takže null, je opět přichází na obrázku zde. Nejen, že je null používán jako například speciální Návratová hodnota pro věci, jako getString a malloc, null je rovněž nulová ukazatel, nedostatek ukazatele, chcete-li. To prostě znamená, že nic, co je ještě tady. Nyní poprvé, mohl jsem volal to cokoliv. Mohl jsem to nazval "seznam" nebo libovolný počet dalších věcí. Ale já jsem volat to "první", takže , aby se ocitl obrázku. Tak jako řetězec může být reprezentován s adresou svého prvního bytu, takže může spojový seznam. A uvidíme další data konstrukce je zastoupena pouze s jedním ukazatelem, 32-bit šipka směřující v prvním uzlu ve struktuře. 

Ale teď pojďme předpokládat problém. Pokud jsem jen vzpomínání v mém programu adresy z prvního uzlu, nejdříve obdélník v této datové struktuře, co bylo lepší být případ o Realizace zbytek mého seznamu? Co je to klíčový detail, co se děje zajistit, že toto skutečně funguje? A tím "skutečně funguje" I Tedy, podobně jako řetězec, nám umožňuje přejít od prvního znaku v Davin jménem na druhé, na třetí, na čtvrtý, až do samého konce, jak víme, když jsme na konci propojeného seznamu, který vypadá takhle? Když je null. A já jsem představoval tento druh jako jako elektrický inženýr silou, s malou uzemnění symbol, druhů. Ale to jen znamená, null v tomto případě. Můžete nakreslit libovolný počet způsoby, ale tento autor Stalo se zde používat tento symbol. 

Tak dlouho, jak budeme navlékat všech těchto uzlů společně, zapamatování pouze v případě, První z nich je, tak dlouho jak vložit speciální symbol na úplně poslední uzel v seznamu, a budeme používat hodnotu null, protože to je to, co máme k dispozici pro nás, Tento seznam je kompletní. A i když jsem jen dát ukazatel na první prvek, ty, programátor, určitě přístup zbytek. Ale pojďme se nechat svou mysl bloudit trochu, v případě, že nejsou již docela wandered-- co je bude doba běhu najít něco v tomto seznamu? Sakra, je to velké O n, což není špatné, v spravedlnosti. Ale je to lineární. Vzdali jsme to, co funkce polí přesunutím více k tomuto obrázku dynamicky tkané společně nebo propojeny uzly? Dali jsme si náhodný přístup. Pole je pěkné, protože matematicky vše je zády k sobě k sobě k sobě. I když tento obrázek vypadá pěkně, a dokonce i i když to vypadá, že tyto uzly jsou pěkně od sebe, ve skutečnosti by mohly být kdekoliv. OX1, Ox50, Ox123, Ox99, tito uzly by mohly být kdekoliv. Vzhledem k tomu, malloc dělá alokovat paměť z haldy, ale kdekoliv v haldě. Nemusíte nutně vědět, že je bude zády k sobě k sobě. A tak to registrace do reality je to bude docela to hezká. 

Takže to bude trvat trochu pracovat na provádění této funkce. Takže pojďme realizovat Hledat. A uvidíme, druh chytrý způsob, jak to udělat. Takže když jsem vyhledávací funkce a Já jsem vzhledem k proměnné, číslo N hledat, musím vědět, Nová syntaxe hledá uvnitř struktury, která je ukázal, najít n. Tak pojďme na to. 

Takže nejprve jsem jít dopředu a prohlásit uzel *. A budu to říkat ukazatel, jen konvencí. A já se inicializovat ji jako první. A teď můžu udělat v mnoha ohledech. Ale budu mít společný přístup. Zatímco ukazatel není rovno null, a to je platné syntaxe. A to prostě znamená, že následující kód, takže pokud nejste ukázal na nic. Co chcete dělat? 

Pokud se ukazatel tečka n, dovolte mi, abych se vrátil k tomu, equals-- rovná co? Jaké hodnoty mám hledat? Skutečná n, který byl schválen v. Tak tady je další vlastnost, o C a mnoha jazyků. I když uzel struktury zvané má hodnotu n, zcela legitimní také mít místní argumentu nebo proměnné s názvem n. Protože i my, s lidské oko může rozlišit že toto n je pravděpodobně odlišný od tohoto n. Vzhledem k tomu, syntaxe je odlišná. Máš tečku a ukazatel, že tato jedna nemá žádnou takovou věc. Takže to je v pořádku. To je v pořádku, aby jim říkat stejné věci. 

Mám-li se vám najít to, já jsem bude chtít něco udělat jako oznamujeme, že jsme našli n. A necháme to jako komentář nebo pseudokód kód. Else, a tady je Zajímavostí, co nechci dělat, když aktuálního uzlu není obsahující n, že mi záleží? Jak mohu dosáhnout následující? Pokud se můj prst na moment je PTR, a to je ukázal na cokoliv První ukazuje na, jak se mohu pohnout prstem k dalšímu uzlu v kódu? No, co je strouhanka jsme bude následovat v tomto případě? Diváků: [neslyšitelné]. David J. Malan: Jo, tak příště. Takže když se vrátím k mému Kód tady, opravdu, já jsem jít dál a říct ukazatel, který je to jen dočasné proměnná-- je to divný název, ptr, ale Je to jako temp-- Chystám se nastavit ukazatel rovná jakéhokoli ukazatele je-- a znovu, to bude malý kočárek pro moment-- tečkou. Jinými slovy, já vezmu můj prst, který se ukázal v tomto uzlu tady a budu říkat, víte, co, podívejte se na další pole a pohybem prstu bez ohledu na to ukazují. A to bude opakovat, opakovat, opakovat. Ale když se dělá můj prst přestat dělat vůbec nic? Jakmile se to, co řádek kódu kopy v? Diváků: [neslyšitelné] David J. Malan: Je-li bod, zatímco ukazatel není rovno null. Na nějakém místě můj prst je bude ukazovat na null a budu si uvědomit, to je konec tohoto seznamu. Nyní, to je malý lež pro jednoduchost. Ukazuje se, že i když jsme se dozvěděl tuto tečkové notace pro stavby, ukazatel není struct. ptr je co? Stačí, aby se více nitpicky. Je to ukazatel na uzel. Není to uzel sám. Kdybych neměl hvězdu zde, ukazatel absolutely-- je to uzel. To je jako týden jedno deklarace proměnné, i když slovo "uzel" je nový. 

Ale jakmile jsme zavedli hvězda, to je teď ukazatel na uzel. A bohužel nelze použít tečka zápis pro ukazatel. Musíte použít šipky zápis, který, překvapivě, Je to poprvé, kdy nějaký kus syntaxe vypadá intuitivní. Tento doslova vypadá jako šíp. A tak to je dobrá věc. A tady doslova Vypadá jako šíp. Takže si myslím, že je to la-- vůbec se mi nelíbí myslím, že jsem příliš spáchání tady-- I si myslí, že je to poslední nový kus syntaxe budeme vidět. A díkybohu, že je to opravdu trochu více intuitivní. 

Teď, pro ty z vás, kteří by raději postaru, můžete stále používat tečkové notace. Ale podle pondělního rozhovor, nejprve je třeba jít tam, jděte na to řešit, a pak přístup k poli. Tak to je také v pořádku. A upřímně řečeno, je to trochu pedantský. Ty doslova říká, dereference ukazatel a tam. Pak si n, pole s názvem n. Ale upřímně řečeno, nikdo nechce psát nebo číst. A tak svět vynalezl notace šipky, které je ekvivalentní, totožné, je to jen syntaktický cukr. Takže ozdobný způsob, jak říkat to vypadá lépe, nebo vypadá jednodušší. 

Takže teď budu dělat jednu věc. Budu říkat "pauzu", jakmile jsem Zjistili, že je tak nemám udržet ji hledají. Ale to je podstata vyhledávací funkce. Ale je to mnohem jednodušší, v konec, a ne projít kód. To je skutečně formální realizace hledání v dnešní distribuce kódu. Troufám si říci, že vložka není zvláště zábavné projít vizuálně, ani je mazat, a to i i když na konci dne se redukuje na poměrně jednoduché heuristiky. 

Tak pojďme na to. Pokud budete humor mě tady, jsem přináší spoustu stresu koule. Přinesl jsem spoustu čísel. A mohli bychom získat jen několik dobrovolníků reprezentovat 9, 17, 20, 22, 29, a 34? Takže v podstatě každý kdo je tady dnes. To byl jeden, dva, tři, čtyři, pět, šest lidí. A já jsem byl požádán, aby jít-- vidět, no jeden na zadní straně zvyšuje své ruce. OK, jeden, dva, tři, čtyři, five-- dovolte mi načte balance-- šest. OK, šest pojď nahoru. Budeme potřebovat další lidi. Přinesli jsme další stres koule. A pokud byste mohl, pro jen na chvíli, linka Sami si prostě líbí tento obrázek zde. 

V pořádku. Pojďme se podívat, Jak se jmenujete? 

DIVÁKŮ: Andrew. 

David J. Malan: Andrew, jste číslo 9. Těší mě. Tady to máš. DIVÁKŮ: Jen. David J. Malan: Jen. David. Číslo 17. Ano? 

Diváků: Jsem Julia. 

David J. Malan: Julia, David. Číslo 20. DIVÁKŮ: Christian. David J. Malan: Christian, David. Číslo 22. A? 

DIVÁKŮ: JP. David J. Malan: JP. Číslo 29. Takže jděte do toho a dostat v-- Uh oh. Uh oh. Standby. 20. Má někdo značku? Diváků: Mám Sharpie. David J. Malan: Máš Sharpie? OK. A má někdo kus papíru? Uložit přednášku. Pojď. Diváků: Máme to. David J. Malan: Máme to? Dobře, děkuji. Jdeme na to. Bylo to od vás? Právě jste zachránil den. Tak 29. V pořádku. I chybně 29, ale OK. Jen do toho. Dobře, dám vám pero zpět na okamžik. Takže máme tyto lidi tady. Pojďme se jeden druhého. Gabe, chceš hrát první prvek tady? Musíme vás upozornit v těchto jemných lidí. Takže 9, 17, 20, 22, třídit z 29, a pak 34. Jsme ztratili někoho? Mám 34. Kde udělal-- OK, kdo chce být 34? OK, pojď nahoru, 34. Tak jo, to bude stojí za vyvrcholení. Jak se jmenujete? 

DIVÁKŮ: Peter. 

David J. Malan: Peter, pojď nahoru. Dobře, takže tady je Celá parta uzlů. Každý z vás představuje jeden z těchto obdélníků. A Gabe, trochu zvláštní člověk se představuje jako první. Takže jeho ukazatel je o něco menší na obrazovce, než všichni ostatní. A v tomto případě, každý po levé straně ruce, bude buď směřovat dolů, v důsledku čehož se null, tak jen absence ukazatele, nebo to bude ukazovat v uzlu vedle vás. 

Takže teď, když se zdobí sami jako na obrázku tu, jděte do toho a bod na sebe, s Gabe zejména ukazuje na číslo 9 reprezentovat seznam. OK, a číslo 34, vaše levá ruka by měla být jen ukázal na podlahu. 

OK, takže to je provázaný seznam. Tak tohle je scénář v pochybnost. A skutečně, to je reprezentativní třídy problémů , že by se mohli pokusit řešit s kódem. Chcete-li nakonec vložit nový prvek do seznamu. V tomto případě budeme zkuste vložit číslo 55. Ale tam to bude různé případy, aby zvážila. A skutečně, to bude jeden z big-obraz takeaways tady, je, Jaké jsou různé případy. Jaké jsou různé, pokud podmínky, nebo větve, které váš program mohl mít? 

No, číslo se snažíte vložka, která dnes už víme, že je 55, ale pokud jste nevěděli, v předstihu, troufám si tvrdit, spadá do nejméně tří možné situace. Tam, kde by mohl být nový prvek? Diváků: A konec nebo střed. David J. Malan: Na konci, v střední, nebo na začátku. Tak jsem se tvrdí, že je alespoň tři problémy musíme řešit. Pojďme si vybrat, co je třeba pravděpodobně nejjednodušší jeden, kde nový prvek patří na začátku. Takže budu mít kód zcela jako je vyhledávání, které jsem napsal. A já budu mít ptr, které Budu reprezentovat tady s mým prstem, jako obvykle. 

A pamatujte si, jakou hodnotu jsme inicializovat ptr na? Tak jsme se inicializuje ji zpočátku null. Ale to, co jsme udělali, jakmile jsme byly v naší funkci vyhledávání? Vydali jsme se rovná první, což neznamená, že dělá. Mám-li nastavit první ptr rovnou, co by moje ruka opravdu ukazuje na? Přesně tak. Takže pokud Gabe a já se chystáte být stejné hodnoty zde Potřebujeme jak bodu číslo 9. 

Tak tohle byl začátek našeho příběhu. A teď je to jen jednoduchý, i když syntaxe je nového. Koncepčně je to jen lineární hledání. Je 55 rovná 9? Nebo spíš, řekněme, méně než 9. Protože se snažím přijít na to, kam umístit 55. Méně než 9, méně než 17, méně než 20, méně než 22, méně než 29, méně než 34, ne. Takže teď jsme v případě jeden z nejméně tří. 

Pokud chci vložit 55 sem, co řádky kódu třeba se dostat popraven? Jak to obrázek lidé potřebují změnit? Co mám dělat s mou levou ruku? To by mělo být null zpočátku, proto, že jsem na konci seznamu. A co by se stalo, tady s Petrem, že? Očividně bude ukazovat na mě. Takže tvrdím, že je to nejméně dva řádky kódu v ukázkovém kódu ode dneška že to bude k provedení tohoto Scénář přidání 55 na ocasu. A mohl bych mít někoho hop a právě představuje 55? Dobře, že jste nový 55. 

Takže teď, co když další scénář přijde, a chceme vložit na na začátku nebo na čele tohoto seznamu? A jaké je vaše jméno, číslo 55? 

DIVÁKŮ: Jack. 

David J. Malan: Jack? OK, rád tě poznávám. Vítejte na palubě. Takže teď budeme vložit, řekněme, číslo 5. Zde je druhý případ tři jsme přišli s před. Takže v případě, 5 patří na začátku, pojďme se podívat, jak jsme zjistili, že ven. I inicializovat svůj ptr ukazatel opět číslo 9. A uvědomil jsem si, oh, 5 je menší než 9. Takže opravit tento obrázek pro nás. Čí ruce, Gabe či Davida nebo--, co je číslo devět jméno? 

DIVÁKŮ: Jen. 

David J. Malan: Jenin hands-- které v našich rukou je třeba změnit? OK, takže Gabe poukazuje na to, co teď? Na mě. Jsem nový uzel. Tak jsem si jen trochu pohybu zde vidět vizuálně. A mezitím co jsem zdůraznit, že? Přesto, kde jsem ukázal. Tak takhle to je. Takže opravdu jen jeden řádek kódu opravy tento konkrétní problém, by se mohlo zdát. Dobře, takže to je dobré. A může někdo být zástupný symbol pro 5? Pojď nahoru. Budeme vám příště. 

Dobře, takže teď-- a Mimochodem, názvy Nebudu dělat explicitní zmínku o právu Nyní, pred ukazatel, předchůdce ukazatel a nový ukazatel, který je vzhledem k tomu jen jména v ukázkovém kódu na ukazateli nebo ruce, že to trochu polohovací kolem. Jak se jmenujete? 

DIVÁKŮ: Christine. 

David J. Malan: Christine. Vítejte na palubě. Dobře, takže uvažujme nyní poněkud nepříjemné scénář, čímž Chci vložit něco jako 26 do toho. 20? Co je? Tyto jsou-- dobrou věc máme tohle pero. V pořádku, 20. Pokud se někdo mohl dostat ještě kousek papír připravený, jen case-- v pořádku. Oh, zajímavé. No to je příklad přednáškového chyby. OK, takže to, co se jmenuješ? DIVÁKŮ: Julia. David J. Malan: Julia, můžete pop , a předstírat, že jsi nikdy nebyl? OK, to se nikdy nestalo. Děkuji vám. Takže předpokládám, že chceme vložit Julia do tohoto propojeného seznamu. Je číslo 20. A samozřejmě, že je bude patřit k begin-- neukazují na nic zatím. Takže vaše ruka může být trochu dolů null nebo nějaké odpadky hodnotu. Pojďme říct, rychlý příběh. Jsem ukázal na číslo 5 této době. Pak jsem zkontrolovat 9. Pak jsem zkontrolovat 17. Pak jsem zkontrolovat 22. A já si uvědomuji, ooh, Julia musí jít před 22. Takže to, co se musí stát? Čí ruce je třeba změnit? Julie, moje, nebo-- co se jmenuješ? 

DIVÁKŮ: Christian. 

David J. Malan: Christian, nebo? 

DIVÁKŮ: Andy. 

David J. Malan: Andy. Christian, nebo Andy? Andy je třeba poukázat na? Julia. V pořádku. Tak Andy, chceš ukázat na Julia? Ale počkejte chvilku. V příběhu tak daleko, Já jsem tak nějak jedno na starosti, v tom smyslu, že ukazatel je věc, která je pohybující se v seznamu. Mohli bychom mít název pro Andyho, ale není proměnná s názvem Andy. Pouze jiné proměnné máme, je První, kdo zastupuje Gabe. 

Takže to je vlastně důvod, proč se tak Zatím jsme to potřebovali to. Ale teď na obrazovce je znovu zmínit o pred ukazatele. Tak nech mě být konkrétnější. Pokud je to ukazatel, měl jsem lepší trochu inteligentnější o mém iteraci. Pokud vám nevadí, že můj prochází zde opět ukázal zde, ukazuje zde. Ale dovolte mi mít pred ukazatel, předchůdce ukazatel, který je druh ukazuje na element jsem byla na. Takže když jdu tady a teď Moje levá ruka aktualizace. Když jdu tady moje levá aktualizace ručně. A teď mám nejen ukazatel prvek, který jde po Julii, Stále mám ukazatel Andy, prvek před. Takže budete mít přístup, v podstatě, strouhanka, chcete-li, na všech potřebných ukazatelů. 

Takže když jsem ukázal na Andy a já jsem také ukázal u křesťana, jehož ruce by nyní měla být zdůrazněno jinde? Takže Andy nyní lze poukázat na Julii. Julia se nyní poukázat na Christiana. Vzhledem k tomu, že můžete kopírovat moje pravá ruka je ukazatel. A to vám účinně přenáší zpět na toto místo zde. Takže stručně řečeno, i když toto nás bere druh navždy skutečně aktualizovat spojový seznam, realizovat že operace jsou relativně jednoduché. Je to z jednoho, dva, tři řádků kódu nakonec. Ale omotal kolem těch řádků kódu pravděpodobně je trochu logiky, která účinně klade otázku, kde to jsme? Jsme na začátku, střední, nebo konec? 

Nyní, tam jsou určitě jiné operace můžeme realizovat. A tyhle fotky zde jen popsat to, co jsme právě dělali s lidmi. Co je odstranění? Pokud chci, například, odebrat číslo 34 nebo 55, Možná mám stejný druh kódu, ale budu potřebovat jeden nebo dva kroky. Vzhledem k tomu, co je nového? Mám-li odstranit někoho, kdo na konci, jako číslo 55 a 34, co má také změnit, jak to udělat? Musím se evict-- co se jmenuješ? 

DIVÁKŮ: Jack. 

David J. Malan: Jack. Musím nejen evict-- zdarma Jack, tak doslova Volejte zdarma Jack, nebo alespoň tam ukazatel taky, ale teď to, co se musí změnit s Petrem? Jeho ruka lepší start směrem dolů. Protože jakmile jsem volat zdarma na Jacku, jestli Peter je stále ukazuje na Jacka a proto, aby křížení Seznam a přístup tohoto ukazatele, to je, když náš starý přítel segmentace Porucha může skutečně kopat do. Vzhledem k tomu, že jsme s ohledem na paměť zpět na Jacka. 

Můžete tam zůstat nešikovně jen na chvíli. Protože máme jen pár finální operace, aby zvážila. Odstranění hlavy seznamu, nebo beginning-- a ten je trochu nepříjemné. Vzhledem k tomu, musíme vědět, že Gabe je tak trochu zvláštní v tomto programu. Protože ve skutečnosti, má vlastní ukazatel. On není jen se ukázal na, stejně jako téměř všichni ostatní tady. 

Takže když v čele seznamu je odstraněna, jehož ruce je třeba změnit právě teď? Jak se jmenuješ? 

DIVÁKŮ: Christine. 

David J. Malan: Jsem hrozný na jména, zřejmě. Takže Christine a Gabe, jehož ruce je třeba změnit kdy se snažíme odstranit Christine, číslo 5, z obrázku? OK, tak se pojďme dělat Gabe. Gabe se děje na bod, Lze předpokládat, že u čísla 9. Ale co další by se mělo stát? Diváků: Christine by být null [neslyšitelné]. David J. Malan: OK, měli bychom asi make-- Slyšel jsem, "null" někde jinde. Diváků: Null a osvobodit ji. David J. Malan: Null co? Diváků: Null a osvobodit ji. David J. Malan: Null a osvobodit ji. Takže je to velmi jednoduché. A je to perfektní, že jsi teď nějak ze tam stál, která nepatří. Vzhledem k tomu, že jste byl oddělena od seznamu. Vy jste skutečně byli osiřel ze seznamu. A tak jsme měli lepší volat zdarma nyní Christine, aby tu vzpomínku zpět. Jinak pokaždé, když odstranit uzel ze seznamu bychom mohli být dělat seznam kratší, ale ne ve skutečnosti snižuje velikost v paměti. A tak, pokud budeme držet přidávání a přidávat, přidávat věci do seznamu, Můj počítač se může dostat pomalejší a pomalejší a pomalejší, protože běžím z paměť, i když nejsem ve skutečnosti pomocí Christine bajtů paměti ještě. 

Takže na konci jsou jiné scénáře, z course-- odstranění ve středu, odstranění Na konci, jak jsme viděli. Ale ještě zajímavější Nyní je bude uvažovat přesně co je doba chodu je. Takže nejen můžete nechat kousky papíru, v případě, Gabe, by vám nevadilo dát každý stres míček. Děkuji moc našeho propojeného seznamu dobrovolníků tady, kdybys mohl. 

[APPLAUSE] 

David J. Malan: Dobře. Takže pár analytické otázek, pak, kdybych mohl. Jsme viděl tento zápis, velké O a omega, horní hranice a dolní hranice na doba chodu nějakého algoritmu. Takže uvažujme jen pár otázek. 

Jednou, a to řekl, že jsme předtím, co je běh Doba hledání seznam, pokud jde o velké O? Co je to horní mez na provoz Doba hledání spojový seznam jak realizovat naše dobrovolníky tady? Je to velký O n, lineární. Vzhledem k tomu, v nejhorším případě, prvek, jako je 55, můžeme hledat, kde by mohla být Jack, úplně na konci. A bohužel, na rozdíl od řady nemůžeme dostat chuť tentokrát. I přesto, že všichni naši lidé byli řazeny od malých prvků, 5, celou cestu až do většího prvku, 55, je to obvykle dobrá věc. Ale to, co dělá tento předpoklad už nám umožňují dělat? Diváků: [neslyšitelné] David J. Malan: znovu, řekni? Diváků: Random přístup. David J. Malan: s náhodným přístupem. A zase to znamená, že můžeme bez dále používat slabý nuly, intuice, a samozřejmost použití binární vyhledávání a rozděl a panuj. Vzhledem k tomu, i když jsme lidé mohli samozřejmě vidět, že Andy a Christian byli zhruba v polovině seznamu, Víme jen, že jako Počítač sbíráním na seznam od samého začátku. Tak jsme se vzdali, že náhodný přístup. 

Tak velký O n je nyní horní vázané na našeho vyhledávacího času. Co omega našeho vyhledávání? Co je dolní mez na vyhledávání pro nějaké číslo v tomto seznamu? Diváků: [neslyšitelné] David J. Malan: znovu, řekni? DIVÁKŮ: One. David J. Malan: One. Takže časová konstanta. V nejlepším případě, Christine opravdu na začátku seznamu. A my hledáme číslo 5, takže jsme ji našli. Takže žádný velký problém. Ale to musí být na začátku seznamu v tomto případě. Co asi něco jako Delete? Co když chcete smazat prvek? Co je horní mez a dolní mez o smazání něco z spojena Seznam? Diváků: [neslyšitelné] David J. Malan: znovu, řekni? DIVÁKŮ: n. David J. Malan: n je opravdu horní mez. Vzhledem k tomu, v nejhorším případě se snažíme odstranit Jacka, jako jsme to udělal. Je to úplně na konci. Nám trvá celou věčnost, nebo n kroky, aby ho našli. Tak to je horní hranice. To je lineární, jistě. A v nejlepším případě doba chodu nebo dolní hranice v nejlepším případě by být konstantní čas. Vzhledem k tomu, že bychom se snaží odstranit Christine, a my jen mít štěstí ona je na začátku. Nyní počkejte chvilku. Gabe byl také na začátku, a také jsme museli aktualizovat Gabe. Takže to nebyl jen jeden krok. Tak to je opravdu konstantní Doba, v nejlepším případě, k odstranění nejmenší prvek? To znamená, že i když to může být dvě, tři, nebo dokonce sto řádků kódu, jestli je to stejný počet linky, ne v nějaké smyčce, a nezávisí na velikosti seznamu, absolutně. Odstranění prvku na začátek seznamu, i když máme co do činění s Gabe, je stále konstantní čas. 

Takže to vypadá, masivní krok zpět. A co je ztráta času v případě, v jednom týdnu a týden nula jsme měli nejen pseudokód kód, ale skutečný kód realizovat něco, co deník base n, nebo přihláste spíše n, základ 2, pokud jde o jeho provozu. Tak proč sakra bychom chtěli začít používat něco jako propojeného seznamu? Jo. 

Diváků: Takže můžete přidat prvky do pole. David J. Malan:, takže můžete přidat prvky do pole. I to je tematická. A budeme i nadále vidět by tento trade-off, hodně jak jsme viděli, trade-off s slučovací druhu. Opravdu by se urychlit vyhledávání nebo třídění, spíše pokud bychom strávit trochu více prostoru a mají další kus paměti nebo pole pro sloučení druhu. Ale trávíme více prostor, ale šetří čas. V tomto případě jsme vzdát se času, ale my jsme získání flexibility, dynamika chcete-li, což je pravděpodobně pozitivní vlastnost. 

Jsme také výdaje prostor. V jakém smyslu je spojen Seznam dražší z hlediska prostoru, než pole? Pokud je prostor navíc přichází? Jo? 

Diváků: [neslyšitelné] ukazatel. 

David J. Malan: Jo, to jsme mají také ukazatel. Tak tohle je minorly nepříjemné v tom, že už jsem I ukládání jen int reprezentovat int. Jsem uložení int a A ukazatel, který je také 32 bitů. Takže jsem doslova zdvojnásobí množství prostoru podílet. Takže je to kompromis, ale to je v případě int. Předpokládejme, že si nejste ukládání int, ale předpokládám, že každý z těchto obdélníků nebo každý z těchto lidí byla představující slovo, anglické slovo, které může mít pět znaků, 10 postavy, možná i víc. Pak se přidá pouze 32 více bitů může být méně velký problém. 

Co když každý ze studentů na demonstraci doslova studentské structs že mají jména a domy a možná telefonní čísla a Twitter zpracovává a podobně. Takže všechna pole jsme začali mluví o jiný den, mnohem méně velký problém, jak naše uzly dostat mnohem zajímavější a velké utratit, co, další ukazatel jen jejich propojení. Ale opravdu, je to kompromis. A skutečně, je kód složitější, jak budete viz sbíráním prostřednictvím že konkrétní příklad. Ale co v případě, že byly nějaký svatý grál zde. Co když nebudeme brát krok dozadu, ale masivní krok vpřed a implementaci dat Struktura přes kterou můžete najít prvky, jako je Jack, nebo Christine nebo jakékoli jiné prvky v tomto poli v pravém konstantním čase? Vyhledávání je konstantní. Odstranit je konstantní. Vložte je konstantní. Všechny tyto operace jsou konstantní. To by nám svatý grál. A to je místo, kde jsme se zvedne příště. Uvidíme se pak.