JASON Hirschhorn: Vítejte všichni k § Seven. Jsme v týdnu sedm kurzu. A to nadcházející čtvrtek je Halloween, takže jsem oblečený jako dýně. Nemohl jsem se ohnout a dát na moje boty, takže to je důvod, proč jsem jen v ponožkách. Jsem také na sobě nic pod to, takže nemůžu sundat, pokud je to rušivě na vás. Předem se omlouvám za to. Nemusíte si představit, co se děje. Mám na sobě trenýrky. Takže je to všechno dobré. 

Mám delší příběh o tom, proč jsem oblečený jako dýně, ale budu kromě toho, že později v této sekci protože chci, abyste mohli začít. Máme spoustu zajímavých věcí jít na tento týden. Většina z nich se přímo vztahují k této týden problém set, pravopisné chyby. Chystáme se jít přes spojeny seznamy a hash tabulky za celý oddíl. Každý týden dal jsem tento seznam se, seznam prostředky pro vás, aby vám pomohl s materiál na tomto kurzu. Je-li na rozpacích, nebo pokud hledáte pro některé více informací, podívejte se na jednu z Tyto zdroje. 

Opět platí, že pset6 je překlepů, tento týden pset. A to také povzbuzuje vás, a já Doporučujeme vám, použít jiné prostředky speciálně pro tento pset. Zejména tři jsem uvedeny na obrazovce - gdb, který jsme byli obeznámeni s a byl s použitím na chvíli teď, je Bude velmi užitečné tento týden. Tak jsem si dal, že až tady. Ale vždy, když pracujete s C, měli byste být vždy pomocí gdb do ladění programů. Tento týden také Valgrind. Ví někdo, co valgrind dělá? 

DIVÁKŮ: Kontroluje úniky paměti? 

JASON Hirschhorn: Valgrind kontroly těsnosti paměti. Takže pokud jste malloc něco ve vaší Program, se ptáte na paměti. Na konci programu, budete mít psát zdarma na všechno, co jste malloced aby paměti zpět. Pokud nechcete psát zdarma na konci a Váš program je dodáván k závěru, vše se automaticky být osvobozen. A pro malé programy, je to Není to velký problém. Ale pokud píšete delší běh program, který se neukončí, nutně, za pár minut nebo pár vteřin, pak se nevrací paměť může být obrovský problém. 

Takže pset6, očekává, že budete mít nulovou paměť úniky váš program. Chcete-li zkontrolovat těsnost paměti, spusťte valgrind a dám ti nějaký pěkný výstup vám vědět, zda nebo ne všechno bylo zdarma. Budeme cvičit s ním později dnes, doufejme. 

Konečně, příkaz diff. Použili jste něco podobného na to v pset5 s Peek nástroje. Povoleno můžete se podívat dovnitř. Můžete také použít diff, taky, za problém nastavit spec. Ale nechá vás porovnat dva soubory. Dalo by se porovnat rastrový soubor a info hlavičky řešení zaměstnanců a vaše řešení v pset5 pokud jste se rozhodli použít. Rozdíl vám umožní to, že stejně. Můžete porovnat správnou odpověď na tento týden problém nastavena na vaši odpověď a sledujte, zda se seřadí nebo viz kde jsou chyby. 

Tak to jsou tři dobré nástroje, které byste měli použít pro tento týden, a určitě zkontrolujte svůj program s těmito třemi nástroji než ji dovnitř Opět, jak jsem se již zmínil každý týden, Máte-li jakoukoliv zpětnou vazbu pro mě - jak pozitivní a konstruktivní - neváhejte a zamiřte na webové stránky ve spodní části tohoto snímku a vstup je tam. Opravdu si toho vážím jakékoliv a všechny zpětné vazby. A když mi dáš konkrétní věci, které Mohu udělat pro zlepšení, nebo, že jsem dělá dobře, že jste mě chtěli pokračovat, beru k srdci a opravdu snažit poslouchat na Váš názor. Nemůžu slíbit, že budu dělat všechno, i když, jako na sobě dýně kostým každý týden. 

Takže budeme trávit většinu část, jak jsem již zmínil, mluví o spojové seznamy a hashovací tabulky, z nichž budou přímo použitelná pro problém nastavit tento týden. Spojové seznamy půjdeme přes relativně rychle, protože jsme strávili trochu kousavou času, bude přes to v řezu. A tak se dostaneme přímo do kódování problémy spojových seznamů. A pak na konci budeme mluvit o tom, hash tabulky a jak se vztahují k tomuto týden problém nastavit. 

Vy jste viděl tento kód. To je struct, a definuje něco nového, tzv. uzel. A v uzlu je celé číslo tady a tam je ukazatel na jiný uzel. Už jsme viděli to. To bylo přijít na Pár nyní týdnů. To kombinuje ukazatele, které jsme byli práci s, a struktur, které umožňují nám spojit dva různé věci do jednoho datového typu. 

Je tu hodně děje na obrazovce. Ale to by mělo být relativně obeznámeni s vámi. Na prvním řádku jsme vyhlásit nový uzel. A pak se v tomto novém uzlu, nastavit celé číslo se tím, že k jednomu uzlu. Vidíme na dalším řádku dělám printf příkaz, ale já jsem šedě příkaz printf, protože opravdu Důležitou součástí je tato linka zde - new_node.n. Co tečka znamená? 

DIVÁKŮ: Jděte do uzlu a posoudit n hodnotu pro něj. 

JASON Hirschhorn: To je Přesně tak. Dot znamená, že přístup k N part tohoto nového uzlu. Tento další řádek co dělá? Michael. 

DIVÁKŮ: Vytváří další uzel která bude ukazovat na nový uzel. 

JASON Hirschhorn: Takže to není vytvořit nový uzel. Vytváří co? 

DIVÁKŮ: ukazatel. 

JASON Hirschhorn: ukazatel na uzel, jak je uvedeno v tomto uzlu * tu. Takže to vytváří ukazatel na uzel. A který uzel je směřující k, Michael? 

DIVÁKŮ: Nový uzel? 

JASON Hirschhorn: Nový uzel. A to je ukázal, že proto, že jsme vzhledem k tomu adresu nového uzlu. A teď v tomto řádku vidíme dva různé způsoby vyjadřuje stejnou věc. A chtěl jsem poukázat na to, jak tyto dvě věci jsou stejné. V prvním řádku, dereference jsme ukazatel. Tak jdeme do uzlu. To je to, co tato hvězda znamená. Viděli jsme, že předtím, než s ukazateli. Přejít na tomto uzlu. To je v závorkách. A pak přístup přes operátora dot n element tohoto uzlu. 

Takže to bere syntaxi jsme tady a teď viděl, použití s ​​ukazatelem. Samozřejmě, že to bude dost práce, pokud píšete ty závorky - že hvězdy a tečka. To je trochu zaneprázdněný. Takže máme nějaký syntaktický cukr. A tento řádek tady - ptr_node-> n. To dělá přesně stejný věc. Takže tyto dva řádky kódu jsou rovnocenné, a bude dělat přesně to samé. 

Ale chtěl bych upozornit ty, před půjdeme dál, takže chápete že opravdu to, co tady je jen syntaktický cukr pro dereferencing ukazatel a pak jít na n část tohoto struct. Máte otázky k tomuto snímku? OK. 

Takže jdeme projít pár operací, které můžete udělat na spojové seznamy. Spojový seznam, odvolání, je řada uzly, které ukazují na sebe. A my jsme obvykle začínají s ukazatelem volal hlava, obecně, že poukazuje na První věc, kterou v seznamu. Takže na prvním řádku tady jsme nejprve náš původní L. Takže to, co si můžete myslet - to text, tady si můžete myslet, jak jen ukazatel máme uloženy někde, že body na první prvek. A v tomto propojeném seznamu máme čtyři uzly. Každý uzel je velký box. Větší box uvnitř velké box je celá část. A pak máme ukazatel část. 

Tyto boxy nejsou vypracovány na měřítko, protože, jak velký je celé číslo v bytech? Jak teď velký? Čtyři. A jak velká je ukazatel? Čtyři. Takže opravdu, když jsme se k tomu toto měřítko obě políčka by mít stejnou velikost. V tomto případě, chceme vložit něco do propojeného seznamu. Takže můžete vidět tady dole jsme vkládání pět jsme přejít přes spojový seznam, zjistit, kde pět jde, a pak ji zasuňte. 

Pojďme se zlomit to dolů a jít trochu pomaleji. Budu poukázat na desce. Takže máme pět uzel, který jsme vytvořili v mallocs. Proč se všichni smát? Jen si dělám srandu. OK. Takže jsme malloced pět. Vytvořili jsme tento uzel někde jinde. Musíme je připravena jít. Začneme na přední straně náš seznam se dvěma. A chceme vložit na tříděný módě. 

Takže pokud vidíme dva a chceme, aby v pět, co budeme dělat, když vidíme, něco méně než my? Co je? Chceme vložit pět do této spojový seznam, zachováním řazeny. Vidíme číslo dvě. Tak co budeme dělat? Marcus? 

