[Powered by Google Translate] [Article 7] [Menys Còmode]
[Nate Hardison] [Harvard University]
[Aquesta és CS50.] [CS50.TV]
>> Benvingut a la Secció 7.
Gràcies a huracà de sorra,
en lloc de tenir una secció normal d'aquesta setmana,
estem fent aquest recorregut, a través de la secció de preguntes.
Vaig a estar seguint juntament amb el butlletí de problemes 6 Especificació,
i passant per totes les preguntes de la
Una secció de la secció de Preguntes.
Si hi ha alguna pregunta,
si us plau, publicar-lo en aquests CS50 discutir.
>> Molt bé. Anem a començar.
En aquest moment estic buscant a la pàgina 3 de l'Especificació de problemes.
Anem a començar a parlar primer sobre arbres binaris
ja que aquests tenen una gran rellevància per a conjunt de problemes d'aquesta setmana -
la codificació de l'arbre de Huffman.
Una de les estructures de dades molt 1 parlem sobre CS50 va ser l'arranjament.
Recordeu que una matriu és una seqüència d'elements -
totes del mateix tipus - emmagatzema un al costat de l'altre en la memòria.
Si tinc una matriu d'enters que puc dibuixar amb aquest estil de caixes-numbers-nombres enters -
Diguem que tinc 5 a la primera casella, tinc 7 al segon,
llavors tenen 8, 10, i 20 en el quadre final.
Recordeu les coses, els dos realment bones d'aquesta matriu
és que tenim aquest accés constant a temps a qualsevol element particular
en la matriu si se sap que el seu índex.
Per exemple, si vull agafar el tercer element de la matriu -
al índex 2 usant la nostra base zero sistema d'indexació -
Jo, literalment, només cal fer un càlcul matemàtic simple,
saltar a la posició en la matriu,
tregui el 8 que estigui emmagatzemat,
i estic llest per sortir.
>> Una de les coses dolentes d'aquest conjunt - que parlem
quan parlem de llistes enllaçades -
és que si voleu inserir un element en l'array,
Vaig a haver de fer algun canvi al seu voltant.
Per exemple, aquesta matriu aquí
està en l'ordre establert - en ordre ascendent -
5, a continuació, 7, 8 i després, a continuació, 10, i després 20 -
però si ho desitja inserir el número 9 en aquesta matriu,
Vaig a haver de canviar alguns dels elements per tal de fer espai.
Podem extreure aquesta aquí.
Vaig a haver de moure el 5, el 7 i després la 8;
crear un espai on puc posar el 9,
i després el 10 i el 20 pot anar a la dreta de la 9.
Aquest és un tipus de dolor perquè en el pitjor dels casos -
quan estem haver de inserir ja sigui al principi o al final
de la matriu, en funció de com estem canviant -
podríem arribar a haver de canviar tots els elements
que actualment estem emmagatzemant en la matriu.
>> Llavors, ¿quina era la forma d'evitar això?
La forma d'evitar això era anar al nostre mètode de llista enllaçada, on -
en lloc d'emmagatzemar els elements 5, 7, 8, 10 i 20 tots un al costat de l'altre en la memòria -
el que en el seu lloc se'ls estava emmagatzemar espècie d'on volíem per emmagatzemar
en aquests nodes de la llista enllaçada que estic dibuixant aquí, una mica ad hoc.
I llavors ells connectats entre si mitjançant aquests indicadors següents.
Puc tenir un punter del 5 al 7 de
un triple des de la 7 a la 8,
un triple des de la 8 a la 10,
i finalment, un triple des de la 10 a la 20,
i després un punter nul en els anys 20 el que indica que no hi ha res a l'esquerra.
La disjuntiva que tenim aquí
és que ara si volem inserir el número 9 a la llista ordenada,
tot el que hem de fer és crear un nou node amb 9,
cablejar cap amunt perquè apunti al lloc adequat,
i després re-cablejat del 8 a l'apuntar cap avall a la 9.
Això és bastant ràpid, en el supòsit que sabem exactament on volem inserir el 9.
Però la compensació a canvi d'això és que hem perdut l'accés constant de temps
a qualsevol element particular en la nostra estructura de dades.
Per exemple, si vull trobar el quart element en aquesta llista enllaçada,
Vaig a haver de començar des del principi de la llista
i treballar a la meva manera a través de comptar node per node fins que trobi el quart.
>> Per tal d'obtenir un millor rendiment d'accés d'una llista enllaçada -
però també retenen alguns dels avantatges que teníem
en termes d'inserció a temps d'una llista enllaçada -
un arbre binari es va a haver d'utilitzar la memòria una mica més.
En particular, en lloc de només tenir un punter a un node d'arbre binari -
igual que la llista enllaçada de nodes fa -
anem a afegir un segon punter per al node de l'arbre binari.
En lloc de tenir un punter al següent element,
tindrem un punter a un fill esquerre i un fill dret.
>> Anem a fer un dibuix per veure el que realment sembla.
Un cop més, vaig a utilitzar aquestes caixes i fletxes.
Un node de l'arbre binari a començar amb només una caixa simple.
Tindrà un espai per al valor,
i llavors també tindrà un espai perquè el fill esquerre i el fill dret.
Vaig a etiquetar aquí.
Anem a tenir el fill esquerre, i després ens anem a tenir el fill dret.
Hi ha moltes maneres diferents de fer això.
De vegades per espai i comoditat,
De fet, em vaig a dibuixar com que estic fent aquí a la part inferior
on jo vaig a tenir el valor en la part superior,
i llavors el nen a la dreta a la part inferior dreta,
i el fill esquerre a la part inferior esquerra.
Tornant a aquest diagrama superior,
tenim el valor en la part superior,
llavors tenim el punter esquerre-fill, i llavors tenim el punter dret de l'infant.
>> En l'especificació del conjunt de problemes,
es parla de l'elaboració d'un node que té un valor de 7,
i després un punter esquerre nen que és nul, i un punter dret de l'infant que és nul.
Podem escriure NULL capital en l'espai per
tant el fill esquerre i el fill dret, o podem treure aquesta barra diagonal
a través de cadascuna de les caselles per indicar que és nul.
Vaig a fer això només perquè és més simple.
El que es veu aquí són dues formes de diagramació d'un node d'arbre binari molt senzill
on tenim el valor 7 i punters nuls infantil.
>> La segona part de les nostres converses amb les especificacions sobre com les llistes enllaçades -
recordi, només vam haver d'esperar al primer element d'una llista
per recordar tota la llista -
i de la mateixa manera, amb un arbre binari, només hem d'aguantar a un punter a l'arbre
amb la finalitat de mantenir el control sobre l'estructura de dades completa.
Aquest element especial de l'arbre s'anomena node arrel de l'arbre.
Per exemple, si aquest node d'un - aquest node que conté el valor 7
amb punters nuls esquerra i dreta per a nens -
eren l'únic valor al nostre arbre,
llavors aquest seria el nostre node arrel.
És el començament mateix del nostre arbre.
Podem veure això una mica més clara un cop que comenci a afegir més nodes al nostre arbre.
Deixa treure una nova pàgina.
>> Ara anem a dibuixar un arbre que té 7 a l'arrel,
i 3 dins de la fill esquerre, i 9 a l'interior de el fill dret.
Un cop més, això és bastant simple.
Tenim 7, dibuixi un node per al 3, un node 9,
i jo vaig a posar el punter esquerre nen de 7 a apuntar al node amb 3,
i el punter dret del fill del node que conté 7 al node que conté 9.
Ara, des del 3 i 9 no tenen fills,
farem que tots els punters als seus fills a ser nul.
Aquí, l'arrel del nostre arbre correspon al node que conté el número 7.
Es pot veure que si tot el que tenim és un punter a aquest node arrel,
llavors podem caminar a través del nostre arbre i accedir a tots dos nodes secundaris -
ambdós 3 i 9.
No cal mantenir els punters a cada node en l'arbre.
Molt bé. Ara anem a afegir un node a aquest diagrama.
Anem a afegir un node que conté 6,
i anem a afegir això com el fill dret del node amb 3.
Per fer això, vaig a esborrar aquest punter nul al 3-node
i cablejar perquè apunti al node que conté 6. Molt bé.
>> En aquest punt, anem a repassar una mica de la terminologia.
Per començar, la raó per la qual això es diu un arbre binari en particular
és que té dos punters nen.
Hi ha altres tipus d'arbres que tenen més punters del nen.
En particular, es va fer un 'try' en Butlletí de problemes 5.
Es donarà compte de que en aquest intent, que va tenir 27 punters diferents per diferents nens -
un per a cadascuna de les 26 lletres en l'alfabet anglès,
i després el dia 27 per l'apòstrof -
és així, que és similar a un tipus d'arbre.
Però aquí, ja que és binari, només tenim dos punters del nen.
>> A més d'aquest node arrel que hem parlat,
també hem estat llançant al voltant d'aquest terme "nen".
Què significa per a un node a ser un fill d'un altre node?
És, literalment, significa que un node fill és un fill d'un altre node
si un altre node que té una de les seves punters de nens fixen per apuntar a aquest node.
Per posar-ho en termes més concrets,
si 3 és apuntat per un dels punters de nen de 7, llavors 3 és un nen de 7.
Si haguéssim de entendre el que els nens de 7 són -
així, veiem que 7 té un punter a 3 i un punter a 9,
el 9 i 3 són fills de 7.
Nou no té fills, perquè els seus fills són punters nuls,
i 3 només té un fill de 6.
Sis tampoc té fills, perquè els seus dos punters són nuls, el que anomenarem ara mateix.
>> A més, també parlem dels pares d'un node en particular,
i això és, com era d'esperar, el revers d'aquesta descripció nen.
Cada node té un sol pare - en lloc de dos com es podria esperar dels éssers humans.
Per exemple, la matriu de 3 és 7.
El pare de 9 és també 7, i el pare de 6 és 3. No hi ha molt a ella.
També tenim termes per parlar dels avis i els néts,
i en general es parla dels avantpassats
i descendents d'un node en particular.
L'ancestre d'un node - o avantpassats, més aviat, d'un node -
són tots els nodes que es troben en el camí des de l'arrel a aquest node.
Per exemple, si estic buscant en el node 6,
llavors els avantpassats serà alhora 3 i 7.
Els avantpassats de 9, per exemple, són - si estic buscant en el node 9 -
llavors l'avantpassat de 9 és només 7.
I descendents són exactament el contrari.
Per veure tots els descendents de 7,
llavors he de mirar tots els nodes que en depenen.
Per tant, tinc 3, 9, i 6 tots com a fills de 7.
>> El termini final que parlarem és d'aquesta noció de ser un germà.
Germans - alguna cosa seguint al llarg d'aquests termes famílies -
són nodes que estan en el mateix nivell en l'arbre.
Així, 3 i 9 són germans perquè estan en el mateix nivell en l'arbre.
Tots dos tenen el mateix pare, 7.
El 6 no té germans perquè 9 no tinc fills.
I 7 no té germans, perquè és l'arrel del nostre arbre,
i només hi ha sempre una arrel.
Per tenir 7 germans no hauria de ser un node per sobre de 7.
No hauria de ser una matriu de 7, en aquest cas 7 ja no seria l'arrel de l'arbre.
Després que els pares nous de 7 també hauria de tenir un fill,
i que nen seria llavors el germà de 7.
>> Molt bé. Canviant de tema.
Quan vam començar la nostra discussió dels arbres binaris,
parlem del que anàvem a utilitzar per
obtenir un avantatge sobre ambdues matrius i llistes enllaçades.
I la manera com ho farem és amb aquesta propietat comanda.
Es diu que un arbre binari és ordenat, d'acord amb l'especificació,
si per a cada node en el nostre arbre, tots els seus descendents de l'esquerra -
el fill de l'esquerra i tots els descendents del fill esquerre -
tenen valors menors, i tots els nodes de la dreta -
el fill dret i tots els descendents dels fills de dret -
tenen nodes més grans que el valor del node actual que estem veient.
Només per simplificar, suposarem que no hi ha nodes duplicats al nostre arbre.
Per exemple, en aquest arbre no tractarem el cas
on tenim el valor 7 a l'arrel
i després també tenim el valor 7 en un altre lloc en l'arbre.
En aquest cas, es donarà compte que aquest arbre és de fet ordenat.
Tenim el valor 7 a l'arrel.
Tot a l'esquerra de 7 -
si puc desfer totes aquestes petites marques aquí -
tot a l'esquerra de 7 - el 3 i el 6 -
aquests valors es troben a menys de 7, i tot a la dreta - que és precisament aquest 9
és més gran que 7.
>> Aquest no és l'únic arbre ordenat que conté aquests valors,
però farem una mica més d'ells.
En realitat, hi ha un munt de maneres en què podem fer això.
Vaig a utilitzar una drecera només per mantenir les coses simples on -
en comptes d'extreure la totalitat caixes i fletxes -
Jo només vaig a dibuixar els números i afegir fletxes connecten.
Per començar, només haurem d'escriure el nostre arbre original de nou on teníem 7, i després un 3,
i després 3 va assenyalar de nou a la dreta a la 6,
i 7 van tenir un fill dret que tenia 9 anys.
Molt bé. De quina altra manera que no puguem escriure aquest arbre?
En comptes de tenir 3 serà el fill esquerre de 7,
També podria tenir el 6 ser el fill esquerre de 7,
i després 3 serà el fill esquerre de la 6.
Això s'assemblaria a aquest arbre aquí on tinc 7,
després 6, després 3, i un 9 a la dreta.
Tampoc ha de tenir 7 com el nostre node arrel.
També podria tenir 6 com el nostre node arrel.
Què es veu?
Si anem a mantenir aquest immoble ordenat,
tot a l'esquerra de la 6 ha de ser menor que ella.
Només hi ha una possibilitat, i això és 3.
Però llavors, com el fill dret de 6, tenim dues possibilitats.
En primer lloc, podríem tenir el 7 i després el 9,
o podríem dir - que estic a punt de fer aquí -
on tenim el 9 com el fill dret de la 6,
i després el 7 com el fill esquerre de la 9.
>> Ara, 7 i 6 no són els únics valors possibles de l'arrel.
També podríem tenir 3 a l'arrel.
Què passa si 3 és l'arrel?
Aquí, les coses es posen una mica més interessant.
Tres no té valors que són menors del que,
de manera que tot el costat esquerre de l'arbre és només serà nul.
No serà gens allà.
A la dreta, podríem enumerar les coses en ordre ascendent.
Podríem tenir 3, després 6, després 7, després 9.
O bé, podem fer 3, després 6, després 9, després 7.
O bé, podem fer 3, després 7, després 6, després 9.
O, 3, 7 - en realitat no, no podem fer un 7 més.
Aquesta és la nostra única cosa allà.
Podem fer 9, i després des del 9 podem fer 6 i 7.
O bé, podem fer 3, després 9, després 7 i després 6.
>> Una cosa per cridar la seva atenció aquí és
que aquests arbres són una mica d'aspecte estrany.
En particular, si ens fixem en els quatre arbres al costat dret -
Vaig a envoltar, aquí -
aquests arbres es veuen gairebé exactament igual que una llista enllaçada.
Cada node té un sol fill,
pel que no té cap d'aquesta estructura en forma d'arbre que veiem, per exemple,
en aquest arbre un solitari aquí a la part inferior esquerra.
Aquests arbres es diu en realitat degenerada arbres binaris,
i anem a parlar d'aquests més en el futur -
especialment si vostè va a prendre altres cursos de ciències de la computació.
Aquests arbres són degenerats.
No són molt útils perquè, en efecte, aquesta estructura es presta
per buscar temps similars a la d'una llista enllaçada.
No aconseguim aprofitar la memòria addicional - aquest punter extra -
perquè de la nostra estructura de ser dolent d'aquesta manera.
En comptes de seguir endavant i treure els arbres binaris que tenen 9 a l'arrel,
que és el cas final que tindria,
estem en canvi, en aquest punt, parlarem una mica sobre aquest altre terme
que utilitzem quan parlem d'arbres, que es diu l'alçada.
>> L'altura d'un arbre és la distància des de l'arrel fins al node més distant,
o més bé el nombre de salts que s'hauria de fer per tal de
començar des de l'arrel i després acaben en el node més llunyà en l'arbre.
Si ens fixem en alguns d'aquests arbres que hem dibuixat aquí,
podem veure que si prenem aquest arbre a la cantonada superior esquerra i comencem a 3,
llavors hem de fer un salt per arribar a la 6, un segon salt per arribar als 7,
i una tercera hop per arribar a la 9.
Així, l'alçada d'aquest arbre és 3.
Podem fer el mateix exercici per als altres arbres assenyalats amb aquest color verd,
i es veu que l'altura de tots aquests arbres és també de fet 3.
Això és part del que els fa degenerar -
que la seva altura és només un menys que el nombre de nodes al arbre.
Si ens fixem en aquest altre arbre que està envoltat de vermell, d'altra banda,
veiem que els nodes de fulla més distants són el 6 i el 9 -
la deixa ser aquells nodes que no tenen fills.
Així, amb la finalitat d'obtenir des del node arrel a ja sigui el 6 o el 9,
hem de fer un salt per arribar a la 7 i després un segon salt per arribar a la 9,
i de la mateixa manera, només un salt de la segona 7 per arribar a la 6.
Així, l'alçada d'aquest arbre d'aquí és només 2.
Vostè pot tornar enrere i fer que per a tots els altres arbres que prèviament discutit
començant amb el 7 i el 6,
i et donaràs compte de que l'altura de tots aquests arbres és també 2.
>> La raó per la qual hem estat parlant ordenar arbres binaris
i per què estem bé és perquè vostè pot cercar a través d'ells en
d'una manera molt similar a la recerca a través d'una matriu ordenada.
Aquí és on parlem d'aconseguir que el temps de recerca millorada
sobre la llista enllaçada simple.
Amb una llista enllaçada - si vol trobar un element en particular -
ets el millor farà algun tipus de recerca lineal
on s'inicia al començament de la llista i saltar d'un en un -
un node a un node -
a través de tota la llista fins que trobi el que vostè està buscant.
Mentre que si vostè té un arbre binari que s'emmagatzema en aquest format agradable,
preguntes més d'una recerca binària passant
on es divideix i venceràs
i buscar a la mitjana corresponent de l'arbre en cada pas.
Anem a veure com funciona.
>> Si tenim - de nou, tornant al nostre arbre original -
comencem a 7, que tenen 3 a l'esquerra, 9 a la dreta,
i sota la 3 tenim la 6.
Si volem buscar el número 6 d'aquest arbre, ens agradaria començar en l'arrel.
Volem comparar el valor que busquem, per exemple 6,
amb el valor emmagatzemat en el node que estem mirant, 7,
trobar que 6 és de fet menor que 7, de manera que ens mou a l'esquerra.
Si el valor de 6 havia estat major que 7, hauríem es mouen a la dreta.
Ja que sabem que - a causa de l'estructura del nostre arbre binari ordenat -
tots els valors de menys de 7 seran emmagatzemats a l'esquerra de 7,
no hi ha necessitat de molestar tan sols mirar pel costat dret de l'arbre.
Quan ens movem cap a l'esquerra i ara estem en el node amb 3,
podem fer aquesta comparació mateixa de nou on es compara el 3 i el 6.
I trobem que mentre que el 6 - el valor que estem buscant - és més gran que 3,
que pot anar cap al costat dret del node amb 3.
No hi ha costat esquerre aquí, així que podria haver ignorat això.
No obstant això, només se sap que pel fet que estem veient en el propi arbre,
i podem veure que l'arbre no té fills.
>> També és molt fàcil buscar 6 d'aquest arbre si ho fem a nosaltres mateixos com a éssers humans,
però seguirem aquest procés mecànicament com un ordinador faria
per comprendre realment l'algorisme.
En aquest punt, ara estem veient un node que conté 6,
i estem buscant el valor 6,
així que, de fet, hem trobat el node apropiat.
Trobem el valor 6 en el nostre arbre, i podem aturar la nostra recerca.
En aquest punt, depenent del que està passant,
podem dir, sí, hem trobat el valor 6, existeix al nostre arbre.
O bé, si estem planejant per inserir un node o fer alguna cosa, podem fer això en aquest moment.
>> Anem a fer un parell de recerques només per veure com funciona això.
Fem una ullada al que succeeix si anéssim a tractar de buscar el valor 10.
Si haguéssim de buscar el valor 10, que començaria a l'arrel.
Ens agradaria veure que 10 és més gran que 7, pel que ens mou a la dreta.
Arribàvem a les 9 i comparar 9 a les 10 i veure que el 9 és de fet inferior a 10.
Així que de nou, ens agradaria tractar de moure a la dreta.
Però en aquest punt, es donaria compte de que estem en un node nul.
No hi ha res allà. No hi ha res que el 10 ha de ser.
Aquí és on podem informar fracàs - que hi ha de fet no 10 en l'arbre.
I, finalment, passarem pel cas en què estem tractant de buscar una al arbre.
Això és similar al que passa si mirem cap amunt 10, excepte que en lloc d'anar a la dreta,
anirem a l'esquerra.
Comencem al 7 i veure que 1 és menor que 7, de manera que es mouen a l'esquerra.
Arribem a la 3 i veure que 1 és menor que 3, pel que de nou es tracta de moure a l'esquerra.
En aquest moment tenim un node nul, així que de nou podem informar fracàs.
>> Si vostè vol aprendre més sobre els arbres binaris,
hi ha un munt de divertits petits problemes que es poden fer amb ells.
Suggereixo practicar el dibuix d'aquests diagrames d'una per un
i seguint a través de tots els diferents passos,
perquè això vindrà en super manejable
no només quan estàs fent la codificació Huffman conjunt de problemes
sinó també en els futurs cursos -
aprenent a dibuixar aquestes estructures de dades i reflexionar sobre els problemes
amb llapis i paper o, en aquest cas, l'iPhone i el llapis.
>> En aquest punt, però, passarem a fer algunes pràctiques de codificació
i realment jugar amb aquests arbres binaris i veure.
Vaig a tornar al meu equip.
Per aquesta part de la secció, en lloc d'utilitzar CS50 CS50 Run o Spaces,
Vaig a utilitzar l'aparell.
>> Seguint amb l'especificació conjunt de problemes,
Veig que he d'obrir l'aparell,
anar a la carpeta de Dropbox, creï una carpeta anomenada Secció 7,
a continuació, creeu un fitxer anomenat binary_tree.c.
Aquí anem. Tinc l'aparell ja està obert.
Vaig a aixecar una terminal.
Vaig a anar a la carpeta de Dropbox, creeu un directori anomenat Secció 7,
i veure que és totalment buit.
Ara vaig a obrir binary_tree.c.
Molt bé. Aquí anem - arxiu buit.
>> Tornem a l'especificació.
L'especificació demana que creï una definició de tipus nou
per a un node d'arbre binari que conté valors int -
igual que els valors que ens va treure de la nostra diagramació abans.
Utilitzarem aquest text model typedef que hem fet aquí
que s'ha de reconèixer de Sèrie de problemes 5 -
si ho va fer de la manera taula hash de conquerir el programa corrector ortogràfic.
També ha de reconèixer a partir de la secció de la setmana passada
on parlem sobre les llistes enllaçades.
Tenim aquesta typedef d'un node d'estructura,
i li hem donat a aquest node struct aquest nom de node d'estructura per endavant
perquè després pugui referir-s'hi ja que voldrà tenir punters struct node
com a part de la nostra estructura, però després ens hem envoltat aquest -
o més aviat, tancat això - en un typedef
de manera que, més endavant en el codi, es pot fer referència a aquesta estructura com un node en lloc d'un node d'estructura.
>> Això serà molt similar a la definició de la llista simplement enllaçada que vam veure la setmana passada.
Per això, anem a començar per escriure el text model.
Sabem que hem de tenir un valor sencer,
així que posarem en valor int, i llavors, en lloc de tenir només un punter al següent element -
com ho vam fer amb simplement enllaçada llistes -
tindrem punters fill esquerre i dret.
Això és bastant simple també - nen struct node * left;
struct node i nen * dreta;. Cool.
Això sembla un bon començament.
Tornem a l'especificació.
>> Ara hem de declarar una variable de node * global per l'arrel d'un arbre.
Anem a fer d'aquest mundial igual que vam fer en el nostre primer punter llista enllaçada també global.
Això era perquè en les funcions que escrivim
nosaltres no hem de seguir passant al voltant d'aquesta arrel -
encara que ja veurem que si vull escriure aquestes funcions de manera recursiva,
pot ser que sigui millor ni tan sols ho passen al seu voltant com un mundial al primer lloc
i en lloc d'iniciar a nivell local en la seva funció principal.
Però, ho farem a nivell mundial per començar.
Un cop més, donarem un parell d'espais, i jo vaig a declarar una arrel * node.
Només per assegurar-se que no em deixa aquesta sense inicialitzar, em fixaré igual a null.
Ara, en la funció principal - el que anem a escriure molt ràpid aquí -
int main (int argc, const char * argv []) -
i jo vaig a començar a declarar la meva matriu argv com construïts només perquè jo sàpiga
que aquests arguments són els arguments que probablement no volen modificar.
Per modificar Probablement hauria d'estar fent còpies d'ells.
Vostè veurà això molt en el codi.
Està bé de qualsevol manera. Està bé deixar-lo com - ometre la construïts si ho desitja.
Em solen posar-lo en només perquè em recordo
que probablement no voleu canviar aquests arguments.
>> Com sempre, vaig a incloure aquesta línia return 0 al final del principal.
Aquí, vaig a iniciar el meu node arrel.
Tal com està ara mateix, tinc un punter que s'estableix en null,
el que apunta al no-res.
Per tal d'iniciar realment la construcció del node,
La primera vegada que assignar memòria per a ell.
Vaig a fer que en fer memòria al heap usant malloc.
Vaig a establir root igual al resultat de malloc,
i vaig a utilitzar l'operador sizeof per calcular la mida d'un node.
La raó per la qual ús node sizeof a diferència de, diguem,
fer alguna cosa com això - malloc (4 + 4 + 4) o malloc 12 -
és perquè vull que el meu codi sigui el més compatible possible.
Vull ser capaç de prendre aquest arxiu. C, compilar en l'aparell,
i després compilar en el meu 64-bit Mac -
o en una arquitectura completament diferent -
i vull que tot això funcioni de la mateixa.
>> Si estic fent suposicions sobre la mida de les variables -
la mida d'un int o la mida d'un punter -
llavors jo també estic fent suposicions sobre els tipus d'arquitectures
en què el meu codi es pot compilar amb èxit quan s'executa.
Sempre utilitzi sizeof en lloc de manualment sumant els camps struct.
L'altra raó és que també pot haver encoixinat que el compilador posa en l'estructura.
Encara que només sigui sumant els camps individuals no és una cosa que normalment es vol fer,
així, eliminar aquesta línia.
Ara, per inicialitzar realment aquest node arrel,
Vaig a haver de connectar els valors per a cada un dels seus camps.
Per exemple, per al valor sé que vull per inicialitzar a 7,
i per ara em vaig a posar el nen esquerra a ser nul
i el fill dret a ser també nul. Great!
Ho hem fet part de l'especificació.
>> L'especificació baix a la part inferior de la pàgina 3 em demana que creu més tres nodes -
una que conté 3, una que conté 6, i un amb 9 -
i després cablejar perquè es vegi exactament igual que el nostre diagrama d'arbre
que parlàvem anteriorment.
Farem això molt ràpidament aquí.
Vostè veurà realment ràpid que vaig a començar a escriure un munt de codi duplicat.
Vaig a crear un node * i vaig a trucar tres.
Vaig a posar igual a malloc (sizeof (node)).
Em posaré tres-> valor = 3.
Tres -> left_child = NULL; tres -> dreta _child = NULL; també.
Això es veu molt semblant a la inicialització de l'arrel, i això és exactament el que
Vaig a haver de fer si començar la inicialització de 6 i 9 també.
Ho faré molt ràpid aquí - en realitat, jo vaig a fer una mica de còpia i pega,
i assegurar-se que jo - bé.
Ara, he de copiar i puc seguir endavant i crear aquesta igual a 6.
Es pot veure que això pren temps i no és super-eficient.
En tan sols una mica, anem a escriure una funció que ho farà per nosaltres.
Vull substituir això amb un 9, reemplaçar amb un 6.
>> Ara tenim tots els nostres nodes creat i inicialitzat.
Tenim la nostra arrel igual a 7, o que conté el valor 7,
nostre node amb 3, el nostre node que conté 6, i el nostre node conté 9.
En aquest punt, tot el que hem de fer és cablejar tot.
La raó per la qual inicialitza tots els punters a null és només perquè m'asseguro que
Jo no tinc cap punter sense inicialitzar en allà per accident.
I també perquè, en aquest moment, només ha de connectar realment els nodes entre si -
als que en realitat estan connectats a - Jo no he d'anar a través i fer
Assegureu-vos que tots els nuls hi són en els llocs apropiats.
>> A partir de l'arrel, ho sé fill esquerre de l'arrel és 3.
Sé que fill dret de l'arrel és 9.
Després d'això, el fill únic que em queda per preocupar
és fill dret 3, que és 6.
En aquest punt, tot es veu molt bé.
Anem a eliminar algunes d'aquestes línies.
Ara tot es veu molt bé.
Tornem a les nostres especificacions i veure el que hem de fer a continuació.
>> En aquest punt, hem d'escriure una funció anomenada "conté"
amb un prototip del 'conté bool (int value).
I això inclou la funció tornarà true
si l'arbre apuntat per la variable arrel global
conté el valor que es passa a la funció i false en cas contrari.
Seguirem endavant i fer això.
Això serà exactament igual que la recerca que hem fet a mà en l'iPad una mica enrere.
Anem a tornar a augmentar una mica i desplaceu-vos cap amunt.
Posarem aquesta funció just a sobre de la nostra funció principal
de manera que no hem de fer cap tipus de prototips.
Per tant, conté bool (int value).
Aquí anem. Aquí està la nostra declaració repetitiu.
Només per assegurar-se que aquesta es compilarà,
Vaig a seguir endavant i només ho fa igual a tornar false.
En aquest moment aquesta funció simplement no fer res i sempre informen que
el valor que està buscant no està en l'arbre.
>> En aquest punt, és probablement una bona idea -
ja que he escrit un munt de codi i ni tan sols hem intentat provar encara -
per assegurar-se que tot es compila.
Hi ha un parell de coses que hem de fer per assegurar-se que això va a compilar.
En primer lloc, veure si hem estat utilitzant qualsevol de les funcions de les biblioteques que encara no hem inclosos.
Les funcions que hem utilitzat fins ara són malloc,
i també hem estat utilitzant aquest tipus - aquest tipus no estàndard anomenada "bool '-
que s'inclou en l'arxiu de capçalera bool estàndard.
Definitivament, volem incloure bool.h estàndard per al tipus bool,
i també volem incloure # lib.h estàndard per les biblioteques estàndard
que inclouen malloc i lliure, i tot això.
Per tant, allunyar la imatge, anem a deixar de fumar.
Tractarem d'assegurar-se que això realment va fer compilació.
Veiem que el fa, així que estem en el camí correcte.
>> Anem a obrir binary_tree.c nou.
Compila. Anem cap avall i assegureu-vos que inserim algunes trucades a la nostra funció conté -
només per assegurar-se que això és tot bé i bo.
Per exemple, quan vam fer algunes recerques en el nostre arbre abans,
hem tractat de buscar els 6 valors, 10 i 1, i sabíem que el 6 era al arbre,
10 no estava en l'arbre, i 1 no estava en l'arbre tampoc.
Anem a utilitzar aquestes trucades és una manera d'esbrinar si és o no
nostra funció conté està funcionant.
Per tal de fer això, vaig a utilitzar la funció printf,
i anem a imprimir el resultat de la crida a la contingui.
Em vaig a posar en una cadena "conté (% d) = perquè
anem a endollar el valor que anem a buscar,
i =% s \ n ", i usar això com la nostra cadena de format.
Només veurem - literalment imprimir a la pantalla -
el que sembla una trucada de funció.
Això no és realment la crida a la funció.
Això és només una cadena dissenyat per assemblar-se a una trucada de funció.
>> Ara, anem a connectar els valors.
Intentarem conté els dies 6,
i llavors, què farem aquí és utilitzar aquest operador ternari.
Anem a veure - inclou 6 - així que, ara que he contenia 6 i si conté 6 és cert,
la cadena que enviarem al caràcter de format% s
serà la cadena "true".
Anem a desplaçar-se durant una estona.
En cas contrari, volem enviar la cadena "false" si conté 6 retorna false.
Això és una mica maldestre aspecte, però m'imagino que bé podria il · lustrar
el que l'operador ternari sembla, ja que no l'he vist per un temps.
Aquesta serà una manera agradable, molt pràctic per saber si la nostra funció conté està funcionant.
Vaig a desplaçar-se de nou cap a l'esquerra,
i vaig a copiar i enganxar aquesta línia un parell de vegades.
Va canviar alguns d'aquests valors al voltant,
així que això serà 1, i això serà de 10.
>> En aquest punt tenim una funció conté agradable.
Tenim algunes proves, i anem a veure si funciona tot això.
En aquest punt hem escrit codi una mica més.
És hora de deixar de fumar i assegurar-se que tot el que encara compila.
Sortir fora, i ara intentarem fer arbre binari de nou.
Bé, sembla que tenim un error,
I tenim aquesta declarar explícitament la funció de biblioteca printf.
Sembla que hem d'anar i # include standardio.h.
I amb això, tot ha compilar. Estem tots bé.
Ara intentarem executar arbre binari i veure què passa.
Aquí estem. / Binary_tree,
i veiem que, com esperàvem -
perquè no han posat en pràctica conté, però,
o més aviat, acabem de posar en return false -
veiem que s'acaba de tornar false per a tots ells,
de manera que tot està funcionant en la seva major part bastant bé.
>> Anem a anar de nou i posar en pràctica en realitat conté en aquest punt.
Vaig a desplaçar-se cap avall, apropar, i -
recordi, l'algorisme que es va utilitzar va ser que vam començar en el node arrel
i després en cada node que trobem, fem una comparació,
i d'acord amb aquesta comparació que o moure el nen a l'esquerra oa la dreta nen.
Això semblarà molt similar al codi binari de recerca que hem escrit anteriorment en el terme.
Quan ens vam posar en marxa, sabem que volem mantenir en el node actual
que estem veient, i el node actual serà inicialitzat al node arrel.
I ara, seguirem endavant a través de l'arbre,
i recordar que la nostra condició de parada -
quan realment acabat amb l'exemple a mà -
Va ser llavors quan ens trobem amb un node nul,
no quan mirem a un nen nul,
sinó més bé quan realment mou a un node a l'arbre
i van trobar que estem en un node nul.
Anem a iterar fins act no és igual a null.
I què farem?
Anem a provar si (act -> valor value ==),
llavors sabem que en realitat hem trobat el node que estem buscant.
Així que aquí, podem tornar realitat.
En cas contrari, volem veure si el valor és menor que el valor.
Si el valor del node actual és menor que el valor que busquem,
mourem a la dreta.
Per tant, act act = -> right_child, i si no, anem a moure cap a l'esquerra.
act = act -> left_child;. Bastant simple.
>> És probable que reconèixer el llaç que es veu molt similar a la d'aquest
cerca binària anteriorment al terme, excepte llavors es tractava de mitjans baixa i alta.
En aquest cas, només hem de mirar a un valor actual,
així que és agradable i simple.
Ens assegurarem que el codi estigui funcionant.
Primer, assegureu-vos que compila. Sembla que ho fa.
Tractarem d'executar.
I, en efecte, imprimeix tot el que esperàvem.
Es troba a 6 al arbre, no troba 10 perquè 10 no està en l'arbre,
i no troba ja sigui perquè 1 1 No és també a l'arbre.
Cool stuff.
>> Molt bé. Tornem a la nostra especificació i veure el que es ve.
Ara, vol afegir nodes alguns més per al nostre arbre.
Vol afegir 5, 2 i 8, i assegureu-vos que conté el nostre codi
encara funciona com s'esperava.
Farem això.
En aquest punt, en lloc de fer que còpia molest i enganxar de nou,
escriurem una funció per crear realment un node.
Si ens desplacem cap avall fins arribar a principal, veiem que hem estat fent això
codi molt semblant una i altra vegada cada vegada que volem crear un node.
>> Anem a escriure una funció que en realitat va a construir un node per a nosaltres i el torna.
Vaig a dir-build_node.
Vaig a construir un node amb un valor determinat.
Acosta't aquí.
El primer que vaig a fer és crear un espai per al node en el munt.
Per tant, el node * n = malloc (sizeof (node)); n -> valor = valor;
i després aquí, jo només vaig a inicialitzar tots els camps per als valors adequats.
I al final, tornarem a la nostra node.
Molt bé. Una cosa a tenir en compte és que aquesta funció aquí
tornarà un punter a la memòria que ha estat assignada per munt.
El millor d'això és que aquest node ara -
hem de declarar en el munt perquè si ho declarat a la pila
no seríem capaços de fer en aquesta funció com aquesta.
Aquesta memòria es surtin de l'àmbit
i no seria vàlida si intentem accedir-hi més endavant.
Ja que estem declarant munt assignat per la memòria,
haurem de cuidar d'alliberar més tard
per al nostre programa no s'escapi cap record.
Hem estat en el qual safata per tota la resta en el codi
només per raons de simplicitat en el moment,
però si mai escriure una funció que té aquest aspecte
on tens - alguns en diuen un malloc o realloc interior -
vostè voldrà assegurar-se que vostè posa algun tipus de comentari per aquí que diu:
bé, ja saps, torna un node de heap assignat s'inicialitza amb el valor passat com.
I llavors vostè vol assegurar-se que vostè posa en una mena de nota que diu:
el picador d'alliberar la memòria retornada.
D'aquesta manera, si algú alguna vegada va i fa servir aquesta funció,
ells saben que qualsevol cosa que torni d'aquesta funció
en algun moment haurà de ser alliberat.
>> Suposant que tot està bé i bo aquí,
podem baixar al nostre codi i reemplaçar totes aquestes línies aquí
amb trucades a la nostra funció de node de generació.
Farem això molt ràpidament.
L'única part que no anem a substituir és aquesta part aquí baix
a la part inferior on realment cablejar els nodes perquè apunti a l'altra,
ja que no podem fer en la nostra funció.
Però, farem root = build_node (7); node * = build_node tres (3);
node * 6 = build_node (6); node * 9 = build_node (9);.
I ara, també volíem afegir nodes per -
node * 5 = build_node (5); node * = build_node vuit (8);
i el que era l'altre node? Anem a veure aquí. Hem volgut afegir també un 2 -
node * = build_node dos (2);.
Molt bé. En aquest punt, sabem que tenim el 7, el 3, el 9 i el 6
tots connectats de manera apropiada, però què passa amb el 5, el 8, i el 2?
Per mantenir tot en l'ordre apropiat,
sabem que el fill dret és tres 6.
Per tant, si anem a afegir als 5,
el 5 pertany també al costat dret de l'arbre dels quals 3 és l'arrel,
així com 5 pertany el fill esquerre de 6.
Podem fer això dient, sis -> left_child = cinc;
i després el 8 pertany com fill esquerre de 9, de manera que nou -> left_child = vuit;
i després 2 és el fill esquerre de 3, pel que podem fer això aquí - et -> left_child = dues;.
Si no acabava d'assistir a juntament amb això, li suggereixo que ho arribarà a tu mateix.
>> Molt bé. Anem a guardar aquest. Anem a sortir i assegurar-se que recopila,
i després podem afegir a les nostres trucades conté.
Sembla que tot segueix compila.
Anem a entrar i afegir en alguns conté trucades.
Un cop més, vaig a fer una mica de copiar i enganxar.
Ara anem a buscar a 5, 8 i 2. Molt bé.
Anem a fer de tot això es veu bé encara. Great! Guardar i sortir.
Ara farem, compilar, i ara anem a córrer.
A partir dels resultats, sembla que tot està funcionant molt bé i bé.
Great! Així que ara tenim a la nostra funció contains escrit.
Seguirem endavant i començar a treballar en la forma d'inserir nodes en l'arbre
ja que, com ho estem fent en aquest moment, les coses no són molt bonics.
>> Si ens remuntem a l'especificació,
ens demana que escrigui una funció anomenada inserir - de nou, tornant a bool
per saber si estem o no en realitat podria inserir el node a l'arbre -
i després el valor per inserir en l'arbre s'especifica com
l'únic argument a la nostra funció d'inserció.
Ens retornarà true si realment pot inserir el valor del node que conté l'arbre,
el que significa que, un, tenia suficient memòria,
i després dos, aquest node no existeix en l'arbre ja que -
Recordeu, nosaltres no tindrem valors duplicats a l'arbre, només per fer les coses simples.
Molt bé. Tornar al principi Codi.
Obre'l. Apropar una mica, a continuació, desplaceu-vos cap avall.
Anem a posar la funció d'inserció just a sobre de les contains.
Un cop més, serà anomenat insert bool (int value).
Dóna-li una mica més espai i, a continuació, per defecte,
posarem en return false al final.
Ara, en el fons, seguirem endavant i en comptes de construir manualment els nodes
principal en nosaltres mateixos i el cablejat fins al punt que l'un a l'altre com ho estem fent,
anem a confiar en la nostra funció d'inserció de fer això.
No anem a confiar en la nostra funció d'inserció per construir l'arbre sencer des de zero encara,
sinó que més aviat ens desfarem d'aquestes línies - ens tornarem comentar aquestes línies -
de construir els nodes 5, 8 i 2.
I en el seu lloc, anem a inserir trucades a la nostra funció d'inserció
per assegurar-se que que realment funciona.
Aquí anem.
>> Ara hem comentat aquestes línies.
Només tenim 7, 3, 9, i 6 en el nostre arbre en aquest punt.
Per assegurar-se que tot això està funcionant,
podem allunyar, fer el nostre arbre binari,
executar, i podem veure que conté ara ens està dient que tenim tota la raó -
5, 8, i 2 ja no estan en l'arbre.
Tornar enrere en el codi,
i com podem inserir?
Recordeu el que vam fer quan estàvem en realitat la inserció de 5, 8, i 2 prèviament.
Hem jugat a aquest joc Plinko on vam començar a l'arrel,
va baixar l'arbre per un per un
fins a trobar el buit apropiat,
i després per cable al node al punt apropiat.
Anem a fer el mateix.
Això és bàsicament com escriure el codi que fem servir en la funció contains
per trobar el punt on el node ha de ser,
i llavors només anem a inserir el node allà.
Anem a començar a fer això.
>> Així que tenim un node * act = root, només seguirem el codi conté
fins que ens trobem que no acaba de funcionar per a nosaltres.
Anirem a través de l'arbre, mentre que aquest element no és nul,
i si trobem que act valor és igual al valor que estem tractant d'inserir -
bo, aquest és un dels casos en què no vam poder inserir el node
en l'arbre perquè això vol dir que tenim un valor duplicat.
Aquí estem en realitat tornarà false.
Ara bé, si el valor actual és menor que el valor,
ara sabem que ens movem cap a la dreta
perquè el valor pertany a la meitat dreta de l'arbre act.
En cas contrari, mourem cap a l'esquerra.
Això és bàsicament la nostra funció contains aquí.
>> En aquest punt, un cop hàgim completat aquest bucle while,
nostre punter act estarà apuntant a null
si la funció no ha tornat.
Estem per tant tenir act al lloc on volem inserir el nou node.
El que queda per fer és construir realment el nou node,
que podem fer amb força facilitat.
Podem utilitzar la nostra super manejable i funció de node de generació,
i és una cosa que no hem fet abans -
nosaltres només tipus de donava per fet, però ara ho farem només per assegurar-se -
anem a provar per assegurar-se que el valor retornat pel nou node en realitat era
no és nul, perquè no vull començar a accedir a aquesta memòria si és nul.
Podem provar per assegurar-se que el nou node no és igual a null.
O per contra, només podem veure si realment és nul,
i si és nul, llavors només pot tornar false hora.
>> En aquest punt, hem de cablejar nou node en el seu lloc corresponent en l'arbre.
Si mirem cap enrere en la principal i en el qual en realitat eren el cablejat en els valors d'abans,
veiem que la manera com ho feien quan volien posar 3 al arbre
S'accedeix a que el fill esquerre de l'arrel.
Quan posem 9 al arbre, vam haver accedir al fill dret de l'arrel.
Havíem de tenir un punter a la matriu per tal de posar un nou valor en l'arbre.
Desplaçament d'una còpia de seguretat per inserir, això no funcionarà bastant aquí
perquè no tenim un punter pares.
El que vull ser capaç de fer és, en aquest punt,
comprovar el valor dels pares i veure - bé, caram,
si el valor dels pares és menor que el valor del corrent,
llavors fill dret dels pares ha de ser el nou node;
en cas contrari, fill esquerre del pare hauria de ser el node nou.
Però, no tenim aquest punter pare encara.
>> Per aconseguir-ho, estem en realitat haurà de seguir a mesura que avancem a través de l'arbre
i trobar el lloc adequat en el nostre bucle anterior.
Podem fer-ho de nou, desplaçant-se fins la part superior de la nostra funció d'inserció
i el seguiment d'una altra variable punter anomenat el pare.
Anem a posar igual a null inicialment,
i llavors cada vegada que passem per l'arbre,
anem a establir el punter pare perquè coincideixi amb el punter actual.
Establir pare igual act.
D'aquesta manera, cada vegada que anem a través,
anem a garantir que, com l'actual punter s'incrementa
el punter del pare que segueix - només un nivell més alt que l'actual punter en l'arbre.
Que tot es veu molt bé.
>> Crec que l'única cosa que anem a voler ajustar és construir aquest node nul retorn.
Per tal d'aconseguir construir node per tornar realitat amb èxit nul,
haurem de modificar el codi,
perquè aquí, mai hem provat per assegurar-se que malloc retorna un punter vàlid.
Així, si (n = NULL), llavors -
si malloc retorna un punter vàlid, llavors anem a inicialitzar;
en cas contrari, només haurem de tornar i que acabarà retornant un valor nul per a nosaltres.
Ara tot es veu molt bé. Ens assegurarem que això realment compila.
Feu arbre binari, i oh, tenim algunes coses que estan passant aquí.
>> Tenim una declaració implícita de la funció de construir node.
Un cop més, amb aquests compiladors, anem a començar a la part superior.
El que això vol dir és que estic trucant a construir node abans que jo he fet el va declarar.
Tornem al codi molt ràpid.
Desplaceu-vos cap avall i, per descomptat, la meva funció d'inserció es declara
per sobre de la funció de node de generació,
però estic tractant d'usar construir node dins del inserit.
Vaig a entrar i copiar - enganxar i després el node de generació manera funció aquí a la part superior.
D'aquesta manera, és d'esperar que funcioni. Anem a donar aquesta altra oportunitat.
Ara tot es compila. Tot està bé.
>> Però en aquest punt, no han cridat la nostra funció d'inserció.
Només sabem que compila, així que anirem i posar algunes trucades polz
Farem que en la funció principal.
En aquest sentit, comentada 5, 8, i 2,
i després no els cable fins aquí.
Farem algunes trucades per inserir,
i també utilitzarem el mateix tipus de coses que hem utilitzat
quan vam fer aquestes trucades printf per assegurar-se que tot el que t'ha inserit correctament.
Vaig a copiar i enganxar,
i conté en lloc que farem d'inserció.
I en comptes de 6, 10 i 1, que utilitzarem 5, 8 i 2.
Això hauria inserir 5, 8, i 2 en l'arbre.
Compilació. Tot està bé. Ara estem realment s'executarà el nostre programa.
>> Tot el torna false.
Així, 5, 8 i 2 no anar, i sembla que conté no els va trobar tampoc.
Què està passant? Anem a reduir.
El primer problema va ser que s'insereixen semblava tornar falsa,
i sembla que això és perquè ens vam anar al nostre call return false,
i que en realitat mai va tornar realitat.
Podem posar això en marxa.
El segon problema és que ara fins i tot si ho fem - guardar això, surti d'això,
fer funcionar de nou, han compilar, a continuació, executeu-lo -
veiem que alguna cosa més va passar aquí.
El 5, 8, i 2 mai es troben encara a l'arbre.
Llavors, què està passant?
>> Anem a fer una ullada a això en el codi.
A veure si podem resoldre això.
Comencem amb el pare no és nul.
Hem establert el punter actual és igual al punter arrel,
i treballarem nostre camí cap avall a través de l'arbre.
Si el node actual no és nul, llavors sabem que podem baixar una mica.
Hem creat el nostre punter pare per ser igual al punter actual,
comprovat el valor - que els valors són els mateixos que vam tornar falsa.
Si els valors són menors que ens mudem a la dreta;
en cas contrari, ens traslladem a l'esquerra.
A continuació, es construeix un node. Vaig a ampliar una mica.
I aquí, anem a tractar de cablejar els valors a ser el mateix.
Què està passant? A veure si possiblement Valgrind pot donar-nos una pista.
>> M'agrada utilitzar Valgrind Valgrind només perquè corre molt ràpid
i et diu si hi ha errors de memòria.
Quan correm Valgrind en el codi,
com poden veure afectats here--Valgrind./binary_tree--and dret entrar.
Ja veus que no tenia cap error de memòria, així que sembla que tot està bé fins ara.
Tenim algunes pèrdues de memòria, el que coneixem, perquè no som
passant a alliberar a qualsevol dels nostres nodes.
Intentarem executar GDB per veure el que realment està passant.
Farem gdb. / Binary_tree. Es arrencat bé.
Anem a posar un punt d'interrupció de la plaqueta.
Anem a córrer.
Sembla que mai ens diu en realitat inserció.
Sembla que el problema era que quan em vaig canviar aquí a principal -
totes aquestes trucades de printf conté -
En realitat, mai va canviar immediatament a trucar inserció.
Ara anem a donar-li una oportunitat. Anem a compilar.
Tot es veu bé. Ara anem a tractar d'executar, a veure què passa.
Molt bé! Tot es veu molt bé.
>> L'última cosa a considerar és, hi ha casos límit a aquesta inserció?
I resulta que, bé, el cas extrem que és sempre interessant pensar
És a dir, què passa si l'arbre està buit i es crida a aquesta funció d'inserció?
Funcionarà? Bé, anem a donar-li una oportunitat.
- Binary_tree c. -
La manera com anem a provar això, anirem a la nostra funció principal,
i en lloc de cablejat d'aquests nodes d'aquesta manera,
només comentarem tota la cosa,
i en comptes de nosaltres mateixos cablejant els nodes,
en realitat podem simplement seguir endavant i esborrar tot això.
Anem a fer tot el que una crida a inserir.
Per tant, farem - en comptes de 5, 8 i 2, anem a inserir 7, 3, i 9.
I després també voldrà inserir 6 també.
Guardar. Sortir. Fer arbre binari.
Tot compila.
Només es pot executar com està i veure què passa,
però també serà molt important per assegurar-se que
no tenim cap error de memòria,
ja que aquest és un dels nostres casos extrems que coneixem.
>> Anem a fer de funciona bé sota Valgrind,
que farem simplement executant Valgrind. / binary_tree.
Sembla que sí que tenen un error d'un context -
tenim aquesta fallada de segmentació.
¿Què ha passat?
Valgrind en realitat ens diu on és.
Reduir una mica.
Sembla que el que està succeint en la nostra funció d'inserció,
on tenim una lectura no vàlida del 4 a la mida d'inserció, la línia 60.
Anem a tornar enrere i veure el que està passant aquí.
Allunyar molt ràpid.
Vull per assegurar-se que no va fins la vora de la pantalla perquè puguem veure tot.
Tire que en una mica. Molt bé.
Desplaceu-vos cap avall, i el problema està aquí.
Què passa si ens posem mans i el nostre node actual ja és nul,
nostre node pare és nul, de manera que si mirem cap amunt a la part superior, a la dreta aquí -
si mai aquest bucle while executa realment
perquè el nostre valor actual és nul - nostra arrel és nul així act és nul -
llavors mai el nostre pare s'estableix en act oa un valor vàlid,
així, els pares també serà nul.
Hem de recordar per comprovar que
en el moment en què ens posem aquí, i començar a accedir valor dels pares.
Llavors, què passa? Bé, si el pare és nul -
if (pare == NULL) - llavors sabem que
no ha d'haver res en l'arbre.
Hem d'estar intentant inserir en l'arrel.
Podem fer això amb només ajustar l'arrel igual al nou node.
Llavors en aquest punt, que en realitat no volen passar per aquestes altres coses.
En canvi, aquí, podem fer bé una cosa-if-else,
o podem combinar tot aquí en una cosa,
però aquí només haurem de fer servir més i fer-ho d'aquesta manera.
Ara, anem a provar per assegurar-se que el nostre pare no és nul
abans d'aquesta realitat tractant d'accedir als seus camps.
Això ens ajudarà a evitar la fallada de segmentació.
Així doncs, deixar de fumar, reduir, compilar, executar.
>> No hi ha errors, però encara tenim un munt de pèrdues de memòria
perquè no alliberar a qualsevol dels nostres nodes.
Però, si anem per aquí i ens fixem en el nostre llistat,
veiem que, bé, sembla que tots els nostres inserits es torna true, la qual cosa és bo.
Els inserits són totes vertaderes,
i després les trucades conté apropiats, són certes.
>> Bona feina! Sembla que has escrit correctament inserit.
Això és tot el que tenim per a la especificació d'aquesta setmana Problema.
Un divertit desafiament és pensar en com vostè aniria a
i lliure de tots els nodes d'aquest arbre.
Podem fer un nombre de maneres diferents,
però ho deixo a vostè per experimentar,
i com un repte divertit, intentar assegurar-se que vostè pot assegurar-se que
que aquest informe Valgrind troba cap error i sense fuites.
>> Bona sort en el set d'aquesta setmana Huffman problema de codificació,
i ens veiem la propera setmana!
[CS50.TV]