>> JASON Hirschhorn: Vitajte všetci k § Seven.
Sme v týždni sedem kurze.
A to nadchádzajúce štvrtok je Halloween, takže som
oblečený ako tekvica.
Nemohol som sa ohnúť a dať na moje topánky, takže to je dôvod, prečo som
len v ponožkách.
Som tiež na sebe nič pod to, takže nemôžem dať dole, ak je to
rušivo na vás.
Vopred sa ospravedlňujem za to.
Nemusíte si predstaviť, čo sa deje.
Mám na sebe trenírky.
Takže je to všetko dobré.
>> Mám dlhší príbeh o tom, prečo som oblečený ako tekvica, ale budem
okrem toho, že neskôr v tejto sekcii pretože chcem, aby ste mohli začať.
Máme veľa zaujímavých vecí ísť na tento týždeň.
Väčšina z nich sa priamo vzťahujú k tejto týždeň problém set, pravopisné chyby.
Chystáme sa ísť cez spojené zoznamy a hash tabuľky
za celý oddiel.
Každý týždeň dal som tento zoznam sa, zoznam prostriedky pre vás, aby vám pomohol s
materiál na tomto kurze.
Je-li na rozpakoch, alebo ak hľadáte pre niektoré viac informácií, pozrite sa na jednu z
Tieto zdroje.
>> Opäť platí, že pset6 je preklepov, tento týždeň pset.
A to tiež povzbudzuje vás, a ja Odporúčame vám, použiť iné
prostriedky špeciálne pre tento pset.
Najmä tri som uvedené na obrazovke -
gdb, ktorý sme boli oboznámení s a bol s použitím na chvíľu teraz, je
Bude veľmi užitočné tento týždeň.
Tak som si dal, že až tu.
Ale vždy, keď pracujete s C, mali by ste byť vždy pomocou gdb do
ladenie programov.
Tento týždeň tiež Valgrind.
Vie niekto, čo Valgrind robí?
>> DIVÁKOV: Kontroluje úniky pamäte?
>> JASON Hirschhorn: Valgrind kontroly tesnosti pamäti.
Takže ak ste malloc niečo vo vašej Program, sa pýtate na pamäti.
Na konci programu, budete mať písať zadarmo na všetko, čo ste
malloced aby pamäti späť.
Ak nechcete písať zadarmo na konci a Váš program je dodávaný k záveru,
všetko sa automaticky byť oslobodený.
A pre malé programy, je to Nie je to veľký problém.
Ale ak píšete dlhší beh program, ktorý sa neukončí,
nutne, za pár minút alebo pár sekúnd, potom sa nevracia pamäť
môže byť obrovský problém.
>> Takže pset6, očakáva, že budete mať nulovú pamäť úniky
váš program.
Ak chcete skontrolovať tesnosť pamäti, spustite Valgrind a dám ti nejaký pekný
výstup vám vedieť, či alebo nie všetko bolo zadarmo.
Budeme cvičiť s ním neskôr dnes, dúfajme.
>> Konečne, príkaz diff.
Použili ste niečo podobné na to v pset5 s Peek nástroja.
Povolené môžete sa pozrieť dovnútra.
Môžete tiež použiť diff, taky, za problém nastaviť špec.
Ale nechá vás porovnať dva súbory.
Dalo by sa porovnať rastrový súbor a info hlavičky riešenia zamestnancov a
vaše riešenie v pset5 ak ste sa rozhodli použiť.
Rozdiel vám umožní to, že rovnako.
Môžete porovnať správnu odpoveď na tento týždeň problém nastavená na vašu odpoveď
a sledujte, či sa zoradia alebo pozri kde sú chyby.
>> Tak to sú tri dobré nástroje, ktoré by ste mali použiť pre tento týždeň, a
určite skontrolujte svoj program s týmito tromi nástrojmi
než ju dovnútra
Opäť, ako som sa už zmienil každý týždeň, Ak máte akúkoľvek spätnú väzbu pre mňa - ako
pozitívny a konštruktívny -
neváhajte a zamierte na webové stránky v spodnej časti tohto snímku
a vstup je tam.
Naozaj si toho vážim akékoľvek a všetky spätnej väzby.
A keď mi dáš konkrétne veci, ktoré Môžem urobiť pre zlepšenie, alebo, že som
robí dobre, že ste ma chceli pokračovať, beriem k srdcu a
naozaj snažiť počúvať na Váš názor.
Nemôžem sľúbiť, že budem robiť všetko, aj keď, ako na sebe
tekvica kostým každý týždeň.
>> Takže budeme tráviť väčšinu časť, ako som už spomenul, hovorí o
spojové zoznamy a hashovacie tabuľky, z ktorých budú priamo použiteľná pre
problém nastaviť tento týždeň.
Spojové zoznamy pôjdeme cez relatívne rýchlo, pretože sme strávili trochu kusavou
času, bude cez to v reze.
A tak sa dostaneme priamo do kódovanie problémy spojových zoznamov.
A potom na konci budeme hovoriť o tom, hash tabuľky a ako sa tento
týždeň problém nastaviť.
>> Vy ste videl tento kód.
To je struct, a definuje niečo nové, tzv uzol.
A v uzle je celé číslo tu a tam je ukazovateľ na
iný uzol.
Už sme videli to.
To bolo prísť na Pár teraz týždňov.
To kombinuje ukazovatele, ktoré sme boli prácu s, a štruktúr, ktoré umožňujú
nám spojiť dva rôzne veci do jedného dátového typu.
>> Je tu veľa deje na obrazovke.
Ale to by malo byť relatívne oboznámení s vami.
Na prvom riadku sme vyhlásiť nový uzol.
A potom sa v tomto novom uzle, nastaviť celé číslo sa tým, že k jednému uzlu.
Vidíme na ďalšom riadku robím printf príkaz, ale ja som sivo
príkaz printf, pretože naozaj Dôležitou súčasťou je táto linka tu -
new_node.n.
Čo bodka znamená?
>> DIVÁKOV: Choďte do uzla a posúdiť n hodnotu pre neho.
>> JASON Hirschhorn: To je Presne tak.
Dot znamená, že prístup k N part tohto nového uzla.
Tento ďalší riadok čo robí?
Michael.
>> DIVÁKOV: Vytvára ďalšie uzol ktorá bude ukazovať na nový uzol.
>> JASON Hirschhorn: Takže to nie je vytvoriť nový uzol.
Vytvára čo?
>> DIVÁKOV: ukazovateľ.
>> JASON Hirschhorn: ukazovateľ na uzol, ako je uvedené v tomto uzle * tú.
Takže to vytvára ukazovateľ na uzol.
A ktorý uzol je smerujúca k, Michael?
>> DIVÁKOV: Nový uzol?
>> JASON Hirschhorn: Nový uzol.
A to je ukázal, že preto, že sme vzhľadom k tomu adresu nového uzla.
A teraz v tomto riadku vidíme dva rôzne spôsoby
vyjadruje rovnakú vec.
A chcel som poukázať na to, ako tieto dve veci sú rovnaké.
V prvom riadku, dereferencia sme ukazovateľ.
Tak ideme do uzla.
To je to, čo táto hviezda znamená.
Videli sme, že predtým, než s ukazovateľmi.
Prejsť na tomto uzle.
To je v zátvorkách.
A potom prístup cez operátora dot n element tohto uzla.
>> Takže to berie syntax sme tu a teraz videl,
použitie s ukazovateľom.
Samozrejme, že to bude dosť práce, ak píšete tie zátvorky -
že hviezdy a bodka.
To je trochu zaneprázdnený.
Takže máme nejaký syntaktický cukor.
A tento riadok tu -
ptr_node-> n
To robí presne rovnaký vec.
Takže tieto dva riadky kódu sú rovnocenné, a bude robiť
presne to isté.
>> Ale chcel by som upozorniť tých, pred pôjdeme ďalej, takže chápete
že naozaj to, čo tu je len syntaktický cukor pre dereferencing
ukazovateľ a potom ísť na n časť tohto struct.
Máte otázky k tomuto snímku?
OK.
>> Takže ideme prejsť pár operácií, ktoré môžete urobiť na
spojové zoznamy.
Spájať zoznam, odvolanie, je rad uzly, ktoré ukazujú na seba.
A my sme zvyčajne začínajú s ukazovateľom volal hlava, všeobecne, že poukazuje na
Prvá vec, ktorú v zozname.
Takže na prvom riadku tady sme najprv náš pôvodný L.
Takže to, čo si môžete myslieť - to text, tu si môžete myslieť, ako
len ukazovateľ máme uložené niekde, že body
na prvý prvok.
A v tomto prepojenom zoznamu máme štyri uzly.
Každý uzol je veľký box.
Väčší box vnútri veľkej box je celá časť.
A potom máme ukazovateľ časť.
>> Tieto boxy nie sú vypracované na mierka, pretože, ako veľký je
celé číslo v bytoch?
Ako teraz veľký?
Štyri.
A aká veľká je ukazovateľ?
Štyri.
Takže naozaj, keď sme sa k tomu toto meradlo obe políčka
by mať rovnakú veľkosť.
V tomto prípade, chceme vložiť niečo do prepojeného zoznamu.
Takže môžete vidieť tu dole sme vkladanie päť sme prejsť cez
spájať zoznam, zistiť, kde päť ide, a potom ju zasuňte.
>> Poďme sa zlomiť to dole a ísť trochu pomalšie.
Budem poukázať na doske.
Takže máme päť uzol, ktorý sme vytvorili v mallocs.
Prečo sa všetci smiať?
Len si robím srandu.
OK.
Takže sme malloced päť.
Vytvorili sme tento uzol niekde inde.
Musíme je pripravená ísť.
Začneme na prednej strane náš zoznam s dvoma.
A chceme vložiť na triedený móde.
>> Takže ak vidíme dva a chceme, aby v päť, čo budeme robiť, keď vidíme,
niečo menej ako my?
Čo je?
Chceme vložiť päť do tejto spájať zoznam, zachovaním radené.
Vidíme číslo dva.
Tak čo budeme robiť?
Marcus?
>> DIVÁKOV: Zavolajte ukazovateľ k ďalšiemu uzlu.
>> JASON Hirschhorn: A prečo ideme na ten budúci?
>> DIVÁKOV: Vzhľadom k tomu, že je to ďalší uzol v zozname.
A my len vieme, že iné umiestnenie.
>> JASON Hirschhorn: A päť je väčšia ako dva, a to najmä.
Pretože chceme, aby to zoradené.
Takže päť je väčšia ako dva.
Tak sme sa presunúť na ďalšie.
A teraz sa dostaneme štyri.
A čo sa stane, keď sa dostaneme štyri?
>> Five je väčší ako štyri.
Tak sme ďalej.
A teraz sme v šesť.
A čo vidíme v šesť?
Áno, Carlos?
>> DIVÁKOV: Šesť je väčšia ako päť.
>> JASON Hirschhorn: Šesť je väčší ako päť.
Tak to je miesto, kde chceme vložiť päť.
Avšak, majte na pamäti, že ak by sme majú iba jeden ukazovateľ tu -
To je náš ďalší ukazovateľ, ktorý je prechádzajúcej cez zoznamu.
A my sme ukázal na šesť.
Stratili sme stopu z čoho prichádza pred šiestou.
Takže ak chceme vložiť niečo do tento zoznam udržiavať ju radené sme
pravdepodobne potrebovať koľko rád?
>> DIVÁKOV: Two.
>> JASON HIRSCHORN: Two.
Jeden sledovať aktuálne jeden a sledovať
ten predchádzajúci.
Toto je iba jednotlivo spájať zoznam.
Je to len ide jedným smerom.
Keby sme mali dvojnásobne spájať zoznam, kde všetko ukazoval na vec
po ňom a vec pred ním, potom nebudeme musieť robiť, že.
Ale v tomto prípade nechceme stratiť track z toho, čo prišli pred nami v prípade,
musíme vložiť päť niekde v stredu.
Povedzme, že sme boli vkladanie deväť.
Čo sa stane, keď sme sa dostali na osem?
>> DIVÁKOV: Museli by ste dostať, že nulový bod.
Namiesto toho, aby nulový bod budeš mať pridať prvok a potom
že poukazujú na deväť.
>> JASON HIRSCHORN: Presne tak.
Tak dostaneme osem.
Dostávame sa na koniec zoznamu, pretože to ukazuje na hodnotu null.
A teraz, namiesto toho, aby to poukázať na null to máme poukázať na našom novom uzle.
A nastavíme ukazovateľ náš nový uzol na hodnotu null.
Má niekto nejaké otázky, o vkladanie?
Čo keď nemám starať o vedenie zoznamu radené?
>> DIVÁKOV: Stick to na začiatok alebo koniec.
>> JASON HIRSCHORN: Stick to na začiatok alebo koniec.
Ktorý z nich by sme mali robiť?
Bobby?
Prečo koniec?
>> DIVÁKOV: Vzhľadom k tomu, začiatok je už naplnená.
>> JASON HIRSCHORN: OK.
Začiatok je už naplnená.
Kto chce argumentovať proti Bobbymu.
Marcus.
>> DIVÁKOV: No pravdepodobne budete chcieť držať ju na začiatku, pretože
inak, ak si to dať na Koniec ste museli
prechádzať celý zoznam.
>> JASON HIRSCHORN: Presne tak.
Takže ak budeme premýšľať o behu, runtime vloženie na konci
by n, veľkosť.
Čo je to veľký O runtime vloženie na začiatku?
Konštantný čas.
Takže ak nechcete starať o udržanie niečo ďalej, oveľa lepšie, len
vložiť na začiatku tohto zoznamu.
A to možno vykonať v konštantnom čase.
>> OK.
Ďalšie operácie je nájsť, ktoré ďalšie - sme formulovali to ako hľadanie.
Ale my ideme prezrieť spájať zoznam z nejakého objektu.
Vy ste videli kód hľadať ešte v prednáške.
Ale my sme tak nejako práve urobil to s vložiť, alebo aspoň vkladanie
niečo ďalej.
Môžete prezrieť, bude uzol uzla, kým nenájdete číslo, že ste
hľadať.
Čo sa stane, keď sa dostanete koniec zoznamu?
Povedz Hľadám deväť a ja dostať sa na koniec zoznamu.
Čo budeme robiť?
>> DIVÁKOV: return false?
>> JASON HIRSCHORN: Návrat false.
Nenašli sme ju.
Ak sa dostanete na koniec zoznamu a ste nenašli číslo, ktoré ste
hľadá, nie je to tam.
Akékoľvek otázky týkajúce sa nájsť?
Ak to bolo zoradený zoznam, čo by byť pre naše vyhľadávanie?
Jo.
>> DIVÁKOV: To nájde prvú hodnotu to je väčšia ako jedna
hľadáte a potom sa vrátiť false.
>> JASON HIRSCHORN: Presne tak.
Takže ak je to zoradený zoznam, ak sa dostaneme do niečo, čo je väčšie ako to, čo
sme hľadali, nepotrebujeme, aby pokračuj na koniec zoznamu.
Môžeme v tomto bode vráti false pretože nebudeme ho nájsť.
Otázkou je teraz, sme hovorili o vedenie prepojené zoznamy radené,
ich udržiavanie netriedený.
To bude niečo, čo ste pravdepodobne bude musieť premýšľať o tom,
pri kódovaní problém nastaviť päť, ak vybrať hash tabuľku s samostatný
reťazenie prístup, ktorý budeme hovoriť o neskôr.
>> Ale je to stojí za to, aby sa zoznam triedeného a potom budú môcť možno mať
rýchlejšie vyhľadávanie?
Alebo je lepšie rýchlo vloženie niečo v neustálom behu, ale potom
majú už hľadáte?
To je jedna z vecí, tu, že vám dostať sa rozhodnúť, čo je vhodnejšie,
pre váš konkrétny problém.
A tam to nemusí byť nutne jedným úplne správna odpoveď.
Ale je to určite rozhodnutie, ktoré sa aby sa, a asi dobre brániť
že, povedzme, komentár alebo dva, prečo ste si vybrali jeden cez druhého.
>> A konečne, mazanie.
Videli sme mazanie.
Je to podobné, ako hľadať.
Hľadáme prvku.
Povedzme, že sa snažíme odstrániť šesť.
Tak nájdeme šesť tady.
Ide o to, že sa musíme uistiť, že sme urobiť, je, že čokoľvek sa ukazuje na
šesť - ako vidíme v kroku dva tu dole -
bez ohľadu na to ukázal na šesť potreby na preskočiť šesť teraz a byť zmenený na
čo šesť je ukazuje.
Nechceme, aby vôbec ojedinelé ochorenia zvyšok náš zoznam by zabudol nastaviť, aby
predchádzajúci ukazovateľ.
A potom niekedy, v závislosti na programe, ale budem len
odstrániť úplne tento uzol.
Niekedy sa budete chcieť vrátiť hodnota, ktorá je v tomto uzle.
Tak to je, ako funguje mazanie.
Akékoľvek otázky týkajúce sa zmazať?
>> DIVÁKOV: Takže ak sa chystáte odstrániť to by ste stačí použiť zadarmo, pretože
pravdepodobne to bolo malloced?
>> JASON HIRSCHORN: Ak chcete uvoľniť niečo, čo je úplne v poriadku a vy
malloced to.
Povedzme, že sme sa chceli vrátiť túto hodnotu.
Mohli by sme sa vrátiť šesť a potom zadarmo tento uzol a volania zadarmo na neho.
Alebo by sme snáď volať zadarmo prvý a potom sa vrátiť šesť.
>> OK.
Takže poďme sa presunúť na prax kódovanie.
Budeme kódovať tri funkcie.
Prvý z nich sa nazýva insert_node.
Takže máte kód, ktorý som zaslané e-mailom vás, a ak sledujete neskôr na to
môžete pristupovať ku kódu v linked.c na internetových stránkach CS50.
Ale v linked.c, tam je nejaký kostra kód, ktorý je už
bola napísaná pre vás.
A potom je tu pár FUNKCIE musíte napísať.
>> Najprv ideme do napísať insert_node.
A čo robí insert_node znamená vloží číslo.
A dávate celé číslo do prepojeného zoznamu.
A najmä, budete potrebovať udržať zoznamu zoradené
od najmenšieho po najväčšie.
Tiež nechcete, aby vložte všetky duplikáty.
V neposlednom rade, ako môžete vidieť insert_node vracia bool.
Takže ste mal dať užívateľovi vedieť či je alebo nie je insert
úspešný vrátením true alebo false.
Na konci tohto programu -
a pre túto fázu nemusíte sa starať o uvoľnenie čokoľvek.
Takže všetko, čo robíte, je prijatie celé číslo a vloženie do zoznamu.
>> To je to, čo sa pýtam vás robiť teraz.
Opäť platí, že v linked.c, ktoré všetci majú, je kostra kódu.
A mali by ste vidieť na spodnej časti Deklarácia funkcie vzorky.
Avšak predtým, než ísť do jeho kódovania v C, vrelo odporúčame vám ísť
jednotlivými krokmi sme boli cvičiť každý týždeň.
Už sme prešli obraz toho.
Takže by ste mali mať nejaké znalosti o tom, ako to funguje.
Ale ja by som povzbudiť vás písať niektoré pseudokódu pred potápaním palcov
A ideme prejsť pseudokódu ako skupina.
A potom, akonáhle ste napísali svoj pseudokódu, a akonáhle ste napísali naši
pseudokódu ako skupiny, môžete ísť na to kódovanie v C.
>> Ako heads up, funkcia insert_node je pravdepodobne najkomplikovanejšie zo
tri budeme písať, pretože som pridal niektoré ďalšie obmedzenia na
vaše programovania, najmä to, že nebudete vložiť akýkoľvek
duplikáty a že zoznam by mala zostať triedené.
Tak to je non-triviálne program, že budete musieť kód.
A prečo si nevezmeš päť-sedem minút len ​​preto, aby sa práce na
pseudokódu a kód.
A potom začneme ísť ako skupina.
Opäť platí, že ak máte nejaké otázky stačí zdvihnúť ruku a pôjdem okolo.
.
>> Tiež sme všeobecne robiť to -
alebo nemám explicitne povedať vám môže pracovať s ľuďmi.
Ale samozrejme, vrelo vám odporúčame, Ak máte otázky, požadovať
sused sedí vedľa teba alebo dokonca pracovať s niekým,
inak, ak chcete.
To nemusí byť individuálna tichá činnosť.
>> Poďme začať s písaním niektorých pseudokódu na palube.
Kto mi môže dať prvý riadok pseudokódu pre tento program?
Pre túto funkciu, skôr - insert_node.
Alden?
>> DIVÁKOV: Takže prvá vec, ktorú som urobil, bolo, vytvoriť nový ukazovateľ na uzol a ja
inicializovaný to ukazuje na rovnaký vec, že ​​zoznam je ukazuje.
>> JASON HIRSCHORN: OK.
Takže budete vytvárať nový ukazovateľ na zozname, a to k uzlu.
>> DIVÁKOV: Správne.
Jo.
>> JASON HIRSCHORN: OK.
A potom to, čo chceme robiť?
Čo je po tom?
Čo uzla?
Nemáme uzol.
Máme len hodnotu.
Ak chceme vložiť uzol, čo máme je potrebné urobiť skôr, než sa budeme môcť ešte
premýšľať o tom, vloženie?
>> DIVÁKOV: Oh, ospravedlňujem sa.
musíme malloc priestor pre uzol.
>> JASON HIRSCHORN: Výborný.
Poďme urobiť -
OK.
Nemožno dosiahnuť tak vysoko.
OK.
Chystáme sa ísť dole, a potom sme pomocou dvoch stĺpcov.
Nemôžem ísť, že -
OK.
Vytvoriť nový uzol.
Môžete vytvoriť ďalší ukazovateľ na zoznam alebo stačí použiť zoznam, ako to existuje.
Nemáte naozaj potrebujete urobiť, že.
>> Tak sme sa vytvoriť nový uzol.
Skvelé.
To je to, čo robíme ako prvý.
Čo bude ďalej?
>> DIVÁKOV: Počkajte.
Mali by sme vytvoriť nový uzol sa podnikom alebo Mali by sme počkať, aby sa uistil, že
tam žiadne duplikáty uzla na zozname, ako ju vytvoriť?
>> JASON HIRSCHORN: Dobrá otázka.
Poďme si myslí, že na neskôr, pretože väčšinu času budeme vytvárať
nový uzol.
Takže budeme držať tu.
Ale to je dobrá otázka.
Ak by sme ju vytvoriť a nájdeme duplicitné, čo by
budeme robiť, než sa vráti?
>> DIVÁKOV: Uvoľnite sa.
>> JASON HIRSCHORN: Jo.
Pravdepodobne ho uvoľniť.
OK.
Čo budeme robiť, keď sme vytvoriť nový uzol?
Annie?
>> DIVÁKOV: Dali sme Číslo v uzle?
>> JASON HIRSCHORN: Presne tak.
Kladieme číslo - budeme malloc priestor.
Chystám sa nechať, že všetko ako jeden riadok.
Ale máš pravdu.
Malloc sme priestor, a potom dáme číslo palcov
Dokonca môžeme nastaviť ukazovateľ časť na hodnotu null.
To je presne to pravé.
A potom čo po tom?
Nakreslil sme tento obrázok na tabuli.
Tak čo budeme robiť?
>> DIVÁKOV: Prejdeme zoznamu.
>> JASON HIRSCHORN: Prejdite si zoznam.
OK.
A čo si budeme kontrolovať na každom uzle.
Kurt, čo môžeme skontrolovať pre každý uzol v?
>> DIVÁKOV: Pozrite sa, či n hodnota že uzol je väčšia, než je hodnota n
nášho uzla.
>> JASON HIRSCHORN: OK.
Budem robiť -
jo, OK.
Tak to je n -
Chystám sa povedať, či hodnota je väčšia ako v tomto uzle, potom to, čo budeme robiť?
>> DIVÁKOV: No, potom vložíme přmo pred tým.
>> JASON HIRSCHORN: OK.
Takže ak je to väčšie ako to, potom chceme vložiť.
Ale chceme, tesne predtým, než ju vložiť pretože tiež bude musieť byť
sledovanie, a potom, z toho, čo bolo predtým.
Takže vložte pred.
Takže sme asi niečo uniklo skôr.
Asi sme potrebné udržať track z toho, čo sa deje.
Ale dostaneme sa tam.
Takže to, čo je hodnota nižšia ako?
Kurt, čo budeme robiť, keď hodnota je nižšia ako?
>> DIVÁKOV: Potom stačí ísť ďalej ak je to posledné.
>> JASON HIRSCHORN: Páči sa mi to.
Tak choďte na ďalší uzol.
Ak to posledné -
sme asi kontrola, ktorá v podmienkach stave.
Ale jo, ďalší uzol.
A to je stále príliš nízka, takže budeme pohybovať sem.
Ale ak -
môže každý vidieť?
Ak sme rovnaká, čo budeme robiť?
Ak hodnota sa snažíme vložiť sa rovná hodnote tohto uzla?
Jo?
>> DIVÁKOV: [nepočuteľné].
>> JASON HIRSCHORN: Jo.
Vzhľadom k tejto -
Marcus je v poriadku.
Mohli sme možno urobili niečo iné.
Ale vzhľadom k tomu, že sme vytvorili to, tu by sme sa mali uvoľniť a potom sa vrátiť.
Ach jo.
Je to lepšie?
Ako to?
OK.
Zadarmo a potom to, čo máme vrátiť, [nepočuteľný]?
OK.
Sme niečo chýba?
Takže tam, kde sme sledovanie z predchádzajúceho uzla?
>> DIVÁKOV: Myslím, že to pôjde Po vytvorení nového uzla.
>> JASON HIRSCHORN: OK.
Takže na začiatku sme sa asi -
jo, môžeme vytvoriť ukazovateľ na nový uzol, ako predchádzajúci ukazovateľ uzla a
aktuálny uzol ukazovateľ.
Takže poďme vložte tu.
Vytvorte aktuálne a predchádzajúce ukazovatele na uzly.
Ale keď budeme nastaviť tie odkazy?
Tam, kde to urobíme v kóde?
Jeff?
>> DIVÁKOV: - Podmienky hodnota?
>> JASON HIRSCHORN: Ktoré jeden najmä?
>> DIVÁKOV: Ja som len zmätená.
Je-li hodnota je vyššia, než v tomto uzle, Neznamená to, že chcete ísť
na ďalší uzol?
>> JASON Hirschhorn: Takže ak naša hodnota je väčšia, než je hodnota tohto uzla.
>> DIVÁKOV: Jo, potom by ste chceli, aby ísť ďalej v rade, nie?
>> JASON Hirschhorn: Správne.
Takže nemáme vložte ho sem.
Ak je hodnota nižšia ako v tomto uzle, potom ideme na ďalší uzol - a potom sme
vložte pred.
>> DIVÁKOV: Počkajte, čo je v tomto uzol a ktorá je hodnota?
>> JASON Hirschhorn: Dobrá otázka.
Hodnota za tejto definície funkcie je to, čo sme vzhľadom.
Takže hodnota je číslo sme vzhľadom.
Takže v prípade, že hodnota je nižšia ako tento uzol, potrebujeme čas na vloženie.
Je-li hodnota je vyššia, než v tomto uzle, ideme na ďalší uzol.
A späť k pôvodnej otázke, aj keď, kde -
>> DIVÁKOV: Ak je hodnota väčšia ako tento uzol.
>> JASON Hirschhorn: A tak Čo tu robíme?
Sladké.
To je správne.
Idem písať aktualizovať ukazovatele.
Ale áno, sa existujúce by ste ho aktualizovať
poukazujú na ten budúci.
Ešte niečo nám chýba?
Takže budem písať tento kód do gedit.
A keď som to urobiť, môžete mať pár ďalších minút k práci na kódovanie
to v C.
>> Takže mám Zadajte pseudokódu.
Krátka poznámka, než začneme.
My nemusí byť schopný úplne dokončiť to vo všetkých
tri z týchto funkcií.
Tam je správne riešenie k nim že som sa e-mailom na vás chlapci
po bode, a to bude byť zanechané CS50.net.
Tak som sa ťa povzbudiť, aby ísť pozrieť na sekciách.
Odporúčam vám vyskúšať to na vašom vlastné, a potom použiť v praxi
problémy, aby sme zistili, či vaše odpovede.
Tie boli všetky navrhnuté tak, aby úzko týkajú, a dodržiavať to, čo
čo musíte urobiť, na problém sade.
Tak som sa povzbudiť vás k praxi to na vlastnú päsť, a potom použite kód
skontrolujte svoje odpovede.
Pretože chcem prejsť na hash Stoly na nejakom mieste v sekcii.
Takže by sme mohli dostať cez to všetko.
Ale budeme robiť teraz, ako moc môžeme.
>> OK.
Poďme začať.
Asam, ako sme sa vytvoriť nový uzol?
>> DIVÁKOV: Ty struct *.
>> JASON Hirschhorn: Tak sme si, že sa tu.
Oh, ospravedlňujem sa.
Hovoril ste struct *.
>> DIVÁKOV: A potom [? druh?] uzol alebo c uzol.
>> JASON Hirschhorn: OK.
Budem hovoriť new_node takže môžeme zostať konzistentné.
>> DIVÁKOV: A chcete nastaviť, ktoré na hlavu, prvý uzol.
>> JASON Hirschhorn: OK.
Takže teraz to ukazujúce na - tak to nebol vytvorený nový uzol doteraz.
To je len ukazuje na prvý uzol v zozname.
Ako môžem vytvoriť nový uzol?
Ak je potreba priestor pre vytvorenie nového uzla.
Malloc.
A ako veľký?
>> Divákov: veľkosť struct.
>> JASON Hirschhorn: veľkosť struct.
A čo struct volá?
>> DIVÁKOV: Uzol?
>> JASON Hirschhorn: Node.
Takže malloc (sizeof (node)); nám dáva priestor.
A je to linka -
jedna vec je nesprávne na tomto riadku.
Je new_node ukazovateľ na struct?
To je všeobecný názov.
Čo je to -
uzol, presne tak.
Je to uzol *.
A čo budeme robiť hneď po sme malloc niečo, Asan?
Čo je prvá vec, ktorú budeme robiť?
Čo keď to nefunguje?
>> DIVÁKOV: Oh, skontrolujte, či je poukazuje na uzle?
>> JASON Hirschhorn: Presne tak.
Takže ak ste new_node rovná rovná null, čo budeme robiť?
Tento vracia bool, túto funkciu.
Presne tak.
Vyzerá to dobre.
Niečo sa tam pridať?
Budeme pridávať veci na konci.
Ale to zatiaľ vyzerá dobre.
Vytvorte aktuálne a predchádzajúce ukazovatele.
Michael, ako to mám urobiť?
>> DIVÁKOV: Budete musieť urobiť uzol *.
Musel by si urobiť jednu nie pre new_node ale
uzly už máme.
>> JASON Hirschhorn: OK.
Takže aktuálny uzol sme ďalej.
Zavolám, že curry.
Dobrá.
Rozhodli sme sa chceme udržať dva, pretože potrebujeme vedieť,
to, čo je pred ním.
Čo oni si inicializovaný?
>> DIVÁKOV: Ich hodnota v našom zozname.
>> JASON Hirschhorn: Takže to, čo je Prvá vec, ktorú na našom zozname?
Alebo ako vieme, kde začiatok nášho zoznamu je?
>> DIVÁKOV: Nie je to prešlo do funkcie?
>> JASON Hirschhorn: Správne.
To bol schválený v roku tady.
Takže ak je to prešiel do funkcie, začiatok zoznamu, čo by sme mali
nastaviť prúd rovný?
>> DIVÁKOV: List.
>> JASON Hirschhorn: List.
To je presne to pravé.
Teraz má adresu začiatok nášho zoznamu.
A čo predchádzajúce?
>> DIVÁKOV: Zoznam mínus jedna?
>> JASON Hirschhorn: tu nič pred ním.
Čo teda môžeme urobiť pre to, znamenať nič?
>> DIVÁKOV: Null.
>> JASON Hirschhorn: Jo.
To znie ako dobrý nápad.
Perfect.
Ďakujem.
Prejdite si zoznam.
Constantine, ako dlho sa budeme prejsť zoznamu?
>> DIVÁKOV: až sa dostaneme null.
>> JASON Hirschhorn: OK.
Takže v prípade, zatiaľ čo pre slučku.
Čo budeme robiť?
>> DIVÁKOV: Možno, že pre sláčiky?
>> JASON Hirschhorn: Poďme urobiť pre sláčiky.
OK.
>> DIVÁKOV: A my hovoríme na -
až do súčasnej ukazovateľ nie je rovné null.
>> JASON Hirschhorn: Takže ak vieme, stav, ako môžeme napísať slučku
vychádza z tohto stavu.
Aký druh slučky by sme mali používať?
>> DIVÁKOV: Kým.
>> JASON Hirschhorn: Jo.
To dáva väčší zmysel na základe off z toho, čo ste povedal.
Ak chceme len ísť do sme, že Len viem, že vec, bolo by
zmysel robiť while.
Kým súčasná nie je rovné null, ak hodnota je nižšia ako tento uzol.
Akshar, daj mi tento riadok.
>> DIVÁKOV: Ak je aktuálna-> n n menšia ako hodnota.
Alebo zvrátiť to.
Spínač, ktorý držiak.
>> JASON Hirschhorn: Ospravedlňujem sa.
>> DIVÁKOV: Zmeňte držiak.
>> JASON Hirschhorn: Takže ak je to vyššia ako hodnota.
Vzhľadom k tomu, že je to mätúce komentár vyššie, budem robiť, že.
Ale áno.
Ak je naša hodnota je nižšia ako tento uzol, čo budeme robiť?
Oh.
Mám ho tu.
Vložte predtým.
OK.
Ako to urobíme?
>> DIVÁKOV: Je to ešte ja?
>> JASON Hirschhorn: Jo.
>> DIVÁKOV: Vy -
new_node-> ďalšie.
>> JASON Hirschhorn: Takže to, čo je že bude rovnať?
>> DIVÁKOV: Bude to rovnaké prúdu.
>> JASON Hirschhorn: Presne tak.
A tak ďalšie -
čo ešte musíme aktualizovať?
>> DIVÁKOV: Skontrolujte, či minulosť rovná null.
>> JASON Hirschhorn: Ak prev -
takže ak predchádzajúci rovná null.
>> DIVÁKOV: To znamená, že sa deje aby sa stal hlavou.
>> JASON Hirschhorn: To znamená je to stáť hlavy.
Tak čo budeme robiť?
>> DIVÁKOV: Robíme hlava rovná new_node.
>> JASON Hirschhorn: Head rovná new_node.
A prečo hlava tu, nie zoznam?
>> DIVÁKOV: Vzhľadom k tomu, hlava je globálna variabilný, čo je východiskové miesto.
>> JASON Hirschhorn: Sladký.
OK.
A -
>> DIVÁKOV: Potom si ešte prev-> Ďalšie rovná new_node.
A potom sa vrátiť true.
>> JASON Hirschhorn: Kam sme sa vydali new_node koniec?
>> DIVÁKOV: Ja by som -
Nastaviť, že na začiatku.
>> JASON Hirschhorn: Tak čo linka?
>> DIVÁKOV: Po if kontrolovať, či je známe.
>> JASON Hirschhorn: Tu?
>> DIVÁKOV: ja by som to new_node-> n sa rovná hodnote.
>> JASON Hirschhorn: To znie dobre.
Pravdepodobne to dáva zmysel - my nie Potrebujeme vedieť, čo zoznam sme na
preto, že sme len do činenia s jedného zoznamu.
Takže lepšie funkcie vyhlásenie o je to len, ako sa zbaviť tohto
úplne a len vložiť hodnota do hlavy.
My ani nemusíte vedieť čo zoznam sme dovnútra
Ale nechám to teraz a potom ho zmeniť na aktualizáciu
sklíčka a kód.
Takže to vyzerá dobre teraz.
Je-li hodnota - kto môže robiť tento riadok?
Ak -
Čo budeme robiť tu, Noah.
>> DIVÁKOV: Ak je hodnota väčšia ako akt-> n -
>> JASON Hirschhorn: Ako ideme na ďalší uzol?
>> DIVÁKOV: Mena-> n je rovná new_node.
>> JASON Hirschhorn: Tak n je aká časť struct?
Celé číslo.
A new_node je ukazovateľ na uzol.
Takže to, čo časť Curr by sme mali aktualizovať?
Ak n nie, potom to, čo je tá druhá časť?
Noah, čo je tá druhá časť.
>> DIVÁKOV: Oh, ďalšie.
>> JASON Hirschhorn: Ďalšie, presne tak.
Presne tak.
Ďalšia je správna.
A čo ešte potrebujeme aktualizovať, Noe?
>> DIVÁKOV: Ukazovatele.
>> JASON Hirschhorn: Tak Aktualizovali sme prúd.
>> DIVÁKOV: Prev-> ďalšie.
>> JASON Hirschhorn: Jo.
OK, budeme pozastaviť.
Kto nám môže pomôcť tu?
Manu, čo by sme mali robiť?
>> DIVÁKOV: Musíš nastaviť je rovná akt-> ďalšie.
Ale to, že skôr, než v predchádzajúcom riadku.
>> JASON Hirschhorn: OK.
Ešte niečo?
Akshar.
>> DIVÁKOV: Nemyslím si, že si chcel zmeniť akt-> ďalšie.
Myslím, že si chcel robiť Mena rovná akt-> ďalšie prejsť na ďalší uzol.
>> JASON Hirschhorn: Je mi ľúto, kam?
Na čo linka?
Táto linka?
>> DIVÁKOV: Jo.
Uistite sa curry rovná akt-> ďalšie.
>> JASON Hirschhorn: Tak to je pravda pretože prúd je
ukazovateľ na uzol.
A my chceme, aby to poukázať na ďalšie uzol, čo sa dostáva v súčasnej dobe
ukázal.
Curry sama o sebe má ďalšie.
Ale ak by sme mali aktualizovať curr.next sme by sa aktualizácia aktuálnej poznámku
sama o sebe, nie tam, kde to ukazovateľ ukazoval.
Čo o tejto línii, hoci.
Avi?
>> DIVÁKOV: Prev-> Ďalšie rovná curry.
>> JASON Hirschhorn: Takže znova, ak predchádzajúci je ukazovateľ na uzol, náhľad-> ďalšie je
aktuálny ukazovateľ v uzle.
Takže by to byť aktualizácia ukazovateľ na uzol Curr.
Nechceme aktualizovať ukazovateľ v uzle.
Chceme aktualizovať predchádzajúce.
Tak ako to urobíme?
>> DIVÁKOV: Bolo by to byť prev.
>> JASON Hirschhorn: Správne.
Predchádzajúce je ukazovateľ na uzol.
Teraz meníme ju nový ukazovateľ na uzol.
OK Poďme dole.
A konečne, tento posledný podmienka.
Jeff, čo budeme robiť tu?
>> DIVÁKOV: Ak je hodnota rovnajúcu sa akt-> n
>> JASON Hirschhorn: Ospravedlňujem sa.
Ach môj bože.
Čo je?
Hodnota == akt-> n
Čo budeme robiť?
>> DIVÁKOV: Ty by si oslobodiť našu new_node, a potom by ste sa vrátiť false.
>> JASON Hirschhorn: To je to, čo sme písali tak ďaleko.
Má niekto niečo pridať skôr, než urobíme?
OK.
Poďme to skúsiť.
Kontrola môže dostať na koniec z non-void funkcie.
Avi, čo sa deje?
>> DIVÁKOV: Ste mal dať návrate platí mimo while?
>> JASON Hirschhorn: Ja neviem.
Máte ma chcete?
>> DIVÁKOV: Nevadí.
Nie.
>> JASON Hirschhorn: Akshar?
>> DIVÁKOV: Myslím, že ste mal na mysli, aby dať return false na konci
z cyklu while.
>> JASON Hirschhorn: Tak kde chceš, aby to šlo?
>> DIVÁKOV: Rovnako ako u cyklu while.
Takže ak opustíte while to znamená, že že ste prišli na koniec a
nič sa nestalo.
>> JASON Hirschhorn: OK.
Tak čo budeme robiť tu?
>> DIVÁKOV: Vrátite false aj tam.
>> JASON Hirschhorn: Oh, my to na oboch miestach?
>> DIVÁKOV: Jo.
>> JASON Hirschhorn: OK.
Mali by sme ísť?
Ach môj bože.
Je mi to ľúto.
Ospravedlňujem sa za obrazovku.
Je to trochu desí nás.
Tak si vyberte jednu z možností.
Zero, podľa kódu, ukončí program.
Jeden vloží niečo.
Poďme vložte tri.
Vložka nebol úspešný.
Idem vytlačiť.
Nemám nič.
OK.
Možno, že to bola len náhoda.
Vložte jeden.
Nie je úspešná.
OK.
Poďme si prejsť GDB veľmi rýchlo zistiť, čo sa deje.
>> Nezabudnite gdb. / Názov vášho Program nás dostane do GDB.
Je to veľa zvládnuť?
Bliká?
Pravdepodobne.
Zavrite oči a vziať nejaké hlboké dýcha, ak vás omrzí
z pohľadu na neho.
Som v GDB.
Čo je prvá vec, ktorú robím v GDB?
Musíme prísť na to, to, čo sa tu deje.
Poďme sa pozrieť.
Máme šesť minút na obrázku čo sa deje.
Prestávka hlavné.
A potom to, čo mám robiť?
Carlos?
Spustiť.
OK.
Poďme možnosť.
A čo N robiť?
Ďalšie.
Jo.
>> DIVÁKOV: Vari ste spomenul -
ste to nepovedal, že hlava, to bolo inicializovaná na hodnotu NULL na začiatku.
Ale myslel som, že si povedal, že je v poriadku.
>> JASON Hirschhorn: Poďme - poďme sa pozrieť v GDB, a potom pôjdeme späť.
Ale vyzerá to, že už máte niektoré myšlienky o tom, čo sa deje.
Takže chceme vložiť niečo.
OK.
Máme vložiť.
Prosím, zadajte int.
Budeme vložte tri.
A potom som na tejto trati.
Ako mám ísť spustiť ladenie vložka známe funkcie?
Ach môj bože.
To je veľa.
Je to vyšilovat veľa?
>> DIVÁKOV: Oh, to zomrel.
>> JASON Hirschhorn: som vytiahol ho von.
OK.
>> DIVÁKOV: Možno, že je to druhý koniec drôtu.
>> JASON Hirschhorn: Wow.
Takže spodnom riadku -
Čo si hovoril?
>> DIVÁKOV: Povedal som, že irónia technické ťažkosti v tejto triede.
>> JASON Hirschhorn: Ja viem.
Kiež by som mal kontrolu nad tou časťou.
[Nepočuteľný]
To znie skvele.
Prečo nie vy začať premýšľať o tom, to, čo sme mohli urobiť zle,
a budeme späť za 90 sekúnd.
>> AVIC, budem sa vás opýtať, ako to chodí vnútri insert_node ladiť.
Tak toto je miesto, kde sme naposledy skončili.
Ako môžem ísť dovnútra insert_node, AVIC, skúmať, čo sa deje?
Čo GDB príkazu?
Prestávka by ma vziať dovnútra.
Má Marquise vedieť?
>> DIVÁKOV: Čo?
>> JASON Hirschhorn: Aký príkaz GDB Používam ísť dovnútra tejto funkcie?
>> DIVÁKOV: krok?
>> JASON Hirschhorn: Krok cez S. To ma berie dovnútra.
OK.
New_node mallocing nejaký priestor.
To všetko vyzerá ako jeho bude.
Poďme preskúmať new_node.
To má nejakú adresu v pamäti.
Poďme sa pozrieť -
že je všetko v poriadku.
Takže všetko tu zdá sa, pracovať správne.
>> DIVÁKOV: Aký je rozdiel medzi P a displej?
>> JASON Hirschhorn: P je skratka pre tlač.
A tak sa pýtate, čo je Rozdiel medzi týmto a to?
V tomto prípade nič.
Ale všeobecne sú niektoré rozdiely.
A mali by ste sa pozrieť do manuálu GDB.
Ale v tomto prípade nič.
Máme tendenciu používať tlač, hoci, pretože nepotrebujeme robiť oveľa viac, než
vytlačiť jednu hodnotu.
>> OK.
Takže sme na riadku 80 nášho kódu, nastavenie uzla * curry rovnajúcu sa zoznamu.
Poďme vytlačiť curry.
To sa rovná zoznamu.
Sladké.
Počkajte.
To sa rovná niečo.
To sa nezdá byť v poriadku.
Tam ideme.
Je to preto, že v GDB, vpravo, ak je to čiara, že ste na to
nebol vykonaný ešte.
Takže je potrebné, aby skutočne písať Vedľa prevedenie linky
ako vidieť svoje výsledky.
Tak sme tu.
Len sme vykonali tento riadok, predchádzajúce rovná null.
Takže znova, ak tlačíme predchádzajúce nebudeme vidieť nič divného.
Ale ak sme skutočne spustiť, že linka, potom uvidíme
že linka funguje.
>> Takže máme curry.
Tí, ktorí sú obaja dobré.
Je to tak?
Teraz sme na tejto trati tu.
Kým Mena nie je rovné null.
No, čo robí bc rovnaké?
Práve sme videli, že sa rovnal null.
Vytlačiť sme to.
Budem ju vytlačiť znova.
Tak je to, že zatiaľ čo slučka bude vykonávať?
>> Divákov: Nie
>> JASON Hirschhorn: Takže, keď som napísal, že linka, vidíte, sme skočili po celú cestu
až na dno, vráti false.
A potom sa budeme vracať false a vrátiť sa do nášho programu a
nakoniec vytlačiť, ako sme videli, vložka nebola úspešná.
Takže, niekto nejaké nápady na to, čo musíme urobiť, aby tento problém vyriešiť?
Budem čakať, kým neuvidím pár rúk nahor.
Nechceli sme spustiť tento.
Majte na pamäti, to bol prvý čo sme robili.
Nebudem robiť pár.
Budem robiť len málo.
Vzhľadom k tomu pár znamená dva.
Počkám na viac ako dva.
>> Prvý vloženie, bc, v predvolenom nastavení sa rovná null.
A táto slučka vykonáva iba ak bc nie je null.
Tak ako môžem získať okolo tohto?
Vidím tri ruky.
Počkám na viac ako tri.
Marcus, čo si o tom myslíte?
>> DIVÁKOV: No, ak to budete potrebovať, aby vykonať viac ako raz, stačí
zmeniť ho na do-while.
>> JASON Hirschhorn: OK.
Bude to vyriešiť náš problém, nie?
>> DIVÁKOV: V tomto prípade nie je, pretože Skutočnosť, že zoznam je prázdny.
Takže potom ste pravdepodobne stačí pridať vyhlásenie, že v prípade, že slučka ukončí
potom musíte byť na konci roka list, na ktorom mieste sa vám
stačí vložiť ju.
>> JASON Hirschhorn: Páči sa mi to.
To dáva zmysel.
Je-li slučka ukončí -
preto, že sa vrátim false tu.
Takže ak slučky východov, potom sme na koniec zoznamu, alebo možno
začiatok zoznamu, ak tam nič nie je je to, ktoré je rovnaké ako na konci.
Takže teraz chceme vložiť niečo tu.
Tak ako to, že kód vyzerať, Marcus?
>> DIVÁKOV: Ak ste už dostal uzol malloced, mohol by si povedať,
new_node-> ďalšie rovný null, pretože , Že musí byť na konci.
Alebo new_node-> Ďalšie rovná null.
>> JASON Hirschhorn: OK.
Prepáčte.
New_node-> ďalšie rovný null preto, že sme na konci.
To nie je dať dovnútra
Ako môžeme dať je na zozname?
Správne.
To je len nastavením rovná.
No, ako to vlastne vložte ho do zoznamu?
Čo ukazuje na koniec zoznamu?
>> DIVÁKOV: Head.
>> JASON Hirschhorn: Je nám ľúto?
>> DIVÁKOV: Hlava smeruje na koniec zoznamu.
>> JASON Hirschhorn: Ak nie je nič v zoznam, hlava smeruje k
koniec zoznamu.
Takže to bude fungovať pre prvý vloženie.
A čo v prípade, že sú pár veci na zozname?
Ako nechceme nastaviť hlava rovná new_node.
Čo chceme, aby tam robiť?
Jo?
Pravdepodobne predchádzajúce.
Bude to fungovať?
Pripomeňme, že predchádzajúce je len ukazovateľ na uzol.
A predchádzajúce je lokálna premenná.
Takže tento riadok bude nastavený lokálne premenné, predchádzajúcej, ktorá sa rovná alebo
smerovať k tomuto novému uzla.
To nebude v skutočnosti dať v našom zozname, hoci.
Ako sme dali, že v našom zozname?
Akchar?
>> DIVÁKOV: Myslím, že vám to aktuálne-> ďalšie.
>> JASON Hirschhorn: OK.
akt-> ďalšie.
Takže znova, jediný dôvod, prečo sme sa Tu je to, čo robí prúd rovný?
>> DIVÁKOV: Rovná null.
>> JASON Hirschhorn: A tak čo sa stane, keď budeme robiť null-> ďalšie?
Čo dostaneme?
Dostaneme segmentation fault.
>> DIVÁKOV: Do bc rovná null.
>> JASON Hirschhorn: To je to isté ako prev, hoci, pretože tam je
lokálne premenná sme nastavenie rovnajúce sa tejto novej uzla.
Vráťme sa k nášmu obrazu vkladanie niečo.
Povedzme, že sme vkladanie na koniec zoznamu, tak tu.
Máme aktuálne ukazovateľ, ktorý je ukazuje na null a predchádzajúci bod
že je ukazuje na 8..
Takže to, čo potrebujeme aktualizovať, Avi?
>> DIVÁKOV: Predchádzajúca-> ďalej?
>> JASON Hirschhorn: Predchádzajúca-> ďalšie je to, čo chceme aktualizovať, pretože to
bude skutočne vložte ho na koniec zoznamu.
Máme ešte jednu chybu, aj keď, že budeme bežať do.
Čo je to chyba?
Jo?
>> DIVÁKOV: Bude to návrat false v tomto prípade?
>> JASON Hirschhorn: Oh, je sa chystá sa vrátiť false.
Ale je tu ďalší problém.
Takže budeme musieť dať na oplátku skutočné.
>> DIVÁKOV: Moja predchádzajúca stále rovnaká null v hornej časti zoznamu?
>> JASON Hirschhorn: Tak ešte predchádzajúca rovná null na samom začiatku.
Takže, ako môžeme dostať cez to?
Jo?
>> DIVÁKOV: Myslím, že môžete urobiť kontrolu pred while, aby zistil, či je to
prázdny zoznam.
>> JASON Hirschhorn: OK.
Takže poďme tu.
Vykonajte kontrolu.
Ak -
>> DIVÁKOV: Takže ak hlava rovná sa rovná null.
>> JASON Hirschhorn: Keď je hlava rovná sa rovná null -
že nám povie, či je to prázdny zoznam.
>> DIVÁKOV: A potom ste to hlava rovná nové.
>> JASON Hirschhorn: Head rovná new_node?
A čo ešte musíme urobiť?
>> DIVÁKOV: A potom sa vrátiť true.
>> JASON Hirschhorn: Nie tak celkom.
Chýba nám jeden krok.
>> DIVÁKOV: New_node ďalšie má upozorniť na hodnotu null.
>> JASON Hirschhorn: Presne tak, Alden.
A potom sa môžeme vrátiť true.
OK.
Ale je to stále dobrý nápad urobiť veci na konci zoznamu, nie?
Dobrá.
Stále by v skutočnosti mohli dostať na koniec zoznamu.
Tak je tento kód v poriadku, ak sme na koniec zoznamu, a tam sú niektoré
veci na zozname?
Je to tak?
Vzhľadom k tomu máme ešte Marcusov nápad.
Mohli by sme opustiť túto slučku, pretože sme na konci zoznamu.
Takže sme stále chcú to kód tu dole?
>> DIVÁKOV: Áno.
>> JASON Hirschhorn: Jo.
A čo musíme zmeniť to?
Pravda.
Znie to dobre všetkým tak ďaleko?
Niekto nejaké -
Avi, máte niečo dodať?
>> Divákov: Nie
>> JASON Hirschhorn: OK.
Takže sme urobili pár zmien.
Urobili sme túto kontrolu, než sme šiel na prázdny zoznam.
Takže sme sa postarali o prázdneho zoznamu.
A tu sme sa starali o vkladaní niečo na koniec zoznamu.
Takže to vyzerá, že tento zatiaľ čo slučka odberu starostlivosť o veci medzi tým,
niekde v zozname, ak sú veci, ktoré v zozname.
>> OK.
Poďme tento program spustiť znova.
Nie je úspešná.
>> DIVÁKOV: Vy ste to.
>> JASON Hirschhorn: Oh, Neurobil som to.
Dobrý postreh, Michael.
Poďme pridať značku spojenú.
Linka 87 je tam chyba.
Linka 87.
Alden, to bol linku, ktorú mi dal.
Čo sa deje?
>> DIVÁKOV: Musí to byť null.
>> JASON Hirschhorn: Výborný.
Presne tak.
Malo by to byť null.
Poďme urobiť znovu.
Kompilácie.
OK.
Poďme vložte tri.
Vložka bola úspešná.
Poďme ju vytlačiť.
Ach, keby len mohli skontrolovať.
Ale my sme neurobili tlač ešte funkciu.
Poďme zadať niečo iné.
Čo by sme mali vstúpiť?
>> DIVÁKOV: Sedem.
>> JASON Hirschhorn: Seven?
>> DIVÁKOV: Áno.
>> JASON Hirschhorn: Máme poruchu seg.
Takže máme jednu, ale jasne nemôže dostať dva.
Je 5:07.
Takže by sme to mohli ladiť po dobu troch minút.
Ale ja idem na nás tu nechať a prejsť na hash tabuľky.
Ale opäť, odpovede tohto kódu Budem poslať e-mailom na vás trochu.
Sme veľmi blízko k nej.
Vrelo odporúčame vám zistiť, čo sa deje tu a opraviť ju.
Tak som vám pošleme tento kód ako dobre a riešenia -
pravdepodobne riešenie neskôr.
Najprv tento kód.
>> Ďalšia vec, ktorú chcem urobiť, ako my Povrchová úprava je nám nie je uvoľnené nič.
Takže chcem vám ukázať, čo Valgrind vyzerá.
Ak narazíme Valgrind hranice na našom programe,. / spojené.
Opäť platí, že podľa tohto snímku, sa by mal bežať Valgrind s nejakým typom
možnosť, v tomto prípade - Únik kontrola = plná.
Takže poďme napísať Valgrind - Únik kontrola = plná.
Takže to bude bežať Valgrind na našom programe.
A teraz sa program vlastne beží.
Takže ideme na to bežať rovnako ako pred, dať niečo dovnútra
Chystám sa dať v troch.
To funguje.
Nebudem sa snažiť dať do niečoho iného, ​​pretože budeme
dostať seg false v tomto prípade.
Tak som len tak odísť.
>> A teraz vidíte, tu dole úniku a zhrnutie haldy.
To sú dobré veci, ktoré Ak chcete vyskúšať.
Takže zhrnutie haldy - to hovorí, v prevádzke na výstupe - osem bajtov v jednom bloku.
To jeden blok uzol sme malloced.
Michael, si hovoril pred uzol je osem uhryznutie, pretože má celé číslo
a ukazovateľ.
Tak to je náš uzol.
A potom sa hovorí, že sme použili malloc sedemkrát a budeme oslobodení
niečo šesťkrát.
Ale my sme nikdy volal zadarmo, takže nemám tušenie, čo je to hovoríš.
>> Ale stačí, keď poviem, že keď si program beží, malloc je nazývaný
v niektorých iných miestach, kde sa Nemusíte sa obávať.
Takže malloc bol pravdepodobne nazvaný v niektorých miestach.
Nepotrebujeme robiť starosti, kde.
Ale je to naozaj my.
Prvý riadok je nám.
Opustili sme tento blok.
A vidíte, že tu v súhrne úniku.
Ešte dosiahnuteľný -
osem bajtov v jednom bloku.
To znamená, že pamäť -
sme unikli, že pamäť.
Definitívne stratil -
niečo, čo sa stratil nadobro.
Všeobecne platí, že nebudete nič vidieť tu.
Napriek tomu je všeobecne dostupný, ak budete vidieť veci, kde budete chcieť
sa pozrieť, čo kód, ktorý by mal sa oslobodil, ale ste zabudli oslobodiť.
>> A potom, ak to nie je tento prípad, pokiaľ sme urobili všetko zadarmo,
môžeme zistiť, že.
Povedzme, spustite program nie je uvedenie v ničom.
Uvidíte tu v použití na výstupe -
nula bajtov nulových blokov.
To znamená, že skoro nič neopustila ak tento program ukončený.
Takže pred zapnutím v pset6, spustite Valgrind a uistite sa, že nemáte
uvoľňovanie každej pamäte vo vašom programe.
Ak máte akékoľvek otázky s Valgrind, neváhajte osloviť.
Ale to je, ako ho použiť.
Veľmi jednoduchá - zistiť, či ste majú v užívaní na výstupe -
žiadne bytov v akýchkoľvek blokov.
>> Takže sme pracovali na vloženie uzla.
Mal som dve ďalšie funkcie tu - tlačiť uzly a uzly zadarmo.
Opäť platí, že sa jedná o funkcie, ktoré sú bude pre vás dobré praxe
pretože vám pomôže nielen s tieto cvičenia vzorky, ale tiež
na problém nastaviť.
Oni máp na celkom blízko k veciam budete musieť urobiť v
problém nastaviť.
Ale ja chcem, aby sa ubezpečil, sa dotkneme na všetko.
A hash tabuľky sú tiež veľmi dôležité, aby čo robíme v časti tejto
týždeň - alebo v sade problém.
>> Takže ideme dokončiť časť hovorí o hash tabuľky.
Ak zistíte, že som malý hash tabuľky.
To nie je to, čo hovoríme o, však.
Hovoríme o iný typ hash tabuľky.
A v jeho jadre, hash tabuľky nie je nič viac než
pole a haš funkcie.
Budeme hovoriť na chvíľu len uistite sa, že každý chápe, čo je to
hash funkcie.
A ja vám hovorím teraz, že je nič viac než dve veci -
pole a haš funkcie.
A tu sú kroky, prostredníctvom ktoré toto funguje.
>> Tu je náš poľa.
Tu je naša funkcia.
Najmä, hashovacie funkcie je potrebné urobiť pár vecí s tým.
Ja budem hovoriť konkrétne o tento problém nastaviť.
Je to pravdepodobne bude sa v reťazci.
A čo to ide vrátiť?
Aký typ dát?
Alden?
Váš hash funkcie vrátiť?
Číslo.
Tak toto je to, čo hash Tabuľka sa skladá z -
tabuľka vo forme poľa a haš funkcie.
Ako to funguje?
Pracuje v troch krokoch.
Dávame mu kľúč.
V tomto prípade, dáme to reťazec.
Hovoríme funkcia hash za prvý krok na kľúč a dostaneme hodnotu.
>> Konkrétne budeme hovoriť dostaneme číslo.
To celé číslo, sú veľmi špecifické hranice toho, čo môže byť, že celé číslo.
V tomto príklade, naše pole o veľkosti tri.
Takže to, čo čísla možno, že číslo je.
Aký je rozsah platných hodnôt pre že celé číslo, návratový typ tejto
hash funkcie?
Nula, jedna a dve.
Bod hašovacej funkcie je prísť na miesto v poli
kde je naším kľúčovým deje.
Existujú iba tri možné miesta tu -
nula, jeden, alebo dva.
Takže táto funkcia lepšiu návratnosť nula, jeden, alebo dva.
Niektoré platný Index v tomto poli.
>> A potom v závislosti na tom, kde sa vráti, môžete vidieť, že pole otvorené
uholník hodnotu.
To je miesto, kde sme dali kľúč.
Tak sme hodiť do tekvice, dostaneme von nulu.
Na poli držiaku 0, dáme tekvicu.
Hodíme u mačiek, dostaneme sa na jednu.
Dali sme mačku v jednom.
Dali sme do pavúka.
Vystupujeme dva.
Dali sme pavúka na pole držiaku dvoch.
Bolo by to pekné, keby to fungovalo takto.
Ale bohužiaľ, ako uvidíme, je to trochu zložitejšie.
>> Ako sa tam dostaneme, Akékoľvek otázky o tento základný
set-up z hash tabuľky?
To je obraz presne čo nakreslil na tabuľu.
Ale od tej doby sme ju nakreslil na tabuľu, som Nehodlám ísť do toho ďalej.
V podstate kľúče, mágia čierna skrinka - alebo v tomto prípade, teal box - z
hash funkcia je stavia do vedier.
A v tomto prípade sme nie je uvedenie názvu.
Dávame tým spojené telefónu číslo meno vo vedre.
Ale vy ste mohol veľmi dobre len dať meno do vedra.
>> To je len obraz toho, čo sme vychádzali z hracej plochy.
Máme potenciálne úskalia, hoci.
A tam sú dva a to najmä šmykľavky, že chcem ísť preč.
Prvý z nich je o funkcia hash.
Tak som sa spýtal na otázku, čo robí dobrý hash funkcie?
Dávam dve odpovede.
Prvá je, že je deterministický.
V súvislosti s hašovacej funkcií, Čo to znamená?
Áno?
>> DIVÁKOV: Je možné nájsť Obsah v konštantnom čase?
>> JASON Hirschhorn: To nie je to, čo to znamená.
Ale to je dobrý odhad.
Niekto iný má hádať na to, čo to znamená?
To je dobrá funkcia hash je deterministický?
Annie?
>> DIVÁKOV: To kľúč môže byť mapovaný iba na jedno miesto v tabuľke hash.
>> JASON Hirschhorn: To je Presne tak.
Zakaždým, keď dáte do tekvice, vždy vráti nulu.
Ak dáte do tekvice a vaše hash Funkcia vracia nulu, ale má
pravdepodobnosť vrátenia niečo inak väčšia ako nula -
takže možno to môže vrátiť jednu niekedy alebo dva iné časy -
že nie je dobré funkcie hash.
Ty si úplnú pravdu.
Váš hash funkcia by mala vrátiť Rovnaký presné číslo, v tomto prípade pre
rovnaký presný reťazec.
>> Možno, že sa vráti presne rovnakou číslo pre rovnaký reťazec presné
bez ohľadu na kapitalizáciu.
Ale v tomto prípade je to ešte deterministický, pretože viac vecí
sú mapované na rovnakú hodnotu.
To je v poriadku.
Ako dlho ako tam je len jeden výstup pre daný vstup.
>> OK.
Druhá vec je, že vráti platné indexy.
Priviezli sme si, že skôr.
Tento hash funkcie -
oh boy -
hašovacej funkcie by návrat platné indexy.
Takže povedať -
vráťme sa k tomuto príkladu.
Môj hash funkcie počíta až písmená v slove.
To je funkcia hash.
A vráti, že celé číslo.
Takže keď mám slovo A, je to chystá sa vrátiť jeden.
A to bude dať tu.
Čo keď som dal slovo bat?
Bude to vrátiť tri.
Kde sa bat ísť?
>> To sa nehodí.
Ale je potrebné niekam ísť.
To je môj hash tabuľka po tom všetkom, a všetko, čo je potrebné niekam ísť.
Takže tam, kde by sa bat ísť?
Akékoľvek myšlienky?
Háda?
Dobré odhady?
>> DIVÁKOV: Zero.
>> JASON Hirschhorn: Prečo nula?
>> DIVÁKOV: Vzhľadom k tomu, tri modulo tri je nula?
>> JASON Hirschhorn: Three modulo tri je nula.
To je skvelý odhad, a to je správne.
Takže v tomto prípade by mal asi ísť na nulu.
Takže dobrý spôsob, ako zabezpečiť, aby tento hash Funkcia vracia iba platné indexy sa
na modulo to podľa veľkosti tabuľky.
Ak modulo Čokoľvek priznania podľa tri, ste vždy dostane
niečo medzi nulou, jeden a dva.
A ak sa to vždy vracia sedem, a vždy modulo tri, ty si
Vždy dostane to isté.
>> Takže je to stále deterministický ak modulo.
Ale, že zabezpečí, že vám Nikdy si niečo -
neplatný priemyslu.
Všeobecne platí, že modulo by sa malo stať vnútri hash funkcie.
Takže nemusíte sa starať o to.
Ty jednoducho nemôže zabezpečiť, že to je platný Index.
Akékoľvek otázky týkajúce sa tejto potenciálne úskalia?
>> OK.
A tam ideme.
Ďalšie potenciálne úskalia, a To je veľký.
Čo keď mapa dva kľúče na rovnakú hodnotu?
Takže existujú dva spôsoby, ako zvládnuť to.
Prvý z nich sa nazýva lineárny snímanie, ktoré som
nie ísť preč.
Ale mali by ste byť oboznámení s tým, ako že funguje a čo to je.
>> Druhý Chystám sa ísť cez pretože to je ten, že mnoho
ľudia budú pravdepodobne skončí rozhodovanie o tom, používať v ich problému sade.
Samozrejme, že nemusíte.
Ale pre problémové sady, mnoho ľudí majú sklon vyberať si vytvoriť hash tabuľky
s oddelenou reťazenie prevedení ich slovníka.
Takže sme ísť nad tým, čo to znamená, na vytvorenie hash tabuľky sa
oddelené zreťazenie.
>> Tak som sa dal do tekvice.
Je to vráti nulu.
A dal som tekvica tu.
Potom som sa dal do -
čo je ďalší Halloween-themed vec?
>> DIVÁKOV: Candy.
>> JASON Hirschhorn: Candy!
To je skvelá jedna.
Dal som do cukroviniek a sladkosti tiež mi dáva nulu.
Čo mám robiť?
Nejaké nápady?
Pretože ste všetci tak nejako viem, čo oddelený reťazenie je.
Takže nejaké nápady, čo robiť?
Jo.
>> DIVÁKOV: Uvedenie reťazec v skutočnosti v tabuľke hash.
>> JASON Hirschhorn: Tak ideme na nakresliť dobrý nápad sem.
OK.
>> DIVÁKOV: Už Hashtable [Nepočuteľný]
ukazovateľ, ktorý ukazuje na začiatok zoznamu.
A potom si tekvica byť prvá hodnota v tomto prepojenom zoznamu a sladkosti sa
druhá hodnota v tomto prepojenom zozname.
>> JASON Hirschhorn: OK.
Marcus, že bol vynikajúci.
Chystám sa zlomiť dole.
Marcus hovorí nie prepísať tekvica.
To by bolo zlé.
Nedávajte cukroví niekde inde.
Chystáme sa dať obaja na nule.
Ale budeme sa zaoberať ich uvádzanie na nulu
vytvorenie zoznamu na nulu.
A budeme chcete vytvoriť zoznam všetko, mapované na nulu.
A najlepší spôsob, ako sme sa naučili vytvárať Zoznam, ktorý môže rásť a zmenšovať
dynamicky nie je v ďalšie pole.
Takže nie multi-dimenzionální pole.
Ale len vytvorenie prepojeného zoznamu.
>> Takže to, čo navrhol -
Idem si nový -
je vytvoriť pole s ukazovateľmi, pole ukazovateľov.
OK.
Nejaký nápad, alebo náznak toho, čo typ z týchto ukazovateľov by mali byť?
Marcus?
>> DIVÁKOV: Ukazovatele na -
>> JASON Hirschhorn: Pretože vám povedal spájať zoznam, takže -
>> DIVÁKOV: ukazovatele uzla?
>> JASON Hirschhorn: ukazovatele uzla.
Ak sa veci v našom spojené Zoznam sú uzly potom
by mala byť uzol ukazovatele.
A to, čo sa im rovnajú pôvodne?
>> DIVÁKOV: Null.
>> JASON Hirschhorn: Null.
Takže je tu náš prázdna vec.
Tekvicové vráti nulu.
Čo budeme robiť?
Prechádzka ma cez neho?
Vlastne, Marcus už mi dal.
Niekto chodí ma cez neho.
Čo budeme robiť, keď -
to vyzerá veľmi podobne ako to, čo sme práve robí.
Avi.
>> DIVÁKOV: Budem hádať.
Takže keď sa dostanete cukríky.
>> JASON Hirschhorn: Jo.
No, máme tekvica.
Poďme si našu prvú.
Máme tekvica.
>> DIVÁKOV: OK.
Tekvicové vráti nulu.
Takže ste to v tom.
Alebo vlastne, to si dal v prepojenom zozname.
>> JASON Hirschhorn: Ako sme vložte ho do prepojeného zoznamu?
>> DIVÁKOV: Oh, je vlastný syntax?
>> JASON Hirschhorn: Len chodiť -
povedať viac.
Čo budeme robiť?
>> DIVÁKOV: Len vložiť že ako prvý uzol.
>> JASON Hirschhorn: OK.
Takže máme uzol, tekvica.
A teraz, ako mám vložiť to?
>> DIVÁKOV: Môžete priradiť to ukazovateľ.
>> JASON Hirschhorn: Aké ukazovatele?
>> Divákov: ukazovateľ na nule.
>> JASON Hirschhorn: Tak kde robí tento bod?
>> DIVÁKOV: Ak chcete null práve teraz.
>> JASON Hirschhorn: No, to ukazuje na hodnotu null.
Ale dávam do tekvice.
Takže tam, kde by to ukazovať?
>> DIVÁKOV: Ak chcete tekvica.
>> JASON Hirschhorn: Ak chcete tekvica.
Presne tak.
Takže to ukazuje na tekvice.
A kde sa to robí ukazovateľ v tekvica bode?
Na
>> DIVÁKOV: Null.
>> JASON Hirschhorn: Ak chcete hodnotu null.
Presne tak.
Takže sme jednoducho vloží niečo do prepojeného zoznamu.
Práve sme napísal tento kód, ako to urobiť.
Takmer sme skoro mám úplne popraskané.
Teraz vložíme cukríky.
Naše cukroví tiež klesne na nulu.
Tak čo budeme robiť cukroví?
>> DIVÁKOV: Záleží na tom, či Nie je sa snažíme triediť.
>> JASON Hirschhorn: To je Presne tak.
Záleží na tom, či snažíme sa ho vyriešiť.
Predpokladajme, že nie sme bude triediť.
>> DIVÁKOV: Tak, ako sme sa bavili pred, je to najjednoduchšie len aby to
hneď na začiatku, aby ukazovateľ od nulových bodov, do cukroviniek.
>> JASON Hirschhorn: OK.
Vydrž.
Dovoľte mi, aby som vytvoriť cukroví práve tu.
Takže tento ukazovateľ -
>> DIVÁKOV: Jo, mal by sa sa ukázal na cukrovinky.
Potom sa ukazovateľ od candy prejdite na tekvica.
>> JASON Hirschhorn: Ako, že?
A povedať, že sme dostali ďalšie vec máp na nulu?
>> DIVÁKOV: No, práve robiť to isté?
>> JASON Hirschhorn: Vykonajte to isté.
Takže v tomto prípade, keď to neurobíme chcete, aby ju udržali radené ju
Znie to pomerne jednoduché.
Berieme ukazovateľ na Index vzhľadom k našej hash funkcie.
Musíme tento bod do nášho nového uzla.
A potom, čo to bolo ukázal skôr -
v tomto prípade hodnotu null, v Druhý prípad tekvice -
že, ako sa to ukazuje na skôr, pridáme do najbližšieho
náš nový uzol.
Sme vkladanie niečo na začiatku.
V skutočnosti je to oveľa jednoduchšie, než sa snaží udržať zoznamu zoradené.
Ale opäť, vyhľadávanie bude viac komplikované tu.
Budeme mať vždy ísť až do konca.
>> OK.
Máte otázky k samostatnej reťazenie?
Ako to funguje?
Prosím, spýtajte sa ich teraz.
Naozaj chcem, aby sa ubezpečil všetky pochopiť, ako sme vyraziť.
>> DIVÁKOV: Prečo si dať tekvicu a cukrovinky do rovnakej
časť tabuľky hash?
>> JASON Hirschhorn: Dobrá otázka.
Prečo dať ich do rovnakej časť tabuľky hash?
No, v tomto prípade naše hash funkcie vráti nulu pre obe z nich.
Takže je potrebné ísť na Index nule pretože to je miesto, kde budeme
pozrite sa na ne, ak sa niekedy Chcete ich vyhľadať.
Opäť platí, že sa lineárne snímanie prístupu by sme im dať obaja na nule.
Ale v samostatnom prístupe reťazca, ideme dať obaja na nule
a potom vytvoriť zoznam off nulu.
>> A my nechceme prepísať tekvica len pre to, pretože potom budeme
Predpokladám, že tekvica sa nikdy vložená.
Ak budeme len držať jednu vec miesto, ktoré by bolo zlé.
Potom by tam byť žiadny šanca na nás vôbec -
ak sme kedy mali duplikát, potom sme by len vymazať našu počiatočnú hodnotu.
Takže to je dôvod, prečo robíme tento prístup.
Alebo, že je dôvod, prečo sme sa rozhodli - ale opäť, my zvolil samostatný zreťazenie prístup,
, Ktoré je tu mnoho ďalších prístupov by sa dalo vybrať.
Znamená to, že odpoveď na vašu otázku?
>> OK.
Carlos.
Lineárne snímanie by znamenalo -
ak by sme našli kolízii na nule, sme bude vyzerať v ďalšom mieste, aby zistili, či
to bolo otvorené a dať to tam.
A potom sa pozrieme v ďalšom športe a uvidíme, či to bolo otvorené a dať to tam.
Tak sme sa nájsť ďalšie dostupné otvorené miesto a dať to tam.
Nejaké ďalšie otázky?
Jo, Avi.
>> DIVÁKOV: V nadväznosti na to, Čo myslíš tým ďalšom mieste?
V tabuľke hash alebo prepojeného zoznamu.
>> JASON Hirschhorn: Pre lineárne programovanie, žiadne spojové zoznamy.
Ďalšie miesto na stole hash.
>> DIVÁKOV: OK.
Takže hash tabuľka bude inicializovaný veľkosti -
ako je počet reťazcov že ste boli vkladanie?
>> JASON Hirschhorn: Tie by Chcem, aby to bolo naozaj veľké.
Áno.
Tu je obrázok toho, čo sme len kreslil na tabuľu.
Opäť máme kolízii tu.
152.
A uvidíte, sme vytvorili spájať zoznam z nej.
Opäť platí, že hash tabuľky oddelené zreťazenie prístup nie je ten, ktorý
musí brať v nastavení problémy šesť, ale je jedno, že veľa
študenti majú tendenciu brať.
Tak v takom prípade, poďme krátko pohovoril predtým, než sme vyraziť o probléme šesť,
a potom budem zdieľať svoj príbeh sa s vami.
Máme tri minúty.
>> Problém set šesť.
Máte štyri funkcie -
zaťaženie, skontrolujte, veľkosť, a vyložiť.
Load -
dobre, že sme sa deje po záťaži práve teraz.
Kreslil sme zaťažení na palube.
A dokonca sme začali kódovanie veľa vloženie do prepojeného zoznamu.
Takže zaťaženie nie je o moc väčšie ako to, čo sme práve robili.
>> Kontrola je raz budete mať niečo načítať.
Je to rovnaký proces, ako je tento.
Rovnaké prvé dve časti, kde sa hodiť niečo, čo do funkcie hash
a získať jeho hodnotu.
Ale teraz nie sme vloženie.
Teraz hľadáme pre neho.
Som ukážkový kód napísaný pre vyhľadávanie niečo v prepojenom zozname.
Chcel by som vyzvať vás k praxi, že.
Ale intuitívne nájsť niečo, čo je celkom podobný vkladanie niečo.
Naozaj sme nakreslil obrázok nájsť niečo v prepojenom zozname, pohybujúce sa
až kým sa dostal až do konca.
A ak ste sa dostali na koniec a nemohol nájsť, potom to tam nie je.
Tak to je kontrola, v podstate.
>> Ďalšie je veľkosť.
Poďme preskočiť veľkosti.
Konečne ste sa uvoľniť.
Uvoľniť je tá, ktorú sme doteraz vypracované na palube alebo ešte kódované.
Ale ja Odporúčame vám vyskúšať kódovanie v našom vzorke Google napríklad zoznam.
Ale vyložiť intuitívne je podobný zadarmo -
alebo som na mysli, je podobný skontrolovať.
S výnimkou teraz zakaždým, keď vy budete vďaka, že ste jednoducho kontroluje,
zistiť, či máte hodnotu tam.
Ale ty berieš ten uzol a uvoľňovať to, v podstate.
To je to, čo vyložiť vás spýta na to.
Zadarmo všetko, čo ste malloced.
Takže idete cez celý zoznam opäť prechádza celý hash
opäť tabuľka.
Tentoraz sa nekontrolujú vidieť, čo tam je.
Stačí uvoľniť to, čo tam je.
>> A konečne veľkosti.
Veľkosť by mala byť vykonaná.
Ak nechcete vykonávať veľkosť -
Poviem to takto.
Ak nechcete vykonávať veľkosť v presne jeden riadok kódu, vrátane
vrátiť vyhlásenie, ste robí veľkosť nesprávne.
Takže uistite sa, že veľkosť, pre úplné vykonanie body, robíte to presne jeden
riadok kódu, vrátane return.
>> A to zabaliť ešte, Akchar.
Snaživec.
Chcel som povedať, ďakujem chlapci prišiel do sekcie.
Majú Happy Halloween.
To je môj kostým.
Budem mať na sebe tento štvrtok keď som ťa vidieť na úradné hodiny.
A ak ste zvedaví, niektorí viac pozadia, ako k tomuto kostýmu, cítite
zadarmo vyskúšať 2.011 sekcie pre príbeh o tom, prečo som
na sebe kostým tekvice.
A to je smutný príbeh.
Takže uistite sa, že máte Niektoré tkanivá v okolí.
Ale na to, že ak máte nejaké otázky, budem držať okolo
mimo po bode.
Veľa šťastia na problém nastaviť šesť.
A ako vždy, ak máte nejaké otázky, dajte mi vedieť.