[Powered by Google Translate] [§ 7] [méně komfortní]
[Nate Hardison] [Harvard University]
[To je CS50.] [CS50.TV]
>> Vítejte v § 7.
Díky hurikánu Sandy,
místo toho, aby normální část tento týden,
děláme to průchozí, prostřednictvím sekce otázek.
Budu se po spolu s Problem Set 6 Specification,
a procházejí všechny otázky v
Sekce Dotazy sekce.
Pokud máte nějaké dotazy,
prosím poslat tyto na CS50 diskutovat.
>> Dobře. Pojďme začít.
Právě teď se dívám na straně 3 specifikace problému Set.
Budeme nejprve začít mluvit o binárních stromech
protože ty mají hodně důležité pro tento týden problému set -
Strom Huffman kódování.
Jedním z prvních datových struktur jsme o tom mluvili na CS50 bylo pole.
Si uvědomit, že pole je posloupnost prvků -
všechny stejného typu - uloženy přímo vedle sebe v paměti.
Pokud mám celé číslo pole, které mohu čerpat pomocí tohoto boxy-čísla-celá čísla styl -
Řekněme, že mám 5 v prvním poli, mám 7 ve druhém,
pak jsem si 8, 10, a 20 v konečném poli.
Pamatujte si, že opravdu dva dobré věci o tomto poli
je, že máme tuto konstantu-time přístup k jakékoli konkrétní prvek
v poli, pokud známe jeho index.
Například, pokud chci chytit třetí prvek v poli -
na indexu 2 pomocí našeho nuly indexování systému -
Doslova jsem prostě udělat jednoduchý matematický výpočet,
hop do této polohy v poli,
vytáhněte 8, který je uložen tam,
a já jsem dobré jít.
>> Jedním ze špatných věcí na tomto poli -, že jsme o tom mluvili
když jsme hovořili o propojených seznamů -
je, že když chci vložit prvek do tohoto pole,
Budu muset udělat nějaké řazení okolí.
Například, toto pole tady
je v tříděném pořádku - ve vzestupném pořadí -
5, pak 7, pak 8, pak 10, a pak se 20 -
ale když chci vložit číslo 9 do tohoto pole,
Budu muset posunout některé prvky, aby místo.
Můžeme čerpat tuto tady.
Budu muset přesunout 5, 7, a pak 8;
vytvořit mezeru, kde jsem můžete dát 9,
a pak se 10 a 20 může jít vpravo od 9.
To je druh bolesti, protože v nejhorším případě -
když jsme s vložit buď na začátku a na konci
z pole, v závislosti na tom, jak jsme posouvání -
můžeme skončit museli posunout všechny prvky
že se to v současné době skladování v poli.
>> Takže, co bylo jak vyřešit tento problém?
Cesta kolem to bylo jít do našeho Linked-seznam metoda, kde -
místo uložení prvků 5, 7, 8, 10, a 20 všechny vedle sebe v paměti -
to, co jsme místo toho jsem byla ukládat jim druhu tam, kde jsme chtěli uložit
v těchto linked-seznam uzlů, které jsem kreslení tady, druh ad hoc.
A pak jsme spojili dohromady pomocí těchto dalších ukazatelů.
Mohu mít ukazatel z 5 na 7,
ukazatel z 7 na 8,
ukazatel z 8 na 10,
a konečně, ukazatel od 10 do 20,
a pak nulový ukazatel na 20 naznačuje, že nic nezbylo.
Trade-off, že tu máme
je, že teď, když chceme vložit číslo 9 do našeho seznamu seřazeny,
všechno, co musíme udělat, je vytvořit nový uzel s 9,
byla připojena až k bodu na příslušné místo,
a pak re-wire 8 bodu dolů na 9.
To je docela jednoduché, za předpokladu, že přesně víme, kam chceme vložit 9.
Ale trade-off výměnou za to, že jsme dnes ztratili konstantní časový přístup
pro konkrétní prvek v naší datové struktury.
Například, pokud chci najít čtvrtý prvek v tomto propojeném seznamu,
Budu muset začít na začátku seznamu
a pracovat svou cestu přes počítání uzlů s-node, až najdu čtvrtém.
>> S cílem získat lepší přístup k výkonu než propojeného seznamu -
ale také udržet některé z výhod, které jsme měli
pokud jde o vložení čase z propojeného seznamu -
binární strom bude potřebovat trochu více paměti.
Zejména, místo toho, aby jen s jednou ukazatel v binárním stromu uzlu -
jako linked-seznamu uzel dělá -
budeme-li přidat druhý ukazatel do binárního stromu uzel.
Spíše než jen s jednou ukazatel na další prvek,
budeme mít ukazatel na levé dítě a pravé dítě.
>> Pojďme nakreslit obrázek, co to vlastně vypadá.
Opět, budu používat tyto krabice a šípy.
Binární strom uzel bude začít s jednoduchým krabici.
To bude mít prostor pro hodnotu,
a pak je to také bude mít prostor pro levé dítě a pravé dítě.
Chystám se popsat zde.
Budeme mít levé dítě, a pak budeme mít ten správný dítě.
Existuje mnoho různých způsobů, jak to udělat.
Někdy na prostor a pohodlí,
Budu vlastně kreslit jako já tady dělám na dně
kde budu mít hodnotu na vrcholu,
a pak na pravé dítě na pravé dolní,
a levou dítě na dolní-levý.
Vraťme se zpět k tomuto nahoru diagramu,
máme hodnotu na samém vrcholu,
pak máme levou dítě ukazatel, a pak máme právo-dítě ukazatel.
>> V problému Nastavit specifikace,
Hovoříme-li o kreslení uzel, který má hodnotu 7,
a pak levé dítě ukazatel, který je nulový, a pravým dítě ukazatel, který je prázdný.
Můžeme buď napsat kapitálové NULL v prostoru pro
jak levé dítě a právo dítěte, nebo můžeme čerpat tento úhlopříčka lomítko
každým z polí naznačují, že je to null.
Já budu dělat, že právě proto, že je to jednodušší.
To, co vidíte tady jsou dva způsoby, jak diagramů velmi jednoduchý binární strom uzel
kde máme hodnotu 7 a nulové podřízené uvedeme.
>> Druhá část našich specifikace hovoří o tom, jak s lineárními seznamy -
pamatujte, jsme měli jen držet na úplně první prvek v seznamu
pamatovat celý seznam -
a podobně, s binárním stromem, stačí držet na jedné ukazatel na strom
za účelem zachování kontroly nad celou datové struktury.
Tato speciální prvek stromu se nazývá kořen stromu.
Například, pokud se tento uzel - to uzel obsahující hodnotu 7
s null levé a pravé dítě ukazatelů -
byly pouze hodnota v našem stromu,
pak by to být náš kořenový uzel.
Je to úplně na začátku našeho stromu.
Vidíme to trochu jasněji, jakmile začneme přidávat další uzly náš strom.
Dovolte mi, abych vytáhnout novou stránku.
>> Nyní budeme kreslit strom, který má 7 u kořene,
a 3 uvnitř levého dítěte, a 9 vnitřek pravé dítě.
Opět, to je docela jednoduchý.
Máme 7, nakreslete uzel 3, uzel pro 9,
a já jdu nastavit levou dítě ukazatel 7 ukazoval na uzel obsahující 3,
a na pravé dítě ukazatel na uzel obsahující 7 k uzlu obsahující 9.
Nyní, od 3 a 9 nemají žádné děti,
budeme nastavit všechny jejich podřízené ukazatele budou mít hodnotu null.
Zde kořen našeho stromu odpovídá uzlu obsahující číslo 7.
Můžete vidět, že pokud vše, co máme, je ukazatel na tento kořenový uzel,
pak můžeme projít náš strom a přístup k oběma podřízené uzly -
oba 3 a 9.
Není třeba zachovat odkazy na jednotlivý uzel na stromě.
Dobře. Nyní budeme přidávat další uzel tohoto schématu.
Budeme-li přidat uzel obsahující 6,
a budeme přidávat to jako pravé dítě uzlu obsahujícího 3.
Chcete-li se, že budu mazat, že nulový ukazatel v 3-uzel
byla připojena až k bodu uzlu obsahující 6. Dobře.
>> V tomto bodě, pojďme přes trochou terminologie.
Chcete-li začít, důvod, že tento se nazývá binární strom, zejména
je to, že má dva podřízené ukazatele.
Existují i ​​jiné druhy stromů, které mají více dětí ukazatele.
Zejména, jste "vyzkoušet" v problému Set 5.
Určitě jste si všimli, že v tomto pokusu, jste měli 27 různých ukazatelů na různé děti -
jeden pro každou z 26 písmen v anglické abecedě,
a pak 27. pro apostrofem -
tak, že je podobný typ stromu.
Ale tady, protože je to binární, máme jen dvě podřízené ukazatele.
>> Kromě tohoto kořenového uzlu, který jsme mluvili,
jsme také hází kolem tohoto pojmu "dítě."
Co to znamená pro jeden uzel být dítě jiného uzlu?
To znamená, že se doslova podřízený uzel je dítě dalšího uzlu
pokud je toto uzel má jeden z jeho podřízených ukazatelů stanovených upozornit na tento uzel.
K tomu, aby to do více konkrétních podmínkách,
pokud 3 je zaměřena na jeden z dětských ukazatelů z 7, pak 3 je dítě 7.
Pokud bychom měli přijít na to, co děti 7 arů -
dobře, vidíme, že 7 má ukazatel na 3 a ukazatel na 9,
tak 9 a 3 jsou děti 7.
Devět nemá žádné děti, protože jeho podřízené ukazatele jsou null,
a 3 má pouze jedno dítě, 6.
Šest také nemá žádné děti, protože oba jeho ukazatelů jsou null, které budeme čerpat hned.
>> Kromě toho jsme také mluvit o rodičích určitého uzlu,
a to je, jak byste očekávali, opak tohoto dítěte popisu.
Každý uzel má jen jednoho rodiče - místo dvou jak se dalo očekávat s lidmi.
Například, mateřská 3 je 7.
Rodič 9 je také 7, a rodič 6 je 3. Nic moc na to.
Máme také podmínky hovořit o prarodičů a vnoučat,
a obecněji budeme mluvit o předcích
a potomci v konkrétním uzlu.
Předchůdce uzlu - nebo předci, spíše o uzlu -
jsou všechny uzly, které leží na cestě z kořene do tohoto uzlu.
Například, když jsem při pohledu na uzlu 6,
pak předkové se bude i 3 a 7.
Předkové 9, například, jsou - když jsem při pohledu na uzlu 9 -
pak předek 9 je jen 7.
A potomci jsou přesně naopak.
Pokud se chci podívat na všechny potomky 7,
pak jsem se podívat na všechny uzly pod ním.
Takže, mám 3, 9, a 6 všechny jako potomků 7.
>> Konečný termín, který budeme mluvit, je tento pojem je sourozenec.
Sourozenci - druh po podél těchto rodinných podmínek -
jsou uzly, které jsou na stejné úrovni ve stromu.
Takže, 3 a 9 jsou sourozenci, protože jsou na stejné úrovni ve stromu.
Oba mají stejné rodiče, 7.
Na 6 nemá žádné sourozence, protože 9 nemá žádné děti.
A 7 nemá žádné sourozence, protože je to kořen našeho stromu,
a tam je vždy jen 1 root.
Na 7 mají sourozenců by muselo být uzel nad 7.
By muselo být rodič 7, v takovém případě 7 by již kořen stromu.
Pak, že nová mateřská 7 by také měla mít dítě,
a že dítě by pak být sourozenec 7.
>> Dobře. Dál.
Když jsme začali náš rozhovor binárních stromů,
jsme si povídali o tom, jak jsme chtěli použít k
získat výhodu nad obou polích a vzájemně provázaných seznamů.
A způsob, jakým budeme dělat, že je s tímto uspořádání majetku.
Můžeme říci, že binární strom je nařízeno, v souladu se specifikací,
pokud pro každý uzel v našem stromu, všechny jeho potomky na levé -
vlevo dítě a všechny levé dítě potomků -
mají menší hodnoty, a všechny uzly na pravé straně -
právo dítě a všechny pravé dítě potomků -
mají uzly větší než hodnota aktuálního uzlu, který se právě díváte.
Jen pro jednoduchost, budeme předpokládat, že zde nejsou žádné duplicitní uzly v našem stromu.
Například, v této větvi nebudeme zabývat se případem
kde mají hodnotu 7 u kořene
a pak také mají hodnotu 7 jinde ve stromu.
V tomto případě, všimnete si, že tento strom je opravdu nařídil.
Máme hodnotu 7 v kořenovém adresáři.
Všechno na levé straně 7 -
když jsem zpět všechny z těchto maličkých značek zde -
všechno vlevo od 7 - za 3 a 6 -
tyto hodnoty jsou oba méně než 7, a vše se vpravo - což je přesně to 9 -
je větší než 7.
>> To však není jediným objednat strom obsahující tyto hodnoty,
ale pojďme tomu pár dalších z nich.
Tam je skutečně celá parta způsobů, jak to můžeme udělat.
Budu používat těsnopis jen aby to jednoduché, pokud -
spíše než protahoval celé krabice-a šípy -
Já jsem prostě jít kreslit čísla a přidejte šipky je spojují.
Chcete-li začít, prostě budeme psát naše původní strom zase tam, kde jsme měli 7, a pak 3,
a pak 3 ukazuje směrem vpravo na 6,
a 7 měl pravý dítě, které bylo 9.
Dobře. Co je další způsob, jak bychom mohli napsat tento strom?
Místo toho, aby 3 je vlevo dítě 7,
můžeme také 6 bude levá dítě 7,
a pak 3 musí být na levé dítětem 6.
To by vypadat jako na tomto stromu přímo tady, kde mám 7,
pak 6, pak 3, a 9 na pravé straně.
My také nemusí mít 7 jako naše kořenového uzlu.
Mohli bychom také mít 6 jako náš kořenový uzel.
Co by to vypadat?
Pokud budeme udržovat tuto objednanou vlastnost,
všechno vlevo od 6 musí být menší než to.
Je tu jen jedna možnost, a to 3.
Ale pak jako pravé dítě 6, máme dvě možnosti.
Za prvé, mohli bychom mít 7 a pak 9,
nebo můžeme kreslit - jako bych chtěl dělat tady -
kde máme 9 jako pravé dítě v 6,
a pak 7 jako levé podřízený 9.
>> Nyní, 7 a 6 nejsou jediné možné hodnoty pro kořen.
Mohli bychom také 3 musí být v kořenovém adresáři.
Co se stane, když 3 je u kořene?
Zde, věci se trochu zajímavé.
Tři nemá žádné hodnoty, které jsou menší než to,
tak, že celá levá strana stromu je jen tak, že je nulový.
Je tu nebude nic tam.
Na pravé straně, mohli bychom uvést věci ve vzestupném pořadí.
Mohli bychom mít 3, pak 6, pak 7, pak 9.
Nebo bychom to mohli udělat 3, pak 6, pak 9, pak 7.
Nebo bychom to mohli udělat 3, pak 7, pak 6, pak 9.
Nebo, 3, 7 - vlastně ne, nemůžeme udělat 7 už.
To je naše jediná věc tam.
Můžeme to udělat 9, a pak z 9 můžeme udělat 6 a pak 7.
Nebo, můžeme 3, pak 9, potom 7, a pak 6.
>> Jedna věc je upozornit na zde
že tyto stromy jsou trochu divný-dívat.
Zejména, pokud se podíváme na 4 stromy na pravé straně -
Budu obíhat je, zde -
Tyto stromy vypadají téměř stejně jako propojeného seznamu.
Každý uzel má pouze jedno dítě,
a tak není k dispozici žádný z tohoto stromové struktury, které vidíme, například,
v této jedné osamělý strom přes tady na levém dolním rohu.
Tyto stromy jsou vlastně jen degenerují binární stromy,
a budeme mluvit o nich více v budoucnosti -
zvláště pokud jdete na přijmout další kurzy informatiky.
Tyto stromy jsou degenerované.
Jsou to velmi užitečné, protože skutečně, tato struktura propůjčuje
k vyhledávání časy podobné jako propojeného seznamu.
Nechceme se využít extra paměti - tento dodatečný ukazatel -
protože naší struktury je špatná tímto způsobem.
Spíše než jít dál a upozornit na binární stromy, které mají 9 u kořene,
která je konečným případ, že by mohl být
jsme místo, v tomto bodě, bude mluvit trochu o tomto jiný termín
že používáme, když mluvíme o stromech, které se nazývá výška.
>> Výška stromu je vzdálenost od kořene k nejvíce vzdálené uzlu,
nebo spíše počet chmele, které by se, aby se za účelem
začít od kořene a pak skončí na nejvíce vzdálené uzlu ve stromu.
Podíváme-li se na některé z těchto stromů, které jsme vypracovány tady,
můžeme vidět, že pokud budeme mít tento strom v levém horním rohu a začneme na 3,
pak musíme udělat 1 hop se dostat na 6, druhá hop se dostat do 7,
a třetí hop se dostat do 9.
Takže, výška tohoto stromu je 3.
Můžeme to udělat stejný výkon pro ostatní stromy uvedených s tímto zeleným,
a vidíme, že výška všech těchto stromů je také opravdu 3.
To je součástí toho, co dělá je zvrhlík -
, že jejich výška je jen jeden méně než je počet uzlů v celém stromu.
Podíváme-li se na tento druhý strom, který je obklopen s červenou, na straně druhé,
vidíme, že nejvíce vzdálené koncové uzly jsou 6 a 9 -
listy, což jsou uzly, které nemají žádné děti.
Takže, aby se dostal z kořenového uzlu buď 6 nebo 9,
musíme udělat jednu hop se dostat do 7 a pak druhý hop se dostat do 9,
a podobně, jen druhý hop z 7 se dostat k 6.
Takže, výška tohoto stromu sem je pouze 2.
Můžete se vrátit zpět, a to pro všechny ostatní stromy, které jsme dříve diskutovali
počínaje 7 a 6,
a zjistíte, že výška všech těchto stromů je také 2.
>> Důvod, proč jsme mluvili o nařízeno binární stromy
a proč jsou v pohodě, je proto, že se můžete probírat ně
velmi podobný způsob vyhledávání přes tříděném poli.
To je místo, kde budeme mluvit o získání že lepší vyhledávání čas
přes jednoduché propojeného seznamu.
S propojeného seznamu - pokud chcete najít konkrétní prvek -
jste na nejlepší dělat nějaké lineární hledání
kde začít na začátku seznamu a hop jeden po jednom -
jeden uzel jedním uzlem -
celý seznam, dokud nenajdete, co hledáte.
Vzhledem k tomu, pokud máte binární strom, který je uložen v této pěkné formátu,
můžete skutečně dostat více binárního vyhledávání děje
kde si rozděl a panuj
a hledání přes odpovídající polovině stromu na každém kroku.
Pojďme se podívat, jak to funguje.
>> Pokud máme - opět vrací do původního stromu -
začneme v 7, my máme 3 vlevo, 9 na pravé straně,
a pod 3 máme 6.
Pokud chceme vyhledat číslo 6 v tomto stromu, měli bychom začít u kořene.
Rádi bychom tyto hodnoty jsme hledali, řekněme 6,
na hodnotu uloženou v uzlu, který jsme v současné době při pohledu na, 7,
zjistí, že 6 je opravdu méně než 7, a tak jsme si přesunout doleva.
Pokud je hodnota 6 byl vyšší než 7, bychom se místo toho se pohyboval napravo.
Vzhledem k tomu, víme, že - vzhledem ke struktuře našeho objednaného binárního stromu -
všechny hodnoty menší než 7 se bude uložen na levé straně 7,
není třeba, aby neobtěžoval pohledu přes pravé straně stromu.
Jakmile jsme se přesunout doleva a my jsme nyní v uzlu obsahující 3,
můžeme udělat stejnou srovnání zase tam, kde jsme porovnat 3 a 6.
A my zjistíme, že zatímco 6 - hodnota, kterou hledáte - je větší než 3,
můžeme jít na pravé straně uzlu, která obsahuje 3.
Není levá strana tady, takže jsme mohli ignorovat, že.
Ale my jen víme, že proto, že se díváme na strom sám,
a my můžeme vidět, že strom nemá žádné děti.
>> Je také docela snadné se podívat do 6 v této větvi, pokud děláme to sami jako lidé,
ale pojďme sledovat tento proces mechanicky jako počítač udělá
opravdu pochopit algoritmus.
V tomto bodě, jsme nyní podíváme na uzlu, který obsahuje 6,
a hledáme pro hodnotu 6,
tak, opravdu, jsme našli odpovídající uzel.
Našli jsme hodnotu 6 v našem stromu, a můžeme zastavit naše vyhledávání.
V tomto bodě, v závislosti na tom, co se děje,
můžeme říci, že ano, jsme našli hodnotu 6, to je v naší stromu.
Nebo, pokud plánujeme vložit uzel, nebo dělat něco, můžeme dělat, že v tomto bodě.
>> Pojďme udělat pár dalších vyhledávání, jen aby viděl, jak to funguje.
Pojďme se podívat na to, co se stane, když jsme byli vyzkoušet a podívat se na hodnotu 10.
Pokud bychom se podívali do hodnoty 10, my bychom začali u kořene.
Měli bychom vidět, že 10 je větší než 7, tak bychom přesune doprava.
Měli bychom dostat na 9 a porovnejte 9 do 10 a uvidíte, že 9 je opravdu méně než 10.
Takže znovu, tak se snažíme přesunout doprava.
Ale v tomto bodě, měli bychom si všimnout, že jsme na null uzlu.
Tam nic není. Není nic, kde by měla být 10.
Toto je místo, kde se může hlásit selhání -, že skutečně č. 10 ve stromu.
A konečně, pojďme projít případě se snažíme vyhledat 1 do stromu.
To je podobné tomu, co se stane, když se podíváme do 10, s výjimkou místo toho, aby práva,
jsme jít doleva.
Začneme na 7 a uvidíte, že 1 je menší než 7, tak jsme se přesunout doleva.
Dostáváme se na 3 a uvidíte, že 1 je menší než 3, takže opět se snažíme přesunout doleva.
V tomto bodě máme null uzel, takže opět můžeme hlásit poruchu.
>> Pokud se chcete dozvědět více o binárních stromech,
existuje celá parta veselých malých problémů, které můžete dělat s nimi.
Navrhuji cvičit kresbu z těchto diagramů jeden po druhém
a po přes všechny jednotlivé kroky,
protože to přijde super-praktický
nejen, když děláte kódování Huffmanova problém sadu
ale také v budoucích kurzů -
jen naučit, jak čerpat z těchto datových struktur a myslím, že přes problémy
s pero a papír nebo, v tomto případě, iPad a pero.
>> V tomto bodě ačkoli, budeme se pohybovat na udělat nějaké kódování praxi
a skutečně si hrát s těmito binárními stromy a vidět.
Chystám se přejít zpátky na mém počítači.
Pro tuto část sekce, namísto použití CS50 Spustit nebo CS50 prostory,
Budu používat spotřebič.
>> Po společně se specifikací problému Set,
Vidím, že mám otevřít spotřebič,
jít do mého složky Dropbox, vytvořte složku s názvem § 7,
a pak vytvořit soubor s názvem binary_tree.c.
Jdeme na to. Mám spotřebič již otevřen.
Jdu vytáhnout terminál.
Chystám se jít do složky Dropbox, aby se adresář s názvem section7,
a vidět, že je to úplně prázdný.
Teď jdu otevřít binary_tree.c.
Dobře. Jdeme - prázdný soubor.
>> Vraťme se specifikací.
Specifikace žádá, aby vytvořit novou definici typu
pro binární uzel stromu obsahuje int hodnoty -
stejně jako hodnoty, které jsme vypracovali v naší diagramů před.
Budeme používat tento standardní text typedef, že jsme udělali tady
že byste měli poznat z problémových Set 5 -
pokud jste hash tabulky způsob dobývání pravopisu programu.
Měli byste také uznat z minulého týdne oddílu
kde jsme o tom mluvili v souvislosti seznamech.
Máme to typedef struct z uzlu,
a my jsme stejně Tato struktura uzlu tento název struct uzel si předem
takže pak můžeme odkazovat se na to, protože budeme chtít mít ukazatele struct uzel
jako součást naší struct, ale my jsme pak obklíčen to -
nebo spíše, uzavřený toto - v typedef
tak, že později v kódu, lze odkázat na tento struct jen jako uzel namísto struct uzel.
>> To bude velmi podobný singly propojené definice seznamu, které jsme viděli minulý týden.
Chcete-li to provést, pojďme začít psát se na standardizovaný.
Víme, že musíme mít celočíselnou hodnotu,
tak dáme do int hodnoty, a pak místo toho, aby jen jeden ukazatel na další prvek -
jako jsme to udělali s singly vázaných seznamů -
budeme mít levé a pravé podřízené ukazatele.
To je docela jednoduchá také - struct node * levá dítě;
a struct uzel * P dítě;. Cool.
To vypadá jako docela dobrý začátek.
Vraťme se specifikací.
>> Nyní musíme deklarovat globální proměnné uzlu * pro kořen stromu.
Budeme dělat to globální, stejně jako jsme udělali první ukazatel v našem propojeném seznamu i globální.
To bylo tak, že ve funkcích, které jsme napsat
nemáme držet procházení kolem tohoto kořene -
když budeme vidět, že pokud si chcete napsat tyto funkce rekurzivně,
to by mohlo být lepší ani projít kolem jako globální na prvním místě
a místo toho inicializovat ji lokálně ve vašem hlavním funkce.
Ale uděláme to globálně začít.
Opět, dáme pár míst, a budu deklarovat uzlu * kořen.
Jen aby se ujistil, že nemám nechat tento inicializována, budu ji nastavit rovná null.
Nyní, v hlavní funkci - což budeme psát opravdu rychle přímo zde -
int main (int argc, char * argv []) -
a já začnu prohlášením své argv pole jako const jen proto, že vím,
že tyto argumenty jsou argumenty, které jsem asi nechtějí měnit.
Pokud chci změnit jsem jim měla být pravděpodobně dělat jejich kopie.
Uvidíte to hodně v kódu.
To je v pořádku tak jako tak. Je to v pořádku nechat to jako - vynechat const, pokud chcete.
I typicky dát do jen proto, že jsem si připomínám
že jsem asi nechci měnit tyto argumenty.
>> Jako vždy, budu zahrnout tento návratový 0 řádek na konci hlavní.
Zde budu inicializovat svůj kořenový uzel.
Jak to stojí teď, mám ukazatel, který je nastaven na hodnotu null,
tak to ukazuje na nic.
Aby se skutečně začít stavět uzel,
Poprvé jsem třeba alokovat paměť pro něj.
Já budu dělat, že tím, že paměť na haldě pomocí malloc.
Jdu nastavit kořen rovnající se výsledku malloc,
a budu používat sizeof operátor vypočítat velikost uzlu.
Důvod, proč jsem použít sizeof uzel na rozdíl od, řekněme,
něco takového - malloc (4 + 4 +4) nebo malloc 12 -
Je tomu tak proto chci, aby můj kód, aby bylo kompatibilní, jak je to možné.
Chci být schopen učinit takové. C soubor, zkompilovat na zařízení,
a pak zkompilovat na mém 64-bit Mac -
nebo na zcela jinou architekturu -
a chci to všechno fungovat stejně.
>> Pokud dělám předpoklady o velikosti proměnných -
velikost int nebo velikost ukazatel -
pak jsem také dělat předpoklady o druhy architektur
na které můj kód lze úspěšně zkompilovat při spuštění.
Vždy používejte sizeof na rozdíl od ručně součet struct pole.
Dalším důvodem je to, že může být také padding, že kompilátor dává do struct.
I jen součet jednotlivých polí není něco, co obvykle chtějí udělat,
tak, odstraňte tento řádek.
Teď, opravdu inicializovat kořenový uzel,
Budu muset připojit hodnot pro každou z jeho různých oborů.
Například pro hodnotu vím chci inicializovat až 7,
a teď jdu nastavit doleva dítě budou mít hodnotu null
a právo dítě také být nula. Výborně!
Udělali jsme, že část spec.
>> Specifikace se v dolní části stránky 3 se mě ptá, chcete-li vytvořit další tři uzly -
z nichž jedna obsahuje 3, jeden obsahující 6, a jeden s 9 -
a pak propojte je tak, že vypadá přesně jako náš stromovém diagramu
že jsme mluvili o minulosti.
Udělejme to docela rychle sem.
Uvidíte opravdu rychle, že jsem začnu psát spoustu duplicitních kódu.
Jdu vytvořit uzlu * a budu to nazývat tři.
Jdu nastavit to stejné malloc (sizeof (uzel)).
Jdu nastavit tři-> hodnota = 3.
Tři -> left_child = NULL; tři -> P _child = NULL; stejně.
To vypadá dost podobně jako inicializaci kořen, a to je přesně to, co
Budu muset dělat, když začnu inicializaci 6 a 9 stejně.
Udělám to opravdu rychle sem - vlastně, já budu dělat trochu kopírovat a vložit,
a ujistěte se, že jsem - v pořádku.
Teď jsem dostal to kopírovat a můžu jít dál a nastavit rovná 6.
Můžete vidět, že to trvá chvíli a není super-efektivní.
V jen trochu, budeme napsat funkci, která bude dělat to pro nás.
Chci nahradit to s 9, nahradit to s 6.
>> Nyní máme všechny naše uzlů vytvořena a inicializována.
Máme naše kořen položí rovny 7, nebo obsahující hodnotu 7,
náš uzel obsahující 3, naše uzel obsahující 6, a naše uzel obsahující 9.
V tomto bodě, vše, co musíte udělat, je drát vše až.
Důvod, proč jsem inicializaci všech ukazatelů na hodnotu null, je jen proto, že jsem se ujistěte, že
Nemám žádné neinicializovaná ukazatele v tu náhodou.
A také, protože v tomto bodě, jsem jen skutečně připojit uzly navzájem -
těm, že oni jsou vlastně spojené s - nemám projít a udělat
zda jsou všechny nuly jsou tam na příslušných místech.
>> Od kořene, já vím, že kořen levá dítě 3.
Já vím, že kořen právo dítě je 9.
Poté, pouze jiné dítě, které jsem nechal na starosti
je 3 právo dítě, které je 6.
V tomto okamžiku, to vše vypadá docela dobře.
Budeme odstranit některé z těchto linek.
Nyní vše vypadá docela dobře.
Vraťme se k našemu specifikace a vidět to, co máme dělat dál.
>> V tomto bodě, musíme psát volaná funkce "obsahuje"
s prototypem "bool obsahuje (int value)".
A tato obsahuje funkce bude vracet hodnotu true
jestliže strom poukázal na naší celosvětové kořenové proměnné
obsahuje hodnotu předán do funkce a false jinak.
Pojďme dál a dělat, že.
To bude přesně jako při vyhledávání, že jsme se po ruce na iPad jen trochu před.
Pojďme přibližování se trochu a stiskněte navigační tlačítko nahoru.
Budeme dát tuto funkci přímo nad naší hlavní funkcí
takže nemáme dělat nějaký druh prototypování.
Takže, bool obsahuje (int value).
Tam jdeme. Tady je náš standardní text prohlášení.
Jen aby se ujistil, že to bude sestavovat,
Chystám se jít dopředu a jen nastavit rovné vrátit false.
Právě teď tato funkce prostě nebude dělat nic a vždy hlásí, že
hodnota, která hledáme, není ve stromu.
>> V tomto bodě, je to asi dobrý nápad -
protože jsme napsali spoustu kódu a my jsme se ani nesnažili vyzkoušení - dosud
aby se ujistil, že to všechno kompiluje.
Existuje pár věcí, které musíme udělat, aby se ujistil, že to bude skutečně kompilovat.
Za prvé, zda jsme byli s použitím jakýchkoli funkcí v žádné knihovny, které jsme doposud nebyly zahrnuty.
Funkce, které jsme používali doposud, jsou malloc,
a pak jsme také používali tento typ - tento nestandardní typ zvaný "bool' -
který je součástí standardní bool záhlaví souboru.
Určitě chceme, aby zahrnovala standardní bool.h pro typu bool,
a také chceme # include standardní lib.h pro standardní knihovny
které zahrnují malloc, a bezplatné, a všechny, které.
Takže, oddálit, jedeme ukončit.
Pojďme zkusit a ujistěte se, že to ve skutečnosti dělal kompilace.
Vidíme, že to dělá, tak jsme na správné cestě.
>> Pojďme otevřít binary_tree.c znovu.
Shrnuje. Pojďme dolů a ujistěte se, že vložíme několik hovorů do našeho obsahuje funkce -
jen aby se ujistil, že je všechno v pořádku.
Například, když jsme dělali nějaké vyhledávání v našem stromu dříve,
jsme se snažili podívat do hodnoty 6, 10, a 1, a věděli jsme, že 6 je na stromě,
10 není ve stromu, a 1 nebyl ve stromu buď.
Pojďme použít tyto ukázkové volání jako způsob, jak zjistit, zda nebo ne
naše obsahuje funkce pracuje.
Aby k tomu, že, budu používat printf funkce,
a budeme vytisknout výsledek volání obsahuje.
Jdu dát v řetězci "obsahuje (% d) = protože
budeme typem hodnoty, které budeme hledat,
a =% s \ n ", a použít jej jako náš formátovacím řetězci.
Jsme jen tak vidět - doslova vytisknout na obrazovce -
co vypadá jako volání funkce.
To není vlastně volání funkce.
To je jen řetězec navržen tak, aby vypadal jako volání funkce.
>> Nyní, budeme připojit hodnot.
Budeme se snažit obsahuje na 6,
a pak to, co budeme dělat, je zde použít tento trojice operátor.
Pojďme se podívat - obsahuje 6 - tak, teď jsem obsahoval 6, a pokud obsahuje 6 je pravda,
řetězec, který budeme posílat na% s formátu charakteru
bude řetězec "true".
Pojďme projděte trochu.
Jinak, chceme poslat řetězec "false", pokud obsahuje 6 vrátí False.
To je malý praštěný vyhlížející, ale podle mě bych mohl také ilustrují
co ternární operátor vypadá, protože jsme ho ještě neviděli na chvíli.
To bude pěkný, šikovný způsob, jak zjistit, jestli naše obsahuje funkce pracuje.
Jdu listovat nad vlevo,
a budu kopírovat a vložit tento řádek několikrát.
To změnilo některé z těchto hodnot kolem,
takže to bude 1, a to bude 10.
>> Na tomto místě jsme dostali pěknou obsahuje funkce.
Máme nějaké testy, a uvidíme, jestli to všechno funguje.
V tomto bodě jsme napsali některé další kód.
Čas ukončení, a ujistěte se, že vše, co ještě kompiluje.
Ukončete ven, a teď pojďme zkusit dělat binární strom znovu.
No, vypadá to, že máme chybu,
a my jsme dostali to výslovně prohlašuje knihovny funkci printf.
Vypadá to, že musíme jít a # include standardio.h.
A s tím, vše by mělo sestavit. Jsme v pohodě.
Nyní se pojďme zkusit spustit binární strom a uvidíme, co se stane.
Zde jsme,. / Binary_tree,
a vidíme, že, jak jsme očekávali -
protože jsme není implementována obsahuje ještě,
nebo spíše, že jsme jen dát na oplátku falešné -
vidíme, že je to jen vrací false pro všechny z nich,
tak to je vše pracuje z větší části velmi dobře.
>> Pojďme zpět a skutečně provádět obsahuje v tomto bodě.
Chystám se posunout dolů, přibližovat, a -
pamatujte, algoritmus, který jsme použili je, že jsme začali na kořenový uzel
a pak v každém uzlu, který setkáváme, děláme srovnání,
a na základě tohoto porovnání se buď přesunout na levou dítěte nebo pravé dítě.
To bude vypadat velmi podobně jako kód binární vyhledávání, které jsme napsali dříve v termínu.
Když začneme, víme, že chceme držet na aktuální uzel
že se díváme na, a je aktuální uzel se bude inicializován na kořenový uzel.
A teď, budeme pokračovat přes strom,
a pamatujte, že naše zastavení podmínku -
když my vlastně pracovali na příkladu ručně -
bylo, když jsme se setkali s null uzel,
ne, když jsme se dívali na null dítě,
ale když se ve skutečnosti přesunuty do uzlu ve stromu
a zjistil, že jsme na null uzlu.
Budeme opakovat, než teď není rovno null.
A co budeme dělat?
Budeme testovat, zda (teď -> hodnota == hodnota),
pak víme, že jsme skutečně našli uzel, který jsme hledali.
Tak tady se můžeme vrátit true.
Jinak, my chceme vidět, zda je hodnota nižší než hodnota.
Pokud je aktuální uzel je hodnota nižší než hodnota, kterou hledáme,
budeme pohybovat doprava.
Takže, teď = teď -> right_child, a jinak, budeme se pohybovat doleva.
cur = cur -> left_child;. Docela jednoduché.
>> Pravděpodobně jste rozpoznat smyčku, která vypadá velmi podobně, jako tato z
binární vyhledávací dříve v termínu, s výjimkou pak jsme se zabývali s nízkou, střední a vysokou.
Zde, právě jsme se podívat na současné hodnotě,
tak je to pěkný a jednoduchý.
Pojďme ujistěte se, že tento kód funguje.
Nejprve se ujistěte, že sestavuje. Vypadá to, že to dělá.
Pojďme zkuste ji spustit.
A skutečně, že vypíše vše, co jsme očekávali.
To najde 6 ve stromu, nenajde 10, protože 10 není ve stromu,
a nenajde 1 buď proto, že 1 to také není ve stromu.
Vychytávky ke stažení.
>> Dobře. Vraťme se k našemu specifikace a uvidíme, co bude dál.
Nyní se chce přidat některé další uzly do našeho stromu.
To chce přidat 5, 2, a 8, a ujistěte se, že naše obsahuje kód
stále funguje podle očekávání.
Pojďme udělat.
V tomto bodě, spíše než dělat, že nepříjemné kopírovat a vložit znovu,
pojďme napsat funkci skutečně vytvořit uzel.
Pokud bychom posunout dolů celou cestu k hlavnímu, vidíme, že jsme dělali to
velmi podobný kód znovu a znovu pokaždé, když chceme vytvořit uzel.
>> Pojďme napsat funkci, která bude skutečně stavět na uzel pro nás a vrátit jej.
Jdu volat to build_node.
Chystám se stavět uzel s konkrétní hodnotu.
Přibližte zde.
První věc, kterou budu dělat, je skutečně vytvořit prostor pro uzel na haldy.
Takže, uzel * n = malloc (sizeof (node)), n -> hodnota = hodnota;
a pak je tu, Já jsem prostě jít k inicializaci všech oblastech se příslušné hodnoty.
A na samém konci, vrátíme naše uzel.
Dobře. Jedna věc k poznámce je, že tuto funkci přímo zde
bude vracet ukazatel do paměti, která byla haldy přidělená.
Co je hezké na tom je, že tento uzel nyní -
musíme prohlásit ho na hromadu, protože pokud jsme deklarovali ji na zásobník
bychom nebyli schopni to udělat v této funkci, jako je tato.
Že paměť by jít mimo rozsah
a bylo by neplatné, pokud jsme se snažili přistupovat k ní později.
Protože jsme se prohlašuje haldy přidělené paměti,
budeme muset postarat o uvolnění později
pro náš program není úniku nějakou vzpomínku.
Byli jsme plavit se na to pro všechno ostatní v kódu
Jen pro jednoduchost v té době,
ale pokud jste někdy napsat funkci, která vypadá takto
kde máš - někteří říkají, že malloc nebo realloc uvnitř -
Chcete, aby se ujistil, že jste dal nějaký komentář sem, že říká,
hej, víš, vrátí haldy přidělených uzel inicializován s předaný v hodnotě.
A pak chcete, aby se ujistil, že jste vložili do nějaké poznámky, které říká, že
volající musí uvolnit vrácené paměti.
Tak, když se někdo někdy jde a používá tuto funkci,
vědí, že všechno, co se vrátíme z této funkce
v určitém okamžiku bude muset být propuštěn.
>> Za předpokladu, že je vše v pořádku a tady dobře,
můžeme jít dolů do našeho kódu a nahradit všechny tyto řádky tady
s voláním naší funkce uzlu sestavení.
Pojďme udělat opravdu rychle.
Jedna část, která nebudeme nahradit je tato část dole
na dně, kde se ve skutečnosti drát uzly poukázat na sebe,
protože to nemůžeme udělat v naší funkci.
Ale pojďme udělat root = build_node (7); uzel * tři = build_node (3);
uzel * Šest = build_node (6); uzel * Devět = build_node (9);.
A teď, jsme také chtěli přidat uzly pro -
Uzel * pět = build_node (5); uzel * osm = build_node (8);
a co byla ta druhá uzel? Pojďme se podívat, zde. Chtěli jsme také přidat 2 -
Uzel * dvě = build_node (2);.
Dobře. V tomto bodě, víme, že jsme dostali 7, 3, 9, a 6
všechny zapojen správně, ale co 5, 8, a 2?
Aby bylo vše ve správném pořadí,
víme, že tři právo dítě je 6.
Takže, pokud budeme přidat 5,
5 také patří do pravé straně stromu, z nichž tři jsou kořenová,
tak 5 patří jako levé dítě 6.
Můžeme to udělat tím, že říká, šest -> left_child = pět;
a pak 8 patří jak levý dítě 9, tak devět -> left_child = osm;
a pak 2 je levý dítě 3, takže můžeme udělat, že sem - tebe -> left_child = dva;.
Pokud jste tak docela sledovat spolu s tím, navrhuji, abyste nakreslit to sami.
>> Dobře. Pojďme zachránit to. Pojďme ven a ujistěte se, že sestavuje,
a pak můžeme přidat v našem obsahuje volání.
Vypadá to, že všechno, co ještě kompiluje.
Pojďme a přidat v některých obsahuje volání.
Opět, budu dělat trochu kopírování a vkládání.
Nyní pojďme hledat 5, 8, a 2. Dobře.
Pojďme se ujistěte, že to všechno vypadá dobře ještě. Výborně! Uložit a ukončete.
Nyní pojďme udělat, kompilovat, a teď pojďme běžet.
Z výsledků, vypadá to, že vše funguje jen hezké a dobře.
Výborně! Takže teď máme naše obsahuje funkce psaný.
Pojďme dál a začít pracovat na tom, jak vložit uzlů do stromu
neboť, jak to děláme teď, věci nejsou moc hezká.
>> Vrátíme-li se do specifikace,
to nás žádá, abychom napsat funkci nazvanou vložení - opět vrací bool
o otázku, zda nebo ne bychom mohli skutečně vložit uzel do stromu -
a pak je hodnota vložit do stromu je specifikována jako
jediným argumentem naší vlož funkci.
Budeme vrátí true, pokud bychom mohli skutečně vložit uzlu obsahující hodnotu do stromu,
, což znamená, že se jeden, měl dostatek paměti,
a pak dva, že uzel nebyl již existují ve stromu od -
Pamatujte si, že se nebudeme mít duplicitní hodnoty ve stromu, jen aby to jednoduché.
Dobře. Zpět do kódu.
Otevřete ji. Zvětšit trochu, posuňte zobrazení dolů.
Pojďme dát vložte funkci přímo nad obsahuje.
Opět, to bude nazýván bool vložka (int value).
Dejte mu trochu více prostoru, a pak, jako výchozí,
pojďme dát na oplátku falešné na samém konci.
Nyní se na dně, pojďme do toho a namísto ručně budování uzly
v hlavním sami a zapojení je až poukázat na sobě, jako to děláme,
budeme spoléhat na naše vlož funkci k tomu, že.
Nebudeme spoléhat na našem vlož funkci postavit celý strom od nuly ještě ne,
ale budeme se zbavit těchto řádků - Dáme komentář, tyto řádky -
které budou vycházet uzly 5, 8, a 2.
A místo toho, budeme vložit volání do našeho vlož funkci
aby se ujistil, že skutečně funguje.
Jdeme na to.
>> Nyní jsme komentáři těchto řádků.
Máme jen 7, 3, 9, a 6 v našem stromu v tomto bodě.
Ujistěte se, že je to všechno funguje,
můžeme oddálit, aby naše binární strom,
spusťte jej, a my můžeme vidět, že obsahuje je nyní nám říká, že jsme úplně pravdu -
5, 8, a 2 jsou již ve stromu.
Jděte zpět do kódu,
a jak se budeme vložit?
Vzpomeňte si, co jsme dělali, když jsme byli vlastně vložení 5, 8, a 2 dříve.
Hráli jsme tuto hru Plinko, kde jsme začali u kořene,
šel stromu jeden po jeden po druhém
dokud jsme nenašli odpovídající mezeru,
a pak se zapojený v uzlu na příslušné místo.
Chystáme se udělat to samé.
To je v podstatě jako psaní kódu, který jsme použili v obsahuje funkce
najít místo, kde se uzel by měl být,
a pak jsme jen tak vložit uzel tady.
Pojďme začít dělat, že.
>> Takže máme uzel * teď = root, budeme jen tak sledovat obsahuje kód
dokud nezjistíme, že to není úplně pracovat pro nás.
Budeme procházet stromu, zatímco aktuální prvek není null,
a pokud zjistíme, že teď je hodnota rovna hodnotě, že se snažíme vložit -
no, to je jeden z případů, které jsme nemohli skutečně vložit uzel
do stromu, protože to znamená, že máme duplicitní hodnotu.
Zde jsme vlastně bude vracet false.
Nyní, jinak jestliže CUR je hodnota nižší než hodnota,
Nyní víme, že jsme se pohybovat k pravému
protože hodnota patří v pravé polovině cur stromu.
Jinak budeme pohybovat doleva.
To je v podstatě naše obsahuje funkce přímo tam.
>> V tomto bodě, jakmile jsme dokončili tento while,
náš teď ukazatel se bude ukazovat na nulu
v případě, že funkce není již vrátil.
Máme proto mít CUR na místě, kde chceme vložit nový uzel.
Co je ještě třeba udělat, je skutečně stavět nový uzel,
které můžeme udělat docela snadno.
Můžeme použít naše super-praktický sestavení uzlu funkci,
a něco, co jsme neudělali dříve -
jsme tak nějak brali za samozřejmost, ale teď budeme dělat, jen aby se ujistil -
budeme testovat, aby se ujistil, že hodnota vrácená nový uzel byl vlastně
není null, protože nechceme začít přístupu k této paměti, pokud je null.
Můžeme testovat, aby se ujistil, že nový uzel není rovno null.
Nebo místo, můžeme jen zjistit, jestli to vlastně je null,
a pokud je null, pak se můžeme jen vrátit false brzy.
>> V tomto bodě, musíme zapojit nový uzel do jeho příslušné místo ve stromu.
Podíváme-li se zpět na hlavní a kde jsme byli vlastně kabeláž hodnoty před,
vidíme, že způsob, jakým jsme to dělali, když jsme chtěli dát 3 ve stromu
byla jsme vstoupili do levé dítě kořene.
Když dáme 9 do stromu, jsme měli přístup k správné dítě kořene.
Měli mít ukazatel na mateřské aby dal nové hodnoty do stromu.
Rolování zpět vložit, že to nebude úplně fungovat zde
protože nemáme nadřazené ukazatel.
Co chceme být schopni udělat, je, v tomto bodě,
zjistit hodnotu rodiče a vidět - dobře, sakra,
pokud rodiče hodnota je nižší než aktuální hodnota,
pak mateřského právo Dítě by mělo být nový uzel;
jinak by se rodiče levá dítě bude nový uzel.
Ale nemáme tento mateřský ukazatel ještě dost.
>> S cílem získat to, jsme ve skutečnosti bude muset sledovat to, jak jsme jít přes strom
a najít vhodné místo v našem smyčce výše.
Můžeme to udělat, že přechodem zpět na začátek našeho vlož funkce
a sledování jiného proměnnou ukazatele volal rodiče.
Budeme ji nastavit rovná null zpočátku,
a pak pokaždé, když jdeme přes strom,
budeme nastavit nadřazené ukazatel tak, aby odpovídala aktuální ukazatel.
Nastavit rodiče rovnající se součas.
Tímto způsobem, pokaždé, když procházíme,
budeme k zajištění toho, současný ukazatel dostane zvýšen
mateřská ukazatel sleduje ji - jen o jeden stupeň vyšší, než je aktuální ukazatel ve stromu.
To vše vypadá velmi dobře.
>> Myslím, že jedna věc, kterou budete chtít upravit, je tento build uzlu vrací null.
S cílem získat stavět uzel skutečně úspěšně vrátit null,
budeme muset upravit tento kód,
protože tady jsme nikdy testovány, aby se ujistil, že malloc vrací platný ukazatel.
Takže, pokud (n = NULL!), Pak -
pokud malloc vrací platný ukazatel, pak budeme ji inicializovat;
jinak budeme jen vracet, a že skončí vrací hodnotu null pro nás.
Nyní vše vypadá docela dobře. Pojďme ujistěte se, že to ve skutečnosti sestavuje.
Udělejte binární strom, a oh, máme nějaké věci tu děje.
>> Máme implicitní prohlášení funkcí stavět uzel.
Opět, s těmito kompilátory, budeme začít nahoře.
Co to musí znamenat, že volám stavět uzel než jsem vlastně deklaroval to.
Vraťme se ke kódu opravdu rychle.
Přejděte dolů, a opravdu, je prohlášen za moje vložka funkce
nad uzlu sestavení funkce,
ale já se snažím používat sestavení uzlu uvnitř vložky.
Chystám se jít a kopie - a pak vložte uzlu sestavení funkční až sem na vrcholu.
Tak, doufám, že bude fungovat. Dejme to jiného jít.
Teď to všechno kompiluje. Vše je dobré.
>> Ale v tomto bodě, jsme ve skutečnosti jen naše vložte funkci.
Víme jen, že to překládá, tak pojďme dovnitř a dát nějaké hovory dovnitř
Pojďme udělat, že v naší hlavní funkce.
Zde jsme se v komentáři 5, 8 a 2,
a pak jsme neměli propojte je nahoru dolů sem.
Pojďme udělat některé hovory vložit,
a pojďme také použít stejný druh věcí, které jsme použili
když jsme se tyto printf volání, aby se ujistil, že vše se dostat správně vložena.
Jdu kopírovat a vložit,
a místo obsahuje budeme dělat vložku.
A místo 6, 10, a 1, budeme používat 5, 8, a 2.
To by snad vložit 5, 8, a 2 do stromu.
Kompilace. Vše je dobré. Teď budeme vlastně běží náš program.
>> Všechno se vrátil false.
Takže, 5, 8, a 2 nešel, a vypadá to, že obsahuje nenalezl ani.
Co se děje? Pojďme oddálit.
Prvním problémem bylo, že vložka se zdálo vrátit false,
a vypadá to, že je to proto, že jsme opustili v naší zpáteční falešné volání,
a nikdy jsme vlastně vrátil pravda.
Můžeme nastavit, aby se.
Druhým problémem je, teď, i když jsme to - uložte tento, ukončete to,
příkazem make znovu, že to zkompilovat, spusťte jej -
vidíme, že něco jiného se tady stalo.
5, 8, a 2 byly ještě nikdy nalezeny ve stromu.
Takže, co se děje?
>> Pojďme se podívat na to v kódu.
Pojďme se podívat, jestli se nám podaří to vyřešit.
Začneme s mateřskou není null.
Jsme-li nastavit aktuální ukazatel ve výši do kořenového ukazatel,
a budeme pracovat naši cestu dolů přes strom.
Pokud je aktuální uzel není null, pak víme, že se může pohybovat dolů trochu.
My jsme nastavili nadřazené ukazatel se rovná aktuální ukazatel,
zkontrolovat hodnotu - v případě, že hodnoty jsou stejné jsme se vrátili false.
Pokud jsou hodnoty méně jsme se přestěhovali doprava;
jinak, jsme se přesunuli doleva.
Pak jsme vybudovat uzel. Budu přiblížit trochu.
A tady, budeme se snažit zapojit do hodnoty za stejné.
Co se děje? Pojďme se podívat, když možná Valgrind nám může dát nápovědu.
>> Rád používám Valgrind jen proto, že Valgrind opravdu rychle běží
a řekne vám, zda existují nějaké chyby paměti.
Když jsme se spustit Valgrind na kód,
jak můžete vidět přímo here--Valgrind./binary_tree--and hit Enter.
Můžete vidět, že jsme neměli žádnou chybu paměti, takže to vypadá, že je všechno v pořádku tak daleko.
Máme nějaké úniky paměti, která známe, protože nejsme
děje se uvolnit některý z našich uzlů.
Zkusme běží GDB vidět, co se vlastně děje.
Uděláme gdb. / Binary_tree. Je zaveden až v pohodě.
Pojďme nastavit bod zlomu na vložky.
Pojďme běžet.
Vypadá to, že vlastně nikdy volal vložka.
Vypadá to, že problém byl jen, že když jsem změnil sem v hlavním -
všechny tyto printf volání z obsahuje -
Nikdy jsem vlastně změnil nich volat vložky.
Nyní pojďme to zkusit. Pojďme kompilaci.
Všechny vypadá dobře tam. Nyní se pojďme zkusit spustit to, co se stane.
Dobře! Všechno vypadá docela dobré.
>> Poslední věc myslet, je, existují nějaké ostří případy, na této vložky?
A ukázalo se, že dobře, jedna hrana případ, který je vždy zajímavé přemýšlet o tom,
je, co se stane, když váš strom je prázdná a volat tuto funkci VLOŽENÍ?
Bude to fungovat? Dobře, pojďme to zkusit.
- Binary_tree c. -
Způsob, jakým budeme tento test je, že budeme chodit do naší hlavní funkci,
a spíše než vedení těchto uzlů takhle,
jsme jen tak, aby se vyjádřil ven celou věc,
a místo toho, aby vedení až uzly vlastními silami,
můžeme skutečně prostě jít dopředu a odstraňte vše.
Budeme dělat všechno volání vložit.
Takže, pojďme udělat - místo 5, 8, a 2, budeme vložit 7, 3 a 9.
A pak budeme také chtít vložit 6 stejně.
Uložit. Ukončete. Udělejte binární strom.
To vše kompiluje.
Můžeme jen spustit tak jak je a uvidíme, co se stane,
ale je to také bude velmi důležité, aby se ujistil, že
nemáme žádné chyby paměti,
neboť to je jeden z našich okrajových případů, které jsme znát.
>> Pojďme se ujistit, že to funguje dobře pod Valgrind,
které budeme dělat, tím právě běží Valgrind. / binary_tree.
Vypadá to, že skutečně mají jednu chybu z jednoho kontextu -
máme tuto chybu.
Co se stalo?
Valgrind vlastně nám říká, kde to je.
Oddálení trochu.
Vypadá to, že se to děje v naší vlož funkci,
kde máme neplatný čtení o velikosti 4 na vložky, linka 60.
Pojďme se vrátit zpět a zjistit, co se tu děje.
Oddálení opravdu rychle.
Chci se ujistit, že to není na okraj obrazovky, takže můžeme vidět všechno.
Vytáhnout, že v trochu. Dobře.
Přejděte dolů, a problém je tady.
Co se stane, když se dostaneme dolů a naše aktuální uzel je již null,
naše mateřská uzel je null, takže pokud se podíváme se na samém vrcholu, tady -
v případě, že while nikdy provede
protože naše současná hodnota je null - náš kořen je null, takže teď je null -
pak naše mateřská nikdy nedostane nastavena na součas nebo na platnou hodnotu,
tak, bude rodič zároveň mít hodnotu null.
Musíme mít na paměti, pro kontrolu, že
v době, kdy jsme se sem dolů, a začneme přístup na hodnotu rodiče.
Takže, co se stane? No, pokud rodič je null -
if (rodič == NULL) - pak víme, že
tam nesmí být nic ve stromu.
Musíme se snažit, aby ji vložte u kořene.
My může provést tak, že pouze nastavení kořen rovnající se nový uzel.
Pak v tomto bodě, nemáme vlastně chceme jít přes tyto jiné.
Místo toho, tady, můžeme udělat buď jinde-if-else,
nebo můžeme spojit vše, co se zde v jiný,
ale tady budeme jen používat jiný, a to tímto způsobem.
Nyní, budeme testovat, aby se ujistil, že naše mateřská není null
do té doby vlastně snaží přístup k jeho pole.
To nám pomůže vyhnout se segmentation fault.
Takže, jsme přestat, oddálit, zkompilovat, spustit.
>> Žádné chyby, ale máme před sebou ještě spoustu úniky paměti
protože jsme neměli uvolnit některý z našich uzlů.
Ale, když jdeme sem a my se podívat na naši výtisk,
vidíme, že dobře, vypadá stejně jako všechny naše vložek bylo vrací hodnotu true, což je dobré.
Vložky jsou všechny pravdivé,
a pak příslušné obsahuje volání platí také.
>> Dobrá práce! Vypadá to, že jsme úspěšně zapsán vložku.
To je všechno, co máme pro tento týden Specifikace problému Set.
Jedna zábavná výzva přemýšlet o tom, jak byste vlastně jít
a bez všech uzlů v tomto stromu.
Můžeme tak učinit řadu různých způsobů,
ale nechám, že na vás experimentovat,
a jako zábavu výzvu, vyzkoušet a ujistěte se, že si můžete být jisti
že tato zpráva Valgrind Nebyly nalezeny žádné chyby a žádné úniky.
>> Hodně štěstí na tento týden Huffman kódování problému nastavení,
a uvidíme se příští týden!
[CS50.TV]