DIVÁKŮ: Zavolejte ukazatel k dalšímu uzlu. 

JASON Hirschhorn: A proč jdeme na ten příští? 

DIVÁKŮ: Vzhledem k tomu, že je to další uzel v seznamu. A my jen víme, že jiné umístění. 

JASON Hirschhorn: A pět je větší než dva, a to zejména. Protože chceme, aby to seřazené. Takže pět je větší než dva. Tak jsme se přesunout na další. A teď se dostaneme čtyři. A co se stane, když se dostaneme čtyři? 

Five je větší než čtyři. Tak jsme dál. A teď jsme v šest. A co vidíme v šest? Ano, Carlos? 

DIVÁKŮ: Šest je větší než pět. 

JASON Hirschhorn: Šest je větší než pět. Tak to je místo, kde chceme vložit pět. Nicméně, mějte na paměti, že pokud bychom mají pouze jeden ukazatel zde - To je náš další ukazatel, který je procházející přes seznamu. A my jsme ukázal na šest. Ztratili jsme stopu z čeho přichází před šestou. Takže pokud chceme vložit něco do tento seznam udržovat ji řazeny jsme pravděpodobně potřebovat kolik rad? 

DIVÁKŮ: Two. 

JASON HIRSCHORN: Two. Jeden sledovat aktuální jeden a sledovat ten předchozí. Toto je pouze jednotlivě spojový seznam. Je to jen jde jedním směrem. Kdybychom měli dvojnásobně spojový seznam, kde vše ukazoval na věc po něm a věc před ním, pak nebudeme muset dělat, že. Ale v tomto případě nechceme ztratit track z toho, co přišli před námi v případě, musíme vložit pět někde ve středu. Řekněme, že jsme byli vkládání devět. Co se stane, když jsme se dostali na osm? 

DIVÁKŮ: Museli byste dostat, že nulový bod. Místo toho, aby nulový bod budeš mít přidat prvek a pak že poukazují na devět. 

JASON HIRSCHORN: Přesně tak. Tak dostaneme osm. Dostáváme se na konec seznamu, protože to ukazuje na hodnotu null. A teď, místo toho, aby to poukázat na null to máme poukázat na našem novém uzlu. A nastavíme ukazatel náš nový uzel na hodnotu null. Má někdo nějaké otázky, o vkládání? Co když nemám starat o vedení seznamu řazeny? 

DIVÁKŮ: Stick to na začátek nebo konec. 

JASON HIRSCHORN: Stick to na začátek nebo konec. Který z nich bychom měli dělat? Bobby? Proč konec? 

DIVÁKŮ: Vzhledem k tomu, začátek je již naplněna. 

JASON HIRSCHORN: OK. Začátek je již naplněna. Kdo chce argumentovat proti Bobbymu. Marcus. 

DIVÁKŮ: No pravděpodobně budete chtít držet ji na začátku, protože jinak, pokud si to dát na Konec byste museli procházet celý seznam. 

JASON HIRSCHORN: Přesně tak. Takže pokud budeme přemýšlet o běhu, runtime vložení na konci by n, velikost. Co je to velký O runtime vložení na začátku? Konstantní čas. Takže pokud nechcete starat o udržení něco dále, mnohem lepší, jen vložit na začátku tohoto seznamu. A to lze provést v konstantním čase. 

OK. Další operace je najít, které další - jsme formulovali to jako hledání. Ale my jdeme prohlédnout spojový seznam z nějakého objektu. Vy jste viděli kód hledat ještě v přednášce. Ale my jsme tak nějak právě udělal to s vložit, nebo alespoň vkládání něco dále. Můžete prohlédnout, bude uzel uzlu, dokud nenajdete číslo, že jste hledat. Co se stane, když se dostanete konec seznamu? Řekni Hledám devět a já dostat se na konec seznamu. Co budeme dělat? 

DIVÁKŮ: return false? 

JASON HIRSCHORN: Návrat false. Nenašli jsme ji. Pokud se dostanete na konec seznamu a jste nenašli číslo, které jste hledá, není to tam. Jakékoliv dotazy týkající se najít? Pokud to bylo seřazený seznam, co by být pro naše vyhledávání? Jo. 

DIVÁKŮ: To najde první hodnotu to je větší než jedna hledáte a pak se vrátit false. 

JASON HIRSCHORN: Přesně tak. Takže pokud je to seřazený seznam, pokud se dostaneme do něco, co je větší než to, co jsme hledali, nepotřebujeme, aby pokračuj na konec seznamu. Můžeme v tomto bodě vrátí false protože nebudeme ho najít. Otázkou je nyní, jsme mluvili o vedení propojené seznamy řazeny, jejich udržování netříděný. To bude něco, co jste pravděpodobně bude muset přemýšlet o tom, při kódování problém nastavit pět, pokud vybrat hash tabulku s samostatný řetězení přístup, který budeme hovořit o později. 

Ale je to stojí za to, aby se seznam tříděného a pak budou moci možná mít rychlejší vyhledávání? Nebo je lepší rychle vložení něco v neustálém běhu, ale pak mají už hledáte? To je jedna z věcí, tady, že vám dostat se rozhodnout, co je vhodnější, pro váš konkrétní problém. A tam to nemusí být nutně jedním naprosto správná odpověď. Ale je to určitě rozhodnutí, které se aby se, a asi dobře bránit že, řekněme, komentář nebo dva, proč jste si vybrali jeden přes druhého. 

A konečně, mazání. Viděli jsme mazání. Je to podobné, jako hledat. Hledáme prvku. Řekněme, že se snažíme odstranit šest. Tak najdeme šest tady. Jde o to, že se musíme ujistit, že jsme udělat, je, že cokoliv se ukazuje na šest - jak vidíme v kroku dva tady dole - bez ohledu na to ukázal na šest potřeby na přeskočit šest nyní a být změněn na co šest je ukazuje. Nechceme, aby vůbec vzácná onemocnění zbytek náš seznam by zapomněl nastavit, aby předchozí ukazatel. A pak někdy, v závislosti na programu, ale budu jen odstranit úplně tento uzel. Někdy se budete chtít vrátit hodnota, která je v tomto uzlu. Tak to je, jak funguje mazání. Jakékoliv dotazy týkající se smazat? 

DIVÁKŮ: Takže pokud se chystáte odstranit to byste stačí použít zdarma, protože pravděpodobně to bylo malloced? 

JASON HIRSCHORN: Pokud chcete uvolnit něco, co je úplně v pořádku a vy malloced to. Řekněme, že jsme se chtěli vrátit tuto hodnotu. Mohli bychom se vrátit šest a pak zdarma tento uzel a volání zdarma na něj. Nebo bychom snad volat zdarma první a pak se vrátit šest. 

OK. Takže pojďme se přesunout na praxi kódování. Budeme kódovat tři funkce. První z nich se nazývá insert_node. Takže máte kód, který jsem zasláno e-mailem vás, a pokud sledujete později na to můžete přistupovat ke kódu v linked.c na internetových stránkách CS50. Ale v linked.c, tam je nějaký kostra kód, který je již byla napsána pro vás. A pak je tu pár FUNKCE musíte napsat. 

Nejprve jedeme do napsat insert_node. A co dělá insert_node znamená vloží číslo. A dáváte celé číslo do propojeného seznamu. A zejména, budete potřebovat udržet seznamu seřazeny od nejmenšího po největší. Také nechcete, aby vložte všechny duplikáty. V neposlední řadě, jak můžete vidět insert_node vrací bool. Takže jste měl dát uživateli vědět zda je či není insert úspěšný vrácením true nebo false. Na konci tohoto programu - a pro tuto fázi nemusíte se starat o uvolnění cokoliv. Takže vše, co děláte, je přijetí celé číslo a vložení do seznamu. 

To je to, co se ptám vás dělat teď. Opět platí, že v linked.c, které všichni mají, je kostra kódu. A měli byste vidět na spodní části Deklarace funkce vzorku. Nicméně předtím, než jít do jeho kódování v C, vřele doporučujeme vám jít jednotlivými kroky jsme byli cvičit každý týden. Už jsme prošli obraz toho. Takže byste měli mít nějaké znalosti o tom, jak to funguje. Ale já bych povzbudit vás psát některé pseudokódu před potápěním palců A jdeme projít pseudokódu jako skupina. A pak, jakmile jste napsali svůj pseudokódu, a jakmile jste napsali naši pseudokódu jako skupiny, můžete jít na to kódování v C. 

Jako heads up, funkce insert_node je pravděpodobně nejkomplikovanější ze tři budeme psát, protože jsem přidal některé další omezení na vaše programování, zejména to, že nebudete vložit jakýkoli duplikáty a že seznam by měla zůstat tříděné. Tak to je non-triviální program, že budete muset kód. A proč si nevezmeš pět-sedm minut jen proto, aby se práce na pseudokódu a kód. A pak začneme jít jako skupina. Opět platí, že pokud máte nějaké dotazy stačí zvednout ruku a půjdu kolem. . 

