[Powered by Google Translate] [7. §] [Kevesebb Comfortable]
[Nate Hardison] [Harvard Egyetem]
[Ez a CS50.] [CS50.TV]
>> Üdvözöljük a 7. szakasz.
Hála a hurrikán Sandy,
ahelyett, hogy egy normális szakasz ezen a héten,
csináljuk ezt walk-through keresztül részén kérdésekre.
Fogok követni együtt Problem Set 6 előírásnak
és megy keresztül minden kérdésre a
A szakasz Kérdések részben.
Ha vannak olyan kérdések,
kérjük, tegye ezeket CS50 megvitatni.
>> Rendben. Menjünk az induláshoz.
Most nézem a 3. oldalon A probléma Set specifikáció.
Megyünk először kezdi beszélni bináris fák
mivel ezek sok releváns e heti problémája set -
A Huffman fa kódolást.
Az egyik legelső adatszerkezetek beszélgettünk a CS50 volt a tömbben.
Ne feledje, hogy a tömb egy sorozata elemek -
az összes azonos típusú - a tárolt jog egymás mellett a memóriában.
Ha van egy egész sor, hogy tudok felhívni ezzel a doboz-szám-egész stílus -
Tegyük fel, hogy van 5 az első mezőbe, már 7 a második,
akkor már 8, 10, és 20-ben a végső mezőben.
Ne feledje, hogy a kettő igazán jó dolog ez a tömb
az, hogy itt van ez a konstans idejű hozzáférést adott elem
a tömbben, ha tudjuk, az index.
Például, ha azt akarom, hogy megragad a harmadik elem a tömbben -
az index 2 a mi nulla alapú indexelő rendszer -
Én szó szerint csak meg kell csinálni egy egyszerű matematikai számítás
hop e pozícióját a tömb,
húzza ki a 8 tárolt ott,
és én vagyok jó menni.
>> Az egyik rossz dolog ez a tömb -, hogy beszéltünk
amikor beszéltünk kapcsolódó listák -
hogy ha szeretnék beszúrni egy elemet ebbe a tömb,
Megyek, hogy meg kell csinálni néhány változó körül.
Például ez a tömb itt
a rendezett sorrendben - rendezve növekvő sorrendben -
5, majd a 7, majd 8, akkor a 10, majd 20 és -
de ha szeretné szúrni a 9-es számú ebbe a tömb,
Megyek is váltani néhány tényező annak érdekében, hogy helyet.
Tudjuk felhívni ezt itt.
Megyek kell mozgatni az 5, a 7, majd a 8;
hozzon létre egy rés, ahol lehet, hogy a 9,
majd a 10 és a 20 is megy jobbra a 9.
Ez a fajta a fájdalom, mert a legrosszabb esetben -
amikor mi kellene beilleszteni vagy az elején vagy a végén
a tömb, attól függően, hogy mi változik -
talán a végén kelljen váltani az összes elemet
azt, hogy jelenleg tárolja a tömbben.
>> Szóval, mi volt az út körül ez?
Az út körül ez az volt, hogy menjen a linkelt lista módszer, ahol -
tárolása helyett az elemek 5, 7, 8, 10, és 20 mind egymás mellett a memóriában -
mi inkább nem is tárolja a fajta, ahol szerettünk volna tárolni őket
ezekben a linkelt listát csomópontokon vagyok rajz itt, egyfajta ad hoc.
És akkor kapcsolódik össze őket ezekkel a következő mutatók.
Én lehet egy mutató 5 és a 7,
egy mutatót a 7 és a 8,
egy mutatót a 8 és a 10,
és végül, a mutató a 10 a 20,
majd egy null mutató a 20 azt jelzi, hogy nincs semmi a bal.
A trade-off, hogy mi van itt
az, hogy most, ha azt akarjuk, hogy helyezze be a 9-es szám a mi rendezett lista
minden, amit meg kell tennie, hogy hozzon létre egy új csomópontot, 9,
kösse fel, hogy pont a megfelelő helyre,
és azután újra vezeték a 8 és mutasson le a 9.
Ez elég gyors, feltételezve, hogy pontosan tudjuk, hová akarunk szúrni a 9.
De a trade-off cserébe ez, hogy már most elvesztettük a konstans idejű hozzáférést
hogy valamely elemet a mi adatszerkezet.
Például, ha azt akarom, hogy megtalálják a negyedik elem ebben a linkelt listán,
Megyek, hogy meg kell kezdeni a legelején a lista
és a munka az én utam a számláló node-by-node amíg meg nem találom a negyedik.
>> Annak érdekében, hogy jobb hozzáférés teljesítményt nyújt, mint a láncolt lista -
hanem megtartja néhány az előnyök, hogy mi volt
szempontjából beiktatási idő a láncolt lista -
egy bináris fa lesz szüksége, hogy egy kicsit több memóriát igényel.
Különösen, ahelyett, hogy csak, amelyek egy mutatót egy bináris fa csomópont -
mint a linkelt lista node nem -
fogunk egy második mutatót a bináris fa csomópontot.
Ahelyett, hogy csak, amely egy mutató a következő elemre,
megyünk, hogy egy mutató egy balra gyermek és a jobb gyermek.
>> Hadd dolgozzon egy képet, hogy milyen, hogy néznek ki.
Ismét fogom használni ezeket a dobozokat és nyilakat.
A bináris fa csomópont kezdetben csak egy egyszerű doboz.
Ez lesz egy hely az érték,
, majd ez is megy, hogy egy helyet a bal és a jobb gyermek gyermek.
Megyek felcímkézni őket.
Fogjuk, hogy a bal oldali gyermek, aztán megyünk joga gyermeket.
Sok különböző módon ezt.
Néha a tér és kényelem,
Én tényleg döntetlen érzés csinálok itt az alsó
hová megyek, hogy az érték a tetején,
majd a jobb gyermeket a jobb alsó,
és a bal gyerek a bal alsó.
Visszatérve a top diagram,
van az érték, a legtetején,
akkor mi van a bal-gyermek mutatót, és akkor megvan a joga-gyermek mutatót.
>> A probléma Set előírásnak
beszélünk rajz egy csomópont, amelynek értéke 7,
majd egy bal-utód pointer azaz null, és a jobb-gyermek pointer, ami null.
Mi sem levelet tőkét NULL a teret
a bal és a jobb gyermek gyermek, vagy tudjuk felhívni a diagonális perjel
révén az egyes dobozok, jelezve, hogy ez null.
Fogom csinálni, hogy csak azért, mert ez az egyszerűbb.
Amit itt látsz két módon diagramkészítő egy nagyon egyszerű bináris fa csomópont
ahol van az érték 7 és null gyermek mutatók.
>> A második rész a leírás arról beszél, hogy a kapcsolt listák -
emlékszem, már csak megtartani a legelső elem a listán
meg kell emlékezni a teljes lista -
és hasonlóképpen, egy bináris fa, csak meg kell tartani az egyik mutató a fa
fenntartása érdekében ellenőrzés a teljes adatszerkezet.
Ez a speciális eleme a fa, az úgynevezett gyökér csomópont a fa.
Például, ha ez csomópont - ez csomópont tartalmazza az érték 7
null bal-és jobb-gyermek mutatók -
volt az egyetlen érték a fa,
akkor ez lenne a mi gyökér csomópont.
Ez a kezdetektől fogva a mi fa.
Láthatjuk ezt egy kicsit pontosabban, ha elkezdjük hozzá több csomópont a mi fa.
Hadd húzza fel egy új oldalt.
>> Most megyünk, hogy készítsen egy fa, amely 7-én a gyökér,
és 3 belső a bal gyermek, és 9 belső a jobb gyermek.
Ismét, ez elég egyszerű.
Van 7, rajzoljon egy csomópont a 3, a csomópont 9,
és én fogom be a bal-gyermek 7-pointer mutasson a csomópont, amely 3,
és a jobb-gyermek mutató a csomópont, amely 7, hogy a csomópont, amely 9.
Most, mivel 3 és 9 nincs gyermekek,
fogunk állítani az összes gyermekük mutatókat is null.
Itt a gyökere a fa megfelel a csomópont, amely a 7-es szám.
Láthatjuk, hogy ha minden van egy mutató, hogy a gyökér csomópont,
tudjuk majd séta a fák és a hozzáférést mind a gyermek csomópontok -
mindegyike 3 és 9.
Nem kell fenntartani mutatókat minden egyes csomópontnak a fán.
Rendben. Most megyünk újabb csomópontot ezt diagram.
Megyünk, hogy adjunk egy csomópont, amely 6,
és mi megyünk hozzá ezt a jogot gyermek csomópont, amely 3.
Ehhez fogom kitörölni, hogy null pointer a 3-as csomópont
és bekötésének fel, hogy pont a csomópont, amely 6. Rendben.
>> Ezen a ponton, menjünk át egy kicsit a terminológiát.
Elindításához, az oka, hogy ez az úgynevezett bináris fa, különösen
az, hogy két gyermeke mutatók.
Vannak más típusú fák több gyermek mutatók.
Különösen, ha nem egy "próbálja" a Problem Set 5.
Észre fogod venni, hogy ebben az próbálkozás, hogy volt 27 különböző mutatókat a különböző gyermekek -
egy-egy a 26 betű az angol ábécé,
majd a 27. az aposztróf -
igen, ez hasonló a típusú fa.
De itt, mivel a bináris, akkor csak két gyermeke mutatók.
>> Ezen kívül a gyökér csomópont, hogy mi beszéltünk,
általunk is dobott körül ezt a kifejezést "gyermek".
Mit jelent ez egy csomópont, hogy a gyermek egy másik csomópont?
Ez szó szerint azt jelenti, hogy a gyermek csomópont egy gyermek egy másik csomópont
ha a másik csomópont egyik gyermek mutatók állítva, hogy pont, hogy a csomópont.
Ahhoz, hogy ezt figyelembe konkrétabban,
ha 3 Hangsúlyozzuk, hogy az egyik a gyermek mutatók 7, akkor a 3. gyerek 7.
Ha volt, hogy kitaláljuk, mi a gyerekek közül 7 -
nos, azt látjuk, hogy van egy 7 mutató 3 és a mutató 9,
így 9 és 3 gyermekei 7.
Kilenc nincs gyerek, mert a gyerek pointers null,
és 3 csak egy gyerek, 6.
Hat szintén nem gyermekek, mert mind a mutatók olyan null, amelyet akkor döntetlen most.
>> Továbbá, mi is beszélünk a szülők egy adott csomópont,
és ez, ahogy az elvárható, a fordítottja a gyermek leírás.
Minden csomópont csak az egyik szülő - kettő helyett, mint az várható az emberekkel.
Így például, a szülő a 3 7.
A szülő a 9 is, 7, és a szülő 6-3 lehet. Nem sok hozzá.
Mi is kifejezések beszélni nagyszülők és az unokák,
és általánosságban beszélünk az ősök
és leszármazottai egy adott csomópont.
Az őse egy csomópont - vagy ősök inkább egy csomópont -
mind a csomópontok fekszenek az út a gyökértől az adott csomópont.
Például, ha nézem a 6 csomópont,
akkor az ősök lesznek mind a 3 és 7.
Az ősei 9, például - már ha nézem a csomópont 9 -
akkor az őse a 9 csupán 7.
És leszármazottaik pontosan az ellenkezője történt.
Ha azt akarom, hogy nézd meg az összes leszármazottai 7,
akkor meg kell nézni az összes csomópont alatta.
Szóval, van 3, 9 és 6 Összes leszármazottai 7.
>> Az utolsó kifejezés, hogy fogunk beszélni, ez az elképzelés, hogy egy testvér.
Testvérek - fajta követő mentén e családi feltételek -
olyan csomópontok, amelyek ugyanazon a szinten a fán.
Így, a 3. és a 9. testvérek mert ugyanazon a szinten a fán.
Mindkettő ugyanolyan szülő, 7.
A 6 nincs testvére, mert 9 nincsenek gyerekek.
És 7 nem rendelkezik testvérei, mert ez a gyökér a fa,
és van mindig csak 1 root.
A 7, hogy testvérei oda kellene egy csomópont 7 feletti.
Ehhez az kellene, hogy egy szülő 7, amely esetben 7 nem lenne a gyökér a fa.
Aztán, hogy az új 7-szülő is van, hogy egy gyerek,
és hogy a gyermek akkor lenne a testvére 7.
>> Rendben. Lépjünk tovább.
Amikor elkezdtük vitánk bináris fák,
beszélgettünk arról, hogy hogyan fogunk használni őket, hogy
szert előnyt mind tömbök és láncolt listákat.
És ahogy fogjuk csinálni, hogy van ezzel a rendelési tulajdonság.
Azt mondjuk, hogy a bináris fa elrendelte, a specifikáció szerint,
ha minden csomópont a mi fa, annak minden leszármazottja a bal oldalon -
a bal gyermek, és az összes a baloldal gyermek utódai -
tekintette kisebb értékeket, és az összes a csomópontok a jobb -
a megfelelő gyermek, és az összes a jog gyermek utódai -
tekintette csomópontok nagyobb az értéke a jelenlegi csomópont keresünk.
Csak az egyszerűség kedvéért, fogjuk feltételezni, hogy nincsenek ismétlődő csomópont a mi fa.
Például ez a fa nem fogunk foglalkozni az üggyel
ahol van az érték 7-gyökér
és akkor is az érték 7-mailt a fán.
Ebben az esetben, észre fogod venni, hogy ez a fa valóban rendelhető.
Megvan az érték 7-nél a gyökér.
Minden, ami a bal oldalon 7 -
ha undo az összes ilyen apró jelek itt -
minden balra a 7 - a 3 és a 6 -
ezek az értékek egyaránt kevesebb, mint 7, és minden jobbra -, amely csak ezt a 9 -
több mint 7,.
>> Ez nem az egyetlen rendelt fa tartalmazó ezeket az értékeket,
de hadd dolgozzon még egy pár közülük.
Van egy csomó módon, hogy meg tudjuk csinálni.
Megyek, hogy egy rövidített, csak hogy a dolgok egyszerű, ha -
ahelyett rajz ki az egész doboz-és-nyilak -
Én csak lesz, hogy felhívja a számot és add nyilak azokat összekötő.
Megkezdéséhez, akkor csak írj az eredeti fa újra, ahol volt 7, majd a 3,
majd 3 mutatott vissza a jogot, hogy a 6,
és 7 volt joga gyerek volt 9.
Rendben. Mi más módon, hogy mi lehetett írni ezt a fát?
Ahelyett, hogy 3 legyen a bal gyermek 7,
mi is van a 6 BE a bal gyermek 7,
, majd 3 az a bal gyermeke a 6.
Hogy fog kinézni ez a fa itt, ahol megvan 7,
majd a 6, majd 3, és egy 9 a jobb oldalon.
Azt sem kell, hogy legyen a 7 a gyökér csomópontot.
Azt is, hogy 6-a gyökér csomópontot.
Mi lenne, hogy néz ki?
Ha megyünk, hogy fenntartsák ezt a megrendelt ingatlanok,
minden balra a 6-nak, hogy kevesebb, mint az.
Csak egy lehetőség, és ez 3.
De aztán, mint a jobb gyermek 6, van két lehetőség.
Először is, mi volna a 7, majd a 9,
vagy mi lehet rajzolni - mint fogok itt csinálni -
ahol van a 9, mint a jobb gyermeke 6,
és azután az a 7. a bal gyermek a 9.
>> Most, 7 és 6 nem az egyetlen lehetséges értékeit a gyökér.
Mi is már 3 lennie a gyökér.
Mi történik, ha 3 a gyökere?
Itt, a dolgok egy kicsit érdekes.
Három nem rendelkezik, amelyek értéke kisebb, mint azt,
annak érdekében, hogy teljes bal oldala a fa csak lesz null.
Ott nem lesz semmi.
Jobbra, tudtuk sorolni a dolgokat növekvő sorrendben.
Mi is van 3, majd 6, majd 7, majd 9.
Vagy mi tehetnénk 3, majd 6, majd 9, majd 7.
Vagy mi tehetnénk 3, majd 7, majd 6, majd 9.
Vagy, 3, 7 - valójában nem, nem tehetünk a 7 többé.
Ez a mi egy dolog van.
Tehetünk 9, majd a 9 tehetünk, 6, majd 7.
Vagy, amit tehetünk, 3, majd 9, majd 7, majd 6.
>> Egy dolog, hogy felhívja a figyelmet, hogy itt
hogy ezek a fák egy kicsit fura kinézetű.
Különösen, ha megnézzük a 4 fákat a jobb oldalon -
Majd én karikázza őket, itt -
ezek a fák meg majdnem pontosan olyan, mint a láncolt lista.
Minden csomópont csak egy gyerek,
és így nem rendelkezik az ezen fa-szerű szerkezet azt látjuk, például,
ebben az egy magányos fa alatt itt a bal alsó.
Ezek a fák valóban nevezzük degenerált bináris fák,
és beszélünk ezekről látna a jövőben -
különösen akkor, ha megy, hogy más számítástechnika tanfolyamok.
Ezek a fák degenerált.
Ők nem nagyon hasznos, mert valóban, ez a szerkezet alkalmas arra,
A lookup-szer hasonló egy csatolt lista.
Azt nem értem, hogy kihasználják az extra memória - ezt az extra mutató -
mert a mi szerkezet, hogy rossz az ilyen módon.
Ahelyett, hogy megy és rajzolja ki a bináris fák, amelyek 9 a gyökér,
, mely a végleges helyzet, hogy mi volna,
vagyunk ehelyett ezen a ponton fog beszélni egy kicsit erről a másik kifejezés
hogy használjuk, ha beszélünk a fák, melynek neve a magasságot.
>> A magassága a fa a távolság a gyökér a leginkább távoli csomópont,
vagy inkább az ugrások számát, hogy meg kellett volna tenni annak érdekében, hogy
indul a gyökér, majd végül a leginkább távoli csomópont a fában.
Ha megnézzük néhány ilyen fát, hogy már készített itt,
láthatjuk, hogy ha ezt a fát a bal felső sarokban, és kezdjük a 3,
akkor meg kell, hogy 1 hop, hogy a 6, a második hop, hogy a 7,
és egy harmadik hop eljutni a 9.
Szóval, a magassága a fa 3 lehet.
Meg tudjuk csinálni ugyanezt a gyakorlatot a többi fák felvázolt ezzel a zöld,
Úgy látjuk, hogy a magassága Mindezen fák is valóban 3.
Ez része a mi teszi őket degenerált -
hogy a magasságuk kisebb, mint csak egy a csomópontok száma az egész fa.
Ha megnézzük a másik fát, ami bekerített piros, a másik viszont,
azt látjuk, hogy a legtöbb, távoli levélcsomópontjaiban vannak a 6 és a 9 -
a levelek, hogy azokat a csomópontokat, hogy nem gyerekek.
Tehát annak érdekében, hogy a gyökér csomópont, hogy vagy a 6 vagy a 9,
van, hogy egy ugrás, hogy a 7, majd egy második, hop, hogy a 9,
és a fentiekhez hasonlóan csak a második kitérő a 7, hogy a 6.
Szóval, a magassága ennek a fának ide csak 2.
Mehetsz vissza, és nem, hogy az összes többi fák, hogy korábban tárgyalt
kezdve a 7 és a 6,
, és rájössz, hogy a magassága mindezen fák is 2.
>> Az ok, mi már beszélünk sorrendben bináris fák
és miért ők hűvös van, mert akkor keresni őket
nagyon hasonló módon keres egy rendezett tömbben.
Ez az, ahol beszélni kezd, hogy a jobb keresési idő
az egyszerű láncolt lista.
A láncolt lista - ha meg akarja találni egy adott elem -
te vagy a legjobb csinálni valamilyen lineáris keresés
hol kezdődik az elején egy listát, és hop egy-by-one -
egy csomópont egy csomópont -
keresztül, a teljes listát, amíg meg nem találja, amit keresett.
Mivel, ha van egy bináris fa, ami alatt az szép formátumban,
akkor tényleg kap inkább egy bináris keresés folyik
ahol oszd meg és uralkodj
és keressük a megfelelő felét a fa minden egyes lépést.
Nézzük meg, hogy hogyan működik.
>> Ha van - megint megy vissza az eredeti fa -
kezdjük a 7, már 3, a bal oldalon, 9 a jobb oldalon,
és alatt a 3 van a 6.
Ha azt akarjuk, hogy keressük meg a 6-os szám a fán, mi lenne kezdeni a gyökér.
Mi lenne összehasonlítani az értéket keresünk, mondjuk 6,
A tárolt érték a csomópont, hogy mi jelenleg vizsgálja, 7,
találják, hogy a 6 valóban kisebb, mint 7, ezért mi lenne mozgatni balra.
Ha az érték a 6 volt nagyobb, mint 7, akkor volna inkább jobbra mozdul el.
Mivel tudjuk, hogy - mivel a szerkezetét sorrendben bináris fa -
minden érték kevesebb, mint 7 fognak tárolni a bal 7,
nincs szükség még zavarta nézegette a jobb oldalon a fa.
Amint mozgatni a bal és mi vagyunk most a csomópont, amely 3,
amit tehetünk, hogy ugyanezt az összehasonlítást megint, ahol összehasonlítjuk a 3 és a 6.
És azt látjuk, hogy míg 6 - értéke keresünk - nagyobb, mint 3,
mehetünk a jobb oldalán a csomópont, amely 3.
Nincs bal oldalán van, így tudtuk figyelmen kívül hagyta ezt.
De csak azért, mert tudjuk, hogy keresünk a fa is,
és láthatjuk, hogy a fa nem gyerekek.
>> Ez is elég könnyű, hogy felnézzen 6-ezt a fát, ha csinálunk magunk, mint az emberek,
de hadd kövesse ezt a folyamatot mechanikusan, mint egy számítógép tenne
hogy valóban megértsék az algoritmus.
Ezen a ponton vagyunk most néztem egy csomópont, amely 6,
és keresünk az érték 6,
így van, sőt, most már megtalálta a megfelelő csomópontot.
Megtaláltuk az érték 6 a mi fa, és tudjuk megállítani a keresést.
Ennél a pontnál, attól függően, hogy mi folyik itt,
azt mondhatjuk, igen, megtaláltuk az érték 6, létezik a mi fa.
Vagy, ha azt tervezed, hogy helyezzen be egy csomópont, vagy csinálsz valamit, amit tehetünk, hogy ezen a ponton.
>> Csináljuk egy pár kikeresések csak hogy lássa, hogyan is működik ez.
Nézzük meg, mi történik, ha volt, hogy megpróbálja, és keresse fel a 10 értéket.
Ha volt, hogy néz ki a 10 értéket, mi lenne kezdeni a gyökér.
Mi lenne látni, hogy 10 nagyobb, mint 7, ezért mi lenne mozgatni jobbra.
Mi lenne eljutni a 9 és hasonlítsa össze 9 a 10 és látom, hogy a 9. valóban kisebb, mint 10.
Tehát újra, mi lenne próbálja mozgatni a jobb.
De ezen a ponton, akkor azt észre, hogy vagyunk egy null csomópont.
Nincs ott semmi. Nincs semmi, ahol a 10 kell.
Ez az, ahol lehet jelenteni hiba -, hogy valóban nem 10 a fán.
És végül, menjünk át az esetben, ha próbálunk keresni 1 a fán.
Ez hasonló ahhoz, mi történik, ha megnézzük akár 10, kivéve, ahelyett, hogy a jobb oldalon,
fogunk menni balra.
Kezdjük a 7 és látom, hogy az 1-kevesebb mint 7, így haladunk balra.
Kapunk a 3 és látom, hogy az 1-3-nál kisebb, így megint megpróbálja mozgatni a bal oldalon.
Ezen a ponton van egy null csomópontot, így ismét tudunk jelenteni hiba.
>> Ha szeretne többet megtudni a bináris fák,
van egy csomó jó kis problémákat, hogy meg tudod csinálni velük.
Azt javaslom, gyakorló a rajz ki ezeket a diagramok egy-az-egy
és az azt követő végig a különböző lépések,
mert ez fog jönni szuper-praktikus
Nem csak akkor, ha csinálsz a Huffman kódolás probléma set
hanem a jövőben tanfolyamok -
csak a tanulás, hogyan kell felhívni ezeket adatstruktúrák és gondolja át a problémákat
A toll és papír, vagy ebben az esetben, iPad és a ceruzát.
>> Ezen a ponton azonban fogunk lépni, hogy néhány kódolási gyakorlat
és valóban játszani ezekkel a bináris fák és lásd.
Megyek váltson vissza a számítógéphez.
Ennek része a szakasz használata helyett CS50 Run vagy CS50 Spaces,
Fogom használni a készüléket.
>> Miután együtt Problem Set specifikáció,
Látom, hogy kéne, hogy nyissa ki a készüléket,
megy a Dropbox mappában hozzon létre egy mappát nevű 7. szakasz,
majd hozzon létre egy nevű fájlt binary_tree.c.
Itt vagyunk. Megvan a készülék már nyitva van.
Megyek húzza fel a terminál.
Fogok menni a Dropbox mappába, készíts egy könyvtárat nevű section7,
és nézd meg, hogy ez teljesen üres.
Most fogom nyitni binary_tree.c.
Rendben. Itt vagyunk - üres fájlt.
>> Menjünk vissza a specifikáció.
A specifikáció kéri, hogy hozzon létre egy új típusú definíció
Egy bináris fa csomópontot tartalmazó int értékek -
mint az értékeket, hogy mi hívta ki a diagramm előtt.
Fogjuk használni ezt a boilerplate typedef hogy tettünk itt
hogy el kell ismernie honnan Problem Set 5 -
ha nem a hash tábla módja hódító a helyesírás program.
Azt is elismerik, hogy a múlt heti részben
ahol beszélgettünk kapcsolódó listákat.
Van ez a typedef struct csomópont,
és az általunk megadott e struct csomópont ez a név a struct csomópont előzetes
azért, hogy aztán hivatkozni rá, mivel mi szeretnénk, hogy struct csomópontra mutató
mint a mi struct, de még akkor körülvéve ezt -
vagy inkább zárva ez - egy typedef
úgy, hogy később a kódot, akkor olvassa el ezt a struktúra, mint csak egy csomópont helyett struct csomópont.
>> Ez lesz nagyon hasonló az egyszeres láncolt lista definíció, hogy azt a múlt héten.
Ehhez nézzük csak elkezd írásban ki boilerplate.
Tudjuk, hogy van, hogy van egy egész értéket,
úgyhogy életbe int értéket, majd ahelyett, hogy csak egy mutató a következő elem -
ahogy azt tette egyszeresen kötött listák -
megyünk, hogy a bal és a jobb gyermek mutatók.
Ez elég egyszerű is - struct node * balra gyermek;
és struct node * jobb gyermek;. Cool.
Úgy néz ki, mint egy nagyon jó kezdet.
Menjünk vissza a specifikáció.
>> Most arra van szükség, hogy állapítsa meg a globális node * változót a gyökér egy fa.
Fogjuk, hogy ez a globális, mint tettünk 1. mutató a mi láncolt lista is globális.
Ez volt annak érdekében, hogy a funkciók írunk
nem kell tartanunk tompított körül ez gyökér -
azonban látni fogjuk, hogy ha nem akarsz írni ezeket a funkciókat rekurzív
lehet, hogy jobb, ha nem is adja át a körbe, mint globális az első helyen
és helyette inicializálni azt helyileg a fő funkciója.
De megcsináljuk globálisan kezdeni.
Ismét adok pár terek, és megyek nyilvánítja egy csomópontot * gyökér.
Csak, hogy győződjön meg arról, hogy nem hagyja a inicializált, megyek beállítani egyenlő null.
Most, a fő funkciója - amit írok nagyon gyorsan itt -
int main (int argc, const char * argv []) -
és én fogom kezdeni nyilvánító én argv tömb const csak azért, hogy tudom
hogy ezek az érvek szólnak érvek, hogy én valószínűleg nem szeretné módosítani.
Ha azt szeretnénk, hogy módosítsa azokat kéne valószínűleg másolás őket.
Majd meglátod, ez sokat kódot.
Ez rendben mindkét irányban. Ez rendben van, hogy hagyja azt - kihagyja a const, ha szeretné.
Én általában tedd csak azért, hogy emlékeztessem magam
hogy én valószínűleg nem szeretné módosítani ezeket az érveket.
>> Mint mindig, fogom fel ezt a return 0 sort a végén fő.
Itt fogom inicializálja a gyökér csomópontot.
A jelenlegi helyzet most, van egy mutató, ami null,
így ez mutatott semmit.
Annak érdekében, hogy valóban kezdjék építeni a csomópont,
Először meg kell memóriát kiosztani rá.
Fogom csinálni, hogy azáltal, hogy memóriát a heap malloc használatával.
Megyek be gyökér azonos eredménye malloc,
és én fogom használni a sizeof operátor kiszámításához méretű csomópont.
Ennek az az oka, hogy tudom használni sizeof node szemben, mondjuk,
csinál valamit, mint ez - malloc (4 + 4 +4), vagy malloc 12 -
azért van, mert azt akarom, hogy kódot is összeegyeztethető legyen.
Azt akarom, hogy képes legyen ezt. C fájlt, fordítsd le a készülékre,
majd fordítsd le az én 64-bites Mac -
vagy egy teljesen más architektúra -
és azt akarom, hogy ez mind a munka ugyanaz.
>> Ha csinálok feltételezéseket mérete változó -
méretének int vagy mérete alapján a mutató -
akkor én is, hogy feltételezéseket a fajta architektúrák
, amely a kód sikeresen fordítani, ha fut.
Mindig használjon sizeof szemben kézzel összeadásával struct mezőket.
A másik ok az, hogy nem is lehet padding, hogy a fordító hozza a struct.
Még csak összeadásával egyes mezők nem olyan dolog, amit általában szeretne tenni,
igen, törölje azt a vonalat.
Most, hogy igazán inicializálni ezt a gyökér csomópont,
Megyek is, hogy csatlakoztassa az értékeket minden egyes különböző területeken.
Például érték tudom akarok inicializálni 7,
és most megyek be a bal gyermeket, hogy null
és a megfelelő gyermek is null. Nagyszerű!
Azt csináltam, hogy része a spec.
>> A specifikáció le alján 3 oldalon megkérdezi, hogy hozzon létre három csomópont -
1, 3, 1, amely 6, és egy 9 -
majd bekötni őket, így úgy néz ki, pontosan olyan, mint a fa diagram
hogy beszéltünk korábban.
Csináljuk, hogy elég gyorsan ide.
Látni fogod, nagyon gyorsan, hogy én fogok kezdeni írni egy csomó kettős kódot.
Megyek, hogy hozzon létre egy csomópont * és fogom hívni három.
Fogom állítani egyenlő malloc (sizeof (node)).
Megyek be három-> value = 3.
Három -> left_child = NULL; 3 -> jobb _child = NULL; is.
Úgy néz ki, nagyon hasonlít inicializálása a gyökér, és pontosan ez az, amit
Megyek, hogy meg kell csinálni, ha elkezdek inicializálása 6 és 9 is.
Én megteszem, hogy nagyon gyorsan itt - valójában fogok csinálni egy kis másolás és beillesztés,
és győződjön meg arról, hogy az I - rendben van.
Nos, megvan másolt és tudok menni előre, és állítsa legfeljebb 6.
Láthatjuk, hogy ez eltart egy ideig, és nem szuper-hatékony.
A csak egy kicsit, akkor írjon egy függvényt, amely ezt nekünk.
Azt akarom, hogy váltsa fel e egy 9, cserélje ki, hogy a 6.
>> Most már megvan minden kedves csomópont létrehozása és inicializálni.
Megvan a gyökér egyezni a 7, vagy amely az érték 7,
mi csomópont tartalma 3, a mi csomópont, amely 6, és a mi csomópont, amely 9.
Ezen a ponton minden, amit meg kell tennie, hogy vezetékes mindent.
Azért inicializálja az összes mutató null is csak azért, hogy én arról, hogy
Nekem nincs semmilyen inicializálatlan pointerek ott véletlenül.
És azt is, mivel ezen a ponton, azt csak a ténylegesen csatlakoztassa a csomópontok egymáshoz -
az is, hogy ők valóban kapcsolódik - Nem tudom, hogy menjen át, és
arról, hogy az összes null ott vannak a megfelelő helyeken.
>> Kezdve a gyökér, tudom, hogy a gyökér bal gyermek 3.
Tudom, hogy a root jogot gyermek 9.
Ezt követően, az egyetlen gyerek, hogy hagytam aggódni
a 3-as helyes gyermeke, amely 6.
Ezen a ponton, minden jól néz ki.
Majd törölje néhány ilyen sorokat.
Most minden jól néz ki.
Menjünk vissza a specifikáció, és mi van a következő teendő.
>> Ezen a ponton meg kell írni egy függvényt úgynevezett "tartalmaz"
egy prototípusa "bool tartalmaz (int érték)."
És ez tartalmaz funkciót fog visszatérni true
ha a fa által mutatott globális gyökér változót
értéket tartalmazó átment a funkciót és hamis egyébként.
Menjünk előre, és csinálni.
Ez lesz pontosan olyan, mint a kereső, hogy mi volt kézzel az iPad csak egy kicsit ezelőtt.
Nézzük zoom vissza egy kicsit, és felfelé.
Megyünk, hogy ezt a funkciót jobbra fent a fő funkciója
azért, hogy ne kelljen tennie bármilyen prototípus.
Szóval, bool tartalmaz (int érték).
Ott vagyunk. Itt a mi boilerplate nyilatkozatot.
Csak, hogy győződjön meg arról, hogy ez fog készíteni,
Én megyek előre, és csak állítsa egyenlő return false.
Most ez a funkció csak nem fog tenni semmit, és mindig számolnak be, hogy
az értéket, amelyet keresünk, nem a fán.
>> Ezen a ponton, akkor valószínűleg egy jó ötlet -
hiszen írtam egy csomó kódot, és még nem is próbáltam tesztelés még -
, hogy győződjön meg arról, hogy minden össze.
Van egy pár dolog, amit meg kell tennie, hogy győződjön meg arról, hogy ez valóban fordítani.
Először is, hátha mi már bármilyen funkciót olyan könyvtárakat, amelyek még nem tartalmazza.
A funkciók általunk használt eddig malloc,
és akkor már is használja ezt a típust - ez a szabványos típusú úgynevezett "bool' -
amely szerepel a szabványos bool header file.
Azt mindenképpen szeretnénk tartalmazzák a standard bool.h a bool típusú,
és mi is szeretnénk, hogy # include szabvány lib.h a szabványos könyvtárak
amelyek magukban foglalják malloc és ingyenes, és minden adott.
Szóval, kicsinyítés, fogunk lépni.
Próbáljuk meg és győződjön meg arról, hogy ez valóban tette fordítás.
Látjuk, hogy ez így van, így vagyunk a helyes úton.
>> Nyissuk ki binary_tree.c újra.
Azt állítja össze. Menjünk le, és győződjön meg arról, hogy mi be néhány hívást a mi Tartalom funkció -
csak azért, hogy győződjön meg arról, hogy ez mind szép és jó.
Például, amikor csináltunk néhány lekérdezések a mi korábbi fa,
megpróbáltuk felnéz az értékek 6, 10, és 1, és tudtuk, hogy 6 volt a fa,
10 nem volt a fa, és 1 nem volt a fa sem.
Nézzünk a mintát kéri, mert így, hogy kitaláljuk-e vagy sem
mi Tartalom funkció működik.
Annak érdekében, hogy ezt, hogy fogom használni a printf függvény,
és megyünk, hogy nyomtassa ki az eredményt a hívás tartalmaz.
Megyek, hogy hozzanak egy string "tartalmaz (% d) = mert
fogunk csatlakoztassa az értéket fogunk keresni,
és =% s \ n ", és használni, hogy a mi format string.
Mi csak fog látni - szó szerint nyomtassa ki a képernyőn -
ami úgy néz ki, mint egy függvényhívás.
Ez valójában nem a függvényhívást.
Ez csak egy string tervezték, hogy néz ki, mint egy függvényhívás.
>> Nos, megyünk, hogy csatlakoztassa az értékeket.
Fogunk próbálni tartalmaz 6-án,
és akkor mit fogunk csinálni itt használni, hogy háromkomponensű üzemeltető.
Lássuk - tartalmazza a 6 - igen, most már tartalmazott 6 és ha tartalmaz 6 igaz,
a húr, hogy fogunk küldeni a% s formátum karakter
lesz a húr "igazi".
Nézzük lépjünk át egy kicsit.
Egyébként, szeretnénk küldeni a string "hamis", ha tartalmaz 6 visszatér hamis.
Ez egy kicsit ostoba kinézetű, de rájöttem én is, valamint bemutatják
mi a háromkomponensű üzemeltető néz ki, mivel nem láttuk, hogy egy darabig.
Ez lesz egy szép, praktikus módja annak, hogy kitaláljuk, ha a Tartalom funkció működik.
Megyek lépjen vissza a baloldalt,
és én fogom másolni és beilleszteni ezt a sort egy párszor.
Ez megváltoztatott néhány ezen értékek körül,
így ez lesz 1, és ez lesz a 10-ig.
>> Ezen a ponton van egy szép Tartalom funkciót.
Van néhány vizsgálatot, és majd meglátjuk, ha ez az egész működik.
Ezen a ponton már írt néhány kódot.
Ideje, hogy kilép, és győződjön meg arról, hogy minden még össze.
Lépjen ki, és most próbáljuk, hogy bináris fa újra.
Nos, úgy néz ki, megvan egy hiba,
és megvan ez kifejezetten kimondja a printf könyvtári függvény.
Úgy néz ki, meg kell menni, és # include standardio.h.
És arra, hogy mindent meg kell fordítani. Mindannyian jó.
Most próbáljuk futó bináris fa, és meglátjuk, mi történik.
Itt vagyunk,. / Binary_tree,
és látjuk, hogy amint vártuk -
mert nem hajtották végre tartalmaz még,
vagy inkább, már most bevezetett return false -
azt látjuk, hogy ez csak visszatér hamis mindet,
annak érdekében, hogy ez minden dolgozó a legtöbb elég jól.
>> Menjünk vissza, és ténylegesen végrehajtja tartalmaz, ezen a ponton.
Megyek lapozzunk lefelé, nagyítás, és -
ne feledd, az algoritmus, hogy mi használt volt, hogy indult a gyökér csomópont
majd minden csomópont találkozunk, mi az összehasonlítás,
és ennek alapján összehasonlítva mi vagy mozgassa balra gyermek vagy jobbra gyermek.
Ez fog nézni nagyon hasonló a bináris keresés kódot írtuk korábban a távon.
Amikor elindul, tudjuk, hogy szeretnénk megtartani a jelenlegi csomópont
hogy keresünk, és a jelenlegi csomópont lesz inicializálni a gyökér csomópontot.
És most, mi lesz, hogy megy át a fa,
és ne feledje, hogy a megállási feltétel -
amikor ténylegesen ledolgozott példáján keresztül kézzel -
volt, amikor találkoztunk a null csomópont,
nem akkor, amikor megnéztük a null gyermek,
hanem amikor ténylegesen költözött csomópont a fában
és megállapította, hogy vagyunk egy null csomópont.
Elmegyünk navigálhat amíg akt nem egyenlő null.
És mit fogunk csinálni?
Fogunk tesztelni if ​​(akt -> érték == érték),
akkor tudjuk, hogy már valóban találtak a csomópont, amit keresünk.
Tehát itt, mi is vissza igaz.
Egyébként, szeretnénk-e, vagy sem az érték kisebb, mint az érték.
Ha az aktuális csomópont értéke kisebb, mint az érték keresünk,
fogunk mozgatni jobbra.
Szóval, akt = akt -> right_child, és különben fogunk mozgatni balra.
akt = akt -> left_child,. Elég egyszerű.
>> Akkor valószínűleg ismeri a hurok, hogy nagyon hasonlít az e-től
bináris keresés korábban ezt a kifejezést, csak akkor van dolgunk, alacsony, közepes és magas.
Itt már csak egy pillantást vetni a folyó értéken,
így szép és egyszerű.
Hadd győződjön meg róla, ez a kód működik.
Először is, győződjön meg róla, hogy lefordul. Úgy néz ki, igen.
Próbáljuk fut.
És valóban, ez kiírja mindent, hogy mi várható.
Megállapítja, 6 a fa, nem talál 10 mert 10 nem a fán,
és nem talál 1 vagy azért, mert 1-es szintén nem a fán.
Cool stuff.
>> Rendben. Menjünk vissza a specifikáció, és mi a következő lépés.
Most azt akarja, hogy adjunk néhány csomópont a mi fa.
Azt akarja, hogy adjunk 5, 2 és 8, és győződjön meg róla, hogy a kódot tartalmaz
még mindig működik, mint várták.
Menjünk erre.
Ezen a ponton, és nem csinál, hogy zavaró másolás és beillesztés újra,
írjunk egy függvényt, hogy ténylegesen létre egy csomópont.
Ha lapozzunk lefelé egészen a legfontosabb, azt látjuk, hogy mi már ezt
nagyon hasonló kód újra és újra, minden alkalommal, hogy szeretnénk létrehozni egy csomópont.
>> Nézzünk levelet, hogy a funkció valóban épít egy csomópont a számunkra, és küldje vissza.
Fogom hívni build_node.
Megyek, hogy építsenek egy csomópont egy adott értéket.
Nagyítás itt.
Az első dolog, fogok csinálni valójában teret a csomópont a kupac.
Szóval, node * n = malloc (sizeof (node)), n -> value = érték;
és akkor itt, én csak úgy inicializálja az összes mezőt, hogy megfelelő értékeket.
És a legvégén, akkor vissza a csomópontot.
Rendben. Egy dolog megjegyezni, hogy ezt a funkciót itt
megy vissza a mutató a memóriában, hogy már halom különítettek el.
Mi a szép ebben, hogy ez a csomópont most -
van, hogy állapítsa meg azt a halom, mert ha nyilvánította a verem
nem lennénk képesek csinálni ezt a funkciót, mint ez.
Ez a memória menne ki a hatálya alól
, és érvénytelen, ha megpróbáltuk elérni, hogy később.
Mivel mi nyilvánításáról halom memóriát,
fogjuk, hogy vigyázzon a felszabadítása később
a mi program nem szivároghat semmilyen memóriát.
Már ladikozás, hogy minden mást a kódot
Csak az egyszerűség kedvéért abban az időben,
de ha valaha is írni egy függvényt, amely a következőképpen néz ki
hol van - néhányan a malloc vagy realloc belül -
azt szeretnénk, hogy győződjön meg arról, hogy teszel valami megjegyzést ide, hogy azt mondja,
hé, tudod, vissza halom kiosztott csomópont inicializálja a recirkulált-értéke.
És akkor azt szeretnénk, hogy győződjön meg arról, hogy teszel valami megjegyzést, hogy azt mondja
a hívó kell szabadítanunk a visszaadott memóriát.
Így, ha valaki valaha is megy, és használja ezt a funkciót,
tudják, hogy bármit is kap vissza ezt a funkciót
egy bizonyos ponton meg kell szabadítani.
>> Feltételezve, hogy minden rendben van, és jó itt,
mehetünk le a kódot, és cserélje ki az összes ezeket a sorokat itt
A hívásokat a mi épít node funkciót.
Csináljuk azt nagyon gyorsan.
Az egyik része, hogy nem fogunk cserélni ez a rész itt lent
alján, ahol tulajdonképpen bekötésének fel a csomópontokat, hogy mutasson az egyes más,
mert nem tehetünk a mi funkciót.
De csináljuk root = build_node (7); node * 3 = build_node (3);
node * 6 = build_node (6); node * 9 = build_node (9),.
És most, mi is volna hozzá csomópontok -
node * 5 = build_node (5); node * 8 = build_node (8);
és mi volt a másik csomópont? Lássuk csak. Azt akartuk, hogy még hozzá egy 2 -
node * 2 = build_node (2);.
Rendben. Ezen a ponton, tudjuk, hogy megvan a 7, a 3, a 9 és a 6
Az összes vezetékes up megfelelően, de mi a helyzet az 5, a 8 és a 2?
Annak érdekében, hogy minden a megfelelő sorrendben,
tudjuk, hogy három joga gyermek 6.
Tehát, ha megyünk hozzá az 5,
az 5 is tartozik a jobb oldalon a fa, amelyből 3 a gyökér,
így 5 közé tartozik, mint a baloldali gyermek a 6.
Ezt úgy tehetjük meg, mondván, hat -> left_child = 5;
és azután a 8 tartozik mint a bal gyermek a 9, így 9 -> left_child = 8;
majd 2 a bal gyerek 3, így nem tehetünk, hogy az ide - téged -> left_child = 2,.
Ha nem egészen kövesse végig, hogy azt javaslom, hogy dolgozzon ki magad.
>> Rendben. Nézzük mentéséhez. Menjünk ki, és győződjön meg róla, hogy lefordul,
és akkor adhat a mi Tartalom hívásokat.
Úgy tűnik, még mindig minden össze.
Menjünk, és adjunk hozzá néhány tartalmaz hívásokat.
Ismét fogok csinálni egy kis másolás és beillesztés.
Most kereséséhez az 5., 8., és 2. Rendben.
Hadd győződjön meg arról, hogy ez az egész jól néz ki még mindig. Nagyszerű! Mentés és kilépés.
Most tegyük, lefordítja, és most menjünk futni.
Az eredmény, úgy néz ki minden rendben működik, csak szép és jó.
Nagyszerű! Tehát most megvan a Tartalom funkciót írva.
Menjünk, és elkezd dolgozni, hogyan lehet beilleszteni csomópontok a fa
hiszen, ahogy mi csináljuk, hogy most, a dolgok nem nagyon csinos.
>> Ha visszamegyünk a specifikáció,
azt kéri tőlünk, hogy levelet nevezett funkció be - ismét visszatér a bool
az-e vagy sem tudnánk ténylegesen be a csomópont a fa -
majd az értéket beilleszteni a fa van megadva
az egyetlen érv, hogy a betét funkciót.
Vissza fogunk térni igaz, ha valóban be a csomópont, amely érték a fa,
ami azt jelenti, hogy az egyik volt elég memória,
, majd két, a csomópont nem létezik a fán, mivel -
emlékszem, mi nem megy, hogy ismétlődő értékeket a fa, csak hogy a dolgok egyszerű.
Rendben. Vissza a kódot.
Nyisd ki. Nagyítás egy kicsit, majd görgessen lefelé.
Tegyük a Függvény beszúrása jobbra felett tartalmaz.
Ismét, ez lesz az úgynevezett bool betét (int érték).
Adj neki egy kicsit több helyet, majd az alapértelmezett,
tegyük a return false a legvégén.
Most meg az alján, menjünk előre, és ahelyett, hogy manuálisan épület a csomópontok
a fő magunkat és vezetékek őket mutatni egymásnak, mint mi csinálunk,
mi támaszkodunk betét funkciót csinálni.
Nem fogunk támaszkodni a Függvény beszúrása építeni az egész fát a semmiből csak még,
hanem fogunk megszabadulni ezeket a sorokat - we'll megjegyzésbe az ezeken a vonalakon -
hogy épít a csomópontok az 5., 8., és 2.
És ahelyett, hogy fogjuk be a hívásokat a Függvény beszúrása
hogy győződjön meg arról, hogy tényleg működik.
Itt vagyunk.
>> Most már kommentálta ezeket a sorokat.
Már csak 7, 3, 9, és 6 a mi fa ezen a ponton.
Annak érdekében, hogy ez az egész működik,
tudjuk kicsinyíteni, hogy a bináris fa,
fut, és azt látjuk, hogy tartalmazza a most azt mondja, hogy mi vagyunk teljesen jobbra -
5., 8., és 2 már nem a fa.
Menj vissza a kódot,
és hogyan fogunk be?
Emlékszel, mit tettünk, amikor ténylegesen behelyezése 5, 8, 2 korábban.
Azt játszottam, hogy Plinko játék, ahol elkezdtük a gyökér,
lement a fát egyenként egy
amíg megtaláltuk a megfelelő rést,
aztán vezetékes a csomópont a megfelelő helyen.
Megyünk nem ugyanaz a dolog.
Ez alapvetően, mint az írás a kódot, hogy mi használt funkciót tartalmaz
hogy megtalálja a helyet, ahol a csomópont legyen,
és akkor még csak megy be a csomópont ott.
Kezdjük csinálja.
>> Tehát van egy node * cur = root, mi csak fogja követni a kódot tartalmaz
amíg meg nem találják, hogy nem igazán működik a számunkra.
Megyünk, hogy menjen át a fa, míg az aktuális elem nem nulla,
és ha úgy találjuk, hogy akt értéke egyenlő értéket próbálunk beszúrni -
Nos, ez az egyik olyan esetekben, amikor nem tudtuk valójában be a csomópont
a fa, mert ez azt jelenti, hogy van egy ismétlődő értéket.
Itt most tényleg megy vissza hamis.
Most, else if akt értéke kisebb, mint érték,
Most tudjuk, hogy mozog a jobb
mert az érték tartozik a jobb felén a cur fa.
Máskülönben fogunk mozgatni balra.
Ez alapvetően a mi Tartalom működik ott.
>> Ezen a ponton, ha egyszer már végrehajtotta ezt a while ciklus,
mi cur mutató lesz mutatva null
ha a funkció még nem tért vissza.
Mi tehát, amelynek akt azon a helyen, ahol szeretné szúrni az új csomópontot.
Mit kell még tenni, hogy ténylegesen építeni az új csomópont,
amit tehetünk nagyon könnyen.
Tudjuk használni a szuper-praktikus épít csomópont funkció,
és valami, amit nem tett meg korábban -
már csak ilyen volt a nyújtott, de most megteszem, csak hogy megbizonyosodjon arról -
fogunk tesztelni, hogy győződjön meg arról, hogy a visszaadott érték az új csomópont ténylegesen
nem nulla, mert nem akarjuk kezdeni elérése, hogy az emlékezet, ha null.
Meg lehet próbálni, hogy győződjön meg arról, hogy az új csomópont nem egyenlő null.
Vagy inkább, mi is csak látni, ha valójában null,
és ha null, akkor is csak vissza false elején.
>> Ezen a ponton meg kell bekötni az új csomópontot a megfelelő helyen a fán.
Ha visszatekintünk a főbb és hol voltunk valójában kábelezés értékek előtt,
azt látjuk, hogy az utat csinálunk, amikor akartunk tenni 3 a fán
volt, mi érhető el a bal oldali gyermek root.
Amikor put 9 a fa, mi volt elérni a jobb gyermek a gyökér.
Volt, hogy egy mutató a szülő annak érdekében, hogy egy új értéket a fa.
Görgetés vissza beszúrni, hogy ez nem fog teljesen itt dolgozni
mert nincs szülő mutató.
Mi azt akarjuk, hogy képes megtenni az, ezen a ponton,
ellenőrizze a szülő érték és látni - nos, istenem,
ha a szülő értéke kisebb, mint az aktuális érték,
akkor a szülő joga gyermeknek kell lennie az új csomópont;
ellenkező esetben a szülő bal gyermeke legyen az új csomópontot.
De nincs ez a szülő mutató elég még.
>> Annak érdekében, hogy azt, mi tényleg kell majd követni, hogy ahogy haladunk át a fát
és megtalálni a megfelelő helyet a mi hurok felett.
Meg tudjuk csinálni, hogy a görgetés vissza a csúcsra a Függvény beszúrása
és nyomon követése egy pointer változót nevezzük a szülő.
Fogjuk beállítani egyenlő null kezdetben,
majd minden alkalommal megyünk át a fa,
fogunk beállítani a szülő mutatót, hogy megfeleljen a jelenlegi mutatót.
Állítsa szülő egyenlő cur.
Így minden alkalommal, amikor megyünk keresztül,
fogunk annak biztosítására, hogy a jelenlegi mutató lesz eggyel
az anyavállalat mutató következik, hogy - csak egy szinttel magasabb, mint a jelenlegi mutatót a fán.
Ez mind jól néz ki.
>> Azt hiszem, az egy dolog, hogy mi szeretnénk beállítani ez a csomópont kiépítése visszatérnek null.
Annak érdekében, hogy építeni csomópontot ténylegesen sikeresen vissza null,
akkor kell módosítani, hogy a kódot,
mert itt, soha nem tesztelték, hogy győződjön meg arról, hogy a malloc visszaadott érvényes mutató.
Tehát, ha (n! = NULL), majd -
ha malloc vissza érvényes mutató, aztán inicializálja azt;
másként, akkor csak vissza, és hogy a végén visszatérnek null nekünk.
Most minden jól néz ki. Hadd győződjön meg róla, ez valójában össze.
Győződjön bináris fa, és jaj, mi van néhány dolog folyik itt.
>> Van egy implicit nyilatkozatot funkciót épít csomópont.
Ismét ezekkel fordítóprogramok, fogunk kezdeni a tetején.
Mi az, hogy az azt jelenti, hogy én hívom építeni csomópont előtt, amit ténylegesen bevallott azt.
Menjünk vissza a kód nagyon gyorsan.
Lapozzunk lefelé, és persze elég, a betét funkció bejelentett
felett a build csomópont funkció
de én próbálom használni építeni node belül betét.
Én megyek és másolás -, és illessze be a build függvény csomópont egészen ide a tetején.
Így remélem, hogy működni fog. Adjunk a másik megy.
Most már minden össze. Minden jó.
>> De ezen a ponton, már nem is felhívta a betét funkciót.
Mi csak tudjuk, hogy lefordul, úgyhogy menjünk, és némi kéri be
Csináljuk, hogy a fő funkciója.
Itt, megjegyzésben 5, 8, és 2,
és akkor nem kösse őket ide.
Nézzünk néhány hívást beszúrni,
és menjünk is használja ugyanazt a fajta dolog, hogy mi használt
mikor tette ezeket printf kéri, hogy győződjön meg arról, hogy minden nem kap behelyezve.
Fogom másolni és beilleszteni,
és ahelyett, hogy tartalmaz fogunk csinálni betéttel.
És a 6 helyett, 10, és 1, fogunk az 5, 8, és 2.
Ez remélhetőleg 5 betét, a 8., és 2 a fára.
Fordítsd le. Minden jó. Most akkor tulajdonképpen fut a program.
>> Mindent vissza hamis.
Szóval, 5, 8, és 2 nem ment, és úgy néz ki, mint a Tartalom nem találta őket sem.
Mi folyik itt? Menjünk kicsinyítéshez.
Az első probléma az volt, hogy úgy tűnt, lapka vissza hamis,
és úgy néz ki, hogy azért van, mert mi maradt a return false hívás
és mi soha nem tért vissza igaz.
Azt lehet állítani, hogy akár.
A második probléma, most még ha nem teszünk - mentéséhez lépjen ki ezt,
vagy futtasd a make megint, azt azonnal le, majd futtassa -
azt látjuk, hogy valami más történt itt.
Az 5, 8, és 2 még nem találták a fában.
Szóval, mi folyik itt?
>> Vessünk egy pillantást erre a kódot.
Lássuk, mi is kitaláljuk.
Kezdjük a szülő, hogy nem null.
Mi meg a jelenlegi mutató megegyezik a gyökér mutató,
és fogunk dolgozni az utat lefelé a fáról.
Ha a jelenlegi csomópont nem nulla, akkor tudjuk, hogy tudunk mozogni le egy kicsit.
Mi meg a szülő mutató megegyezik a jelenlegi mutató,
ellenőrizni az értéket - ha az értékek megegyeznek visszatértünk hamis.
Ha az értékek kevésbé költöztünk jobbra;
egyébként költöztünk a bal oldalon.
Majd építünk egy csomópont. Majd nagyítani egy kicsit.
És itt fogunk próbálni bekötésének fel az értékeket meg kell egyeznie.
Mi folyik itt? Lássuk esetleg Valgrind tud adni nekünk egy tippet.
>> Szeretem használni Valgrind csak azért, mert Valgrind nagyon gyorsan fut
és azt mondja, ha van olyan memória hiba.
Amikor fut Valgrind a kódot,
amint látod van here--Valgrind./binary_tree--and hit adja.
Látod, hogy mi nem volt memória hiba, ezért úgy néz ki, minden rendben eddig.
Van némi memóriavesztés, amiről tudjuk, mert nem vagyunk
történik, hogy szabad bármelyik csomópont.
Próbáljuk futó GDB, hogy mi folyik itt valójában.
Megteszünk gdb. / Binary_tree. Ez az indítás megtörtént csak finom.
Nézzünk be egy töréspontot a betét.
Fussunk.
Úgy néz ki, hogy valójában soha nem hívott betéttel.
Úgy néz ki, a probléma az volt csak, hogy mikor változott itt lent a fő -
Mindezen printf hívások tartalmaz -
Én soha nem változott e hívni betéttel.
Most, hogy ez a próbálkozás. Menjünk összeállításához.
Minden jól néz ki ott. Most próbáljuk fut, meglátjuk, mi történik.
Rendben! Minden, ami jól néz ki ott.
>> Az utolsó dolog, amit gondolni, vannak-e olyan esetek él ezen betét?
És kiderül, hogy, nos, az egyik szélén helyzet, hogy mindig érdekes gondolni
az, hogy mi történik, ha a fa üres és hívja ezt betét funkció?
Működni fog? Nos, adjunk neki egy esélyt.
- Binary_tree. C -
Ahogy megyünk tesztelni ezt, fogunk lemenni a fő funkciója,
és ahelyett, hogy ezek a csomópontok vezetékek ki, mint ez,
mi csak megy megjegyzésbe az egész dolog,
és ahelyett, vezetékek ki a csomópontot magunkat,
mi is valójában csak megy előre, és törölje ezt az egészet.
Megyünk, hogy minden hívást beilleszteni.
Szóval, csináljuk - ahelyett, 5, 8, 2, megyünk be 7, 3 és 9.
És akkor mi is szeretnénk beszúrni 6 is.
Mentés. Kilépés. Győződjön bináris fa.
Minden össze.
Mi is csak futni úgy, ahogy van, és meglátjuk, mi történik,
de ez is lesz nagyon fontos, hogy győződjön meg arról, hogy
nem rendelkezik memória hiba,
mivel ez az egyik él esetek tudunk.
>> Legyen biztos abban, hogy jól működik Valgrind alatt,
amit megteszek mellett csak futás Valgrind. / binary_tree.
Úgy néz ki, hogy tényleg van egy hiba az egyik kontextus -
itt van ez szegmentációs hibát.
Mi történt?
Valgrind valójában azt mondja nekünk, hogy hol van.
Kicsinyítés egy kicsit.
Úgy néz ki, ez történik a mi betét funkció,
ha van egy érvénytelen olvasási méret 4-es lapka, line 60.
Menjünk vissza, és nézd meg, hogy mi folyik itt.
Kicsinyítés nagyon gyors.
Azt szeretnénk, hogy győződjön meg arról, hogy nem megy a szélén a képernyőn, így látunk mindent.
Húzza ki, hogy egy kicsit. Rendben.
Lapozzunk lefelé, és a probléma itt.
Mi történik, ha kap le, és a jelenlegi csomópont már null,
a szülő csomópont null, tehát ha felnéz legtetején, itt -
ha ez a while ciklus ténylegesen soha nem hajt végre
mert a jelenlegi értéke null - a gyökér null annyira akt null -
akkor a szülő soha nem lesz beállítva, hogy akt vagy egy érvényes értéket,
így, szülő lesz null.
Emlékeznünk kell arra, hogy ellenőrizze, hogy a
mire jutunk ide, és kezdjük elérni a szülő értékét.
Szóval, mi történik? Nos, ha a szülő null -
if (szülő == NULL) -, akkor tudjuk, hogy
ott nem lehet semmit a fán.
Meg kell próbál helyezze azt a gyökér.
Meg tudjuk csinálni, hogy a csak a root beállítás megegyezik az új csomópont.
Aztán ezen a ponton, akkor valójában nem akar menni ezeken más dolog.
Ehelyett, itt van, amit tehetünk, vagy egy else-if-else,
vagy mi lehet kombinálni mindent itt egy más,
de itt akkor csak használ mást, és nem így.
Most fogunk tesztelni, hogy győződjön meg arról, hogy a szülő nem null
addig próbálunk hozzáférni a mezőket.
Ez segít nekünk elkerülni a szegmentációs hibát.
Szóval, kilép, kicsinyítés, fordításához, futtatásához.
>> Nem hiba, de még mindig van egy csomó memória szivárgás
mert nem szabad sem a csomópontok.
De, ha megyünk ide, és nézd meg a nyomtatás,
azt látjuk, hogy, nos, úgy tűnik, minden kedves lapkák visszatértek igaz, ami jó.
A betétek mind igaz,
majd a megfelelő Tartalom hívás is igaz.
>> Szép munka! Úgy néz ki, most már sikeresen írt betét.
Ennyi van az e heti Problem Set specifikációja.
Egy szórakoztató kihívás gondolni, hogyan ténylegesen megy
és szabad az összes csomópont ezt a fát.
Meg tudjuk csinálni, így számos különböző módon,
de elmegyek, hogy rajtad múlik, hogy kísérlet,
és mint egy szórakoztató kihívás, próbálja meg és győződjön meg róla, hogy biztos lehet benne,
hogy ez a Valgrind jelentés nem ad vissza hibát, és nem szivárog.
>> Sok szerencsét az e heti Huffman kódolás problémája készlet,
és találkozunk jövő héten!
[CS50.TV]