[Powered by Google Translate] [Oddelek 7] [manj udoben]
[Nate Hardison] [Harvard University]
[To je CS50.] [CS50.TV]
>> Dobrodošli v oddelku 7.
Zaradi orkana Sandy,
namesto da bi normalno del ta teden,
to počnemo sprehod skozi, skozi del vprašanj.
Bom lahko po skupaj z Težava Set 6 specifikacije,
in gre skozi vsa vprašanja v
Oddelek oddelka vprašanja.
Če obstajajo vprašanja,
prosim objavite to na CS50 razpravljali.
>> V redu. Pa začnimo.
Zdaj sem si na strani 3 specifikaciji Problem Set.
Bomo najprej začeli govoriti o binarnih dreves
saj so imeli veliko težav pomembna za ta teden set -
Drevo Huffman kodiranja.
Ena od prvih podatkovne strukture smo govorili o CS50 je matrika.
Ne pozabite, da je matrika zaporedje elementov -
vse iste vrste - hranijo v neposredni bližini drug drugega v spominu.
Če imam celoštevilsko matriko, ki jo lahko pripravi z uporabo te škatle-številke-celi števili slog -
Recimo, da imam 5 v prvo polje, imam 7 v drugi,
potem imam 8, 10 in 20 v zadnjem polju.
Ne pozabite, da sta res dobre stvari o tem polju
so, da imamo to konstantno času dostop do vseh posameznega elementa
v polju, če vemo, njen indeks.
Na primer, če želim, da zgrabite tretji element v matriki -
V indeksu 2 uporabo našega ničelnega indeksiranje sistem -
Dobesedno sem samo narediti preprost matematični izračun,
hop na ta položaj v matriki,
izvlecite 8, ki je shranjena,
in sem na dobri poti.
>> Ena od slabih stvari o tem polju -, da smo se pogovarjali o
ko smo razpravljali o povezanih seznamov -
je, da če želim vstaviti element v tem polju,
Jaz bom moral narediti nekaj premika naokoli.
Na primer, ta niz tukaj
v urejenih redu - razvrščene v naraščajočem vrstnem redu -
5, nato pa 7, potem 8, nato 10 in nato 20 -
ampak če želite vstaviti številko 9 v tem polju,
Jaz bom moral premakniti nekaj elementov, da bi naredili prostor.
Mi lahko izdela to tukaj.
Jaz bom moral premakniti 5, 7, nato pa 8;
ustvarjajo vrzel, kjer sem dal 9,
in potem lahko 10 in 20 pojdi na desni strani 9.
To je neke vrste bolečino, ker v najslabšem primeru -
ko smo morali vstaviti bodisi na začetku ali na koncu
na polje, odvisno od tega, kako bomo premika -
lahko bi na koncu morali preusmeriti vse elemente
da smo trenutno shranjevanje v array.
>> Torej, kakšna je bila pot okoli tega?
Pot okoli tega je bil, da gredo na našo povezanost seznam metode, kjer -
Namesto shranjevanja elementov 5, 7, 8, 10 in 20 vsi zraven drugega, v spomin -
kaj smo namesto tega pa je shranjevanje jim nekakšno kjer smo želeli, da jih shranite
V tem povezan seznam-vozlišč, ki sem črpa tukaj vrste ad hoc.
In potem smo jih med seboj povezane z uporabo teh naslednjih nasvetov.
Lahko dobim kazalec od 5 do 7,
kazalec od 7 do 8,
kazalec od 8 do 10,
in končno, kazalec od 10 do 20,
in nato null kazalec na 20 kaže, da ni nič ostalo.
Kompromis, ki ga imamo tukaj
je, da zdaj, če želimo vstaviti številko 9 na našem seznamu razvrščeni,
vse, kar moramo storiti, je ustvariti novo vozlišče z 9,
ga priključite do opozarjajo na ustrezno mesto,
in nato ponovno žica 8 s točko navzdol do 9.
To je zelo hiter, ob predpostavki, da smo točno vedeli, kam hočemo vstaviti 9.
Toda kompromis, v zameno za to, da smo danes izgubili stalno času dostop
za vsako posamezno prvino v našo strukturo podatkov.
Na primer, če želim, da bi našli četrti element v tem povezanega seznama,
Bom moral začeti na samem začetku seznama
in delo, svojo pot skozi vozlišča štetje-by-vozlišča, dokler ne najdem četrti.
>> Da bi dobili boljši dostop do zmogljivosti kot povezan seznam -
ampak tudi ohraniti nekatere prednosti, ki smo jih imeli
v zvezi z delovnim časom vstavitve iz povezanega seznama -
binarno drevo bo treba uporabiti malo več pomnilnika.
Še posebej, namesto da bi samo z eno kazalec v binarnem vozlišču drevesa -
kot povezan seznam-vozlišče ne -
bomo dodali še en kazalec na vozlišče binarno drevo.
Namesto, da samo z eno kazalec na naslednji element,
bomo imeli kazalec na levi in ​​desni otroka otroka.
>> Naj narisati sliko, da vidite, kako dejansko izgleda.
Spet bom uporabila te škatle in puščice.
Binarno drevo vozlišče bo začnete s preprostim polje.
To se dogaja, da imajo prostor za vrednost,
potem pa se tudi dogaja, da imajo prostor za levi in ​​desni otroka otroka.
Grem, da jih tukaj.
Bomo imeli levi otroka, nato pa se bomo, da imajo pravico otroka.
Obstaja veliko različnih načinov za to.
Včasih za prostor in udobje,
Jaz bom dejansko sestavi, kot delam tukaj na dnu
kam grem, da so vrednosti na vrhu,
in nato desno otrok na spodnjem desnem kotu,
in levo otrok v spodnjem levem.
Če se vrnemo na tem vrhu diagrama,
imamo vrednost na samem vrhu,
potem imamo levi kazalec otrok, in potem imamo desno otrok kazalec.
>> V opredelitvi težave Set,
govorimo o oblikovanju vozlišče, ki ima vrednost 7,
in potem levo otrok kazalec, da je nična in desno kazalec, da otrok je nična.
Postanemo lahko napišete kapitala NULL v prostoru za
tako levo otrok in pravico otrok, ali lahko pripravi to poševnico
z vsako od polj, ki označuje, da je to nič.
Jaz bom to storil samo zato, ker je to preprosto.
To, kar vidite tukaj dva načina diagramov zelo preprost vozlišče binarno drevo
kjer imamo vrednost 7 in ničelne kazalce otrok.
>> Drugi del naših pogovorov specifikacij o tem, kako s povezanimi seznamov -
Zapomnite si, da smo imeli samo, da imajo na zelo prvi element na seznamu
zapomniti celoten seznam -
in prav tako tudi z binarno drevo, imamo samo, da imajo na eni kazalec na drevo
da bi ohranili nadzor nad celotno strukturo podatkov.
Ta poseben element drevesa se imenuje vozlišče koren tega drevesa.
Na primer, če je to eno vozlišče - to vozlišče, ki vsebuje vrednost 7
s null levo in desno otrok kazalci -
so bili edina vrednost v našem drevesu
potem bi bila to naša root vozlišča.
To je zelo začetek našega drevesa.
To lahko vidimo malo bolj jasno, ko bomo začeli dodajanjem več vozlišč za naše drevo.
Naj dvigni novo stran.
>> Sedaj bomo narisali drevo, ki ima 7 v korenu,
in 3 znotraj levega otroka in 9 v notranjosti pravo otroka.
Tudi to je zelo preprosta.
Imamo 7, pripravi vozlišče za 3, vozlišča za 9,
in bom nastaviti levi kazalec otrok od 7 do točke na vozlišče, ki vsebuje 3,
in pravico otroka kazalec na vozlišče, ki vsebuje 7 do vozlišča, ki vsebuje 9.
Zdaj, ker 3 in 9 nimata otrok,
da bomo iz vseh svojih otrok napotke za nična.
Tu so korenine naše drevo ustreza vozlišča, ki vsebuje številko 7.
Vidite lahko, da če vse, kar imamo, je kazalec na koren tega vozlišča,
potem lahko sprehodite skozi naše drevo in dostop do obeh otrok vozlišč -
tako 3 in 9.
Ni potrebe, da ohrani napotke za vsako vozlišče v drevesu.
V redu. Sedaj bomo dodali še eno vozlišče, s tem načrtom.
Bomo dodali vozlišče, ki vsebuje 6,
in bomo dodali, da je to pravi otroka vozlišča, ki vsebuje 3.
Če želite to narediti, da bom izbrisati to null kazalec v 3-vozlišče
in ga priključite do točke na vozlišče, ki vsebuje 6. V redu.
>> Na tej točki, gremo v malo terminologije.
Če želite začeti, razlog, da se to imenuje binarno drevo, zlasti
je, da ima dva otroka kazalca.
Obstajajo tudi druge vrste dreves, ki imajo več kazalcev za otroke.
Še posebej si poskusil "v Set Problem 5.
Opazili boste, da v tem poskusu, ste imeli 27 različnih kazalcev za različne otroke -
1 za vsako od 26 črk angleške abecede,
in nato za 27. opuščaj -
tako, da je podoben tip drevesa.
Ampak tukaj, saj je binarno, imamo le dva otroka kazalca.
>> Poleg tega korenskega vozlišča, ki smo govorili,
smo prav tako metali okoli tega pojma "otrok".
Kaj to pomeni za eno vozlišče, da je otrok drugo vozlišče?
To dobesedno pomeni, da je otrok vozlišča je otrok drugo vozlišče
če ta drugi vozlišče ima eno od svojih otrok kazalcev iz točke v tem vozlišču.
Da bi se to v bolj konkretno,
če je 3 opozoril eden od pokazateljev 7 otrok, nato pa 3 je otrok 7.
Če bi ugotovili, kaj otroci so 7 -
No, bomo videli, da ima 7 kazalec na 3 in kazalec do 9,
Tako 9 in 3 otroci 7.
Devet nima otrok, saj so njeni otroci kazalci null,
in 3 ima samo enega otroka, 6.
Šest tudi nima otrok, saj bosta obe kazalcev, so nična, kar bomo pripraviti prav zdaj.
>> Poleg tega govorimo tudi o starših posebnem vozlišču,
in to je, kot ste pričakovali, ravno nasprotno od tega otroka opisa.
Vsako vozlišče ima samo eden od staršev - namesto dveh, kot bi lahko pričakovali pri ljudeh.
Na primer, matično 3 je 7.
Matično dne 9. je 7 in je nadrejena 6 je 3. Ni veliko za to.
Imamo tudi pogoje za pogovor o starimi starši in vnuki,
in bolj na splošno govorimo o prednikih
in potomci v posebnem vozlišču.
Prednik vozlišča - ali prednikov, temveč za vozlišča -
so vsi vozlišč, ki ležijo na poti od korena do vozlišča.
Na primer, če gledam vozlišče 6,
potem predniki se bodo tako 3 in 7.
Predniki 9, na primer, so - če gledam v vozlišču 9 -
potem je prednik 9 je samo 7.
In potomci so ravno obratno.
Če želim, da pogled na vse potomce 7,
potem moram gledati na vseh vozliščih pod njo.
Torej, imam 3, 9, 6 in vse kot potomce 7.
>> Končni rok, da se bova pogovarjala, je ta pojem pa brat.
Bratje in sestre - vrsta skupaj na podlagi teh družinskih pogoji -
so vozlišča, ki so na isti ravni v drevesu.
Torej, 3 in 9 so bratje in sestre, saj so na isti ravni v drevesu.
Oba imata enako starša, 7.
Za 6 nima bratov in sester, ker 9 nima otrok.
In 7 nima bratov in sester, saj je to koren našega drevesa,
in tam je vedno samo 1 korenina.
Za 7 bratov in sester, da bi tam moral biti vozlišče nad 7.
Tu bi morala biti roditelj 7, v tem primeru 7 ne bo več koren drevesa.
Potem bi to novo matično 7 tudi imeti otroka,
in da bo otrok potem brat od 7.
>> V redu. Gremo naprej.
Ko smo začeli razpravo o binarnih dreves,
smo se pogovarjali o tem, kako smo bili, da jih uporabljajo za
pridobiti prednost pred obema nizi in povezanih seznamov.
In kako bomo to, da je s tem odreja premoženja.
Pravimo, da se naloži dvojiško drevo, v skladu s specifikacijo,
če za vsako vozlišče v našem drevesu, v vseh njegovih potomcev na levi -
Na levi strani otrok in vsi potomci levega otroka -
imajo manj vrednosti, in vse vozlišča na desni -
pravice otrok in vsi potomci pravega otroka -
imajo vozlišča večja od vrednosti trenutnega vozlišča, ki jih gledate.
Samo za enostavnosti, bomo za domnevo, da ne obstajajo kakršne koli podvojene vozlišča v našem drevesu.
Na primer, to drevo mi ne bo ukvarjal s tem primerom
kjer imamo vrednost 7 v korenu
in potem imamo tudi vrednost 7 drugje v drevo.
V tem primeru boste opazili, da je to drevo res naročil.
Imamo vrednost 7 v korenu.
Vse levo od 7 -
če bi razveljavili vse te majhne znamk tukaj -
vse na levi 7 - 3 in 6 -
te vrednosti sta manj kot 7, in vse, kar na desno - kar je le to 9 -
večja od 7.
>> To pa ni edina naročiti drevo, ki vsebujejo te vrednote,
vendar naj pripravi nekaj več od njih.
Tam je dejansko cel kup načinov, da lahko to storijo.
Bom uporabo stenografijo samo ohraniti stvari preproste, če -
ne črpa celotna škatle-in puščice -
Grem, da pripravi številke in dodajte puščice, ki jih povezujejo.
Če želite začeti, bomo šele pisati našo prvotno drevo še enkrat, kjer smo imeli 7, nato 3,
in potem 3 opozorila nazaj na desno do 6,
in 7 je imel pravico otroka, ki je bil 9.
V redu. Kaj je še en način, da bi lahko napisal to drevo?
Namesto, da bi 3 z leve otrok 7,
Lahko bi tudi imeli 6 mora biti na levi otrok 7,
in potem 3, je levo otrok iz 6.
To bi bilo videti, kot to drevo tukaj, kjer sem dobil 7,
nato 6, nato pa 3 in 9 na desni strani.
Prav tako ne bi bilo treba imeti 7, kot je naš korenski vozel.
Lahko bi tudi 6, kot je naš korenski vozel.
Kaj bi bilo to videti?
Če bomo ohranili ta lastnost naročil,
vse na levi strani 6 mora biti manjša od nje.
Obstaja samo ena možnost, in da je 3.
Potem pa, kot pravi otrok od 6 let, imamo dve možnosti.
Prvič, lahko imamo 7 in potem 9,
ali bi jo lahko sestavi - kot, da sem na tem, da tu ne -
kjer imamo 9, kot pravi otrok od 6,
in potem 7 kot levi otroka iz 9.
>> Zdaj, 7 in 6, niso edine možne vrednosti za root.
Lahko bi tudi 3 se pri korenu.
Kaj se zgodi, če 3 je vzrok?
Tu se stvari malo zanimivo.
Tri nima vrednosti, ki so manjše od njega,
tako da celoten levi strani drevesa le, da bo nična.
Tam je ne bo nič tam.
Na desni strani smo lahko seznam stvari v naraščajočem vrstnem redu.
Lahko bi imeli 3, nato 6, nato 7, nato pa 9.
Ali lahko naredimo 3, potem 6, potem 9, potem 7.
Ali lahko naredimo 3, nato pa 7, potem 6, potem 9.
Ali, 3, 7 - pravzaprav ne, ne moremo narediti 7 več.
To je naša stvar tam.
To lahko storimo 9, nato pa od 9 lahko storimo, 6 in 7 potem.
Ali lahko naredimo 3, potem 9, potem 7, nato pa 6.
>> Ena stvar, ki vas opozoriti, da je tukaj
da ta drevesa so malo čudno izgleda.
Še posebej, če se ozremo na 4 drevesa na desni strani -
Jaz jih bom krog, tukaj -
ta drevesa videti skoraj natanko tako kot povezan seznam.
Vsako vozlišče ima samo enega otroka,
in tako nimamo nič od tega podobno kot drevesna struktura, ki jo vidimo, na primer,
V tem enem posameznega drevesa tukaj na spodnji levi strani.
Ta drevesa so dejansko izrojene binarnih dreves
in se bova pogovorila o teh več v prihodnosti -
še posebej, če greš na sprejmejo tudi druge tečaje računalništva.
Ta drevesa so degenerirana.
Oni niso zelo koristen, saj res, ta struktura je primerna
za iskanje čase podobno kot povezan seznam.
Ne dobimo izkoristiti dodatne spomina - ta dodatni kazalec -
zaradi naše zgradbe je slaba na ta način.
Namesto da bi šel naprej in potegnili binarnih dreves, ki imajo 9 na koren,
ki je končni primeru, da bi imeli,
namesto tega smo v tem trenutku, bomo govorili malo o tem drugi mandat
, ki ga uporabljamo, ko govorimo o drevesih, ki se imenuje višina.
>> Višina drevesa je razdalja od korena do najbolj oddaljeni vozlišča,
oziroma število hmelja, ki bi jih morali narediti, da bi se
izhajati iz korena in nato končajo na najbolj oddaljeni vozlišče v drevesu.
Če pogledamo nekatere od teh dreves, ki smo jih pripravijo tukaj,
lahko vidimo, da če bomo to drevo v levem zgornjem kotu in začnemo na 3,
potem moramo narediti 1 skok, da pridete do 6, 2. hop priti do 7,
in tretji skok, da pridete do 9.
Tako je višina tega drevesa je 3.
Mi lahko storite enako nalogo za druga drevesa, opisanih v tej green,
Opažamo, da je višina vseh teh dreves je tudi res 3.
To je del tega, kar naredi sprevrgli -
da je njihova višina je le ena manjše od števila vozlišč v celotnem drevesu.
Če pogledamo to drugo drevo, ki je obkrožen z rdečo, na drugi strani,
vidimo, da so najbolj oddaljene-leaf vozlišč sta 6 in 9 -
listov so tisti vozlišča, ki nimajo otrok.
Torej, da bi dobili iz korenskega vozlišča bodisi na 6 ali 9,
imamo tudi en skok priti do 7 in nato 2. hop priti do 9,
in prav, samo 2. hop od 7 priti do 6.
Tako je višina tega drevesa tukaj je samo 2.
Lahko greš nazaj in to, da za vse druge dreves, ki smo že razpravljali
začenši s 7 in 6,
in boste ugotovili, da je višina vseh teh dreves je 2.
>> Razlog, da smo se pogovarjali o naloži binarnih dreves
in zakaj si kul, ker lahko iščete po njih v
zelo podoben način iskanja preko razvrščenih matrike.
To je, če govorimo o že čas, da izboljšano iskanje
nad navadno povezani seznam.
Z povezanega seznama - če želite najti določen element -
ste v najboljšem primeru bomo narediti neke vrste linearni iskanje
če ste začeli na začetku seznama in hop-by-1 1 -
eno vozlišče za eno vozlišče -
skozi celotno seznamu, dokler ne boste našli, kar iščete.
Ker, če imate binarno drevo, ki je shranjen v tej lepi obliki,
lahko dejansko dobili več od binarnega iskanja dogaja
kjer si deli in vladaj
in iskanje z ustreznim polovici drevesa na vsakem koraku.
Poglejmo, kako to deluje.
>> Če imamo - spet vrača v svojo izvorno drevo -
bomo začeli ob 7., imamo 3 na levi strani, na desni strani 9,
in pod 3 imamo 6.
Če želimo, da poiščete številko 6 v tem drevesu, bi začnemo pri korenu.
Mi bi primerjali vrednosti iščemo, recimo 6,
na vrednost, shranjeno v vozlišču, da smo trenutno proučujejo, 7,
Ugotovijo, da je dejansko 6 manj kot 7, zato smo se selili v levo.
Če je vrednost 6 je večja od 7, bi bile namesto tega pomika v desno.
Ker vemo, da je - zaradi strukture naše odredi drevesa binarnem -
vse vrednosti manj kot 7 bodo shranjeni na levi strani 7,
ni treba niti trudile gleda skozi desni strani drevesa.
Ko gremo v levo in smo zdaj v vozlišču, ki vsebuje 3,
lahko storimo, da se še enkrat isto primerjavo, kjer smo primerjali 3 in 6.
In smo ugotovili, da med 6 - večja od 3, - vrednost iščemo
lahko gremo na desni strani vozlišča, ki vsebuje 3.
Ni levi strani tukaj, tako da smo mogoče prezreti, da je.
Ampak samo zato, ker vemo, da smo iskali na drevesu samega,
in lahko vidimo, da je drevo nima otrok.
>> Prav tako je zelo enostavno poiskati 6 tega drevesa, če delamo to sebe kot človeka,
vendar pa si sledijo procesu mehansko kot računalnik bi naredil
zares razumeli algoritem.
Na tej točki smo zdaj gledaš vozlišča, ki vsebuje 6,
in iščemo vrednost 6,
to res, smo našli ustrezno vozlišče.
Našli smo vrednost 6 v našem drevesu in ne moremo ustaviti naše iskanje.
Na tej točki, glede na to, kaj se dogaja,
lahko rečemo, da smo našli vrednost 6, obstaja v našem drevesu.
Ali pa, če nameravate vstaviti vozlišča ali pa nekaj, kar lahko naredimo, da na tej točki.
>> Naredimo nekaj več poizvedbe samo, da vidim kako to deluje.
Oglejmo si, kaj se zgodi, če bi poskušali poiskati vrednosti 10.
Če smo poiskati vrednosti 10, bi začnemo pri korenu.
Radi bi videli, da je 10 več kot 7, zato smo se selili v desno.
Radi bi prišli do 9 in primerjajte 9 do 10, in vidim, da je res 9 manj kot 10.
Torej, še enkrat, bi se trudimo, da se premaknete na desno.
Toda na tej točki, bi opazili, da smo na ničelno vozlišče.
Tukaj ni ničesar. Ničesar ni, kjer bi morala biti 10.
To je, če se lahko poročajo z napako - da je dejansko ne 10 v drevo.
In končno, gremo skozi primeru, ko smo poskušali poiskati 1 v drevo.
To je podobno, kaj se zgodi, če gledamo do 10, razen namesto da bi šel na desno,
smo šli na levo.
Začnemo ob 7 in videli, da je 1 manj kot 7, zato gremo na levo.
Pridemo do 3 in videli, da je 1 manj kot 3, zato še enkrat smo poskušali premakniti na levo.
Na tej točki moramo ničelno vozlišče, tako da bomo lahko ponovno prijaviti napako.
>> Če bi želeli izvedeti več o binarnih dreves
obstaja cel kup zabavno malo težav, ki jih lahko naredite z njimi.
Predlagam prakticiranja risbo iz teh diagramov eno-by-1
in po skozi vse različne korake,
ker se bo to zgodilo v izjemno priročen
ne samo, ko delaš problem kodiranja Huffman niz
ampak tudi v prihodnjih tečajev -
le za učenje, kako pripraviti iz te podatkovne strukture in mislim skozi težave
z pero in papir, ali v tem primeru, iPad in pisalo.
>> Na tej točki, čeprav, bomo naprej, da naredite nekaj kodiranja prakse
in dejansko igrajo s temi binarnih dreves in videti.
Grem nazaj preklopi na mojem računalniku.
V tem delu odseka, namesto da bi uporabili CS50 Run ali CS50 Spaces,
Bom uporabo aparata.
>> Po skupaj s specifikacijo Problem Set,
Vidim, da sem moral odpreti aparat,
pojdi v mojo mapo Dropbox, ustvarite mapo, imenovano oddelek 7,
in nato ustvarite datoteko z imenom binary_tree.c.
Pa gremo. Imam aparat že odprta.
Grem dvigni terminal.
Jaz grem v mapo Dropbox, da mapi section7,
in videti je popolnoma prazna.
Zdaj bom odprl binary_tree.c.
V redu. Pa gremo - prazno datoteko.
>> Vrniva se v specifikaciji.
Specifikacija želi ustvariti novo opredelitev vrste
za binarno drevo vozlišče, ki vsebuje int vrednosti -
tako kot vrednote, ki jih puščala v naši diagramov prej.
Mi bomo to uporabiti boiler typedef, da smo naredili prav tukaj
da bi morali priznati iz Set Problem 5 -
če si razpršene tabele način osvajanja programa speller.
Prav tako bi morali prepoznati od točke prejšnjega tedna
, kjer smo se pogovarjali o povezanih seznamih.
Imamo to typedef struct iz vozlišča,
in smo glede na to struct Node to ime vozlišča struct poprej
tako da bomo lahko nato pa se nanašajo nanj, saj bomo želeli imeti kazalce vozlišče struct
kot del naše struct, vendar smo potem obkroženo to -
ali še bolje, obdan to - v typedef
tako, da je pozneje v kodo lahko sklicuje na to struct kot le vozlišče namesto struct vozlišče.
>> To bo zelo podoben posamezno povezano opredelitvijo seznama, da smo videli prejšnji teden.
Če želite to narediti, kaj je pravkar začela s pisanjem ven boiler.
Vemo, da moramo imeti celoštevilsko vrednost,
tako da bomo dal v int vrednost, nato pa, namesto da bi le en kazalec na naslednji element -
kot smo samostojno povezanih seznamov -
bomo imeli levo in desno kazalca otrok.
To je zelo enostavno preveč - struct vozlišče * levo otrok;
in struct vozlišče * pravice otrok;. Kul.
To izgleda zelo dober začetek.
Vrniva se v specifikaciji.
>> Zdaj moramo opredeliti globalno spremenljivko * vozlišče za koren drevesa.
Bomo, da bo ta globalni, tako kot smo naredili 1. kazalec na našem seznamu povezana tudi globalno.
To je bilo tako, da je v funkcijah, ki jih pišejo
nimamo, da gre okoli tega korena -
čeprav bomo videli, da če ne želite, da napišete svoje funkcije rekurzivno,
da bi bilo bolje, da sploh ne dajati okoli kot globalna na prvem mestu
in namesto tega zagnati lokalno v vašem glavne funkcije.
Ampak, bomo to vsem svetu, da začnete.
Spet vam bomo nekaj mest, in bom, da razglasi vozlišče koren *.
Samo se prepričajte, da se ne pustim nezaceto, grem, da ga postavi na null.
Zdaj, v glavnih funkcij - kar bomo napisali zelo hitro tukaj -
int main (int argc, char * argv []) -
in jaz bom za začetek razglasitvi svoj niz argv kot const samo zato, da vem,
da te trditve so argumenti, ki najbrž ne želijo spremeniti.
Če želim, da jih je treba spremeniti verjetno izdelavo kopije njih.
Videli boste to veliko v kodi.
V redu je tako ali tako. Saj je v redu, da ga pustijo kot - izpustiti konst, če želite.
Jaz ponavadi ga v samo zato, da sem se spomnil
da najbrž ne želite spremeniti te trditve.
>> Kot vedno, bom tudi to Vračilo 0 črto na koncu glavni.
Tukaj bom inicializacijo moje korenine vozlišče.
Ker stoji prav zdaj imam kazalec, ki je nastavljena na null,
tako da je obrnjena na nič.
Da bi dejansko začeli graditi vozlišče,
Najprej je treba dodeliti pomnilnika za to.
Jaz bom to storil tako, da spomin na kup z malloc.
Grem iz korenin, ki je enak rezultat knjižnične funkcije malloc,
in bom uporabljati sizeof operaterja za izračun velikosti vozlišča.
Razlog, da sem uporabo sizeof vozlišče za razliko od, recimo,
gre nekako takole - malloc (4 + 4 +4) ali malloc 12 -
zato, ker hočem, da je moja koda čim bolj združljivi.
Želim, da se bodo lahko tega C datoteko., Njihovo zbiranje na napravi,
in jo pripravijo na moji 64-bitni Mac -
ali na popolnoma drugačno arhitekturo -
in želim, da vse to dela isti.
>> Če delam predpostavke o velikosti spremenljivk -
velikost notr ali velikost kazalca -
potem sem tudi domnevam o vrstah arhitekture
na katere se lahko moja koda uspešno pripravijo ob zagonu.
Vedno uporabljajte sizeof v nasprotju z ročno seštevek struct polj.
Drugi razlog je, da je lahko tudi podloga, da prevajalnik postavlja v struct.
Celo tako, da se seštejejo posamezna področja, ni nekaj, kar običajno želijo storiti,
tako, izbrišite to vrstico.
Zdaj pa zares inicializirati to korensko vozlišče,
Jaz bom moral priključiti vrednosti za vsako od njenih različnih področjih.
Na primer, za vrednost, vem, da želite inicializirati do 7,
in zdaj bom iz leve otrok je nična
in pravico otroka, da je tudi nič. Čudovito!
Naredili smo ta del spec.
>> Specifikacija navzdol na dnu strani 3 me prosi, da ustvarite še tri vozlišča -
1, ki vsebujejo 3, 1, ki vsebuje 6 in 1 z 9 -
in jih nato žice gor, tako da izgleda natanko tako kot naši drevesnega diagrama
da smo govorili prej.
Naredimo to zelo hitro tukaj.
Videli boste res hitro, da bom začel pisati kup dvojnika kode.
Grem ustvariti vozlišče * in bom poklical tri.
Grem jo nastavite enako malloc (sizeof (vozlišče)).
Grem iz 3-> vrednost = 3.
Tri -> left_child = NULL; 3 -> desni _child = NULL; tudi.
To izgleda zelo podoben inicializacijo korenine, in to je točno to, kar
Jaz bom moral storiti, če začnem pri inicializaciji 6 in 9, kot dobro.
Storil bom, da res hitro tukaj - pravzaprav, bom naredil malo kopiraj in prilepi,
in se prepričajte, da sem - v redu.
Zdaj pa sem dobil kopirali in lahko gredo naprej in nastavite enako 6.
Vidite lahko, da to traja nekaj časa in ni super-učinkovita.
V samo malo, bomo napisali funkcijo, ki bo naredil to za nas.
Želim zamenjate z 9, da bi z zamenjavo 6.
>> Zdaj imamo vse naše vozlišč ustvariti in inicializiran.
Imamo naše korenine nastavi na 7 ali vsebuje vrednost 7,
naše vozlišče, ki vsebuje 3, naše vozlišče vsebuje 6, in naše vozlišče, ki vsebuje 9.
Na tej točki je vse, kar morate storiti je, žice vse gor.
Razlog, da sem inicializiramo vse napotke za null le tako, da se prepričam, da
Nimam nobenih kazalcev v nezaceto tam po naključju.
In tudi zato, ker v tem trenutku, sem le, da dejansko povezujejo vozlišča med seboj -
s tistimi, ki ste jih dejansko povezani z - mi ni treba iti skozi in da
Prepričajte se, da so vsi nulls so tam na ustreznih mestih.
>> Začnite pri korenu, vem, da je koren v levo otrok 3.
Vem, da je koren pravica otrok je 9.
Po tem, samo drugi otrok, ki sem jih pustil, da skrbi
je pravica otroka je 3, kar je 6.
Na tej točki je vse izgleda precej dobro.
Mi bomo izbrisati nekatere od teh vrstic.
Zdaj vse izgleda precej dobro.
Vrnimo se na naš specifikacije in videli, kaj moramo narediti.
>> Na tej točki moramo napisati funkcijo imenovano "vsebuje"
s prototipom "Bool vsebuje (int vrednost)."
In ta vsebuje funkcijo vrača res
Če drevo je poudaril, da z našo globalno spremenljivko korenin
vsebuje vrednost izrečene v funkciji in false sicer.
Pojdimo naprej in to.
To se bo točno tako kot lookup, da smo naredili z roko na iPad le malo pred.
Pojdimo povečavo nazaj malo in se pomaknete navzgor.
Bomo dal to funkcijo tik nad našo glavno funkcijo
tako da se nam ni treba narediti kakršno koli prototipov.
Torej, int vsebuje (int vrednost).
Takole. Tam je boiler deklaracija.
Samo se prepričajte, da bo to pripravijo,
Grem, da gredo naprej in samo nastavi na vrne false.
Zdaj je ta funkcija le ne bo naredil ničesar in vedno poročajo, da
vrednost, ki ga iščemo, ni v drevesu.
>> Na tej točki, je verjetno dobra ideja -
saj smo napisali cel kup kode in nismo niti poskusili, da ga testirajo še -
se prepričajte, da je vse pripravlja.
Obstaja nekaj stvari, ki jih moramo storiti, da poskrbite, da se bo to dejansko pripravijo.
Najprej poglejte, če smo bili z uporabo vseh funkcij v vseh knjižnicah, ki smo jih še niso vključene.
Naloge, ki smo jih do sedaj so uporabljeni malloc,
in potem smo tudi bili z uporabo te vrste - to nestandardno vrsto imenovano "bool' -
, ki je vključena v standardni bool datoteke glavo.
Vsekakor želimo vključiti standardne bool.h za bool tip,
in želimo tudi # include standardni lib.h za standardne knjižnice
da so malloc in brezplačno, in vse to.
Torej, pomanjšati, bomo nehal.
Poskusimo in se prepričajte, da je to dejansko storil prevesti.
Vidimo, da je tako, da smo na pravi poti.
>> Odprimo se binary_tree.c znova.
To ureja. Greva dol in se prepričajte, da vstavite nekaj klicev na naš funkcijo vsebuje -
Samo se prepričajte, da je vse lepo in prav.
Na primer, ko smo nekatere poizvedbe v našem drevesu prej,
smo poskušali poiskati vrednosti 6, 10 in 1, in smo vedeli, da je bil 6 v drevesu
10 ni v drevesu in 1 ni v drevesu, bodisi.
Izkoristimo te vzorčne klice kot način, da ugotovimo, ali ne
Vsebuje naša funkcija deluje.
Da bi to storili, bom uporabi printf funkcijo,
in bomo izpisal rezultat razpisa za vsebuje.
Bom dal v nizu "vsebuje (% d) = ker
bomo čep v vrednosti, ki jo bomo iskati,
in =% s \ n "in jo uporabite kot naš obliki niza.
Mi smo le, da bo videl - dobesedno izpiše na zaslonu -
kar izgleda kot klic funkcije.
To pravzaprav ni klic funkcije.
To je samo niz, ki je videti kot klic funkcije.
>> Zdaj pa gremo, da priključite na vrednosti.
Bomo poskušali vsebuje 6.,
in kaj potem bomo tukaj storiti, je, da uporabite trikomponentne operaterja.
Poglejmo - vsebuje 6 - tako, zdaj sem se iz 6, če vsebuje 6 je res,
string, da bomo poslali v formatu% s značaja
se bo niz "true".
Naj se pomaknite čez nekaj trenutkov.
Sicer pa želimo poslati niz "false", če vsebuje 6 vrne false.
To je malo izgleda bedasto, vendar sem ugotovil sem lahko tudi ponazarjajo
kaj trikomponentnih upravljavec izgleda, saj še nismo videli, za nekaj časa.
To bo lepo, priročen način, da ugotovimo, če je naša Vsebuje funkcija deluje.
Grem nazaj pomaknite čez levo,
in bom kopiraj in prilepi to vrstico nekajkrat.
To je spremenilo nekatere od teh vrednosti okoli,
tako da to se bo 1, in to se bo 10.
>> Na tej točki imamo lepo vsebuje funkcijo.
Imamo nekaj testov, in bomo videli, če je to vse deluje.
Na tej točki smo napisal nekaj več kode.
Čas je, da zaprete, in se prepričajte, da je vse še pripravlja.
Zaprite in zdaj probajmo tako binarno drevo znova.
No, izgleda, da imamo napako,
in imamo to izrecno opredeljuje, da je knjižnično funkcijo printf.
Izgleda, da moramo iti in # include standardio.h.
In s tem je treba vse prevesti. Vsi smo v redu.
Zdaj pa poskusite zagnati binarno drevo in glej kaj se zgodi.
Tukaj smo, /. Binary_tree,
in vidimo, da je, kot smo pričakovali -
ker nismo izvajali vsebuje še
ali še bolje, kar smo pravkar dal v zameno lažno -
vidimo, da je samo vrača false, za vse,
tako, da se vsi, ki delajo večinoma dokaj dobro.
>> Pojdimo nazaj in dejansko izvajanje vsebuje na tej točki.
Grem, da se pomaknete navzdol, povečanje, in -
Zapomnite si, da je algoritem smo uporabili, da smo začeli v korenskem vozlišču
in nato v vsakem vozlišču, da se srečamo, naredimo primerjavo,
in na podlagi tega smo za primerjavo premaknite na levo otroka ali desno otroka.
To bo videti zelo podobna binarno kodo iskalno da je napisal v začetku mandata.
Ko smo začeli, smo vedeli, da želimo, da imajo na trenutno vozlišče
da gledaš, in trenutno vozlišče se bo initialized v korensko vozlišče.
In zdaj, gremo, da bo šel skozi drevesa,
in ne pozabite, da je naš zavorno stanje -
ko smo dejansko delal na primeru z roko -
je bilo, ko smo naleteli ničelno vozlišče,
ne takrat, ko smo si ogledali ničelno otroka,
ampak ko smo dejansko preselil v vozlišče v drevesu
in ugotovili, da smo na ničelno vozlišče.
Bomo Ponovil dokler tren ni enaka null.
In kaj bomo storili?
Gremo na test, če (tren -> vrednost == vrednost)
potem vemo, da smo dejansko našli vozlišče, ki ga iščete.
Torej, tukaj se lahko vrnemo res.
Sicer pa bi radi videli, ali je vrednost nižja od vrednosti.
Če je trenutno vozlišče je vrednost nižja od vrednosti, ki ga iščemo,
bomo v desno.
Torej, tren = tren -> right_child in drugače, bomo premakniti na levo.
tren = tren -> left_child;. Precej enostavno.
>> Verjetno si priznati zanko, ki je videti zelo podobna temu iz
binarno iskanje v začetku mandata, razen takrat smo imeli opravka z nizko, srednje in visoko.
Tukaj smo samo še pogled na sedanjo vrednost,
Tako je lepo in preprosto.
Naj poskrbite, da ta številka deluje.
Najprej se prepričajte, da pripravlja. Izgleda, da ne.
Poskusimo ga zaženete.
In res, da natisne vse, kar smo pričakovali.
Ugotavlja 6 v drevo, ne najde 10, ker 10 ni v drevesu
in ne najde 1, bodisi zato, ker 1 je tudi ni v drevesu.
Cool stvari.
>> V redu. Vrnimo se k naši specifikacije in videli, kaj sledi.
Zdaj pa želi dodati nekaj več vozlišč za naše drevo.
To želi dodati 5, 2 in 8 in se prepričajte, da se naše vsebuje kodo
še vedno deluje, kot je bilo pričakovano.
Gremo narediti.
Na tej točki, ne pa delaš da je siten kopiraj in prilepi še enkrat,
dajmo napisati funkcijo, da dejansko ustvarite vozlišče.
Če smo se pomaknite navzdol, vse do glavnega vidimo, da smo počeli to
zelo podobna oznaka znova in znova, vsakič, da želimo ustvariti vozlišče.
>> Naj napisati funkcijo, ki bo dejansko izgradnjo vozlišče za nas in ga vrniti.
Jaz grem, da ga pokličete build_node.
Jaz bom za izgradnjo vozlišče z določeno vrednostjo.
Povečajte tukaj.
Prva stvar, ki jo bom naredil je dejansko ustvariti prostor za vozlišče na kup.
Torej, vozlišče * n = malloc (sizeof (vozlišče)); n -> vrednost = vrednost;
in potem je tu, bom samo za inicializacijo vseh področjih, ki so ustrezne vrednosti.
In čisto na koncu, bomo vrnili naše vozlišče.
V redu. Ena stvar je tudi omeniti, da te funkcije tukaj
vrača kazalec v spomin, da je bil kup dodeljena.
Kaj je lepo o tem, da je ta vozel zdaj -
moramo jo razglaša za na kup, ker če ga razglasi na kupu
ne bi mogli storiti v tej funkciji, kot je ta.
Ta spomin bi šel iz področja
in bi bila neveljavna, če smo želeli priti do njih kasneje.
Ker smo o razglasitvi kup-dodeljenega pomnilnika,
bomo morali skrbeti za njeno osvoboditev kasneje
za naš program, da ne pušča nobenega spomina.
Smo bili punting na to, za vse ostalo v kodeksu
samo zaradi enostavnosti je v času,
ampak, če ste kdaj napisali funkcijo, ki je videti takole
če imaš - nekateri pravijo malloc ali realloc znotraj -
želite poskrbite, da boste dal neke vrste komentar tu gor, ki pravi,
hej, saj veš, vrne kup dodeljena vozlišče initialized z spregledanih-vrednosti.
In potem si želim, da poskrbite, da boste dal v neke vrste opomba, ki pravi:
kličoči mora osvoboditi vrnil spomin.
Na ta način, če bi kdo kdaj gre in uporablja to funkcijo,
vedo, da vse, kar dobijo nazaj od te funkcije
na neki točki bo treba rešiti.
>> Ob predpostavki, da je vse lepo in prav tukaj,
lahko gremo dol v našo kodo in zamenjavo vseh teh vrstic tukaj
s klici na naše delovanje vozlišč izdelave.
Naredimo to zelo hitro.
En del, da mi ne bo nadomestil, je ta del tukaj
na dnu, kjer smo dejansko vodnika do vozlišča s točko med seboj,
ker to ne moremo narediti v našem delovanju.
Ampak, kaj je naredil root = build_node (7), vozlišče * 3 = build_node (3);
vozlišče * 6 = build_node (6), vozlišče * 9 = build_node (9);.
In zdaj smo želeli dodati vozlišča za -
vozlišče * 5 = build_node (5); vozlišče * 8 = build_node (8);
in kakšen je bil drugi vozel? Naj ogledate tukaj. Želeli smo, da dodate tudi 2 -
vozlišče * 2 = build_node (2);.
V redu. Na tej točki smo vedeli, da smo dobili 7, 3, je 9, in 6
vse žično gor pravilno, ampak kaj pa 5, 8, in 2?
Če želite ohraniti vse, kar je v ustreznem vrstnem redu,
vemo, da je pravica otroka 3 je 6.
Torej, če bomo dodali 5,
5 pripada tudi na desni strani drevesa, ki 3 je korenina,
5 tako pripada tudi levi otroka 6.
To lahko storimo z besedami, 6 -> left_child = 5;
in nato 8 pripada tudi levi otroka 9, tako 9 -> left_child = 8;
in potem 2 je na levi otrok 3, tako da lahko storimo, da tu - tebi -> left_child = 2;.
Če niste povsem slediti skupaj s tem, predlagam, da ga potegnili sami.
>> V redu. Rešimo to. Gremo ven in se prepričajte, da zbira,
in potem bomo lahko dodali v naših vsebuje klice.
Izgleda, da je vse še pripravlja.
Pojdimo in dodate v nekaterih vsebuje klice.
Spet bom naredil malo kopiraj in prilepi.
Zdaj Poiščimo 5, 8 in 2. V redu.
Naj se prepričajte, da to izgleda vse v redu vedno. Čudovito! Shrani in zapri.
Zdaj pa, da pripravi, in zdaj gremo teči.
Iz rezultatov, izgleda, da vse deluje samo lepo in dobro.
Čudovito! Torej, zdaj imamo naše Vsebuje funkcija napisana.
Gremo naprej in začeli delati na tem, kako vstaviti vozlišča v drevesu
saj, kot smo to počeli zdaj, stvari niso zelo lepa.
>> Če se vrnemo k specifikaciji,
nas zahteva, da napišete funkcijo imenovano vstavite - spet vrača int
za to, ali bi lahko dejansko vstavite vozlišče v drevesu -
in potem je vrednost, ki jo vstavite v drevo, kot je določeno
edini argument za naše vstaviti funkcijo.
Vrnili se bomo res, če bi lahko dejansko vstavite vozlišča, ki vsebuje vrednost v drevo,
kar pomeni, da je eden je imel dovolj spomina,
nato pa dve, da se vozlišče ne obstaja že od drevesa -
Zapomnite si, da mi ne dogaja, da imajo podvojene vrednosti v drevesu, le da bi stvari poenostavili.
V redu. Nazaj na kodo.
Odpri. Povečaj malo, nato pa se pomaknite navzdol.
Naj je dal vstaviti funkcijo, tik nad vsebuje.
Spet se dogaja, da se imenuje bool vstavi (int vrednost).
Daj mu malo več prostora, in nato, kot privzeto
kaj je dal v zameno lažno čisto na koncu.
Zdaj pa dol na dnu, gremo naprej in namesto ročno gradnjo vozlišč
v glavnem sami in jih žice do točke med seboj, kot delamo,
bomo zanesti na vstaviti funkcijo za to.
Ne bomo se zanesete na naše vstaviti funkcijo za izgradnjo celotno drevo iz nič še,
ampak bomo znebili teh vrstic - Bomo zakomentirajte teh vrstic -
ki gradijo vozlišča 5, 8 in 2.
In namesto, bomo vstavite klicev na naš vstaviti funkcijo
zagotoviti, da dejansko deluje.
Pa gremo.
>> Zdaj smo komentiral od teh vrstic.
Imamo samo še 7, 3, 9, 6 in v našem drevesu na tej točki.
Če se želite prepričati, da je to vse deluje,
lahko pomanjšate, da bi naše binarno drevo,
teči, in vidimo, da vsebuje zdaj nam govorijo, da smo popolnoma prav -
5, 8 in 2 niso več v drevo.
Pojdi nazaj v kodo,
in kako se bomo vstaviti?
Spomnite se, kaj smo naredili, ko smo dejansko vnašanje 5, 8 in 2 prej.
Igrali smo to igro Plinko, kjer smo začeli na koren,
znižala na drevesu enega po enega za
dokler ne bomo našli ustrezno razliko,
in potem žično v vozlišču na ustreznem mestu.
Mi smo naredili isto stvar.
To je v bistvu kot pisno kodo, ki smo jo uporabili, vsebuje funkcijo
da bi našli mesto, kjer bi morala biti vozlišče,
in potem greš samo vstaviti vozlišče tam.
Začnimo s tem.
>> Torej imamo vozlišče * tren = root, da greš samo slediti vsebuje kodo
dokler ne bomo ugotovili, da ni čisto delo za nas.
Mi smo šli skozi drevo, medtem ko je trenutna element ni nič,
in če bomo ugotovili, da je tren vrednost je enaka vrednosti, ki smo ga poskušate vstaviti -
Tudi to je eden od primerov, v katerih ne moremo dejansko vstaviti vozlišče
v drevo, ker to pomeni, da imamo podvojeno vrednost.
Tu smo dejansko dogaja, da vrne false.
Zdaj pa, če je tren vrednost nižja od vrednosti,
Zdaj vemo, da se premaknete na desno
ker je vrednost spada v desni polovici tren drevesa.
V nasprotnem primeru bomo premakniti na levo.
To je v bistvu naša Vsebuje deluje tam.
>> Na tej točki, ko bomo končali to while zanko,
naš tren kazalec se bo obrnjena na null
Če je funkcija še ni vrnil.
Mi smo zato ob CUR na mestu, kjer želite vstaviti novo vozlišče.
Kaj je še treba storiti, je dejansko izgradnjo novega vozlišča
kar lahko naredimo zelo enostavno.
Mi lahko uporabite našo izjemno priročen graditi vozlišča funkcijo,
in nekaj, kar nismo storili že prej -
sva nekako vzel za samoumevno, zdaj pa bomo storili šele prepričati -
bomo test, da se prepričajte, da je vrednost vrnil z novo vozlišče je bilo dejansko
ni nič, ker ne želimo začeti do teh spomin, če je nična.
Mi lahko test, da se prepriča, da je novo vozlišče ni enaka null.
Ali pa namesto tega smo lahko videli, če je v resnici nič,
in če je nična, potem lahko samo vrne false zgodaj.
>> Na tej točki moramo žice novo vozlišče v svoje ustrezno mesto v drevesu.
Če se ozremo nazaj na glavno in kje smo dejansko napeljava vrednosti pred
vidimo, da je način, kako so to počeli, ko smo želeli postaviti 3 v drevo
mi je bila naložena na levi otroka korenine.
Ko smo se 9 na drevesu, smo imeli dostop do pravega otroka korena.
Morali smo se kazalec na starša, da bi dal novo vrednost v drevo.
Pomikanje nazaj vstaviti, da to ne bo delovalo čisto tukaj
ker nimamo matično kazalec.
Kaj želimo biti sposoben narediti je, da na tej točki,
preverite staršev vrednosti in videti - no, bog,
Če eden od staršev je vrednost nižja od trenutne vrednosti,
potem bi obvladujočega pravica otrok je novo vozlišče;
drugače, bi morala starša levo otrok bo novo vozlišče.
Ampak, nimamo to matično kazalec še.
>> Da bi jo dobili, smo dejansko dogaja, da so ga spremljali, ko gremo skozi drevesa
in najti ustrezno mesto v našem zanke zgoraj.
Mi lahko storite, da se premaknete nazaj na vrh našega vstaviti funkcijo
in sledenje drug kazalec spremenljivka se imenuje staršev.
Bomo ga postavi na začetku null,
in nato vsakič, ko gremo skozi drevesa,
bomo nastavili matično kazalec, da se ujema trenutni kazalec.
Nastavite od staršev, ki je enaka cur.
Tako vsakič, ko gremo skozi,
bomo zagotovili, da se sedanji kazalec postane poveča
osnovni kazalec ji sledi - le ena stopnja višja od trenutne kazalca v drevesu.
To je vse izgleda precej dobro.
>> Mislim, da je ena stvar, ki jo bomo želeli prilagoditi, je to zgraditi vozlišče vrača null.
Da bi dobili zgraditi vozlišče, dejansko uspešno vrne null,
bomo morali spremeniti to kodo,
ker tukaj ne bomo nikoli preizkušeni prepričati, da se vrne malloc veljaven kazalec.
Torej, če (n = NIČ!), Nato pa -
če malloc vrne veljaven kazalec, nato pa ga bomo zagnati;
sicer pa bova vrnili in da bo na koncu vrne null za nas.
Zdaj vse izgleda precej dobro. Naj se prepričajte, to dejansko ureja.
Naredite binarno drevo, in oh, imamo nekaj stvari se dogaja tukaj.
>> Imamo implicitno izjavo o delovanju zgraditi vozlišče.
Spet s temi prevajalniki, bomo začeli na vrhu.
Kaj, da je treba reči, da kličem zgraditi vozlišče, preden sem dejansko prijavljeni.
Pojdimo nazaj na oznako res hitro.
Pomaknite se navzdol, in gotovo se razglasi za moje vstaviti funkcijo
nad delovanjem gradnje vozlišča,
vendar sem poskušal uporabiti zgraditi vozlišče znotraj vložka.
Jaz grem v in kopije - in ga prilepite funkcije vozlišča graditi sem gor na vrhu.
Tako, upam, da bo delovalo. Dajmo to še gre.
Zdaj je vse pripravlja. Vse je v redu.
>> Toda na tej točki, ki smo jih dejansko ni pozval naše vstaviti funkcijo.
Vemo samo, da se pripravlja, da gremo v in dal nekaj klicev noter
Naredimo to v naši glavni funkciji.
Tu smo navedli od 5, 8 in 2,
in potem jih nismo žice gor dol.
Naredimo nekaj pozivov za vnos,
in kaj je prav tako uporabiti isto vrsto stvari, ki smo jo uporabili
ko smo te printf klicev se prepričajte, da ni vse, kar se pravilno vstavljen.
Grem kopiranje in lepljenje,
in namesto vsebuje bomo narediti vložek.
In namesto, 6, 10 in 1, gremo uporabiti 5, 8 in 2.
To naj bi, upajmo, vstavite 5, 8 in 2 v drevo.
Prevesti. Vse je v redu. Zdaj bomo dejansko vodijo naš program.
>> Vse se vrne false.
Torej, 5, 8 in 2 ni šel, in izgleda, da Contains jih niso našli niti.
Kaj se dogaja? Naj pomanjšati.
Prvi problem je bil, da je zdelo, da vložek vrne false,
in izgleda, da je to zato, ker smo pustili v naši vrnitvi lažni klic,
in mi nikoli dejansko vrnil res.
Mi lahko nastavite, da gor.
Drugi problem je, zdaj tudi če delamo - razen tega, zaprete tako,
Naklada bo spet moralo zbrati, nato pa ga teči -
vidimo, da je nekaj drugega se je zgodilo.
Za 5, 8, in 2 sta bili še nikoli našli v drevo.
Torej, kaj se dogaja?
>> Oglejmo si to v kodi.
Poglejmo, če lahko to ugotovite.
Začeli smo s starši niso nič.
Postavili smo trenutno kazalec, ki je enak koren kazalcem
in da bomo naš način dela, navzdol po drevesu.
Če je trenutno vozlišče ni nič, potem vemo, da lahko gremo dol malo.
Mi je naša matično kazalec, da je enaka trenutni kazalec,
preverila vrednost - če sta vrednosti enaki smo se vrnili napačen.
Če so vrednosti manj smo se preselili na desno;
sicer pa smo se preselili v levo.
Potem smo zgradili vozlišče. Jaz bom povečate malo.
In tukaj bomo poskušali žice do vrednosti, ki je enaka.
Kaj se dogaja? Bomo videli, če morda lahko Valgrind nam namig.
>> Rad uporabljam Valgrind samo zato, ker res hitro teče Valgrind
in vam pove, če obstajajo kakršne koli napake pomnilnika.
Ko smo teči Valgrind na oznako,
Kot lahko vidite desno here--Valgrind./binary_tree--and zadeti nastopiti.
Vidiš, da nismo imeli nobene napake pomnilnika, tako da izgleda kot da je vse v redu doslej.
Imamo nekaj spomin razpoka, ki jih poznamo, ker nismo
dogaja se osvobodi vseh naših vozlišč.
Poskusimo teče GDB, da vidim, kaj se dejansko dogaja.
Naredili bomo gdb. / Binary_tree. To zažene v redu.
Naj določi odmor točko na vložek.
Naj teče.
Izgleda, da ne bomo nikoli pravzaprav imenuje vložek.
Izgleda, da je problem samo, da ko sem spremenil tukaj v glavnem -
Vse te printf klice iz vsebuje -
Nikoli nisem spremenila te poklicati vložek.
Zdaj pa, da ga poskusite. Naj pripravijo.
Vse zgleda v redu tam. Zdaj pa poskusimo to izvaja, kaj se bo zgodilo.
V redu! Vse, kar izgleda precej dobro tam.
>> Zadnja stvar, da razmišljajo o je, ali obstajajo kakršne koli roba primeri tega vložka?
In izkazalo se je, da je dobro, ena stranica primer, da je vedno zanimivo, da razmišljajo o
je, kaj se zgodi, če je vaš drevo je prazna in jo imenujemo vstaviti funkcijo?
Bo to delovalo? No, dajmo poskusiti.
- Binary_tree c. -
Tako bomo testirali je, da smo šli do naše glavne funkcije,
in namesto kablov te vozle up, kot je ta,
smo le, da bo zakomentirajte celotno stvar,
in namesto napeljave do vozlišča sebe,
lahko dejansko samo pojdi naprej in izbrisati vse to.
Bomo narediti vse, kar je klic za vstavljanje.
Torej, kaj je to - namesto 5, 8 in 2, se bomo, da vstavite 7, 3, 9.
In potem bomo tudi želite vstaviti 6, kot tudi.
Shrani. Končaj. Naredite binarno drevo.
Vse pripravlja.
Mi lahko samo teče, kot je bilo, in videli, kaj se zgodi,
a prav tako bo zelo pomembno, da poskrbite, da
nimamo nobenih spomin napak,
ker je to ena od naših robnih primerov, da vemo o tem.
>> Naj se prepričajte, da dobro deluje v okviru Valgrind,
kar bomo storili s samo vožnjo Valgrind. / binary_tree.
Izgleda, da smo res en napake iz enega konteksta -
imamo to Napaka pri razčlenjenosti.
Kaj se je zgodilo?
Valgrind dejansko ne pove, kje je.
Pomanjšajte malo.
Videti je, da se to dogaja v naši vstaviti funkcijo,
kjer imamo napačno branje velikosti 4 na vložek, linija 60.
Pojdimo nazaj in videli, kaj se dogaja tukaj.
Pomanjšajte res hitro.
Želim, da se prepriča, da ne gre na rob zaslona, ​​tako da lahko vidimo vse.
Povlecite, da v malo. V redu.
Pomaknite se navzdol in problem je tukaj.
Kaj se zgodi, če bomo dol in naš sedanji vozlišče je že null,
naša matična vozlišče nič, tako da, če pogledamo gor na vrhu, prav tukaj -
če je to, medtem ko zanke nikoli dejansko izvaja
ker naša trenutna vrednost nič - naša root je nična, tako tren ničelna -
nato pa nas nikoli ne postane nadrejena naj bi cur ali veljavno vrednostjo,
Tako bodo starši prav tako nična.
Moramo se spomniti, da preverite, da
do takrat, ko bomo prišli tja, in smo začeli dostop do strani staršev vrednost.
Torej, kaj se zgodi? No, če je eden od staršev nič -
če (matično == NULL) -, potem vemo, da
pa ne sme biti nič v drevo.
Moramo se poskuša, da ga vstavite v korenu.
To lahko storimo le za določitev osnovnih enak novo vozlišče.
Nato v tem trenutku pravzaprav ne želim iti skozi te druge stvari.
Namesto, tukaj, lahko naredimo bodisi drugod po-drugega,
ali lahko združimo vse, kar je tukaj v drugega,
ampak tukaj bomo samo uporabo drugje in ne v to smer.
Zdaj bomo test, da se prepričajte, da je naša matična ni nič
pred tem se dejansko poskuša dostopati do svojih polj.
To nam bo pomagalo preprečiti segmentacijo napake.
Torej, smo nehal, pomanjšanje zbrati, teci.
>> Ni napak, vendar smo še vedno imeli kup spomin razpoka
ker nismo osvobodi vseh naših vozlišč.
Ampak, če gremo gor in se ozremo na naše izpisa,
vidimo, da je dobro, izgleda, da so vsi naši vložki so vračanje res, kar je dobro.
Vložki so vse res,
in nato ustrezne vsebuje klice tudi res.
>> Dobro opravljeno! Izgleda, da smo uspešno pisno navodilo.
To je vse, kar imamo za specifikacijo ta teden Problem Set.
En zabaven izziv, da razmišljajo o tem, kako bi dejansko šel v
in brez vseh vozlišč v tem drevesu.
Mi lahko to stori več različnih načinov,
ampak bom pustil, da je do vas, da eksperimentirate,
in kot zabaven izziv, poskusite in se prepričajte, da ste lahko prepričani,
V tem poročilu Valgrind ne vrne napake in ne pušča.
>> Vso srečo na Huffman ta teden kodiranje nabora problemov,
in se vidimo naslednji teden!
[CS50.TV]