Také jsme obecně dělat to - nebo nemám explicitně říci vám může pracovat s lidmi. Ale samozřejmě, vřele vám doporučujeme, Máte-li otázky, žádat soused sedí vedle tebe nebo dokonce pracovat s někým, jinak, pokud chcete. To nemusí být individuální tichá činnost. 

Pojďme začít s psaním některých pseudokódu na palubě. Kdo mi může dát první řádek pseudokódu pro tento program? Pro tuto funkci, spíše - insert_node. Alden? 

DIVÁKŮ: Takže první věc, kterou jsem udělal, bylo, vytvořit nový ukazatel na uzel a já inicializován to ukazuje na stejný věc, že ​​seznam je ukazuje. 

JASON HIRSCHORN: OK. Takže budete vytvářet nový ukazatel na seznamu, a to k uzlu. 

DIVÁKŮ: Správně. Jo. 

JASON HIRSCHORN: OK. A pak to, co chceme dělat? Co je po tom? Co uzlu? Nemáme uzel. Máme jen hodnotu. Pokud chceme vložit uzel, co máme je třeba udělat dřív, než se budeme moci ještě přemýšlet o tom, vložení? 

DIVÁKŮ: Oh, omlouvám se. musíme malloc prostor pro uzel. 

JASON HIRSCHORN: Výborný. Pojďme udělat - OK. Nelze dosáhnout tak vysoko. OK. Chystáme se jít dolů, a pak jsme pomocí dvou sloupců. Nemůžu jít, že - OK. Vytvořit nový uzel. Můžete vytvořit další ukazatel na seznam nebo stačí použít seznam, jak to existuje. Nemáte opravdu potřebujete udělat, že. 

Tak jsme se vytvořit nový uzel. Skvělé. To je to, co děláme jako první. Co bude dál? 

DIVÁKŮ: Počkejte. Měli bychom vytvořit nový uzel se podnikem nebo Měli bychom počkat, aby se ujistil, že tam žádné duplikáty uzlu na seznamu, než ji vytvořit? 

JASON HIRSCHORN: Dobrá otázka. Pojďme si myslí, že na později, protože většinu času budeme vytvářet nový uzel. Takže budeme držet tady. Ale to je dobrá otázka. Pokud bychom ji vytvořit a najdeme duplicitní, co by budeme dělat, než se vrátí? 

DIVÁKŮ: Uvolněte se. 

JASON HIRSCHORN: Jo. Pravděpodobně ho uvolnit. OK. Co budeme dělat, když jsme vytvořit nový uzel? Annie? 

DIVÁKŮ: Dali jsme Číslo v uzlu? 

JASON HIRSCHORN: Přesně tak. Klademe číslo - budeme malloc prostor. Chystám se nechat, že vše jako jeden řádek. Ale máš pravdu. Malloc jsme prostor, a pak dáme číslo palců Dokonce můžeme nastavit ukazatel část na hodnotu null. To je přesně to pravé. A pak co po tom? Nakreslil jsme tento obrázek na tabuli. Tak co budeme dělat? 

DIVÁKŮ: Projdeme seznamu. 

JASON HIRSCHORN: Projděte si seznam. OK. A co si budeme kontrolovat na každém uzlu. Kurt, co můžeme zkontrolovat pro každý uzel v? 

DIVÁKŮ: Podívejte se, zda n hodnota že uzel je větší, než je hodnota n našeho uzlu. 

JASON HIRSCHORN: OK. Budu dělat - jo, OK. Tak to je n - Chystám se říct, jestli hodnota je větší než v tomto uzlu, pak to, co budeme dělat? 

DIVÁKŮ: No, pak vložíme přmo před tím. 

JASON HIRSCHORN: OK. Takže pokud je to větší než to, pak chceme vložit. Ale chceme, těsně předtím, než ji vložit protože také bude muset být sledování, a pak, z toho, co bylo předtím. Takže vložte před. Takže jsme asi něco uniklo dříve. Asi jsme třeba udržet track z toho, co se děje. Ale dostaneme se tam. Takže to, co je hodnota nižší než? Kurt, co budeme dělat, když hodnota je nižší než? 

DIVÁKŮ: Pak stačí jít dál pokud je to poslední. 

JASON HIRSCHORN: Líbí se mi to. Tak jděte na další uzel. Pokud to poslední - jsme asi kontrola, která v podmínkách stavu. Ale jo, další uzel. A to je stále příliš nízká, takže budeme pohybovat sem. Ale pokud - může každý vidět? Jsme-li stejná, co budeme dělat? Pokud hodnota se snažíme vložit se rovná hodnotě tohoto uzlu? Jo? 

DIVÁKŮ: [neslyšitelné]. 

JASON HIRSCHORN: Jo. Vzhledem k této - Marcus je v pořádku. Mohli jsme možná udělali něco jiného. Ale vzhledem k tomu, že jsme vytvořili to, zde bychom se měli uvolnit a pak se vrátit. Ach jo. Je to lepší? Jak to? OK. Zdarma a pak to, co máme vrátit, [neslyšitelný]? OK. Jsme něco chybí? Takže tam, kde jsme sledování z předchozího uzlu? 

DIVÁKŮ: Myslím, že to půjde Po vytvoření nového uzlu. 

JASON HIRSCHORN: OK. Takže na začátku jsme se asi - jo, můžeme vytvořit ukazatel na nový uzel, jako předchozí ukazatel uzlu a aktuální uzel ukazatel. Takže pojďme vložte tady. Vytvořte aktuální a předchozí ukazatele na uzly. Ale když budeme nastavit ty odkazy? Tam, kde to uděláme v kódu? Jeff? 

DIVÁKŮ: - Podmínky hodnota? 

JASON HIRSCHORN: Které jeden zejména? 

DIVÁKŮ: Já jsem jen zmatená. Je-li hodnota je vyšší, než v tomto uzlu, Neznamená to, že chcete jít na další uzel? 

JASON Hirschhorn: Takže pokud naše hodnota je větší, než je hodnota tohoto uzlu. 

DIVÁKŮ: Jo, pak byste chtěli, aby jít dále v řadě, ne? 

JASON Hirschhorn: Správně. Takže nemáme vložte jej sem. Pokud je hodnota nižší než v tomto uzlu, pak jdeme na další uzel - a pak jsme vložte před. 

DIVÁKŮ: Počkejte, což je v tomto uzel a která je hodnota? 

JASON Hirschhorn: Dobrá otázka. Hodnota za této definice funkce je to, co jsme vzhledem. Takže hodnota je číslo jsme vzhledem. Takže v případě, že hodnota je nižší než tento uzel, potřebujeme čas na vložení. Je-li hodnota je vyšší, než v tomto uzlu, jdeme na další uzel. A zpět k původní otázce, i když, kde - 

DIVÁKŮ: Je-li hodnota větší než tento uzel. 

JASON Hirschhorn: A tak Co tady děláme? Sladké. To je správné. Jdu psát aktualizovat ukazatele. Ale ano, se stávající byste jej aktualizovat poukazují na ten příští. Ještě něco nám chybí? Takže budu psát tento kód do gedit. A když jsem to udělat, můžete mít pár dalších minut k práci na kódování to v C. 

Takže mám Zadejte pseudokódu. Krátká poznámka, než začneme. My nemusí být schopen zcela dokončit to ve všech tři z těchto funkcí. Tam je správné řešení k nim že jsem se e-mailem na vás kluci po bodu, a to bude být zanecháno CS50.net. Tak jsem se tě povzbudit, aby jít podívat na sekcích. Doporučuji vám vyzkoušet to na vašem vlastní, a pak použít v praxi problémy, abychom zjistili, zda vaše odpovědi. Ty byly všechny navrženy tak, aby úzce týkají, a dodržovat to, co co musíte udělat, na problém sadě. Tak jsem se povzbudit vás k praxi to na vlastní pěst, a pak použijte kód zkontrolujte své odpovědi. Protože chci přejít na hash Stoly na nějakém místě v sekci. Takže bychom mohli dostat přes to všechno. Ale budeme dělat teď, jak moc můžeme. 

OK. Pojďme začít. Asam, jak jsme se vytvořit nový uzel? 

DIVÁKŮ: Ty struct *. 

JASON Hirschhorn: Tak jsme si, že se tady. Oh, omlouvám se. Říkal jste struct *. 

DIVÁKŮ: A pak [? druh?] uzel nebo c uzel. 

JASON Hirschhorn: OK. Budu říkat new_node takže můžeme zůstat konzistentní. 

DIVÁKŮ: A chcete nastavit, které na hlavu, první uzel. 

JASON Hirschhorn: OK. Takže teď to ukazující na - tak to nebyl vytvořen nový uzel dosud. To je jen ukazuje na první uzel v seznamu. Jak mohu vytvořit nový uzel? Pokud je potřeba prostor pro vytvoření nového uzlu. Malloc. A jak velký? 

