[Powered by Google Translate] [Alt 7] [Lúide Compordach]
[Nate Hardison] [Ollscoil Harvard]
[Tá sé seo CS50.] [CS50.TV]
>> Fáilte go dtí Cuid 7.
Buíochas le Invest Sandy,
in ionad a bheith ag alt gnáth an tseachtain seo,
táimid ag déanamh an siúlóid-trí, tríd an alt ceisteanna.
Tá mé ag dul a bheith a leanas chomh maith leis an Fadhb Set 6 Sonraíocht,
agus ag dul trí gach ceann de na ceisteanna sna
A Alt d'alt Ceisteanna.
Má tá aon cheist agat,
le do thoil iar sin ar CS50 Pléigh.
>> Ceart go leor. A ligean ar tús a chur leis.
Ceart anois tá mé ag féachaint ar leathanach 3 den Sonraíocht Socraigh Fadhb.
Táimid ag dul chun tús a chur ar dtús ag caint faoi chrainn dénártha
ó tá sin go leor a bhaineann leis leagtha fhadhb na seachtaine seo -
an ionchódú Crann Huffman.
Ba é ceann de na struchtúir sonraí an chéad phléamar ar CS50 an eagar.
Cuimhnigh go bhfuil sraith sraith de ghnéithe -
go léir den chineál céanna - a stóráil ceart aice le gach eile i gcuimhne.
Má tá mé le sraith slánuimhir gur féidir liom a tharraingt ag baint úsáide as an stíl boscaí-uimhreacha-slánuimhreacha -
Ligean le rá go bhfuil mé 5 sa chéad bhosca, tá mé 7 sa dara fomhír,
ansin tá mé 8, 10, agus 20 sa bhosca deiridh.
Rudaí cuimhnigh, an dá go maith i ndáiríre faoi seo sraith
Tá go bhfuil muid an rochtain leanúnach-am chun aon ghné ar leith
sa réimse má tá a fhios againn a chur i innéacs.
Mar shampla, más mian liom a grab an eilimint tríú eagar -
ag innéacs 2 ag baint úsáide as ár gcóras innéacsú náid-bhunaithe -
Literally mé ach a dhéanamh ar ríomh simplí matamaiticiúla,
Hap chun an phoist sin ar an eagar,
tarraingt amach an 8 a stóráiltear ann,
agus tá mé go maith chun dul.
>> Ceann de na rudaí dona faoi seo sraith - gur labhair muid faoi
nuair a pléadh againn liostaí nasctha -
is é sin más mian liom a chur isteach gné isteach sa eagar,
Tá mé ag dul a dhéanamh ar roinnt aistriú timpeall.
Mar shampla, seo sraith dheis anseo
Is in ord sórtáilte - curtha in eagar in ord ardaitheach -
5, ansin 7, ansin 8, ansin 10, agus ansin 20 -
ach más mian liom a chur isteach an uimhir 9 isteach sa eagar,
Tá mé ag dul a bheith acu chun athrú roinnt de na gnéithe sin chun spás a dhéanamh.
Is féidir linn a tharraingt seo amach anseo.
Tá mé ag dul a bheith acu chun bogadh an 5, 7, agus ansin an 8;
a chruthú bearna nuair is féidir liom a chur ar an 9,
agus ansin an féidir 10 agus an 20 téigh go dtí an ceart an 9.
Tá sé seo de chineál ar pian mar gheall ar an staid is measa cás -
nuair a bhíonn muid ag chur isteach ceachtar ag tús nó ag deireadh
ar an raon, ag brath ar an gcaoi a bhfuil muid ag aistriú -
d'fhéadfadh muid suas go deireadh a bhfuil a athrú gach ceann de na heilimintí
go bhfuil muid a stóráil faoi láthair sa eagar.
>> Mar sin, cad é an bealach timpeall seo?
An bealach timpeall bhí leis seo ná chun dul go dtí ár modh liosta nasctha-más rud é -
in ionad a stóráil ar an 5 eilimintí, 7, 8, 10, agus 20 ar fad in aice le gach eile i gcuimhne -
cad a ionad raibh a bhí iad a stóráil de chineál ar cibé áit bhíomar ag iarraidh chun iad a stóráil
sna nóid liosta nasctha-a bhfuil mé ag tarraingt amach anseo, de chineál ar ad hoc.
Agus ansin ceangailte dúinn iad le chéile ag baint úsáide as na leideanna seo chugainn.
Is féidir liom a bheith pointeoir ó 5 go dtí an 7,
a pointeoir ón 7 go dtí an 8,
a pointeoir ón 8 go dtí an 10,
agus ar deireadh, ar pointeoir ó 10 go dtí an 20,
agus ansin pointeoir nialasach ag an 20 léiríonn go níl aon rud ar chlé.
An trádáil-uaire go bhfuil muid anseo
is é sin anois más mian linn a chur isteach an uimhir 9 i ár liosta curtha in eagar,
gach ní mór dúinn a dhéanamh ná a chruthú nód nua le 9,
sreang suas go pointe ar an áit is cuí,
agus ansin ath-sreang ar an 8 a chur in iúl síos go dtí an 9.
Sin go tapa go leor, ag glacadh leis fhios againn go díreach áit ar mhaith linn a chur isteach ar an 9.
Ach tá an trádáil-uaire mar mhalairt ar seo go atá caillte againn anois an rochtain leanúnach-am
le haon ghné ar leith in ár struchtúr sonraí.
Mar shampla, más mian liom a fháil ar an ghné ceathrú sa liosta seo nasctha,
Tá mé ag dul a bheith acu chun tús a chur ag an tús an-an liosta
agus ag obair ar mo bhealach a dhéanamh tríd comhaireamh nód-ar-nód go dtí go bhfaighidh mé an ceann ceathrú.
>> D'fhonn a fháil ar fheidhmíocht rochtain níos fearr ná liosta nasctha -
ach a choinneáil freisin ar roinnt de na sochair a bhí againn
i dtéarmaí ama isteach-ó liosta nasctha -
Tá crann dénártha ag dul go mór úsáid a bhaint as cuimhne beag níos mó.
Go háirithe, seachas díreach a bhfuil ceann amháin pointeoir i nód crann dhénártha -
cosúil leis an liosta nasctha-a dhéanann nód -
táimid ag dul go dtí an dara pointeoir a chur leis an nód crann dhénártha.
Seachas a bheith ach amháin pointeoir leis an ngné seo chugainn,
táimid ag dul a bheith acu pointeoir do leanbh ar chlé agus ar leanbh ceart.
>> A ligean ar pictiúr a tharraingt a fheiceáil cad Breathnaíonn iarbhír cosúil go.
Arís, tá mé ag dul chun úsáid na boscaí agus saigheada.
Beidh nód crann dhénártha tús a chur amach le bosca ach simplí.
Tá sé seo ag dul go bhfuil spás le haghaidh an luach,
agus ansin tá sé ag dul freisin go bhfuil spás le haghaidh an leanbh ar chlé agus an leanbh ceart.
Tá mé ag dul a lipéadú orthu anseo.
Táimid ag dul go bhfuil an leanbh ar chlé, agus ansin tá muid ag dul go bhfuil an leanbh ceart.
Tá bealaí éagsúla de seo a dhéanamh.
Uaireanta do spás agus áise,
Feicfidh mé a tharraingt i ndáiríre sé cosúil Tá mé ag déanamh anseo ar an ngrinneall
áit a bhfuil mé ag dul go bhfuil an luach ag an mbarr,
agus ansin an leanbh ar dheis ar an bun ar dheis,
agus an leanbh chlé ar bun ar chlé.
Ag dul ar ais go dtí an léaráid barr,
ní mór dúinn an luach ag an bharr,
ansin ní mór dúinn an pointeoir clé leanbh, agus ansin ní mór dúinn an pointeoir ceart-leanbh.
>> Sa Sonraíocht Fadhb Set,
labhairt linn faoi tharraingt nód go bhfuil luach 7,
agus ansin pointeoir chlé leanbh atá faoin margadh saothair, agus pointeoir ceart an leanbh go bhfuil Eolas faoin margadh saothair.
Is féidir linn a scríobh ceachtar NULLComment caipitil sa spás le haghaidh
is féidir an dá an leanbh ar chlé agus an leanbh ceart, nó linn a tharraingt seo Slais trasnánach
trí gach ceann de na boscaí a chur in iúl go bhfuil sé Eolas faoin margadh saothair.
Tá mé ag dul a dhéanamh go díreach toisc go simplí.
Cad a fheiceann tú anseo tá dhá bhealach diagramming nód crann an-simplí dhénártha
áit a bhfuil muid ar an luach 7 agus leideanna leanbh null.
>> An dara cuid dár cainteanna a shonrú maidir le conas le liostaí atá nasctha -
cuimhnigh, bhí againn ach a shealbhú ar an eilimint an-an chéad i liosta
chun cuimhneamh ar an liosta ar fad -
agus mar an gcéanna, le crann dhénártha, ní mór dúinn ach a shealbhú ar cheann pointeoir chuig an crann
chun smacht a choinneáil ar an struchtúr sonraí ar fad.
Tá an ghné seo speisialta an crann a dtugtar an nód fhréamh an chrainn.
Mar shampla, má tá an nód amháin - an nód ina bhfuil an luach 7
le leideanna clé agus an ceart-leanbh Eolas faoin margadh saothair -
Bhí an luach ach amháin i ár n-crann,
ansin bheadh ​​sé seo ar ár nód fhréamh.
Tá sé an tús an-ár n-crann.
Is féidir linn é seo a fheiceáil beag níos soiléire nuair a thosaíonn muid ag cur nóid níos mó ar ár crann.
Lig dom a tharraingt suas ar an leathanach nua.
>> Anois, táimid ag dul a tharraingt le crann go bhfuil 7 ag an fhréamh,
agus 3 istigh an linbh chlé, agus 9 taobh istigh an linbh ceart.
Arís, tá sé seo simplí go leor.
Táimid agam 7, tarraing nód do na 3, nód le 9,
agus tá mé ag dul a shocrú ar an pointeoir clé leanbh de 7 a chur in iúl leis an nód ina bhfuil 3,
agus an pointeoir ceart-leanbh leis an nód ina bhfuil 7 leis an nód ina bhfuil 9.
Anois, ní gá ó 3 agus 9 má tá aon leanaí,
táimid ag dul a shocrú go léir a n leideanna leanbh a bheith ar neamhní.
Anseo, comhfhreagraíonn an fhréamh ár crann leis an nód ina bhfuil an uimhir 7.
Is féidir leat a fheiceáil go más rud é go bhfuil gach ní mór dúinn a pointeoir leis an nód fréimhe,
is féidir linn siúl ansin tríd ár crann agus nóid leanaí araon rochtain a fháil ar -
araon 3 agus 9.
Níl gá le leideanna a choimeád ar bun do gach nód amháin ar an gcrann.
Ceart go leor. Anois, táimid ag dul go dtí ceann eile nód a chur leis an léaráid.
Táimid ag dul a chur ar nód ina bhfuil 6,
agus táimid ag dul a chur leis seo mar an leanbh ceart an nód ina bhfuil 3.
Chun é sin a dhéanamh, tá mé ag dul a scriosadh go pointeoir nialasach sa 3-nód
agus sreang sé suas go pointe leis an nód ina bhfuil 6. Ceart go leor.
>> Ag an bpointe seo, a ligean ar dul thar beagán de téarmaíochta.
Chun tús a chur, ar an gcúis go bhfuil seo ar a dtugtar crann dénártha go háirithe
is é sin tá sé dhá threo leanbh.
Tá cineálacha eile de chrainn a bhfuil leideanna leanbh níos mó.
Go háirithe, rinne tú a 'iarracht' i 5 Socraigh Fadhb.
Feicfidh tú faoi deara go bhfuil san iarracht, bhí tú 27 leideanna éagsúla do pháistí éagsúla -
ceann amháin do gach ceann de na 26 litreacha sa aibítir Béarla,
agus ansin an 27ú don apostrophe -
mar sin, go bhfuil cosúil le cineál crann.
Ach anseo, ós rud é tá sé dénártha, ní mór dúinn ach dhá threo leanbh.
>> Chomh maith leis an nód fhréamh gur labhair muid faoi,
tá muid freisin a chaitheamh ar fud an téarma 'leanaí.'
Cad a chiallaíonn sé ar cheann nód a bheith ina leanbh eile nód?
Ciallaíonn sé literally go bhfuil nód leanbh eile nód
más rud é go bhfuil nód eile ar cheann dá threo leanbh a leagtar a chur in iúl leis an nód.
Chun seo a chur i dtéarmaí níos nithiúla,
más rud é go 3 léirigh ag ceann de na leideanna leanbh de 7, ansin 3 leanbh de 7.
Más rud é go raibh muid chun an figiúr amach cad iad na páistí de 7 -
go maith, ní mór dúinn a fheiceáil go bhfuil 7 pointeoir go dtí 3 agus de pointeoir go 9,
bhfuil an oiread sin 9 agus 3 leanaí 7.
Naoi bhfuil aon leanaí mar go bhfuil a chuid leideanna leanbh nialasach,
agus tá 3 ach leanbh amháin, 6.
Six Tá aon leanaí toisc go bhfuil an dá de na leideanna faoin margadh saothair, a beidh orainn a tharraingt ceart anois.
>> Ina theannta sin, táimid ag caint freisin faoi na tuismitheoirí nód ar leith,
agus tá sé seo, mar gur mhaith leat bheith ag súil, a mhalairt ar an gcur síos seo linbh.
Tá gach nód ach tuismitheoir amháin - ionad dhá mar a d'fhéadfadh a bheith ag súil le daoine.
Mar shampla, is é an tuismitheoir 3 7.
Is é an tuismitheoir 9 chomh maith 7, agus is é an tuismitheoir de 6 3. Nach bhfuil i bhfad chun é.
Ní mór dúinn freisin téarmaí chun labhairt faoi seantuismitheoirí agus chlann clainne,
agus níos ginearálta a labhairt linn faoi na sinsear
agus sliocht nód ar leith.
An sinsear an nód - nó sinsear, in áit, de nód -
Tá gach ceann de na nóid a luíonn ar an gcosán ó na fréamhacha go dtí nód.
Mar shampla, má tá mé ag féachaint ar an 6 nód,
ansin tá na sinsear ag dul a bheith idir 3 agus 7.
An sinsear an 9, mar shampla, go bhfuil - má tá mé ag féachaint ar an 9 nód -
ansin tá an sinsear an 9 díreach 7.
Agus tá sliocht díreach ar an droim ar ais.
Más mian liom chun breathnú ar gach ceann de na sliocht 7,
ansin tá mé chun breathnú ar gach ceann de na nóid faoi bhun sé.
Mar sin, tá mé 3, 9, agus 6 ar fad mar sliocht 7.
>> Is é an téarma deireanach go beidh orainn labhairt faoi ar an gcoincheap sin de bheith ina sibling.
Siblíní - cineál a leanas chomh maith ar na téarmaí teaghlaigh -
Tá nóid atá ag an leibhéal céanna sa chrann.
Mar sin, tá 3 agus 9 siblíní mar go bhfuil siad ag an leibhéal céanna sa chrann.
Iad araon, tá an tuismitheoir céanna, 7.
Tá an 6 aon siblíní toisc nach bhfuil 9 bhfuil aon leanaí.
Agus nach bhfuil 7 bhfuil aon siblíní mar tá sé an fhréamh ár crann,
agus níl ach riamh 1 fréimhe.
Chun 7 go deartháireacha a bheith a bheadh ​​ann a bheith ina nód os cionn 7.
Ní bheadh ​​a bheith ina thuismitheoir 7, a bheadh ​​sa chás sin 7 a thuilleadh a bheith ar an fhréamh an crann.
Ansin, bheadh ​​an tuismitheoir nua de 7 chomh maith go bhfuil leanbh,
agus go mbeadh an leanbh sin a bheith ansin an sibling de 7.
>> Ceart go leor. Bogadh ar aghaidh.
Nuair a thosaigh muid ár plé na gcrann dénártha,
Labhair linn faoi conas a raibh muid ag dul chun iad a úsáid chun
a fháil buntáiste ar an dá eagair agus liostaí nasctha.
Agus is é an bealach táimid ag dul a dhéanamh go bhfuil an mhaoin a ordú.
Deirimid go bhfuil crann dénártha ordú, i gcomhréir leis an tsonraíocht,
más rud é do gach nód i ár crann, gach ceann dá shliocht ar an taobh clé -
an leanbh ar chlé agus ar gach ceann de na leanbh chlé ar sliocht -
Tá luachanna níos lú, agus gach ceann de na nóid ar dheis -
an leanbh ceart agus go léir an linbh ceart ar sliocht -
Tá nóid níos mó ná an luach an nód atá ann faoi láthair go bhfuil muid ag breathnú ar.
Díreach ar mhaithe le simplíocht, táimid ag dul a glacadh leis nach bhfuil aon nóid dhúbailt in ár crann.
Mar shampla, sa crann ní táimid ag dul chun déileáil leis an gcás
áit a bhfuil muid an luach 7 ag an fhréamh
agus ansin ní mór dúinn freisin ar an luach 7 in áiteanna eile sa chrann.
Sa chás seo, beidh tú faoi deara go bhfuil an crann d'ordaigh go deimhin.
Tá an luach 7 ag an fhréamh.
Gach rud ar an taobh clé de 7 -
má Cealaigh gach ceann de na marcanna beag anseo -
gach rud ar an taobh clé de 7 - an 3 agus an 6 -
Is iad na luachanna sin araon níos lú ná 7, agus gach rud ar dheis - a bhfuil ach an 9 -
níos mó ná 7.
>> Ní hé seo an crann ach d'ordaigh ina bhfuil na luachanna,
ach ligean ar tharraingt níos mó cúpla ceann acu.
Tá iarbhír a bunch iomlán de na bealaí gur féidir linn é seo.
Tá mé ag dul a úsáid shorthand ach a choinneáil ar rudaí simplí más rud é -
seachas ag tarraingt amach an t-iomlán boscaí-agus-saighde -
Tá mé ag dul díreach a tharraingt ar an líon agus saigheada iad a nascadh leis.
Chun tús, beidh muid ag scríobh ár crann bunaidh ach arís nuair a bhí againn 7, agus ansin 3,
agus ansin chuir 3 ar ais go dtí an ceart chun na 6,
agus bhí 7 leanbh ceart go raibh 9.
Ceart go leor. Cad é ar bhealach eile gur féidir linn a scríobh an crann?
In áit a bheith ag 3 an páiste na láimhe clé den 7,
d'fhéadfadh muid freisin an 6 bheith ar an leanbh na láimhe clé den 7,
agus ansin a 3 an páiste na láimhe clé den 6.
Bheadh ​​sé sin breathnú mar seo crann ar dheis anseo nuair a fuair mé 7,
ansin 6, ansin 3, agus 9 ar dheis.
Táimid freisin nach bhfuil a bheith 7 mar ár nód fhréamh.
D'fhéadfadh muid freisin 6 mar ár nód fhréamh.
Cad a bhfuil cuma mhaith?
Má táimid ag dul a choimeád ar bun leis an maoin de réir,
Tá gach rud ar an taobh clé de na 6 a bheith níos lú ná é.
Níl ach aon deis ann, agus sin 3.
Ach ansin an leanbh ceart 6, tá dhá féidearthachtaí.
Gcéad dul síos, d'fhéadfadh muid a bheith ar an 7 agus ansin an 9,
nó d'fhéadfadh muid a tharraingt air - mar tá mé ar tí é a dhéanamh anseo -
áit a bhfuil muid an 9 an leanbh ceart an 6,
agus ansin an 7 an leanbh na láimhe clé den 9.
>> Anois, nach bhfuil 7 agus 6 na luachanna ar chumas an fhréamh.
D'fhéadfadh muid freisin 3 a bheith ag an fhréamh.
Cad a tharlaíonn má tá 3 ag an fhréamh?
Anseo, rudaí a fháil le beagán suimiúil.
Níl a Trí aon luachanna a bhfuil níos lú ná é,
ionas go bhfuil taobh clé den iomlán an crann ag dul ach a bheith ar neamhní.
Níl ann dul a bheith rud ar bith ann.
Chun an ceart, d'fhéadfadh muid rudaí a liostú in ord ardaitheach.
D'fhéadfadh muid a bheith 3, ansin 6, ansin 7, ansin 9.
Nó, d'fhéadfaí linn a dhéanamh 3, ansin 6, ansin 9, ansin 7.
Nó, d'fhéadfaí linn a dhéanamh 3, ansin 7, ansin 6, ansin 9.
Nó, 3, 7 - i ndáiríre ní, ní féidir linn a dhéanamh ar 7 níos mó.
Sin ár n-rud amháin ann.
Féidir linn a dhéanamh 9, agus ansin as an 9 is féidir a dhéanamh 6 againn agus ansin 7.
Nó, is féidir linn a dhéanamh 3, ansin 9, ansin 7, agus ansin 6.
>> Rud amháin a d'aird a tharraingt anseo
go bhfuil na crainn beagán aisteach-lorg.
Go háirithe, má táimid ar an 4 crainn ar thaobh na láimhe deise -
Feicfidh mé ciorcal leo, anseo -
breathnú ar na crainn beagnach díreach cosúil le liosta nasctha.
Tá gach nód ach leanbh amháin,
agus mar sin nach bhfuil againn aon cheann de seo struchtúr crann-mhaith a fheicimid, mar shampla,
sa crann amháin aonair níos mó ná anseo ar thaobh na láimhe clé ag bun.
Tá na crainn ar a dtugtar i ndáiríre degenerate crainn dénártha,
agus beidh muid ag labhairt faoi seo níos mó sa todhchaí -
go háirithe má tá tú ag dul ar a ghlacadh cúrsaí eolaíochta eile ríomhaire.
Tá na crainn degenerate.
Nach bhfuil siad an-úsáideach mar gheall ar, go deimhin, lends, an struchtúr féin
chun lookup amanna cosúil leis sin de liosta nasctha.
Ní chuirimid a fháil leas a bhaint as an chuimhne breise - an pointeoir breise -
mar gheall ar ár struchtúr a bheith dona ar an mbealach seo.
Seachas dul ar aghaidh agus a tharraingt na crainn dénártha go bhfuil 9 ag an fhréamh amach,
a bhfuil an cás deireanach go mbeadh muid a bheith acu,
tá muid ina áit, ag an bpointe seo, ag dul chun labhairt le beagán faoi an téarma eile
go bhfuil muid úsáid a bhaint as nuair ag caint faoi chrainn, ar a dtugtar an airde.
>> Is é an airde crainn ar an achar ó na fréamhacha leis an nód is-i bhfad i gcéin,
nó in áit ar líon na leannlusanna go mbeadh ort a dhéanamh d'fhonn a
tús a chur as an fhréamh agus ansin deireadh suas ag an nód is-i bhfad i gcéin ar an crann.
Má táimid ag roinnt de na crainn go atá againn tarraingthe ar dheis anseo,
féidir linn a fheiceáil más rud é a chur orainn an crann sa chúinne barr ar chlé agus tús a chur againn ar an 3,
ansin ní mór dúinn a dhéanamh 1 Hap a fháil chun an 6, an dara Hap a fháil chun an 7,
agus hop tríú a fháil chun an 9.
Mar sin, is é an airde an chrainn 3.
Is féidir linn a dhéanamh ar an rud céanna le haghaidh na crainn eile atá leagtha amach leis an glas,
agus feicimid go bhfuil an airde de gach ceann de na crainn chomh maith go deimhin 3.
Sin cuid de cad a dhéanann siad degenerate -
go bhfuil a n-airde amháin níos lú ná líon na nóid sa crann ar fad.
Má táimid ar an crann eile go encircled le dearg, ar an láimh eile,
feicimid go bhfuil na nóid duille is-i bhfad i gcéin ar an 6 agus an 9 -
na duilleoga is iad sin na nóid nach bhfuil aon leanaí.
Mar sin, d'fhonn a fháil ón nód fréimhe ar cheachtar an 6 nó an 9,
ní mór dúinn a dhéanamh ar cheann Hap a fháil chun an 7 agus ansin hop an dara a fháil chun an 9,
agus mar an gcéanna, ach Hap dara ón 7 go dtí a fháil chun an 6.
Mar sin, is é an airde an chrainn thar anseo ach 2.
Is féidir leat dul ar ais agus a dhéanamh do gach ceann de na crainn eile pléite againn roimhe seo
ag tosú leis an 7 agus an 6,
agus beidh tú go bhfuil an airde de gach ceann de na crainn chomh maith 2.
>> An chúis tá muid ag caint faoi ordaigh crainn dénártha
agus tá sé cén fáth go bhfuil siad fionnuar mar is féidir leat cuardach a dhéanamh trí iad i
ar bhealach an-cosúil le cuardach thar eagar curtha in eagar.
Tá sé seo nuair a labhairt linn faoi ag fáil an am sin lookup feabhsaithe
níos mó ná an liosta simplí nasctha.
Le liosta nasctha - más mian leat a aimsiú gné ar leith -
tá tú is fearr ag dul a dhéanamh de chineál éigin cuardaigh líneach
nuair a dtosaíonn tú ag tús an liosta agus hop amháin-ar-amháin -
amháin nód amháin nód -
tríd an liosta ar fad go dtí go bhfaighidh tú is cuma cad tá tú ag cuardach do.
De bharr an méid, má tá tú crann dénártha a tá stóráil i bhformáid seo deas,
Is féidir leat a fháil i ndáiríre níos mó de cuardaigh dénártha ag dul ar
áit a bhfuil tú roinnt agus conquer
agus cuardach a dhéanamh tríd an leath iomchuí ar an crann ag gach céim.
A ligean ar a fheiceáil conas go n-oibríonn.
>> Má tá muid - arís, ag dul ar ais go dtí ár crann bunaidh -
tús a chur againn ag 7, ní mór dúinn 3 ar chlé, 9 ar dheis,
agus faoi bhun an 3 táimid tar éis an 6.
Má theastaíonn uainn chun cuardach a dhéanamh ar an líon 6 sa crann, ba mhaith linn tús a chur ag an fhréamh.
Ba mhaith linn comparáid a dhéanamh idir an luach táimid ag lorg, a rá 6,
leis an luach atá stóráilte sa an nód sin tá muid ag lorg faoi láthair ag, 7,
a aimsiú go bhfuil 6 go deimhin, níos lú ná 7, mar sin ba mhaith linn bogadh ar chlé.
Más rud é go raibh an luach de 6 níos mó ná 7, ba mhaith linn a bheith ar athraíodh a ionad in ionad na láimhe deise.
Ós rud é a fhios againn go - mar gheall ar an struchtúr ár crann dhénártha ordaigh -
gach ceann de na luachanna níos lú ná 7 ag dul a stóráil ar an taobh clé de 7,
níl aon ghá a bodhraigh fiú breathnú tríd an taobh dheis an chrainn.
Chomh luath agus táimid ag bogadh ar chlé agus táimid anois ag an nód ina bhfuil 3,
is féidir linn a dhéanamh i gcomparáid céanna arís nuair a chur i gcomparáid againn ar an 3 agus an 6.
Agus feicimid cé go 6 - níos mó ná 3, - an luach táimid ag lorg
is féidir linn dul go dtí an taobh dheis de na nód ina bhfuil 3.
Níl aon taobh clé anseo, agus mar sin d'fhéadfadh muid a bheith neamhaird sin.
Ach tá a fhios againn ach go bhfuil toisc go bhfuil muid ag breathnú ar an crann féin,
agus is féidir linn a fheiceáil go bhfuil an crann aon leanaí.
>> Tá sé freisin éasca go leor chun breathnú suas 6 sa crann má tá ag éirí linn é féin mar dhaoine,
ach a ligean ar leanúint leis an bpróiseas meicniúil cosúil le ríomhaire a bheadh ​​a dhéanamh
a thuiscint i ndáiríre an algartam.
Ag an bpointe seo, táimid ag lorg anois ag nód go bhfuil 6,
agus táimid ag lorg an luach 6,
mar sin, go deimhin, tá muid fuair an nód cuí.
Fuair ​​muid an luach 6 in ár crann, agus is féidir linn stop a chur ar ár cuardaigh.
Ag an bpointe seo, ag brath ar cad atá ar siúl,
féidir linn a rá, tá, ní mór dúinn a fuair an luach 6, tá sé ann in ár crann.
Nó, má tá muid ag pleanáil a chur isteach nód nó rud éigin a dhéanamh, is féidir linn é sin a dhéanamh ag an bpointe seo.
>> Déanaimis a dhéanamh lookups cúpla níos mó ach a fheiceáil conas a oibríonn seo.
Ligean ar breathnú ar cad a tharlaíonn má bhí againn chun iarracht a dhéanamh agus breathnú ar an luach 10 suas.
Más rud é go raibh muid chun breathnú suas ar an luach 10, ba mhaith linn tús a chur ag an fhréamh.
Ba mhaith linn a fheiceáil go bhfuil 10 níos mó ná 7, mar sin ba mhaith linn bogadh ar dheis.
Ba mhaith linn a fháil chun an 9 agus 9 i gcomparáid leis an 10 agus a fheiceáil go bhfuil 9 go deimhin, níos lú ná 10.
Mar sin, arís, ba mhaith linn iarracht a aistriú go dtí an ceart.
Ach ag an bpointe seo, ba mhaith linn faoi deara go bhfuil muid ag nód null.
Níl aon rud ann. Níl aon rud nuair ba chóir na 10 a bheith.
Tá sé seo nuair is féidir linn a thuairisciú teip - nach bhfuil go deimhin aon 10 sa chrann.
Agus ar deireadh, a ligean ar dul tríd an cás nuair a bhíonn muid ag iarraidh chun breathnú suas 1 sa chrann.
Tá sé seo cosúil le cad a tharlaíonn má táimid suas 10, ach amháin in ionad dul go dtí an ceart,
táimid ag dul chun dul go dtí an taobh clé.
Tús a chur againn ar an 7 agus a fheiceáil go bhfuil 1 níos lú ná 7, mar sin againn bogadh ar chlé.
A fháil muid go dtí an 3 agus a fheiceáil go bhfuil 1 níos lú ná 3, mar sin arís déanaimid ár ndícheall chun bogadh ar chlé.
Ag an bpointe seo ní mór dúinn a nód Eolas faoin margadh saothair, mar sin arís gur féidir linn a thuairisciú teip.
>> Más mian leat níos mó a fhoghlaim faoi chrainn dhénártha,
tá a bunch iomlán de na fadhbanna beag spraoi gur féidir leat a dhéanamh leo.
I le fios ag cleachtadh a tharraingt amach as na léaráidí aon-le-duine
agus tar éis trí gach ceann de na céimeanna éagsúla,
mar go mbeidh an teacht i Super-handy
ní amháin nuair a bhíonn tú ag déanamh an leagan Huffman fhadhb ionchódú
ach freisin i gcúrsaí amach anseo -
ach ag foghlaim conas a tharraingt amach na struchtúir sonraí agus smaoineamh tríd na fadhbanna
le peann agus páipéar nó, sa chás seo, iPad agus stylus.
>> Ag an bpointe seo áfach, táimid ag dul chun bogadh ar aghaidh a dhéanamh ar roinnt cleachtas códála
agus spraoi i ndáiríre leis na crainn dénártha agus a fheiceáil.
Tá mé ag dul chun dul ar ais go dtí mo ríomhaire.
Chun an chuid seo den alt seo, seachas úsáid a bhaint CS50 Rith nó CS50 Spásanna,
Tá mé ag dul a bhaint as an fearas.
>> Tar éis chomh maith leis an tsonraíocht Socraigh Fadhb,
Feicim go bhfuil mé ceaptha a oscailt suas an fearas,
téigh go dtí mo fillteán Dropbox, a chruthú fillteán a dtugtar Alt 7,
agus a chruthú ansin comhad a dtugtar binary_tree.c.
Anseo théann muid. Tá mé an fearas oscailte cheana féin.
Tá mé ag dul a tharraingt suas teirminéil.
Tá mé ag dul chun dul go dtí an fillteán Dropbox, a dhéanamh ar eolaire ar a dtugtar hAlt 7,
agus a fheiceáil tá sé go hiomlán folamh.
Anois, tá mé ag dul a oscailt suas binary_tree.c.
Ceart go leor. Seo muid réidh - comhad folamh.
>> A ligean ar dul ar ais chuig an tsonraíocht.
Iarrann an tsonraíocht a chruthú sainmhíniú cineál nua
le haghaidh nód crann dénártha ina bhfuil luachanna slánuimhir -
díreach cosúil leis na luachanna a tharraing muid amach in ár diagramming roimh.
Táimid ag dul a úsáid boilerplate Rialú an go atá déanta againn ar dheis anseo
gur chóir duit a aithníonn ó 5 Set Fadhb -
má rinne tú ar an mbealach tábla hash de chlár conquering an speller.
Ba chóir duit aitheantas a thabhairt freisin sé ón tseachtain seo caite alt
nuair a labhair muid faoi liostaí nasctha.
Táimid iontach fuair an Rialú an de nód struct,
agus tá tugtha againn an nód struct seo ainm an nód struct roimh ré
ionas gur féidir linn a tharchur ansin chun é ó beidh orainn ag iarraidh a bheith leideanna nód struct
mar chuid dár struct, ach tá muid encircled ansin é seo -
nó in áit, faoi iamh leis seo - ar Rialú an
ionas go mbeidh, ina dhiaidh sin sa chód, is féidir linn a tharchur chuig an struct mar nód ach in ionad nód struct.
>> Tá sé seo ag dul a bheith an-chosúil leis an sainmhíniú ar liosta ina n-aonar-nasctha go chonaic muid an tseachtain seo caite.
Chun seo a dhéanamh, a ligean ar tús a chur díreach ag scríobh amach an boilerplate.
Tá a fhios againn go bhfuil muid go bhfuil luach slánuimhir,
sin beidh orainn a chur i luach slánuimhir, agus ansin in ionad a bheith amháin pointeoir leis an ngné seo chugainn -
mar a rinne muid leis ina n-aonar-nasctha liostaí -
táimid ag dul go bhfuil leideanna leanbh chlé agus ar dheis.
Sin simplí go leor freisin - leanbh nód struct * chlé;
agus struct nód * leanbh ceart. Cool.
Go Breathnaíonn an nós tús maith go leor.
A ligean ar dul ar ais chuig an tsonraíocht.
>> Anois, ní mór dúinn a dhearbhú athróg * domhanda nód chun an fhréamh an chrainn.
Táimid ag dul a dhéanamh ar an domhanda go díreach mar a rinne muid pointeoir den chéad uair i ár liosta nasctha chomh maith domhanda.
Bhí sé seo ionas go mbeidh na feidhmeanna a scríobh againn
nach bhfuil againn a choinneáil ag dul timpeall an fhréamh -
cé go beidh orainn a fheiceáil gur mian má dhéanann tú a scríobh na feidhmeanna go hathchúrsach,
d'fhéadfadh sé a bheith níos fearr chun Ní pas fiú é thart mar domhanda sa chéad áit
agus thúsú ionad go háitiúil i do fheidhm is mó.
Ach, beidh orainn é a dhéanamh ar fud an domhain a thosú.
Arís, beidh orainn a thabhairt cúpla spásanna, agus mé ag dul a dhearbhú fhréamh * nód.
Just a dhéanamh cinnte nach bhfuil mé seo a fhágáil neamhuimhriúil, tá mé ag dul a shocrú cothrom le nialasach.
Anois, ar an fheidhm is mó - a beidh muid ag scríobh i ndáiríre go tapa ar dheis anseo -
slánuimhir is mó (slánuimhir argc, CONST ruabhric * argv []) -
agus tá mé ag dul chun tús a dhearbhú mo sraith argv mar CONST ach sin a bhfuil a fhios agam
go bhfuil na hargóintí argóint go bhfuil mé dócha nach bhfuil ag iarraidh a mhodhnú.
Más mian liom a mhodhnú iad a ba chóir dom is dócha a bheith ag déanamh cóipeanna díobh.
Feicfidh tú a fheiceáil seo go leor i cód.
Tá sé go breá bíodh bealach. Tá sé go breá é a fhágáil mar atá - omit an CONST más mhaith leat.
Liom a chur de ghnáth é i díreach ionas go mbeidh mé i gcuimhne dom féin
go bhfuil mé dócha nach bhfuil ag iarraidh a mhodhnú leis na hargóintí.
>> Mar is gnáth, tá mé ag dul a chur san áireamh an tuairisceán seo 0 líne ag deireadh na is mó.
Anseo, beidh mé thúsú mo nód fréimhe.
Mar a sheasann sé ceart anois, tá fuair mé ar pointeoir go s a leagtar chun nialasach,
mar sin tá dírithe ag rud ar bith.
D'fhonn tús a chur iarbhír a thógáil an nód,
Is gá dom ar dtús cuimhne a dháileadh le haghaidh é.
Tá mé ag dul a dhéanamh go trí cuimhne ar an gcarn ag baint úsáide as malloc.
Tá mé ag dul a leagan fhréamh ar cóimhéid leis an toradh malloc,
agus tá mé ag dul a bhaint as an oibreoir Is uimhir a ríomh an méid nód.
An chúis go n-úsáideann mé Is uimhir nód i gcomparáid le, rá,
ag déanamh rud éigin mar seo - malloc (4 + 4 +4) nó malloc 12 -
Is é mar ba mhaith liom mo cód a bheith ag luí agus is féidir.
Ba mhaith liom a bheith in ann seo a ghlacadh. C comhad, a thiomsú ar an fearas,
agus le chéile ansin é ar mo 64-giotán Mac -
nó ar ailtireacht go hiomlán difriúil -
agus ba mhaith liom seo go léir a bheith ag obair mar an gcéanna.
>> Má tá mé ag boinn tuisceana a dhéanamh faoi mhéid na n-athróg -
ar mhéid slánuimhir nó an méid de pointeoir -
ansin tá mé ag déanamh chomh maith boinn tuisceana faoi na cineálacha ailtireachtaí
ar ar féidir le mo cód a thiomsú go rathúil nuair a ritheann.
A úsáid i gcónaí o, seachas de láimh achoimre na réimsí struct.
Is é an chúis eile go bhféadfadh sé go mbeadh stuáil go gcuireann an tiomsaitheoir isteach struct.
Ní Fiú achoimre ach na réimsí ar leith rud éigin gur mian leat de ghnáth a dhéanamh,
mar sin, scrios an líne sin.
Anois, a thúsú i ndáiríre an nód fréimhe,
Tá mé ag dul a bheith acu chun an breiseán i luachanna do gach ceann dá réimsí éagsúla.
Mar shampla, le haghaidh luach a fhios agam ba mhaith liom a thúsú go 7,
agus anois tá mé ag dul a shocrú ar an leanbh chlé a bheith ar neamhní
agus an leanbh ceart chun a bheith chomh maith faoin margadh saothair. Great!
Táimid tar éis a rinneadh an chuid sin den spec.
>> Iarrann an tsonraíocht síos ag bun leathanach 3 dom a chruthú trí níos mó nóid -
ceann ina bhfuil 3, ceann ina bhfuil 6, agus ceann a bhfuil 9 -
agus sreang ansin iad suas mar sin tá sé díreach cosúil ár n-léaráid chrainn
go raibh muid ag caint faoi roimhe sin.
Déanaimis é sin a dhéanamh go tapa go leor anseo.
Feicfidh tú a fheiceáil i ndáiríre go tapa go bhfuil mé ag dul go dtí tús a scríobh a bunch de chód ndúblach.
Tá mé ag dul a chruthú * nód agus mé ag dul a ghlaoch air trí.
Tá mé ag dul a leagan cothrom é a malloc (deachúlach (nód)).
Tá mé ag dul a shocrú trí-> luach = 3.
Trí -> left_child = NULLComment; trí -> ceart _child = NULLComment; chomh maith.
Go Breathnaíonn go leor cosúil leis initializing an fhréamh, agus sin go díreach cad
Tá mé ag dul a bheith le déanamh má thosaíonn mé initializing 6 agus 9 chomh maith.
Feicfidh mé é sin a dhéanamh i ndáiríre go tapa anseo - i ndáiríre, tá mé ag dul a dhéanamh cóip beag agus greamaigh,
agus a chinntiú go I - ceart go leor.
Anois, tá mé fuair sé a chóipeáil agus is féidir liom dul ar aghaidh agus is ionann le 6 leagan síos.
Is féidir leat a fheiceáil go dtarlaíonn seo awhile agus nach bhfuil Super-éifeachtach.
I beagán ach beagán, beidh muid ag scríobh feidhm a dhéanamh dúinn.
Ba mhaith liom a chur in ionad seo le 9, in ionad go le 6.
>> Anois, tá muid fuair i ngach ceann dár nóid cruthaíodh agus initialized.
Táimid iontach fuair ár root leagtar cothrom le 7, nó ina mbeidh an luach 7,
ár n-nód ina bhfuil 3, ár n-nód ina bhfuil 6, agus ár nód ina bhfuil 9.
Ag an bpointe seo, tá gach ní mór dúinn gach rud a dhéanamh sreang suas.
Is é an chúis initialized mé go léir na leideanna nialasach go díreach mar sin a dhéanamh mé cinnte go
Ní féidir liom aon leideanna neamhuimhriúil ann de thimpiste.
Agus freisin ós rud é, ag an bpointe seo, tá mé ach chun nascadh i ndáiríre an nóid le gach ceann eile -
leis na cinn a bhíonn siad nasctha iarbhír - ní dóigh liom go bhfuil dul trí agus a dhéanamh
cinnte go bhfuil na nulls ann sna háiteanna cuí.
>> Ag tosú ag an fhréamh, tá a fhios agam go bhfuil an fhréamh leanbh chlé 3.
Tá a fhios agam go bhfuil an fhréamh leanbh ceart 9.
Tar éis sin, an leanbh amháin eile go bhfuil mé fágtha a bheith buartha faoi
Is leanbh ceart 3, ar a bhfuil 6.
Ag an bpointe seo, tá sé go léir maith go leor.
Beidh muid a scriosadh cuid de na línte.
Anois Breathnaíonn gach rud maith go leor.
A ligean ar dul ar ais go dtí ár sonraíocht agus féach cad atá againn a dhéanamh amach romhainn.
>> Ag an bpointe seo, ní mór dúinn a scríobh le feidhm a dtugtar 'tá'
le fréamhshamhail 'tá bool (slánuimhir luach)'.
Agus tá an fheidhm seo ag dul ar ais fíor
má chuir an crann ag ár athróg fréimhe domhanda
Tá an luach a ritheadh ​​an fheidhm agus bréagach ar shlí eile.
Lig dul ar aghaidh agus é sin a dhéanamh.
Tá sé seo ag dul a bheith díreach cosúil leis an lookup go raibh muid de láimh ar an iPad ach beagán ó shin.
Let s súmáil isteach ar ais i beagán agus scrollaigh suas.
Táimid ag dul a chur ar an fheidhm sin ceart os cionn ár n-phríomhfheidhm
ionas nach bhfuil againn a dhéanamh ar aon saghas prototyping.
Mar sin, tá bool (slánuimhir luach).
Tá muid ag dul. Níl ár dearbhú boilerplate.
Just a dhéanamh cinnte go gcuirfidh sé seo le chéile,
Tá mé ag dul chun dul ar aghaidh agus díreach tar éis é a leagtar cothrom a thabhairt ar ais bréagach.
Ceart anois an fheidhm ní bheidh a dhéanamh ach rud ar bith agus i gcónaí a thuairiscíonn
nach bhfuil an luach sin tá muid ag lorg ar an gcrann.
>> Ag an bpointe seo, is dócha go bhfuil smaoineamh maith -
ós rud é tá muid i scríbhinn a bunch iomlán de chód agus nach bhfuil iarracht déanta againn fiú a thástáil go fóill -
chun a chinntiú go Cuireann sé ar fad.
Tá cúpla rudaí atá againn a dhéanamh chun a chinntiú go mbeidh an chéile i ndáiríre.
Gcéad dul síos, a fheiceáil má tá muid ag baint úsáide as aon fheidhmeanna in aon leabharlanna nach bhfuil san áireamh againn go fóill.
Is iad na feidhmeanna atá againn a úsáid go dtí seo malloc,
agus ansin tá muid freisin ag baint úsáide as an gcineál seo - an cineál neamhchaighdeánach ar a dtugtar 'bool' -
atá san áireamh sa chomhad header caighdeánach bool.
Ba mhaith linn cinnte a chur san áireamh bool.h caighdeánach don chineál bool,
agus ba mhaith linn freisin a chur san áireamh # lib.h caighdeánach do na leabharlanna caighdeán
go n-áiríonn malloc, agus saor in aisce, agus gach ceann de sin.
Mar sin, súmáil amach, táimid ag dul a scor.
Déanaimis iarracht a dhéanamh cinnte go raibh seo i ndáiríre thiomsú.
Feicimid go ndéanann sé, mar sin táimid ar an mbóthar ceart.
>> A ligean ar oscailt suas binary_tree.c arís.
Cuireann sé. A ligean ar dul síos agus a dhéanamh cinnte go bhfuil muid roinnt glaonna isteach go dtí ár fheidhm atá -
ach chun a chinntiú go bhfuil gach maith agus go maith.
Mar shampla, nuair a rinne muid roinnt lookups in ár crann roimhe sin,
rinneamar iarracht chun breathnú suas an 6 luachanna, 10, agus 1, agus bhí a fhios againn go raibh 6 sa gcrann,
Ní raibh 10 sa crann, agus ní raibh 1 sa crann ach an oiread.
A ligean ar úsáid a bhaint as na glaonna sampla mar bhealach chun an figiúr amach an bhfuil nó nach
Is é ár n-Tá feidhm oibre.
Chun é sin a dhéanamh, tá mé ag dul a bhaint as an fheidhm printf,
agus táimid ag dul a phriontáil amach mar thoradh ar an glaoch chun Tá.
Tá mé ag dul a chur i teaghrán bhfuil "(% d) más rud gheall
táimid ag dul chun an breiseán i luach go bhfuil muid ag dul a lorg,
agus =% s \ n "agus sin a úsáid mar ár teaghrán formáide.
Táimid ag dul ach a fheiceáil - literally phriontáil amach ar an scáileán -
cad is cuma an glaoch fheidhm.
Ní hé seo i ndáiríre an glaoch fheidhm.
Is é seo ach teaghrán a ceapadh chun breathnú cosúil le glao feidhm.
>> Anois, táimid ag dul chun an breiseán i luachanna.
Táimid ag dul go bhfuil iarracht ar 6,
agus ansin cad táimid ag dul a dhéanamh anseo sin a úsáid oibreoir trínártha.
A ligean ar a fheiceáil - tá 6 - mar sin, anois tá mé atá 6 agus má tá 6 Is fíor,
an teaghrán go bhfuil muid ag dul a sheoladh chuig carachtar formáide% s
ag dul a bheith an teaghrán "fíor".
Ligean ar scrollaigh thar beagán.
Seachas sin, ba mhaith linn a sheoladh chuig an teaghrán "bréagach" i gcás ina 6 tuairisceáin bhréagacha.
Tá sé seo beagán goofy-lorg, ach figiúr mé d'fhéadfadh mé chomh maith le léiriú
conas mar a bhreathnaíonn an t-oibreoir trínártha cosúil ós rud é nach bhfuil feicthe againn do awhile.
Beidh sé seo ina deas, ar bhealach áisiúil chun an figiúr amach más rud é go bhfuil ár Tá feidhm oibre.
Tá mé ag dul a scrollbharra ais go dtí an taobh clé,
agus tá mé ag dul a chóipeáil agus a ghreamú an líne seo cúpla uair.
Athraigh sé roinnt de na luachanna timpeall,
mar sin tá sé seo ag dul a bheith 1, agus tá sé seo ag dul a bheith 10.
>> Ag an bpointe seo tá muid fuair deas Tá feidhm.
Táimid iontach fuair roinnt tástálacha, agus beidh orainn a fheiceáil más rud é seo gach obair.
Ag an bpointe seo tá muid i scríbhinn cód roinnt níos mó.
Am a scor amach agus a chinntiú go Tiomsaíonn gach rud go fóill.
Scoir amach, agus anois a ligean ar iarracht a dhéanamh crann dhénártha arís.
Bhuel, tá sé cosúil tá muid fuair earráid,
agus tá muid fuair an dearbhú go sainráite an fheidhm leabharlainne printf.
Breathnaíonn sé cosúil is gá dúinn dul i agus # standardio.h san áireamh.
Agus leis sin, ba chóir gach rud a thiomsú. Táimid go léir go maith.
Anois, a ligean iarracht a reáchtáil crann dhénártha agus féach cad a tharlaíonn.
Anseo tá muid,. / Binary_tree,
agus feicimid go, mar a súil againn -
toisc nach mór dúinn i bhfeidhm atá go fóill,
nó in áit, tá muid a chur díreach ar ais bréagach -
feicimid go tá a sheoladh ar ais díreach bréagach ina dtaobh go léir,
mar sin tá go léir ag obair don chuid is mó go cothrom go maith.
>> A ligean ar dul ar ais i agus ar ndóigh, i bhfeidhm ina ag an bpointe seo.
Tá mé ag dul chun scrollú síos, súmáil isteach, agus -
cuimhnigh, ba é an algartam a úsáid againn gur thosaigh muid ag an nód fhréamh
agus ansin ag gach nód go bhfuil muid bhíonn, a dhéanann muid comparáid,
agus atá bunaithe ar an chomparáid muid ag bogadh ceachtar an leanbh clé nó an leanbh ceart.
Tá sé seo ag dul chun breathnú an-chosúil leis an gcód cuardaigh dénártha a scríobh againn níos luaithe sa téarma.
Nuair a thosaíonn muid amach, tá a fhios againn gur mhaith linn a shealbhú ar an nód atá ann faoi láthair
go bhfuil muid ag breathnú ar, agus is é an nód atá ann faoi láthair ag dul a bheith initialized leis an nód fhréamh.
Agus anois, tá muid ag dul a choinneáil ag dul tríd an crann,
agus cuimhnigh go bhfuil ár staid stopadh -
nuair a d'oibrigh muid go hiarbhír tríd an sampla de láimh -
a bhí nuair a bhíonn muid nód Eolas faoin margadh saothair,
ní nuair a d'fhéach muid ag leanbh faoin margadh saothair,
ach nuair a bhog muid i ndáiríre go dtí nód sa crann
agus fuarthas amach go bhfuil muid ag nód null.
Táimid ag dul chun iterate go dtí nach bhfuil rth cothrom le nialasach.
Agus cad tá muid ag dul a dhéanamh?
Táimid ag dul a thástáil más rud é (rth -> Luach == luach),
ansin a fhios againn go bhfuil againn le fáil i ndáiríre an nód go bhfuil muid ag lorg.
Mar sin anseo, is féidir linn ar ais fíor.
Seachas sin, ba mhaith linn a fheiceáil an bhfuil nó nach bhfuil an luach níos lú ná an luach.
Má tá an nód reatha luach níos lú ná an luach táimid ag lorg,
táimid ag dul chun bogadh ar dheis.
Mar sin, rth = rth -> right_child; agus ar shlite eile, táimid ag dul chun bogadh ar chlé.
rth = rth -> left_child. Simplí go leor.
>> Aithníonn tú is dócha an lúb go Breathnaíonn an-chosúil leis seo ó
cuardaigh dénártha níos luaithe sa téarma, ach amháin ansin bhí muid ag déileáil le íseal, lár, agus ard.
Anseo, ní mór dúinn ach chun breathnú ar luach reatha,
mar sin tá sé deas agus simplí.
Déanaimis a dhéanamh cinnte go bhfuil an cód ag obair.
An chéad, déan cinnte cuireann sé le chéile. Breathnaíonn mhaith a dhéanann sé.
A ligean ar iarracht sé ag rith.
Agus go deimhin, priontaí sé amach gach rud go raibh súil againn.
Fhaigheann sé 6 i an crann nach bhfuil, a fháil 10 toisc nach bhfuil 10 i crann,
agus ní fháil 1, mar gheall ar 1 Tá Níl freisin ar an crann.
Stuif fionnuar.
>> Ceart go leor. A ligean ar dul ar ais go dtí ár sonraíocht agus féach cad atá i ndán.
Anois, is mian leis a nóid roinnt níos mó a chur ar ár crann.
Is mian leis a chur 5, 2, agus 8, agus a chinntiú go bhfuil ár gcuid cód
fós ag obair mar súil.
Ligean ar dul a dhéanamh.
Ag an bpointe seo, seachas ag déanamh an chóip sin annoying agus greamaigh arís,
a ligean ar scríobh feidhm a chruthú i ndáiríre nód.
Má scrollaigh muid síos an bealach ar fad is mó, a fheicimid go atá muid ag déanamh seo
Cód an-chosúil arís agus arís eile gach uair a ba mhaith linn a chruthú nód.
>> A ligean ar scríobh feidhm a thógáil i ndáiríre nód dúinn agus seol ar ais.
Tá mé ag dul a ghlaoch air build_node.
Tá mé ag dul a thógáil nód gabhann luach ar leith.
Súmáil isteach anseo.
Is é an chéad rud Tá mé ag dul a dhéanamh a chruthú i ndáiríre spás le haghaidh an nód ar an gcarn.
Mar sin, nód * n = malloc (deachúlach (nód)); n -> luach = luach;
agus ansin anseo, tá mé ag dul díreach tar éis a thúsú gach ceann de na réimsí a luachanna cuí.
Agus ag deireadh an-, beidh muid ar ais ár n-nód.
Ceart go leor. Rud amháin a thabhairt faoi deara go bhfuil an fheidhm anseo ceart
ag dul go dtí pointeoir ais chun cuimhne go bhfuil a gcarn-leithdháileadh.
Cad é deas faoi seo go bhfuil an nód anois -
ní mór dúinn a dhearbhú sé ar an gcarn mar má dearbhaíodh muid é ar an chruach
Ní bheadh ​​muid in ann a dhéanamh i an fheidhm seo mar seo.
Bheadh ​​sé sin chuimhne dul amach raon feidhme
Ba mhaith agus a bheith neamhbhailí má iarracht muid a rochtain a fháil air níos déanaí.
Ós rud é go bhfuil muid ag dearbhú gcarn-leithdháileadh cuimhne,
táimid ag dul go bhfuil aire a thabhairt shaoradh sé níos déanaí
ní le haghaidh ár gclár a sceitheadh ​​aon chuimhne.
Táimid iontach a punting ar gur le haghaidh gach rud eile sa chód
ach ar mhaithe le simplíocht ar mhaithe leis ag an am,
ach má tá tú scríobh riamh feidhm go Breathnaíonn mar seo
nuair a tá tú - glaoch ar roinnt sé malloc nó realloc taobh istigh -
ba mhaith leat a dhéanamh cinnte go bhfuil tú a chur éigin de comment suas anseo a deir,
hug ais, tá a fhios agat, nód gcarn-leithdháileadh initialized leis an luach ritheadh-i.
Agus ansin ba mhaith leat a dhéanamh cinnte go tú a chur i éigin de nóta a deir
ní mór don té atá ag glaoch saor in aisce leis an chuimhne ar ais.
Sa chaoi sin, úsáidí má théann duine éigin riamh agus go bhfuil feidhm,
a fhios acu go bhfuil cuma cad a fhaigheann siad ar ais ón feidhme sin
Beidh ag pointe éigin a bheith freed.
>> Ag glacadh leis go bhfuil gach maith agus go maith anseo,
is féidir linn dul síos isteach inár cód agus gach ceann de na línte in ionad ar dheis anseo
le glaonna ar ár fheidhm nód a thógáil.
Déanaimis é sin a dhéanamh go tapa i ndáiríre.
Is é an pháirt sin ní táimid ag dul a chur in ionad an chuid seo síos anseo
ag bun an áit againn sreang iarbhír suas na nóid a chur in iúl dá chéile,
toisc nach féidir linn a dhéanamh in ár bhfeidhm.
Ach, a ligean ar a dhéanamh fhréamh = build_node (7); nód * trí = build_node (3);
nód * sé = build_node (6); nód * naoi = build_node (9);.
Agus anois, bhíomar ag iarraidh freisin chun nóid chur ar -
nód * cúig = build_node (5); nód * ocht = build_node (8);
agus cad a bhí an nód eile? A ligean ar a fheiceáil anseo. Theastaigh uainn a chur freisin ar 2 -
nód * dhá = build_node (2);.
Ceart go leor. Ag an bpointe seo, tá a fhios againn go againn a fuair an 7, 3, 9, agus an 6
gach wired suas go cuí, ach cad faoi an 5, 8, agus an 2?
Gach rud a choinneáil san ord cuí,
Tá a fhios againn go bhfuil leanbh ceart trí do 6.
Mar sin, má táimid ag dul a chur leis an 5,
an 5 mbaineann freisin ar an taobh dheis an chrainn a bhfuil 3 an fhréamh,
mar sin 5 mbaineann an leanbh na láimhe clé den 6.
Is féidir linn é seo a dhéanamh trí rá, sé -> left_child = cúig;
agus ansin mbaineann an 8 an leanbh clé den 9, mar sin naoi -> left_child = ocht;
agus ansin é 2 an leanbh clé den 3, ionas gur féidir linn a dhéanamh go bhfuil suas anseo - dhuit -> left_child = dhá.
Más rud é nach raibh tú a leanúint go leor chomh maith leis sin, le fios agam ort a tharraingt sé amach duit féin.
>> Ceart go leor. A ligean ar seo a shábháil. Ligean ar dul amach agus a dhéanamh cinnte cuireann sé le chéile,
agus ansin is féidir linn a chur in ár glaonna bhfuil.
Breathnaíonn mhaith Tiomsaíonn gach rud go fóill.
Lig dul isteach agus a chur i roinnt glaonna bhfuil.
Arís, tá mé ag dul a dhéanamh le beagán de cóipeáil agus greamaigh.
Anois, a ligean ar cuardach a dhéanamh ar 5, 8, agus 2. Ceart go leor.
Déanaimis a dhéanamh cinnte go Breathnaíonn seo go léir go maith go fóill. Great! Sábháil agus scor.
Anois, a ligean a dhéanamh, a thiomsú, agus anois a ligean ar siúl.
Ó na torthaí, tá sé cosúil go bhfuil gach rud ag obair ach deas agus go maith.
Great! Mar sin, anois tá muid fuair ár Tá feidhm scríofa.
A ligean ar bogadh ar aghaidh agus tosú ag obair ar an dóigh le nóid chur isteach i an crann
ó shin, mar a tá ag éirí sé ceart anois, nach bhfuil rudaí an-deas.
>> Má théann muid ar ais go dtí an tsonraíocht,
Iarrann sé ar ár gcumas a scríobh fheidhm a dtugtar isteach - arís, ag filleadh ar bool
le haghaidh an bhfuil nó nach raibh muid isteach i ndáiríre an nód isteach sa crann -
agus ansin an luach a chur isteach i gcrann mar a shonraítear
an argóint ach amháin chun ár n-fheidhm isteach.
Beidh muid ar ais fíor má d'fhéadfadh muid isteach go deimhin, ar an luach nód ina bhfuil an crann,
rud a chiallaíonn go raibh muid ar cheann, cuimhne go leor,
agus ansin dhá, nach raibh nód ann cheana sa crann ó -
cuimhnigh, nach bhfuil muid ag dul go bhfuil luachanna dhúbailt sa gcrann, ach chun rudaí a dhéanamh simplí.
Ceart go leor. Ar ais go dtí an gcód.
Oscail sé suas. Zoom i giotán, scrollbharra ansin síos.
A ligean ar chur ar an fheidhm isteach ceart os cionn an bhfuil.
Arís, tá sé ag dul a bheidh le glaoch isteach bool (slánuimhir luach).
Tabhair sé spás beag níos mó, agus ansin, mar réamhshocrú,
a ligean ar chur i tuairisceán bréige ag deireadh an-.
Anois síos ag an mbun, a ligean ar dul ar aghaidh agus ionad de láimh ag tógáil an nóid
i is mó dúinn féin agus sreangú suas iad a chur in iúl do gach eile cosúil le táimid ag déanamh,
beidh muid ag brath ar ár fheidhm isteach chun é sin a dhéanamh.
Ní bheidh muid ag brath ar ár fheidhm isteach a thógáil ar an crann ar fad ó scratch ach go fóill,
ach beidh orainn a fháil haitheantas coibhneasta de na línte seo - we'll trácht amach na línte seo -
a thógáil ar an 5 nóid, 8, agus 2.
Agus ina ionad sin, beidh muid ag glaoch isteach go dtí ár fheidhm isteach
chun a chinntiú go n-oibríonn go hiarbhír.
Anseo théann muid.
>> Anois, tá muid arsa amach na línte seo.
Tá ach 7, 3, 9, agus 6 in ár crann ag an bpointe seo.
Chun a dhéanamh cinnte go bhfuil seo go léir ag obair,
is féidir linn a súmáil amach, a dhéanamh ar ár crann dhénártha,
rith sé, agus is féidir linn a fheiceáil go bhfuil ag rá anois dúinn go bhfuil muid go hiomlán ceart -
5, 8, agus 2 a thuilleadh sa chrann.
Téigh ar ais isteach sa chód,
agus an chaoi a bhfuil muid ag dul a chur isteach?
Cuimhnigh cad a rinne muid nuair a bhí isteach againn i ndáiríre 5, 8, agus 2 roimhe sin.
Bhí muid go cluiche Plinko nuair a thosaigh muid ag an fhréamh,
chuaigh síos an ceann crann ag ceann ar cheann
go dtí go fuair muid an bhearna is cuí,
agus ansin sreinge againn sa nód ag an láthair is cuí.
Táimid ag dul a dhéanamh ar an rud céanna.
Sé seo go bunúsach cosúil le scríobh an cód a úsáid againn i bhfuil an fheidhm
chun teacht ar an bhfód áit ar cheart an nód a bheith,
agus ansin táimid ag dul díreach a chur isteach an nód ceart ann.
Let tús á dhéanamh sin.
>> Mar sin, ní mór dúinn a nód * rth = fréimhe; táimid ag dul díreach a leanúint Tá cód
go dtí go bhfaighidh muid go ní oibríonn sé go maith dúinn.
Táimid ag dul chun dul tríd an crann cé nach bhfuil an ghné atá ann faoi láthair faoin margadh saothair,
agus má fhaighimid amach go rth luach comhionann le luach go bhfuil muid ag iarraidh a chur isteach -
go maith, tá sé seo ar cheann de na cásanna ina ní raibh muid ábalta isteach iarbhír ar an nód
isteach an crann mar ciallaíonn sin ní mór dúinn a luach ndúblach.
Anseo táimid ag dul i ndáiríre a thabhairt ar ais bréagach.
Eile Anois, má rth ar luach níos lú ná luach,
anois tá a fhios againn go bhfuil muid ag bogadh ar dheis
toisc go mbaineann luach sa leath ceart an crann rth.
Seachas sin, táimid ag dul chun bogadh ar chlé.
Sin é go bunúsach ar ár bhfuil feidhmiú ceart ann.
>> Ag an bpointe seo, nuair atá againn i gcrích an lúb agus,
Is é ár n-pointeoir rth ag dul a bheith dírithe ar nialasach
más rud é nach bhfuil an fheidhm ar ais cheana féin.
Táimid ag a bhfuil dá bhrí sin, rth ag an láthair nuair is mian linn a chur isteach an nód nua.
Cad fós le déanamh a thógáil i ndáiríre an nód nua,
ar féidir linn a dhéanamh go leor go héasca.
Is féidir linn úsáid ár Super-handy fheidhm nód a thógáil,
agus rud éigin nach raibh linn a dhéanamh níos luaithe -
againn ach de chineál ar ghlac talamh slán ach anois beidh orainn a dhéanamh ach chun a chinntiú -
beidh orainn a thástáil chun a chinntiú go raibh an luach ar ais ag an nód nua iarbhír
Ní null, toisc nach bhfuil muid ag iarraidh chun tús a rochtain go bhfuil cuimhne má tá sé faoin margadh saothair.
Is féidir linn a thástáil chun a chinntiú nach bhfuil nód nua cothrom le margadh saothair.
Nó ina ionad sin, is féidir linn a fheiceáil ach má tá sé i ndáiríre faoin margadh saothair,
agus má tá sé faoin margadh saothair, ansin is féidir linn ar ais go díreach bréagach go luath.
>> Ag an bpointe seo, ní mór dúinn a shreangú nód nua isteach ina bhfód cuí sa chrann.
Má fhéachaimid siar ar mó agus nuair a bhí againn i ndáiríre sreangú i luachanna roimh,
feicimid gurb é an bealach bhí muid é a dhéanamh nuair a bhíomar ag iarraidh a chur 3 sa crann
Rinneadh rochtain againn ar an leanbh clé den fhréamh.
Nuair a chuir muid 9 sa crann, bhí againn chun rochtain a fháil leanbh ceart an fhréamh.
Bhí orainn a bheith pointeoir leis an tuismitheoir d'fhonn luach a chur nua isteach sa chrann.
Scrollaigh suas ar ais a chur isteach, ní ar sin ag dul ag obair go maith anseo
toisc nach bhfuil muid ag pointeoir tuismitheoir.
Cad ba mhaith linn a bheith in ann a dhéanamh, is é ag an bpointe seo,
seiceáil an tuismitheora luach agus a fheiceáil - go maith, gosh,
má tá an tuismitheoir ar luach níos lú ná an luach reatha,
ansin ba chóir go mbeadh an tuismitheoir linbh ceart an nód nua;
a mhalairt, ba cheart go mbeadh an tuismitheoir an pháiste chlé an nód nua.
Ach, nach bhfuil againn an pointeoir tuismitheoir go fóill.
>> D'fhonn a fháil air, táimid ag dul i ndáiríre go bhfuil a rianú mar a théann muid tríd an crann
agus teacht ar an bhfód cuí in ár lúb thuas.
Féidir linn a dhéanamh go bhfuil ag scrollaithe ar ais suas go dtí an barr ár bhfeidhm isteach
agus rianú eile athróg pointeoir ar a dtugtar an tuismitheoir.
Táimid ag dul a shocrú cothrom le nialasach ar dtús,
agus ansin dul gach uair againn tríd an crann,
táimid ag dul a shocrú ar an pointeoir tuismitheoir a mheaitseáil leis an pointeoir reatha.
Socraigh tuismitheoir cothrom le rth.
Sa tslí seo, gach uair a théann muid tríd,
táimid ag dul chun a chinntiú go réir mar a éiríonn an pointeoir reatha incrimintithe
seo a leanas an pointeoir tuismitheoir é - ach leibhéal amháin níos airde ná an pointeoir reatha sa chrann.
Go Breathnaíonn gach maith go leor.
>> Sílim go bhfuil an rud amháin go mbainfidh muid ag iarraidh a choigeartú seo a thógáil null nód ar ais.
D'fhonn a fháil a thógáil nód a iarbhír ar ais go rathúil faoin margadh saothair,
beidh orainn a mhodhnú an cód,
mar gheall ar anseo riamh, tástáil muid a dhéanamh cinnte go ais malloc a pointeoir bailí.
Mar sin, más rud é (n = NULLComment!), Ansin -
más rud é ar ais malloc a pointeoir bailí, ansin beidh orainn a thúsú é;
ar shlí eile, beidh muid ar ais go díreach agus go mbeidh deireadh suas ar ais null dúinn.
Anois Breathnaíonn gach maith go leor. Déanaimis a dhéanamh cinnte seo Tiomsaíonn ndáiríre.
Déan crann dhénártha, agus ó, tá muid fuair roinnt rudaí ar siúl anseo.
>> Táimid iontach fuair an dearbhú intuigthe d'fheidhm a thógáil nód.
Arís, leis na tiomsaitheoirí, táimid ag dul chun tús a chur ag an mbarr.
Cad nach mór a chiallaíonn go bhfuil mé ag glaoch a thógáil nód roimh mé dhearbhú i ndáiríre é.
A ligean ar dul ar ais chuig an gcód i ndáiríre go tapa.
Scrollaigh síos, agus cinnte go leor, tá mé ag feidhmiú isteach dearbhaithe
os cionn an fheidhm nód a thógáil,
ach tá mé ag iarraidh úsáid a thógáil nód taobh istigh de isteach.
Tá mé ag dul chun dul isteach agus cóip - agus ansin a ghreamú ar an mbealach a thógáil feidhm nód suas anseo ag an mbarr.
Sa chaoi sin, tá súil againn go mbeidh obair. A ligean ar seo a thabhairt eile dul.
Anois, cuireann sé le chéile ar fad. Gach go maith.
>> Ach ag an bpointe seo, ní mór dúinn ar a dtugtar i ndáiríre ár bhfeidhm isteach.
Tá a fhios againn go díreach cuireann sé le chéile, mar sin a ligean ar dul i agus roinnt glaonna a chur isteach
Déanaimis é sin a dhéanamh in ár phríomhfheidhm.
Anseo, dúirt muid amach 5, 8, agus 2,
agus ansin ní raibh muid sreang suas iad síos anseo.
Déanaimis a dhéanamh ar roinnt glaonna a chur isteach,
agus a ligean ar úsáid a bhaint freisin ar an chineál céanna de rudaí a úsáid againn
nuair a rinne muid na glaonna printf a dhéanamh cinnte go bhfuil gach rud raibh a fháil isteach i gceart.
Tá mé ag dul a chóipeáil agus a ghreamú,
agus tá ionad táimid ag dul isteach a dhéanamh.
Agus in ionad 6, 10, agus 1, táimid ag dul a úsáid 5, 8, agus 2.
Ba chóir é sin isteach súil go dtosnódh 5, 8, agus 2 isteach sa chrann.
Thiomsú. Gach go maith. Anois, beidh muid ag reáchtáil i ndáiríre ár gclár.
>> Gach rud ar ais bréagach.
Mar sin, ní raibh 5, 8, agus 2 dul, agus tá sé cosúil nach raibh rud iad a fháil ach an oiread.
Cad atá ar siúl? A ligean ar zúmáil amach.
An chéad fhadhb ná go raibh an chuma isteach a thabhairt ar ais bréagach,
agus tá sé cosúil go bhfuil mar gheall ar d'fhág muid inár glaoch tuairisceán bréagach
riamh agus d'fhill againn i ndáiríre fíor.
Is féidir linn a shocrú go bhfuil suas.
Is é an fhadhb dara, anois fiú má dhéanaimid - shábháil, scor sin,
reáchtáil a dhéanamh arís, tá sé thiomsú, ansin rith sé -
feicimid gur tharla rud éigin eile anseo.
An 5, 8, agus 2 riamh bhfuarthas fós sa chrann.
Mar sin, tá cad atá ar siúl?
>> A ligean ar ghlacadh le breathnú ar seo sa chód.
A ligean ar féach an féidir linn an figiúr seo amach.
Tús a chur againn leis an tuismitheoir nach null.
Leagtha síos againn an pointeoir reatha comhionann leis an pointeoir fréimhe,
agus táimid ag dul a bheith ag obair ár mbealach síos tríd an crann.
Mura bhfuil an nód atá ann faoi láthair faoin margadh saothair, ansin a fhios againn gur féidir linn bogadh síos beagán.
Atá leagtha muid ár pointeoir tuismitheoir a bheith comhionann leis an pointeoir atá ann faoi láthair,
sheiceáil an luach - má tá na luachanna mar an gcéanna muid ar ais bréagach.
Má tá na luachanna níos lú bhog muid go dtí an ceart;
a mhalairt, bhog muid go dtí an taobh clé.
Ansin linn a thógáil nód. Feicfidh mé zúmáil isteach beagán.
Agus anseo, táimid ag dul chun iarracht a dhéanamh a shreangú suas na luachanna a bheith mar an gcéanna.
Cad atá ar siúl? A ligean ar a fheiceáil má d'fhéadfadh is féidir Valgrind a thabhairt dúinn leid.
>> Is maith liom úsáid a bhaint as Valgrind Valgrind ach mar gheall ar Ritheann i ndáiríre go tapa
agus insíonn tú má tá aon earráidí chuimhne.
Nuair a reáchtáil againn Valgrind ar an gcód,
mar is féidir leat a fheiceáil hit here--Valgrind./binary_tree--and ceart isteach.
Féach leat nach raibh againn aon earráid cuimhne, agus mar sin tá sé cosúil Tá gach rud ceart go leor go dtí seo.
Déanann muid go bhfuil roinnt leaks cuimhne, a bhfuil a fhios againn, toisc nach bhfuil muid
ag tarlú go saor in aisce ar bith dár gcuid nóid.
A ligean ar iarracht a reáchtáil GDB a fheiceáil cad atá ar siúl i ndáiríre ar.
Beidh muid a dhéanamh gdb. / Binary_tree. Booted sé suas ach fíneáil.
A ligean ar shocrú le pointe sos ar chur isteach.
A ligean ar siúl.
Breathnaíonn sé riamh mar a dtugtar againn i ndáiríre isteach.
Breathnaíonn sé cosúil go raibh an fhadhb é sin nuair a d'athraigh mé síos anseo i príomh -
gach ceann de na glaonna printf ó bhfuil -
Mé riamh athrú iarbhír na cuir isteach a ghlaoch.
Anois, a ligean a thabhairt dó iarracht. A ligean ar chur le chéile.
Gach Breathnaíonn go maith ansin. Anois, a ligean iarracht sé ag rith, féach cad a tharlaíonn.
Ceart go leor! Gach rud Breathnaíonn maith go leor ann.
>> Is é an rud deireanach chun smaoineamh ar, tá aon chásanna imeall an chur isteach?
Agus casadh sé amach go, go maith, cás an ceann imeall go bhfuil i gcónaí suimiúil smaoineamh ar
is é sin, cad a tharlaíonn má tá do crann folamh agus a ghlaonn tú an fheidhm isteach?
An mbeidh sé ag obair? Bhuel, a ligean ar thabhairt dó iarracht.
- Binary_tree c. -
Is é an bealach táimid ag dul chun tástáil seo a dhéanamh, táimid ag dul chun dul síos go dtí ár phríomhfheidhm,
agus seachas wiring na nóid suas mar seo,
táimid ag dul díreach a trácht a dhéanamh amach an rud ar fad,
agus in ionad wiring suas an nóid féin,
is féidir linn i ndáiríre dul díreach amach romhainn agus seo ar fad a scriosadh.
Táimid ag dul a dhéanamh gach rud a glaoch a chur isteach.
Mar sin, a ligean ar a dhéanamh - in ionad 5, 8, agus 2, táimid ag dul a chur isteach 7, 3, agus 9.
Agus ansin beidh muid ag iarraidh freisin a chur isteach 6 chomh maith.
Sábháil. Scoir. Déan crann dénártha.
Cuireann sé ar fad.
Is féidir linn a reáchtáil ach tá sé mar agus féach cad a tharlaíonn,
ach tá sé ag dul freisin a bheith tábhachtach i ndáiríre a dhéanamh cinnte go
nach bhfuil againn aon earráidí chuimhne,
ós rud é seo ar cheann de na cásanna imeall go bhfuil a fhios againn faoi.
>> Déanaimis a dhéanamh cinnte go n-oibríonn sé go maith faoi Valgrind,
a beidh orainn a dhéanamh ag díreach ag rith Valgrind. / binary_tree.
Breathnaíonn sé cosúil le atá againn deimhin, ar cheann earráid ó chomhthéacs -
ní mór dúinn an locht deighilte.
Cad a tharla?
Valgrind insíonn dúinn i ndáiríre áit a bhfuil sé.
Súmáil amach le beagán.
Breathnaíonn sé cosúil le ag tarlú é i ár bhfeidhm isteach,
áit a bhfuil muid a léamh neamhbhailí de mhéid 4 ag cuir isteach, líne 60.
Lig dul ar ais agus féach cad atá ar siúl anseo.
Súmáil amach i ndáiríre tapaidh.
Ba mhaith liom a dhéanamh cinnte go nach ndéanann sé dul go dtí an imeall an scáileán ionas gur féidir linn a fheiceáil gach rud.
Tarraingt i beagán. Ceart go leor.
Scrollaigh síos, agus is é an fhadhb ar dheis anseo.
Cad a tharlaíonn má fhaigheann muid síos agus is é ár nód atá ann faoi láthair cheana féin faoin margadh saothair,
Is é ár n-nód tuismitheoir null, mar sin má táimid suas ar an an-is fearr, anseo ceart -
riamh má fhorghníomhú an lúb agus iarbhír
toisc go bhfuil ár n-luach reatha faoin margadh saothair - is é ár root null mar sin tá rth Eolas faoin margadh saothair -
Ní fhaigheann ár máthair bun ansin go rth nó le luach bailí,
mar sin, beidh tuismitheoir freisin faoin margadh saothair.
Ní mór dúinn dearmad a sheiceáil le haghaidh sin
ag an am a fháil muid síos anseo, agus tús a chur againn rochtain a fháil ar an tuismitheora luach.
Mar sin, cad a tharlaíonn? Bhuel, má tá an tuismitheoir faoin margadh saothair -
más rud é (tuismitheoir == NULLComment) - ansin a fhios againn go
Ní mór go mbeadh aon ní sa chrann.
Ní mór dúinn a bheith ag iarraidh a chur isteach ag an fhréamh.
Féidir linn a dhéanamh go díreach ag leagan síos an fhréamh is comhionann leis an nód nua.
Ansin, ag an bpointe seo, nach bhfuil muid ag iarraidh i ndáiríre chun dul trí na rudaí eile.
Ina áit sin, ar dheis anseo, is féidir linn a dhéanamh ceachtar eile-más rud é-eile,
nó d'fhéadfadh muid le chéile gach rud suas anseo i eile,
ach anseo beidh orainn a úsáid ach eile agus é sin ar bhealach a dhéanamh.
Anois, táimid ag dul chun tástáil a dhéanamh cinnte go bhfuil ár máthair-null
roimhe sin ag iarraidh iarbhír rochtain a fháil ar laistigh dá réimsí.
Cuideoidh sé seo linn a sheachaint an locht deighilte.
Mar sin, scor againn, súmáil amach, a thiomsú, a reáchtáil.
>> Níl aon earráidí, ach tá muid fós a bunch de leaks cuimhne
toisc nach raibh muid saor in aisce ar bith dár gcuid nóid.
Ach, má théann muid suas anseo agus táimid ag ár n-printout,
feicimid go bhfuil, go maith Breathnaíonn, cosúil le gach ceann dár iatáin a bhí ag filleadh fíor, atá go maith.
Is iad na iatáin ar fad fíor,
agus ansin go bhfuil na glaonna bhfuil oiriúnach fíor freisin.
>> Good job! Breathnaíonn sé cosúil againn scríofa go rathúil isteach.
Sin gach ní mór dúinn ar na seachtaine seo Sonraíocht Socraigh Fadhb.
Is é ceann dúshlán spraoi a smaoineamh ar conas ba mhaith leat dul i ndáiríre i
agus saor in aisce gach ceann de na nóid sa chrann.
Is féidir linn a dhéanamh ar roinnt bealaí éagsúla,
ach beidh mé saoire go bhfuil suas le leat chun turgnamh,
agus mar dhúshlán spraoi, iarracht a dhéanamh cinnte gur féidir leat a dhéanamh cinnte
go bhfilleann an tuarascáil seo Valgrind aon earráidí agus aon leaks.
>> Ádh mór ar a leagan síos na seachtaine seo fadhb Huffman códú,
agus beidh orainn a fheiceann tú an tseachtain seo chugainn!
[CS50.TV]