Diváků: velikost struct. 

JASON Hirschhorn: velikost struct. A co struct jmenuje? 

DIVÁKŮ: Uzel? 

JASON Hirschhorn: Node. Takže malloc (sizeof (node)); nám dává prostor. A je to linka - jedna věc je nesprávné na tomto řádku. Je new_node ukazatel na struct? To je obecný název. Co je to - uzel, přesně tak. Je to uzel *. A co budeme dělat hned po jsme malloc něco, Asan? Co je první věc, kterou budeme dělat? Co když to nefunguje? 

DIVÁKŮ: Oh, zkontrolujte, zda je poukazuje na uzlu? 

JASON Hirschhorn: Přesně tak. Takže pokud jste new_node rovná rovná null, co budeme dělat? Tento vrací bool, tuto funkci. Přesně tak. Vypadá to dobře. Něco se tam přidat? Budeme přidávat věci na konci. Ale to zatím vypadá dobře. Vytvořte aktuální a předchozí ukazatele. Michael, jak to mám udělat? 

DIVÁKŮ: Budete muset udělat uzel *. Musel bys udělat jednu ne pro new_node ale uzly již máme. 

JASON Hirschhorn: OK. Takže aktuální uzel jsme dál. Zavolám, že curr. Dobrá. Rozhodli jsme se chceme udržet dva, protože potřebujeme vědět, to, co je před ním. Co oni si inicializován? 

DIVÁKŮ: Jejich hodnota v našem seznamu. 

JASON Hirschhorn: Takže to, co je První věc, kterou na našem seznamu? Nebo jak víme, kde začátek našeho seznamu je? 

DIVÁKŮ: Není to prošlo do funkce? 

JASON Hirschhorn: Správně. To byl schválen v roce tady. Takže pokud je to přešel do funkce, začátek seznamu, co bychom měli nastavit proud rovný? 

DIVÁKŮ: List. 

JASON Hirschhorn: List. To je přesně to pravé. Nyní má adresu začátek našeho seznamu. A co předchozí? 

DIVÁKŮ: Seznam mínus jedna? 

JASON Hirschhorn: tu nic před ním. Co tedy můžeme udělat pro to, znamenat nic? 

DIVÁKŮ: Null. 

JASON Hirschhorn: Jo. To zní jako dobrý nápad. Perfect. Děkuju. Projděte si seznam. Constantine, jak dlouho se budeme projít seznamu? 

DIVÁKŮ: až se dostaneme null. 

JASON Hirschhorn: OK. Takže v případě, zatímco pro smyčku. Co budeme dělat? 

DIVÁKŮ: Možná, že pro smyčce? 

JASON Hirschhorn: Pojďme udělat pro smyčce. OK. 

DIVÁKŮ: A my říkáme na - až do současné ukazatel není rovno null. 

JASON Hirschhorn: Takže pokud víme, stav, jak můžeme napsat smyčku vychází z tohoto stavu. Jaký druh smyčky bychom měli používat? 

DIVÁKŮ: Zatímco. 

JASON Hirschhorn: Jo. To dává větší smysl na základě off z toho, co jste řekl. Pokud chceme jen jít do jsme, že Jen vím, že věc, bylo by smysl dělat while. Zatímco současná není rovno null, pokud hodnota je nižší než tento uzel. Akshar, dej mi tento řádek. 

DIVÁKŮ: Pokud je aktuální-> n n menší než hodnota. Nebo zvrátit to. Spínač, který držák. 

JASON Hirschhorn: Omlouvám se. 

DIVÁKŮ: Změňte držák. 

JASON Hirschhorn: Takže pokud je to vyšší než hodnota. Vzhledem k tomu, že je to matoucí komentář výše, budu dělat, že. Ale ano. Pokud je naše hodnota je nižší než tento uzel, co budeme dělat? Oh. Mám ho tady. Vložte předtím. OK. Jak to uděláme? 

DIVÁKŮ: Je to ještě já? 

JASON Hirschhorn: Jo. 

DIVÁKŮ: Vy - new_node-> další. 

JASON Hirschhorn: Takže to, co je že bude rovnat? 

DIVÁKŮ: Bude to stejné proudu. 

JASON Hirschhorn: Přesně tak. A tak další - co ještě musíme aktualizovat? 

DIVÁKŮ: Zkontrolujte, zda minulost rovná null. 

JASON Hirschhorn: Pokud prev - takže pokud předchozí rovná null. 

DIVÁKŮ: To znamená, že se děje aby se stal hlavou. 

JASON Hirschhorn: To znamená je to stát hlavy. Tak co budeme dělat? 

DIVÁKŮ: Děláme hlava rovná new_node. 

JASON Hirschhorn: Head rovná new_node. A proč hlava tady, ne seznam? 

DIVÁKŮ: Vzhledem k tomu, hlava je globální variabilní, což je výchozí místo. 

JASON Hirschhorn: Sladký. OK. A - 

DIVÁKŮ: Pak si ještě prev-> Další rovná new_node. A pak se vrátit true. 

JASON Hirschhorn: Kam jsme se vydali new_node konec? 

DIVÁKŮ: Já bych - Nastavit, že na začátku. 

JASON Hirschhorn: Tak co linka? 

DIVÁKŮ: Po if kontrolovat, zda je známo. 

JASON Hirschhorn: Tady? 

DIVÁKŮ: já bych to new_node-> n se rovná hodnotě. 

JASON Hirschhorn: To zní dobře. Pravděpodobně to dává smysl - my ne Potřebujeme vědět, co seznam jsme na proto, že jsme jen do činění s jednoho seznamu. Takže lepší funkce prohlášení o je to jen, jak se zbavit tohoto zcela a jen vložit hodnota do hlavy. My ani nemusíte vědět co seznam jsme dovnitř Ale nechám to teď a pak jej změnit na aktualizaci sklíčka a kód. Takže to vypadá dobře teď. Je-li hodnota - kdo může dělat tento řádek? Pokud - Co budeme dělat tady, Noah. 

DIVÁKŮ: Je-li hodnota větší než akt-> n - 

JASON Hirschhorn: Jak jdeme na další uzel? 

DIVÁKŮ: Měna-> n je rovná new_node. 

JASON Hirschhorn: Tak n je jaká část struct? Celé číslo. A new_node je ukazatel na uzel. Takže to, co část Curr bychom měli aktualizovat? Pokud není n, pak to, co je ta druhá část? Noah, co je ta druhá část. 

DIVÁKŮ: Oh, další. 

JASON Hirschhorn: Další, přesně tak. Přesně tak. Další je správná. A co ještě potřebujeme aktualizovat, Noe? 

DIVÁKŮ: Ukazatele. 

JASON Hirschhorn: Tak Aktualizovali jsme proud. 

DIVÁKŮ: Prev-> další. 

JASON Hirschhorn: Jo. OK, budeme pozastavit. Kdo nám může pomoci tady? Manu, co bychom měli dělat? 

DIVÁKŮ: Musíš nastavit je rovna akt-> další. Ale to, že dříve, než v předchozím řádku. 

JASON Hirschhorn: OK. Ještě něco? Akshar. 

DIVÁKŮ: Nemyslím si, že jsi chtěl změnit akt-> další. Myslím, že jsi chtěl dělat Měna rovná akt-> další přejít na další uzel. 

JASON Hirschhorn: Je mi líto, kam? Na co linka? Tato linka? 

DIVÁKŮ: Jo. Ujistěte se curr rovná akt-> další. 

JASON Hirschhorn: Tak to je pravda protože proud je ukazatel na uzel. A my chceme, aby to poukázat na další uzel, co se dostává v současné době ukázal. Curr sama o sobě má další. Ale pokud bychom měli aktualizovat curr.next jsme by se aktualizace aktuální poznámku sama o sobě, ne tam, kde to ukazatel ukazoval. Co o této linii, ačkoli. Avi? 

DIVÁKŮ: Prev-> Další rovná curr. 

JASON Hirschhorn: Takže znovu, pokud předchozí je ukazatel na uzel, náhled-> další je aktuální ukazatel v uzlu. Takže by to být aktualizace ukazatel na uzel Curr. Nechceme aktualizovat ukazatel v uzlu. Chceme aktualizovat předchozí. Tak jak to uděláme? 

DIVÁKŮ: Bylo by to být prev. 

JASON Hirschhorn: Správně. Předchozí je ukazatel na uzel. Nyní měníme ji nový ukazatel na uzel. OK Pojďme dolů. A konečně, tento poslední podmínka. Jeffe, co budeme dělat tady? 

DIVÁKŮ: Je-li hodnota rovnající se akt-> n. 

JASON Hirschhorn: Omlouvám se. Ach můj bože. Co je? Hodnota == akt-> n. Co budeme dělat? 

DIVÁKŮ: Ty bys osvobodit naši new_node, a pak byste se vrátit false. 

JASON Hirschhorn: To je to, co jsme psali tak daleko. Má někdo něco přidat dříve, než uděláme? OK. Pojďme to zkusit. Kontrola může dostat na konec z non-void funkce. Avi, co se děje? 

DIVÁKŮ: Jste měl dát návratu platí mimo while? 

JASON Hirschhorn: Já nevím. Máte mě chcete? 

DIVÁKŮ: Nevadí. Ne. 

JASON Hirschhorn: Akshar? 

DIVÁKŮ: Myslím, že jste měl na mysli, aby dát return false na konci z cyklu while. 

JASON Hirschhorn: Tak kde chceš, aby to šlo? 

DIVÁKŮ: Stejně jako u cyklu while. Takže pokud opustíte while to znamená, že že jste došli na konec a nic se nestalo. 

JASON Hirschhorn: OK. Tak co budeme dělat tady? 

DIVÁKŮ: Vrátíte false i tam. 

JASON Hirschhorn: Oh, my to na obou místech? 

DIVÁKŮ: Jo. 

JASON Hirschhorn: OK. Měli bychom jít? Ach můj bože. Je mi to líto. Omlouvám se za obrazovku. Je to trochu děsí nás. Tak si vyberte jednu z možností. Zero, podle kódu, ukončí program. Jeden vloží něco. Pojďme vložte tři. Vložka nebyl úspěšný. Jdu vytisknout. Nemám nic. OK. Možná, že to byla jen náhoda. Vložte jeden. Není úspěšná. OK. Pojďme si projít GDB velmi rychle zjistit, co se děje. 

Nezapomeňte gdb. / Název vašeho Program nás dostane do GDB. Je to hodně zvládnout? Bliká? Pravděpodobně. Zavřete oči a vzít nějaké hluboké dýchá, pokud vás omrzí z pohledu na něj. Jsem v GDB. Co je první věc, kterou dělám v GDB? Musíme přijít na to, to, co se tady děje. Pojďme se podívat. Máme šest minut na obrázku co se děje. Přestávka hlavní. A pak to, co mám dělat? Carlos? Spustit. OK. Pojďme možnost. A co N dělat? Další. Jo. 

DIVÁKŮ: Copak jste zmínil - jste to neřekl, že hlava, to bylo inicializována na hodnotu NULL na začátku. Ale myslel jsem, že jsi říkal, že je v pořádku. 

JASON Hirschhorn: Pojďme - pojďme se podívat v GDB, a pak půjdeme zpátky. Ale vypadá to, že už máte některé myšlenky o tom, co se děje. Takže chceme vložit něco. OK. Máme vložit. Prosím, zadejte int. Budeme vložte tři. A pak jsem na této trati. Jak mám jít spustit ladění vložka známé funkce? Ach můj bože. To je hodně. Je to vyšilovat hodně? 

DIVÁKŮ: Oh, to zemřel. 

JASON Hirschhorn: jsem vytáhl ho ven. OK. 

DIVÁKŮ: Možná, že je to druhý konec drátu. 

JASON Hirschhorn: Wow. Takže spodním řádku - Co jsi říkal? 

DIVÁKŮ: Řekl jsem, že ironie technické potíže v této třídě. 

JASON Hirschhorn: Já vím. Kéž bych měl kontrolu nad tou částí. [Neslyšitelný] To zní skvěle. Proč ne vy začít přemýšlet o tom, to, co jsme mohli udělat špatně, a budeme zpět za 90 sekund. 

Avica, budu se vás zeptat, jak to chodí uvnitř insert_node ladit. Tak tohle je místo, kde jsme naposledy skončili. Jak mohu jít dovnitř insert_node, Avica, zkoumat, co se děje? Co GDB příkazu? Přestávka by mě vzít dovnitř. Má Marquise vědět? 

DIVÁKŮ: Co? 

JASON Hirschhorn: Jaký příkaz GDB Používám jít dovnitř této funkce? 

DIVÁKŮ: krok? 

JASON Hirschhorn: Krok přes S. To mě bere dovnitř. OK. New_node mallocing nějaký prostor. To vše vypadá jako jeho bude. Pojďme prozkoumat new_node. To má nějakou adresu v paměti. Pojďme se podívat - že je vše v pořádku. Takže všechno zde zdá se, pracovat správně. 

DIVÁKŮ: Jaký je rozdíl mezi P a displej? 

JASON Hirschhorn: P je zkratka pro tisk. A tak se ptáte, co je Rozdíl mezi tímto a to? V tomto případě nic. Ale obecně jsou některé rozdíly. A měli byste se podívat do manuálu GDB. Ale v tomto případě nic. Máme tendenci používat tisk, ačkoli, protože nepotřebujeme dělat mnohem víc, než vytisknout jednu hodnotu. 

OK. Takže jsme na řádku 80 našeho kódu, nastavení uzlu * curr rovnající se seznamu. Pojďme vytisknout curr. To se rovná seznamu. Sladké. Počkejte. To se rovná něco. To se nezdá být v pořádku. Tam jdeme. Je to proto, že v GDB, vpravo, pokud je to čára, že jste na to nebyl proveden ještě. Takže je potřeba, aby skutečně psát Vedle provedení linky než vidět své výsledky. Tak jsme tady. Jen jsme provedli tento řádek, předchozí rovná null. Takže znovu, pokud tiskneme předchozí nebudeme vidět nic divného. Ale pokud jsme skutečně spustit, že linka, pak uvidíme že linka funguje. 

Takže máme curr. Ti, kteří jsou oba dobré. Je to tak? Teď jsme na této trati tady. Zatímco Měna není rovno null. No, co dělá bc stejné? Právě jsme viděli, že se rovnal null. Vytisknout jsme to. Budu ji vytisknout znovu. Tak je to, že zatímco smyčka bude provádět? 

Diváků: Ne 

JASON Hirschhorn: Takže, když jsem napsal, že linka, vidíte, jsme skočili po celou cestu až na dno, vrátí false. A pak se budeme vracet false a vrátit se do našeho programu a nakonec vytisknout, jak jsme viděli, vložka nebyla úspěšná. Takže, někdo nějaké nápady na to, co musíme udělat, aby tento problém vyřešit? Budu čekat, dokud neuvidím pár rukou nahoru. Nechtěli jsme spustit tento. Mějte na paměti, to byl první co jsme dělali. Nebudu dělat pár. Budu dělat jen málo. Vzhledem k tomu pár znamená dva. Počkám na více než dva. 

První vložení, bc, ve výchozím nastavení se rovná null. A tato smyčka provádí-li pouze pokud bc není null. Tak jak mohu získat kolem tohoto? Vidím tři ruce. Počkám na více než tři. Marcusi, co si o tom myslíte? 

DIVÁKŮ: No, pokud to budete potřebovat, aby provést více než jednou, stačí změnit jej na do-while. 

JASON Hirschhorn: OK. Bude to vyřešit náš problém, ne? 

DIVÁKŮ: V tomto případě není, protože Skutečnost, že seznam je prázdný. Takže pak jste pravděpodobně stačí přidat prohlášení, že v případě, že smyčka ukončí pak musíte být na konci roku list, na kterém místě se vám stačí vložit ji. 

JASON Hirschhorn: Líbí se mi to. To dává smysl. Je-li smyčka ukončí - proto, že se vrátím false zde. Takže pokud smyčky východů, pak jsme na konec seznamu, nebo možná začátek seznamu, pokud tam nic není je to, které je stejné jako na konci. Takže teď chceme vložit něco zde. Tak jak to, že kód vypadat, Marcusi? 

DIVÁKŮ: Pokud jste již dostal uzel malloced, mohl by si říct, new_node-> další roven null, protože , že musí být na konci. Nebo new_node-> Další rovná null. 

JASON Hirschhorn: OK. Promiňte. New_node-> další roven null proto, že jsme na konci. To není dát dovnitř Jak můžeme dát je na seznamu? Správně. To je jen nastavením rovná. No, jak to vlastně vložte jej do seznamu? Co ukazuje na konec seznamu? 

DIVÁKŮ: Head. 

JASON Hirschhorn: Je nám líto? 

DIVÁKŮ: Hlava směřuje na konec seznamu. 

JASON Hirschhorn: Pokud není nic v seznam, hlava směřuje k konec seznamu. Takže to bude fungovat pro první vložení. A co v případě, že jsou pár věci na seznamu? Než nechceme nastavit hlava rovná new_node. Co chceme, aby tam dělat? Jo? Pravděpodobně předchozí. Bude to fungovat? Připomeňme, že předchozí je jen ukazatel na uzel. A předchozí je lokální proměnná. Takže tento řádek bude nastaven lokální proměnné, předchozí, která se rovná nebo směřovat k tomuto novému uzlu. To nebude ve skutečnosti dát v našem seznamu, ačkoli. Jak jsme dali, že v našem seznamu? Akchar? 

DIVÁKŮ: Myslím, že vám to aktuální-> další. 

JASON Hirschhorn: OK. akt-> další. Takže znovu, jediný důvod, proč jsme se Zde je to, co dělá proud rovný? 

DIVÁKŮ: Rovná null. 

JASON Hirschhorn: A tak co se stane, když budeme dělat null-> další? Co dostaneme? Dostaneme segmentation fault. 

DIVÁKŮ: Do bc rovná null. 

JASON Hirschhorn: To je totéž jako prev, ačkoli, protože tam je lokální proměnná jsme nastavení rovnající se této nové uzlu. Vraťme se k našemu obrazu vkládání něco. Řekněme, že jsme vkládání na konec seznamu, tak tady. Máme aktuální ukazatel, který je ukazuje na null a předchozí bod že je ukazuje na 8.. Takže to, co potřebujeme aktualizovat, Avi? 

DIVÁKŮ: Předchozí-> dál? 

JASON Hirschhorn: Předchozí-> další je to, co chceme aktualizovat, protože to bude skutečně vložte jej na konec seznamu. Máme ještě jednu chybu, i když, že budeme běžet do. Co je to chyba? Jo? 

DIVÁKŮ: Bude to návrat false v tomto případě? 

JASON Hirschhorn: Oh, je se chystá se vrátit false. Ale je tu další problém. Takže budeme muset dát na oplátku skutečné. 

DIVÁKŮ: Má předchozí stále stejná null v horní části seznamu? 

JASON Hirschhorn: Tak ještě předchozí rovná null na samém začátku. Takže, jak můžeme dostat přes to? Jo? 

DIVÁKŮ: Myslím, že můžete udělat kontrolu před while, aby zjistil, jestli je to prázdný seznam. 

JASON Hirschhorn: OK. Takže pojďme zde. Proveďte kontrolu. Pokud - 

DIVÁKŮ: Takže pokud hlava rovná se rovná null. 

JASON Hirschhorn: Je-li hlava rovná se rovná null - že nám řekne, jestli je to prázdný seznam. 

DIVÁKŮ: A pak jste to hlava rovná nové. 

JASON Hirschhorn: Head rovná new_node? A co ještě musíme udělat? 

DIVÁKŮ: A pak se vrátit true. 

JASON Hirschhorn: Ne tak docela. Chybí nám jeden krok. 

DIVÁKŮ: New_node další má upozornit na hodnotu null. 

JASON Hirschhorn: Přesně tak, Alden. A pak se můžeme vrátit true. OK. Ale je to pořád dobrý nápad udělat věci na konci seznamu, ne? Dobrá. Stále by ve skutečnosti mohly dostat na konec seznamu. Tak je tento kód v pořádku, pokud jsme na konec seznamu, a tam jsou některé věci na seznamu? Je to tak? Vzhledem k tomu máme ještě Marcusův nápad. Mohli bychom opustit tuto smyčku, protože jsme na konci seznamu. Takže jsme stále chtějí to kód tady dole? 

DIVÁKŮ: Ano. 

JASON Hirschhorn: Jo. A co musíme změnit to? Pravda. Zní to dobře všem tak daleko? Někdo nějaké - Avi, máte něco dodat? 

Diváků: Ne 

JASON Hirschhorn: OK. Takže jsme udělali pár změn. Udělali jsme tuto kontrolu, než jsme šel na prázdný seznam. Takže jsme se postarali o prázdného seznamu. A tady jsme se starali o vkládání něco na konec seznamu. Takže to vypadá, že tento zatímco smyčka odběru péče o věci mezi tím, někde v seznamu, pokud jsou věci, které v seznamu. 

OK. Pojďme tento program spustit znovu. Není úspěšná. 

DIVÁKŮ: Vy jste to. 

JASON Hirschhorn: Oh, Neudělal jsem to. Dobrý postřeh, Michael. Pojďme přidat značku spojenou. Linka 87 je tam chyba. Linka 87. Alden, to byl linku, kterou mi dal. Co se děje? 

DIVÁKŮ: Musí to být null. 

JASON Hirschhorn: Výborný. Přesně tak. Mělo by to být null. Pojďme udělat znovu. Kompilace. OK. Pojďme vložte tři. Vložka byla úspěšná. Pojďme ji vytisknout. Ach, kdyby jen mohli zkontrolovat. Ale my jsme neudělali tisk ještě funkci. Pojďme zadat něco jiného. Co bychom měli vstoupit? 

DIVÁKŮ: Sedm. 

JASON Hirschhorn: Seven? 

DIVÁKŮ: Ano. 

JASON Hirschhorn: Máme poruchu seg. Takže máme jednu, ale jasně nemůže dostat dva. Je 5:07. Takže bychom to mohli ladit po dobu tří minut. Ale já jdu na nás tady nechat a přejít na hash tabulky. Ale opět, odpovědi tohoto kódu Budu poslat e-mailem na vás trochu. Jsme velmi blízko k ní. Vřele doporučujeme vám zjistit, co se děje tady a opravit ji. Tak jsem vám pošleme tento kód jako dobře a řešení - pravděpodobně řešení později. Nejprve tento kód. 

Další věc, kterou chci udělat, než my Povrchová úprava je nám není uvolněno nic. Takže chci vám ukázat, co valgrind vypadá. Pokud narazíme Valgrind hranice na našem programu,. / spojené. Opět platí, že podle tohoto snímku, se by měl běžet valgrind s nějakým typem možnost, v tomto případě - Únik kontrola = plná. Takže pojďme napsat Valgrind - Únik kontrola = plná. Takže to bude běžet Valgrind na našem programu. A teď se program vlastně běží. Takže jdeme na to běžet stejně jako před, dát něco dovnitř Chystám se dát ve třech. To funguje. Nebudu se snažit dát do něčeho jiného, ​​protože budeme dostat seg false v tomto případě. Tak jsem jen tak odejít. 

A teď vidíte, tady dole úniku a shrnutí haldy. To jsou dobré věci, které Chcete-li vyzkoušet. Takže shrnutí haldy - to říká, v provozu na výstupu - osm bajtů v jednom bloku. To jeden blok uzel jsme malloced. Michaeli, jsi říkal před uzel je osm kousnutí, protože má celé číslo a ukazatel. Tak to je náš uzel. A pak se říká, že jsme použili malloc sedmkrát a budeme osvobozeni něco šestkrát. Ale my jsme nikdy volal zdarma, takže nemám tušení, co je to mluvíš. 

Ale stačí, když řeknu, že když si program běží, malloc je nazýván v některých jiných místech, kde se Nemusíte se obávat. Takže malloc byl pravděpodobně nazvaný v některých místech. Nepotřebujeme dělat starosti, kde. Ale je to opravdu my. První řádek je nám. Opustili jsme tento blok. A vidíte, že zde v souhrnu úniku. Ještě dosažitelný - osm bajtů v jednom bloku. To znamená, že paměť - jsme unikly, že paměť. Definitivně ztratil - něco, co se ztratil nadobro. Obecně platí, že nebudete nic vidět zde. Přesto je obecně dostupný, pokud budete vidět věci, kde budete chtít se podívat, co kód, který by měl se osvobodil, ale jste zapomněli osvobodit. 

A pak, pokud to není tento případ, pokud jsme udělali vše zdarma, můžeme zjistit, že. Řekněme, spusťte program není uvedení v ničem. Uvidíte tady v použití na výstupu - nula bajtů nulových bloků. To znamená, že skoro nic neopustila pokud tento program ukončen. Takže před zapnutím v pset6, spusťte Valgrind a ujistěte se, že nemáte úniky jakékoliv paměti ve vašem programu. Pokud máte jakékoli dotazy s valgrind, neváhejte oslovit. Ale to je, jak jej použít. Velmi jednoduchá - zjistit, jestli jste mají v užívání na výstupu - žádné bytů v jakýchkoli bloků. 

Takže jsme pracovali na vložení uzlu. Měl jsem dvě další funkce zde - tisknout uzly a uzly zdarma. Opět platí, že se jedná o funkce, které jsou bude pro vás dobré praxe protože vám pomůže nejen s tato cvičení vzorku, ale také na problém nastavit. Oni map na docela blízko k věcem budete muset udělat v problém nastavit. Ale já chci, aby se ujistil, se dotkneme na všechno. A hash tabulky jsou také velmi důležité, aby co děláme v části této týden - nebo v sadě problém. 

Takže jdeme dokončit část mluví o hash tabulky. Pokud zjistíte, že jsem malý hash tabulky. To není to, co mluvíme o, nicméně. Hovoříme o jiný typ hash tabulky. A v jeho jádru, hash tabulky není nic víc než pole a hashovací funkce. Budeme mluvit na chvíli jen ujistěte se, že každý chápe, co je to hash funkce. A já vám říkám teď, že je nic víc než dvě věci - pole a hashovací funkce. A tady jsou kroky, prostřednictvím které toto funguje. 

Tady je náš pole. Tady je naše funkce. Zejména, hashovací funkce je třeba udělat pár věcí s tím. Já budu mluvit konkrétně o tento problém nastavit. Je to pravděpodobně bude se v řetězci. A co to jde vrátit? Jaký typ dat? Alden? Váš hash funkce vrátit? Číslo. Tak tohle je to, co hash Tabulka se skládá z - tabulka ve formě pole a hashovací funkce. Jak to funguje? Pracuje ve třech krocích. Dáváme mu klíč. V tomto případě, dáme to řetězec. Říkáme funkce hash za první krok na klíč a dostaneme hodnotu. 

Konkrétně budeme říkat dostaneme číslo. To celé číslo, jsou velmi specifické hranice toho, co může být, že celé číslo. V tomto příkladu, naše pole o velikosti tři. Takže to, co čísla lze, že číslo je. Jaký je rozsah platných hodnot pro že celé číslo, návratový typ této hash funkce? Nula, jedna a dvě. Bod hašovací funkce je přijít na místo v poli kde je naším klíčovým děje. Existují pouze tři možné místa zde - nula, jeden, nebo dva. Takže tato funkce lepší návratnost nula, jeden, nebo dva. Některé platný Index v tomto poli. 

A pak v závislosti na tom, kde se vrátí, můžete vidět, že pole otevřené úhelník hodnotu. To je místo, kde jsme dali klíč. Tak jsme hodit do dýně, dostaneme ven nulu. Na poli držáku 0, dáme dýni. Hodíme u koček, dostaneme se na jednu. Dali jsme kočku v jednom. Dali jsme do pavouka. Vystupujeme dva. Dali jsme pavouka na pole držáku dvou. Bylo by to hezké, kdyby to fungovalo takhle. Ale bohužel, jak uvidíme, je to trochu složitější. 

Než se tam dostaneme, jakékoliv dotazy o tento základní set-up z hash tabulky? To je obraz přesně co nakreslil na tabuli. Ale od té doby jsme ji nakreslil na tabuli, jsem Nehodlám jít do toho dál. V podstatě klíče, magie černá skříňka - nebo v tomto případě, teal box - z hash funkce je staví do kbelíků. A v tomto případě jsme není uvedení názvu. Dáváme tím spojené telefonu číslo jméno v kbelíku. Ale vy jste mohl velmi dobře jen dát jméno do kbelíku. 

To je jen obraz toho, co jsme vycházeli z hrací plochy. Máme potenciální úskalí, ačkoli. A tam jsou dva a to zejména skluzavky, že chci jít pryč. První z nich je o funkce hash. Tak jsem se zeptal na otázku, co dělá dobrý hash funkce? Dávám dvě odpovědi. První je, že je deterministický. V souvislosti s hašovacích funkcí, Co to znamená? Ano? 

DIVÁKŮ: Je možné najít Obsah v konstantním čase? 

JASON Hirschhorn: To není to, co to znamená. Ale to je dobrý odhad. Někdo jiný má hádat na to, co to znamená? To je dobrá funkce hash je deterministický? Annie? 

DIVÁKŮ: To klíč může být mapován pouze na jedno místo v tabulce hash. 

JASON Hirschhorn: To je Přesně tak. Pokaždé, když dáte do dýně, vždy vrátí nulu. Pokud dáte do dýně a vaše hash Funkce vrací nulu, ale má pravděpodobnost vrácení něco jinak větší než nula - takže možná to může vrátit jednu někdy nebo dva jiné časy - že není dobré funkce hash. Ty jsi naprostou pravdu. Váš hash funkce by měla vrátit Stejný přesné číslo, v tomto případě pro stejný přesný řetězec. 

Možná, že se vrátí přesně stejnou číslo pro stejný řetězec přesné bez ohledu na kapitalizaci. Ale v tomto případě je to ještě deterministický, protože více věcí jsou mapovány na stejnou hodnotu. To je v pořádku. Jak dlouho jak tam je jen jeden výstup pro daný vstup. 

OK. Druhá věc je, že vrátí platné indexy. Přivezli jsme si, že dříve. Tento hash funkce - oh boy - hašovací funkce by návrat platné indexy. Takže říci - vraťme se k tomuto příkladu. Můj hash funkce počítá až písmena ve slově. To je funkce hash. A vrátí, že celé číslo. Takže když mám slovo A, je to chystá se vrátit jeden. A to bude dát tady. Co když jsem dal slovo bat? Bude to vrátit tři. Kde se bat jít? 

To se nehodí. Ale je třeba někam jít. To je můj hash tabulka po tom všem, a vše, co je třeba někam jít. Takže tam, kde by se bat jít? Jakékoliv myšlenky? Hádá? Dobré odhady? 

DIVÁKŮ: Zero. 

JASON Hirschhorn: Proč nula? 

DIVÁKŮ: Vzhledem k tomu, tři modulo tři je nula? 

JASON Hirschhorn: Three modulo tři je nula. To je skvělý odhad, a to je správné. Takže v tomto případě by měl asi jít na nulu. Takže dobrý způsob, jak zajistit, aby tento hash Funkce vrací pouze platné indexy se na modulo to podle velikosti tabulky. Pokud modulo Cokoliv přiznání podle tři, jste vždy dostane něco mezi nulou, jeden a dva. A pokud se to vždy vrací sedm, a vždy modulo tři, ty jsi Vždycky dostane to samé. 

Takže je to stále deterministický pokud modulo. Ale, že zajistí, že vám Nikdy si něco - neplatný průmyslu. Obecně platí, že modulo by se mělo stát uvnitř hash funkce. Takže nemusíte se starat o to. Ty prostě nemůže zajistit, že to je platný Index. Jakékoliv dotazy týkající se této potenciální úskalí? 

OK. A tam jdeme. Další potenciální úskalí, a To je velký. Co když mapa dva klíče na stejnou hodnotu? Takže existují dva způsoby, jak zvládnout to. První z nich se nazývá lineární snímání, které jsem ne jít pryč. Ale měli byste být obeznámeni s tím, jak že funguje a co to je. 

Druhý Chystám se jít přes protože to je ten, že mnoho lidé budou pravděpodobně skončí rozhodování o tom, používat v jejich problému sadě. Samozřejmě, že nemusíte. Ale pro problémové sady, mnoho lidí mají sklon vybírat si vytvořit hash tabulky s oddělenou řetězení provedení jejich slovníku. Takže jsme jít nad tím, co to znamená, k vytvoření hash tabulky se oddělené zřetězení. 

Tak jsem se dal do dýně. Je to vrátí nulu. A dal jsem dýně zde. Pak jsem se dal do - co je další Halloween-themed věc? 

DIVÁKŮ: Candy. 

JASON Hirschhorn: Candy! To je skvělá jedna. Dal jsem do cukroví a sladkosti také mi dává nulu. Co mám dělat? Nějaké nápady? Protože jste všichni tak nějak vím, co oddělený řetězení je. Takže nějaké nápady, co dělat? Jo. 

DIVÁKŮ: Uvedení řetězec ve skutečnosti v tabulce hash. 

JASON Hirschhorn: Tak jdeme na nakreslit dobrý nápad sem. OK. 

DIVÁKŮ: Už Hashtable [Neslyšitelný] ukazatel, který ukazuje na začátek seznamu. A pak si dýně být první hodnota v tomto propojeném seznamu a sladkosti se druhá hodnota v tomto propojeném seznamu. 

JASON Hirschhorn: OK. Marcus, že byl vynikající. Chystám se zlomit dolů. Marcus říká ne přepsat dýně. To by bylo špatné. Nedávejte cukroví někde jinde. Chystáme se dát oba na nule. Ale budeme se zabývat jejich uvádění na nulu vytvoření seznamu na nulu. A budeme-li vytvořit seznam vše, mapované na nulu. A nejlepší způsob, jak jsme se naučili vytvářet Seznam, který může růst a zmenšovat dynamicky není v další pole. Takže ne multi-dimenzionální pole. Ale jen vytvoření propojeného seznamu. 

Takže to, co navrhl - Jdu si nový - je vytvořit pole s ukazateli, pole ukazatelů. OK. Nějaký nápad, nebo náznak toho, co typ z těchto ukazatelů by měly být? Marcus? 

DIVÁKŮ: Ukazatele na - 

JASON Hirschhorn: Protože vám řekl spojový seznam, takže - 

DIVÁKŮ: ukazatele uzlu? 

JASON Hirschhorn: ukazatele uzlu. Pokud se věci v našem spojené Seznam jsou uzly pak by měla být uzel ukazatele. A to, co se jim rovnají původně? 

DIVÁKŮ: Null. 

JASON Hirschhorn: Null. Takže je tu náš prázdná věc. Dýňová vrátí nulu. Co budeme dělat? Procházka mě přes něj? Vlastně, Marcus už mi dal. Někdo chodí mě přes něj. Co budeme dělat, když - to vypadá velmi podobně jako to, co jsme právě dělá. Avi. 

DIVÁKŮ: Budu hádat. Takže když se dostanete bonbóny. 

JASON Hirschhorn: Jo. No, máme dýně. Pojďme si naši první. Máme dýně. 

DIVÁKŮ: OK. Dýňová vrátí nulu. Takže jste to v tom. Nebo vlastně, to si dal v propojeném seznamu. 

JASON Hirschhorn: Jak jsme vložte jej do propojeného seznamu? 

DIVÁKŮ: Oh, je vlastní syntaxe? 

JASON Hirschhorn: Jen chodit - říci více. Co budeme dělat? 

DIVÁKŮ: Jen vložit že jako první uzel. 

JASON Hirschhorn: OK. Takže máme uzel, dýně. A teď, jak mám vložit to? 

DIVÁKŮ: Můžete přiřadit to ukazatel. 

JASON Hirschhorn: Jaké ukazatele? 

Diváků: ukazatel na nule. 

JASON Hirschhorn: Tak kde dělá tento bod? 

DIVÁKŮ: Chcete-li null právě teď. 

JASON Hirschhorn: No, to ukazuje na hodnotu null. Ale dávám do dýně. Takže tam, kde by to ukazovat? 

DIVÁKŮ: Chcete-li dýně. 

JASON Hirschhorn: Chcete-li dýně. Přesně tak. Takže to ukazuje na dýně. A kde se to dělá ukazatel v dýně bodu? Na 

DIVÁKŮ: Null. 

JASON Hirschhorn: Chcete-li hodnotu null. Přesně tak. Takže jsme prostě vloží něco do propojeného seznamu. Právě jsme napsal tento kód, jak to udělat. Téměř jsme skoro mám zcela popraskané. Nyní vložíme bonbóny. Naše cukroví také klesne na nulu. Tak co budeme dělat cukroví? 

DIVÁKŮ: Záleží na tom, zda Není se snažíme třídit. 

JASON Hirschhorn: To je Přesně tak. Záleží na tom, zda snažíme se ho vyřešit. Předpokládejme, že nejsme bude třídit. 

DIVÁKŮ: Tak, jak jsme se bavili před, je to nejjednodušší jen aby to hned na začátku, aby ukazatel od nulových bodů, do cukroví. 

JASON Hirschhorn: OK. Vydrž. Dovolte mi, abych vytvořit cukroví právě zde. Takže tento ukazatel - 

DIVÁKŮ: Jo, měl by se se ukázal na cukroví. Pak se ukazatel od candy přejděte na dýně. 

JASON Hirschhorn: Jako, že? A říct, že jsme dostali další věc map na nulu? 

DIVÁKŮ: No, právě dělat to samé? 

JASON Hirschhorn: Proveďte totéž. Takže v tomto případě, když to neuděláme chcete, aby ji udrželi řazeny ji Zní to poměrně jednoduché. Bereme ukazatel na Index vzhledem k naší hash funkce. Musíme tento bod do našeho nového uzlu. A pak, co to bylo ukázal dříve - v tomto případě hodnotu null, v Druhý případ dýně - že, jak se to ukazuje na dříve, přidáme do nejbližšího náš nový uzel. Jsme vkládání něco na začátku. Ve skutečnosti je to mnohem jednodušší, než se snaží udržet seznamu seřazeny. Ale opět, vyhledávání bude více komplikované tady. Budeme mít vždy jít až do konce. 

OK. Máte otázky k samostatné řetězení? Jak to funguje? Prosím, zeptejte se jich teď. Opravdu chci, aby se ujistil všechny pochopit, než jsme vyrazit. 

DIVÁKŮ: Proč si dát dýni a cukroví do stejné část tabulky hash? 

JASON Hirschhorn: Dobrá otázka. Proč dát je do stejné část tabulky hash? No, v tomto případě naše hash funkce vrátí nulu pro obě z nich. Takže je třeba jít na Index nule protože to je místo, kde budeme podívejte se na ně, pokud se někdy Chcete je vyhledat. Opět platí, že se lineární snímání přístupu bychom jim dát oba na nule. Ale v samostatném přístupu řetězce, jdeme dát oba na nule a pak vytvořit seznam off nulu. 

A my nechceme přepsat dýně jen pro to, protože pak budeme Předpokládám, že dýně se nikdy vložena. Pokud budeme jen držet jednu věc místo, které by bylo špatné. Pak by tam být žádný šance na nás vůbec - jestliže jsme kdy měli duplikát, pak jsme by jen vymazat naši počáteční hodnotu. Takže to je důvod, proč děláme tento přístup. Nebo, že je důvod, proč jsme se rozhodli - ale opět, my zvolil samostatný zřetězení přístup, , které je zde mnoho dalších přístupů by se dalo vybrat. Znamená to, že odpověď na vaši otázku? 

OK. Carlos. Lineární snímání by znamenalo - pokud bychom našli kolizi na nule, jsme bude vypadat v dalším místě, aby zjistili, zda to bylo otevřené a dát to tam. A pak se podíváme v dalším sportu a uvidíme, jestli to bylo otevřené a dát to tam. Tak jsme se najít další dostupné otevřené místo a dát to tam. Nějaké další otázky? Jo, Avi. 

DIVÁKŮ: V návaznosti na to, Co myslíš tím dalším místě? V tabulce hash nebo propojeného seznamu. 

JASON Hirschhorn: Pro lineární programování, žádné spojové seznamy. Další místo na stole hash. 

DIVÁKŮ: OK. Takže hash tabulka bude inicializován velikosti - jako je počet řetězců že jste byli vkládání? 

JASON Hirschhorn: Ty by Chci, aby to bylo opravdu velké. Ano. Zde je obrázek toho, co jsme jen kreslil na tabuli. Opět máme kolizi tady. 152. A uvidíte, jsme vytvořili spojový seznam z ní. Opět platí, že hash tabulky oddělené zřetězení přístup není ten, který musí brát v nastavení problémy šest, ale je jedno, že mnoho studenti mají tendenci brát. Tak v takovém případě, pojďme krátce pohovořil předtím, než jsme vyrazit o problému šest, a pak budu sdílet svůj příběh se s vámi. Máme tři minuty. 

Problém set šest. Máte čtyři funkce - zatížení, zkontrolujte, velikost, a vyložit. Load - dobře, že jsme se děje po zátěži právě teď. Kreslil jsme zatížení na palubě. A dokonce jsme začali kódování hodně vložení do propojeného seznamu. Takže zatížení není o moc větší než to, co jsme právě dělali. 

Kontrola je jednou budete mít něco načíst. Je to stejný proces, jako je tento. Stejné první dvě části, kde se hodit něco, co do funkce hash a získat jeho hodnotu. Ale teď nejsme vložení. Nyní hledáme pro něj. Jsem ukázkový kód napsaný pro vyhledávání něco v propojeném seznamu. Chtěl bych vyzvat vás k praxi, že. Ale intuitivně najít něco, co je docela podobný vkládání něco. Opravdu jsme nakreslil obrázek najít něco v propojeném seznamu, pohybující se až dokud se dostal až do konce. A pokud jste se dostali na konec a nemohl najít, pak to tam není. Tak to je kontrola, v podstatě. 

Další je velikost. Pojďme přeskočit velikosti. Konečně jste se uvolnit. Uvolnit je ta, kterou jsme dosud vypracovány na palubě nebo ještě kódované. Ale já Doporučujeme vám vyzkoušet kódování v našem vzorku Google například seznam. Ale vyložit intuitivně je podobný zdarma - nebo jsem na mysli, je podobný zkontrolovat. S výjimkou teď pokaždé, když vy budete díky, že jste prostě kontroluje, zjistit, zda máte hodnotu tam. Ale ty bereš ten uzel a uvolňovat to, v podstatě. To je to, co vyložit vás zeptá na to. Zdarma všechno, co jste malloced. Takže jdete přes celý seznam opět prochází celý hash opět tabulka. Tentokrát se nekontrolují vidět, co tam je. Stačí uvolnit to, co tam je. 

A konečně velikosti. Velikost by měla být provedena. Pokud nechcete provádět velikost - Řeknu to takhle. Pokud nechcete provádět velikost v přesně jeden řádek kódu, včetně vrátit prohlášení, jste dělá velikost nesprávně. Takže ujistěte se, že velikost, pro úplné provedení body, děláte to přesně jeden řádek kódu, včetně return. 

A to zabalit ještě, Akchar. Snaživec. Chtěl jsem říct, děkuji kluci přišel do sekce. Mají Happy Halloween. To je můj kostým. Budu mít na sobě tento čtvrtek když jsem tě vidět na úřední hodiny. A pokud jste zvědaví, někteří více pozadí, jak k tomuto kostýmu, cítíte zdarma vyzkoušet 2.011 sekce pro příběh o tom, proč jsem na sobě kostým dýně. A to je smutný příběh. Takže ujistěte se, že máte Některé tkáně v okolí. Ale na to, že pokud máte nějaké otázky, budu držet kolem mimo po bodu. Hodně štěstí na problém nastavit šest. A jako vždy, pokud máte nějaké otázky, dejte mi vědět.