[Ag seinm ceoil] 

DOUG LLOYD: OK, mar sin ag an bpointe seo i gcúrsa, tá muid clúdaithe a lán de na Basics of C. Tá a fhios againn go leor faoi na hathróga, eagair, leideanna, go léir go stuif maith. Glacfar iad go léir saghas tógtha i a fheiceáil mar an bunúsacha, ach is féidir linn a dhéanamh níos mó, ceart? Is féidir linn rudaí a chur le chéile le chéile ar bhealaí spéisiúla. 

Agus mar sin a ligean ar é sin a dhéanamh, a ligean ar tús a chur a brainse amach ar cad a thugann dúinn C, agus tús a chruthú ar ár sonraí féin struchtúir a úsáideann na bhfoirgneamh bloic le chéile rud éigin a dhéanamh i ndáiríre luachmhar, úsáideach. Is bealach amháin is féidir linn é seo a chun labhairt faoi bhailiúcháin. Mar sin, go dtí seo tá muid go raibh ar cheann de chineál sonraí Struchtúr as ionadaíocht bhailiúcháin de cosúil le luachanna, luachanna den chineál céanna. Bheadh ​​sin le sraith. Ní mór dúinn bailiúcháin de slánuimhreacha, nó bailiúcháin de charachtair agus mar sin de. 

Struchtúir shórtáil freisin ar na sonraí Struchtúr chun faisnéis a bhailiú, ach nach bhfuil sé do bhailiú cosúil le luachanna. Meascáin sé de ghnáth cineálacha éagsúla sonraí le chéile taobh istigh de bhosca amháin. Ach nach bhfuil sé é féin a úsáidtear chun slabhra le chéile nó ceangal le chéile den chineál céanna míreanna, cosúil le eagar. Tá Arrays mór do eilimint breathnú suas, ach chun cuimhne go bhfuil sé an-deacair a chur isteach i sraith, ach amháin má táimid a chur isteach ag an deireadh an-an eagar. 

Agus an sampla is fearr Tá mé do go bhfuil a chur isteach saghas. Má tá tú chun cuimhne ár físeán ar chur isteach a shórtáil, go raibh a lán de costas a bhfuil baint acu a bhfuil a phiocadh suas heilimintí, agus athrú orthu amach as an mbealach rud éigin a d'oirfeadh isteach i lár de do eagar. Ag fulaingt Arrays freisin ó eile fhadhb, a bhfuil dolúbthacht. Nuair a dearbhaímid le sraith, a fháil againn lámhaigh amháin ar sé. A fháil againn a rá, ba mhaith liom seo gnéithe go leor. D'fhéadfadh a bheith 100, d'fhéadfadh sé a bheith 1000, d'fhéadfadh sé a bheith x áit a bhfuil x roinnt go bhfuil an t-úsáideoir thug dúinn ag pras nó ag an ordú líne. 

Ach linn a fháil ach amháin lámhaigh ar sé, táimid ag ná a fháil a rá ansin ó, i ndáiríre mé ag teastáil 101, nó is gá mé x móide 20. Ró-dhéanach, tá muid dearbhaithe cheana féin ar an eagar, agus más mian linn a fháil 101 nó x móide 20, ní mór dúinn a dhearbhú le sraith difriúil ar fad, cóip na heilimintí na eagar os a chionn, agus ansin ní mór dúinn go leor. Agus cad má tá muid mícheart arís, cad más gá againn i ndáiríre 102, nó x móide 40, ní mór dúinn a dhéanamh arís. Mar sin, tá siad an-dolúbtha chun méid a athrú ár sonraí, ach má chéile muid le chéile roinnt de na Basics a tá muid cheana d'fhoghlaim siad faoi threo agus struchtúir, go háirithe ag baint úsáide as cuimhne dinimiciúil leithdháileadh le malloc, táimid ag Is féidir a chur ar na píosaí le chéile a chruthú sonraí nua structure-- ar liosta d'fhéadfadh muid say-- ina n-aonar nasctha a ligeann dúinn chun fás agus Laghdaigh bailiúchán de luachanna agus nach mbeidh orainn aon spás amú. 

Mar sin arís, tugaimid an smaoineamh seo, an gcoincheap sin, liosta nasctha. Go háirithe, i físeán seo tá muid ag caint faoi an liosta nasctha ina n-aonar, agus ansin físeán eile beidh muid ag caint liostaí thart nasctha doubly, a ach athrú ar théama anseo. Ach liosta nasctha ina n-aonar comhdhéanta de nóid, nóid bheith ach term-- teibí tá sé ach rud éigin Tá mé ag glaoch go bhfuil ar chineál an struchtúr, go bunúsach, tá mé? Just a ag dul a ghlaoch air node-- agus tá sé seo Tá beirt bhall, nó dhá réimse nód. Tá sé sonraí, de ghnáth ar slánuimhir, snámh carachtar, nó a d'fhéadfadh a bheith de chineál éigin eile sonraí go atá tú a shainmhínítear le def cineál. Agus tá sé ina pointeoir a nód eile den chineál céanna. 

Mar sin, ní mór dúinn dhá rud taobh istigh de an nód, sonraí agus pointeoir go nód eile. Agus má thosaíonn tú a shamhlú seo, is féidir leat a smaoineamh air cosúil le slabhra de nóid sin bhfuil baint le chéile. Tá an chéad nód, sé Tá sonraí, agus pointeoir go dtí an dara nód, ina bhfuil sonraí, agus pointeoir chuig an tríú nód. Agus mar sin go bhfuil an fáth tugaimid sé liosta nasctha, tá siad nasctha le chéile. 

Cad a dhéanann an speisialta Struchtúr nód cuma mhaith? Bhuel, má tá tú chun cuimhne as ár físeán ar shainmhíniú cineálacha saincheaptha, le cineál def, is féidir linn a shainiú structure-- agus cineál struchtúr shainiú mar seo. tyepdef sllist struct, agus ansin tá mé ag baint úsáide as an luach focal anseo treallach a chur in iúl de chineál ar bith sonraí ndáiríre. D'fhéadfá a pas a fháil ar slánuimhir nó snámh, fhéadfadh go mbeadh ort bith is mian leat. Nach bhfuil sé teoranta go dtí díreach slánuimhreacha, nó aon rud mar sin. Mar sin, tá súil le luach ach treallach cineál sonraí, agus ansin pointeoir go nód eile den chineál céanna. 

Anois, níl a ghabháil beag anseo le sainiú struchtúr nuair a tá sé struchtúr féin referential. Caithfidh mé a bheith sealadach ainm do mo struchtúr. Ag deireadh an lae I Ba mhaith go soiléir a ghlaoch air nód SLL, go bhfuil deireadh thiar an nua ainm chuid de mo sainmhíniú chineál, ach ní féidir liom a úsáid nód SLL i lár an. An chúis a bheith, nach bhfuil mé chruthaigh cineál ar a dtugtar nód SLL go dtí go bhuail mé an pointe deiridh anseo. Suas go dtí an bpointe sin, caithfidh mé a bheith acu ar bhealach eile chun tagairt a dhéanamh chineál seo sonraí. 

Agus tá sé seo féin Cineál sonraí referential. Sé; s le cineál sonraí de Struchtúr go bhfuil a sonraí, agus pointeoir go ceann eile struchtúr an chineál céanna. Mar sin, is gá dom a bheith in ann tagairt a dhéanamh chineál seo sonraí ar a laghad, go sealadach, a thugann mar sin tá sé sealadach ainm an sllist struct Ligeann dom a rá ansin ba mhaith liom a pointeoir go sllist struct eile, réalta sllist struct, agus ansin tar éis tá mé críochnaithe an sainmhíniú, Is féidir liom glaoch anois chineál seo nód SLL. 

Mar sin, sin an fáth a fheiceann tú níl ainm sealadach anseo, ach ainm buan anseo. Uaireanta, d'fhéadfadh tú a fheiceáil sainmhínithe ar struchtúr, mar shampla, nach bhfuil go féin referential, go Ní gá go mbeadh ainm sonraitheoir anseo. Bheadh ​​sé ach a rá struct typedef, oscailte brace curly agus ansin shainmhíniú. Ach má tá tú go bhfuil struct féin referential, mar tá sé seo ar cheann, is gá duit a shonrú ainm chineál sealadach. Ach sa deireadh thiar, anois go atá déanta againn seo, Is féidir linn a tharchur díreach tar éis a na nóid, na haonaid, mar nóid SLL chun críocha an chuid eile den físeán seo. 

Ceart go leor, mar sin tá a fhios againn conas a chruthú liosta nód nasctha. Tá a fhios againn conas a shainmhíniú nód liosta a nasctha. Anois, má táimid ag dul chun tús a chur iad a úsáid chun faisnéis a bhailiú, níl cúpla na n-oibríochtaí a chuirimid Ní mór a thuiscint agus ag obair le. Ní mór dúinn a fhios conas a chruthú liosta nasctha as an aer tanaí. Má níl aon liosta cheana, ba mhaith linn a thosú amháin. Mar sin, ní mór dúinn a bheith in ann a chruthú liosta nasctha, ní mór dúinn chun cuardach a is dócha tríd an liosta nasc chun teacht ar an eilimint táimid ag lorg. Ní mór dúinn a bheith in ann a chur isteach rudaí nua isteach ar an liosta, ba mhaith linn ár liosta a bheith in ann fás. Agus mar an gcéanna, ba mhaith linn a bheith in ann chun rudaí a scriosadh as ár liosta, ba mhaith linn ár liosta a bheith in ann a Laghdaigh. Agus ag an deireadh ár cláir, go háirithe má tá tú chun cuimhne go bhfuil muid dinimiciúil leithdháileadh cuimhne a thógáil ar na liostaí de ghnáth, ba mhaith linn go saor in aisce gach ceann de sin chuimhne nuair a bhíonn muid ag obair déanamh leis. Agus mar sin ní mór dúinn a bheith in ann a scriosadh ar liosta nasctha ar fad i gceann swoop theipeann. Mar sin, a ligean ar dul tríd cuid de na hoibríochtaí agus conas a d'fhéadfadh muid a shamhlú iad, ag caint i cód pseudocode go sonrach. Mar sin, ba mhaith linn a chruthú liosta nasctha, agus mar sin b'fhéidir táimid ag ag iarraidh le feidhm a shainiú leis an fhréamhshamhail. SLL réalta nód, a chruthú, agus tá mé ag dul i argóint amháin, cuid de na sonraí treallach cineál arís, de chineál éigin sonraí treallach. Ach tá mé ag returning-- an fheidhm seo ba chóir ar ais chuig dom pointeoir, le ina n-aonar nasctha nód liosta. Arís, tá muid ag iarraidh a chruthú liosta nasctha as an aer tanaí, mar sin de dhíth orm pointeoir go liosta sin nuair atá mé ag déanamh. 

Mar sin, cad iad na céimeanna a bhaineann anseo? Bhuel, an chéad rud Tá mé ag dul a dhéanamh ná dinimiciúil spás a leithdháileadh le haghaidh nód nua. Arís, tá muid ag cruthú sé amach as tanaí aer, mar sin ní mór dúinn a spás malloc chun é. Agus ar ndóigh, díreach tar éis malloc againn, táimid ag seiceáil i gcónaí chun a chinntiú go bhfuil ár pointer-- ní raibh muid a fháil ar ais null. Toisc má iarracht muid agus deference pointeoir null, táimid ag dul ag fulaingt le segfault agus nach bhfuil muid ag iarraidh go. 

Ansin, ba mhaith linn a líonadh isteach ar an réimse, ba mhaith linn a thúsú an réimse luach agus thúsú an réimse seo chugainn. Agus ansin ba mhaith linn to-- deireadh thiar mar an fhréamhshamhail fheidhm indicates-- mhaith linn chun pointeoir filleadh ar an nód SLL. Mar sin, cad a dhéanamh ar an cuma mhaith amhairc? Bhuel, ar an gcéad táimid ag dul a dinimiciúil spás a leithdháileadh le haghaidh nód SLL nua, ionas malloc-- linn a go a amharcléiriú an nód a cruthaíodh againn ach. Agus muid seiceáil a dhéanamh cinnte nach bhfuil sé null-- i chás seo, Ní bheadh ​​an pictiúr mór léirithe suas má bhí sé null, ba mhaith linn a bheith ar siúl as cuimhne, mar sin go bhfuil muid go maith chun dul ann. Mar sin, anois tá muid ar a chéim C, thúsú an réimse luach nóid. Bhuel, bunaithe ar an bhfeidhm seo glaoch mé ag baint úsáide anseo, Breathnaíonn an nós Ba mhaith liom a pas a fháil i 6, mar sin beidh mé 6 i réimse an luach. Anois, thúsú an réimse seo chugainn. Bhuel, cad tá mé ag dul a dhéanamh ann, níl rud ar bith eile, ar dheis, is é seo an rud amháin ar an liosta. Mar sin, cad é an chéad rud eile ar an liosta? 

Níor cheart é a chur in iúl do rud ar bith, ar dheis. Níl rud ar bith eile ann, mar sin cad é an coincheap a fhios againn de go nothing-- leideanna chun rud ar bith? Ba chóir a thabhairt b'fhéidir gur mhaith linn a a chur ar pointeoir null ann, agus beidh mé ionadaíocht a null pointeoir mar ach bosca dearg, ní féidir linn dul ar bith eile. Mar a beidh orainn a fheiceáil beagán níos déanaí ar, beidh orainn deireadh thiar slabhraí de saighde nascadh na nóid chéile, ach nuair a bhuail tú ar an bosca dearg, go null, ní féidir linn dul ar bith eile, go deireadh an liosta. 

Agus ar deireadh, ba mhaith linn ach chun pointeoir filleadh ar an nód. Mar sin, beidh muid ag glaoch air nua, agus beidh sé ar ais nua ionas gur féidir é a úsáid i is cuma cad fheidhm chruthaigh sé. Mar sin, ní théann muid, tá muid a cruthaíodh ina n-aonar nasctha liosta nód as an aer tanaí, agus anois tá liosta is féidir linn a bheith ag obair leis. 

Anois, a ligean ar rá againn cheana go mbeadh slabhra mór, agus ba mhaith linn rud éigin ann a fháil. Agus ba mhaith linn feidhm go bhfuil dul a thabhairt ar ais fíor nó bréagach, ag brath ar an bhfuil luach sa liosta sin. A fhréamhshamhail feidhm, nó dearbhú chun feidhme sin, D'fhéadfadh cuma mhaith Bool this-- aimsiú, agus ansin ba mhaith linn a pas a fháil i dhá argóintí. 

Is é an chéad, pointeoir chuig an an chéad ghné den liosta nasctha. Sé seo i ndáiríre rud éigin go mbainfidh tú ba mhaith i gcónaí súil a choinneáil, agus d'fhéadfadh a bheith i ndáiríre rud éigin a tú a chur fiú i athróg domhanda. Chomh luath agus tú a chruthú liosta, tú i gcónaí, i gcónaí ag iarraidh súil a choinneáil ar an chuid is an chéad ghné den liosta. Sa chaoi sin is féidir leat a tharchur chuig gach ceann eile gnéithe ag díreach tar éis an slabhra, gan a bheith a choinneáil leideanna slán do gach gné amháin. Ní mór duit ach súil a choinneáil ar an chéad a choinneáil ceann má tá siad chained go léir le chéile. 

Agus ansin an dara rud táimid ag dul i arís Is some-- treallach is cuma cén cineál sonraí a tá muid Tá lorg ann taobh istigh de tá súil againn ar cheann de na nóid ar an liosta. Mar sin, cad iad na céimeanna? Bhuel, is é an chéad rud a dhéanann muid chruthú dúinn pointeoir trasnaí dírithe ar na liostaí ceann. Bhuel, cén fáth a dhéanann muid go bhfuil, againn cheana féin bheith pointeoir ar na liostaí ceann, cén fáth nach bhfuil muid ag bogadh go díreach duine ar fud? Bhuel, mar a dúirt mé díreach tar éis, tá sé i ndáiríre tábhachtach dúinn a choinneáil i gcónaí riain an an-an chéad eilimint sa liosta. Agus mar sin tá sé i ndáiríre níos fearr a chruthú dhúbailt sin, agus úsáid a bhaint as go bhfuil a bogadh thart mar sin againn riamh thaisme bogadh ar shiúl, nó muid i gcónaí go mbeadh pointeoir ag pointe éigin go bhfuil ar dheis ar an chéad ghné den liosta. Mar sin, tá sé níos fearr a chruthú an dara ceann a úsáid againn a bhogadh. 

Ansin i gcomparáid againn díreach cé acu an réimse luach ag an nód Is cad tá muid ag lorg, agus má tá sé ní, sinn ag dul díreach chuig an nód seo chugainn. Agus a choinneáil ag éirí linn go os a chionn, agus os a chionn, agus os a chionn, go dtí go táimid ag ceachtar fháil an eilimint, nó bhuail muid null-- tá muid bainte amach an deireadh an liosta agus nach bhfuil sé ann. Ba chóir é seo fáinne le clog tá súil againn a thabhairt duit chomh díreach cuardaigh líneach, táimid ag replicating ach é i struchtúr liosta a nasctha ina n-aonar seachas úsáid a bhaint sraith é a dhéanamh. 

Mar sin, tá anseo sampla de liosta nasctha ina n-aonar. Is éard atá sa cheann de cúig nóid, agus ní mór dúinn pointeoir chuig ceann de na liosta, ar a dtugtar an liosta. Is é an chéad rud ba mhaith linn a dhéanamh arís, a chruthú go pointeoir traversal. Mar sin, ní mór dúinn anois dhá threo go pointe ar an rud céanna. 

Anois, faoi deara anseo freisin, ní raibh mé a malloc aon spás le haghaidh trav. Ní raibh mé a rá ionann trav malloc rud éigin, ann sin nód cheana, go spás i gcuimhne ann cheana. Mar sin go léir Tá mé ag déanamh i ndáiríre é ag cruthú pointeoir eile dó. Níl mé ag mallocing breise spás, ní mór ach anois dhá threo dírithe ar an rud céanna. 

Mar sin, tá 2 a bhfuil mé ag lorg? Bhuel, ní hea, mar sin in ionad tá mé dul chun bogadh go dtí an chéad cheann eile. Mar sin, go bunúsach, ba mhaith liom a rá, ionann trav trav chugainn. Is 3 a bhfuil mé ag lorg, uimh. Mar sin, leanfaidh mé chun dul trí, go dtí sa deireadh a fháil chun 6 a bhfuil cad tá mé ag lorg as bunaithe ar an glaoch fheidhm Tá mé ag an mbarr ann, agus mar sin tá mé ag déanamh. 

Anois, cad má tá mé an eilimint Ní ag lorg ar an liosta, tá sé fós ag dul a bheith ag obair? Bhuel, faoi deara go bhfuil an liosta anseo tá subtly difriúil, agus tá sé seo rud eile go bhfuil tábhachtach le liostaí nasctha, ní gá duit a chaomhnú iad in aon ord ar leith. Is féidir leat más mian leat, ach féadfaidh tú faoi deara cheana nach bhfuil muid ag súil a choinneáil ar cén uimhir eilimint táimid ag. 

Agus sin an saghas na trádála amháin go bhfuil muid tá le liosta a nasctha véarsaí arrays, tá sé nach bhfuil againn rochtain randamach níos mó. Ní féidir linn ach a rá, ba mhaith liom chun dul go dtí an eilimint 0, an 6ú eilimint de mo eagar, Is féidir liom a dhéanamh i sraith. Ní féidir liom a rá Ba mhaith liom dul go dtí an Eilimint 0, nó an eilimint 6, nó an eilimint 25ú de mo liosta nasctha, níl aon innéacs a bhaineann leo. Agus mar sin nach ndéanann sé ábhar i ndáiríre má táimid a chaomhnú ar ár liosta in ord. Más mian leat a thabhairt duit cinnte is féidir, ach níl aon chúis cén fáth ar gá iad a a chaomhnú in ord ar bith. Mar sin arís, a ligean ar iarracht a dhéanamh agus teacht 6 sa liosta seo. Bhuel, tús a chur orainn ag an ag tosú, ní féidir linn a fháil 6, agus ansin ní leanúint ar aghaidh táimid ag aimsiú 6, go dtí go linn a fháil ar deireadh thiar anseo. Mar sin, ceart pointí trav anois go dtí an nód ina bhfuil 8, agus sé nach bhfuil ann. 

Mar sin, bheadh ​​an chéad chéim eile chun dul go dtí an pointeoir seo chugainn, mar sin a rá ionann trav trav chugainn. Bhuel, trav chugainn, le fios ag an bosca dearg ann, null. Mar sin, níl aon áit eile le dul, agus mar sin ag an bpointe seo is féidir linn a thabhairt i gcrích go atá bainte amach againn an deireadh an liosta nasctha, agus nach bhfuil 6 i ann. Agus go mbeadh sé ar ais bréagach sa chás seo. 

OK, conas is féidir linn a chur isteach nua nód isteach ar an liosta nasctha? Mar sin, tá muid in ann a chruthú liosta nasctha amach as an áit, ach ba mhaith linn is dócha a thógáil slabhra agus ní chruthú a bunch de liostaí ar leith. Ba mhaith linn go mbeadh liosta amháin go Tá a bunch de nóid ann, Ní a bunch de liostaí le nód amháin. Mar sin, ní féidir linn a choinneáil ach ag baint úsáide as an Create fheidhm sainmhínithe againn níos luaithe, táimid ag anois ag iarraidh a chur isteach i liosta atá ann cheana. 

Mar sin, chás seo, táimid ag dul chun pas a fháil i dhá argóintí, an pointeoir chuig ceann sin liosta a ba mhaith linn a chur leis nasctha. Arís, sin an fáth go bhfuil sé chomh tábhachtach go againn i gcónaí súil a choinneáil ar é a choinneáil, mar gheall ar tá sé an t-aon bhealach againn i ndáiríre a tharchur chuig an liosta iomlán ach ag pointeoir chuig an chéad eilimint. Mar sin, ba mhaith linn a pas a fháil i pointeoir leis sin chéad eilimint, agus is cuma cad luach táimid ag ag iarraidh a chur leis an liosta. Agus ar deireadh thiar an fheidhm seo ag dul chun filleadh ar pointeoir go dtí an ceann nua de liosta nasctha. 

Cad iad na céimeanna a bhaineann anseo? Bhuel, díreach cosúil le a chruthú, ní mór dúinn a leithdháileadh dinimiciúil spás le haghaidh nód nua, agus seiceáil a dhéanamh cinnte nach bhfuil muid ag siúl as an chuimhne, arís, mar gheall orainn ag baint úsáide as malloc. Ansin, ba mhaith linn a populate agus cuir isteach an nód, mar sin a chur ar an uimhir, is cuma cad Is val, isteach sa nód. Is mian linn a chur isteach ar an nód ag tús an liosta nasctha. 

Níl cúis go bhfuil mé ag iarraidh a dhéanamh, agus é a d'fhéadfadh a bheith fiú cur dara chun sos an físeán anseo, agus smaoineamh ar cén fáth go mbeadh mé ag iarraidh a cuir isteach ar an tús an nasctha liosta. Arís, luaigh mé níos luaithe nach ndéanann sé i ndáiríre ábhar má táimid ag a chaomhnú é in aon ordú, agus mar sin b'fhéidir go bhfuil a clue. Agus chonaic tú cad a tharlódh dá linn a Theastaigh to-- nó ó díreach dara ó shin nuair a bhí muid ag dul trí cuardaigh tú D'fhéadfadh a fheiceáil cad a d'fhéadfadh tharlóidh má bhí muid ag iarraidh a chur isteach ag deireadh an liosta. Toisc nach bhfuil againn pointeoir go dtí deireadh an liosta. 

Mar sin, ar an gcúis go mbeadh mé ag iarraidh a chur isteach ag an tús, Is mar is féidir liom é a dhéanamh láithreach. Tá mé pointeoir ag an tús, agus beidh orainn a fheiceáil seo i radharc sa dara. Ach más mian liom a chur isteach ag an deireadh, Caithfidh mé a thosú ag an tús, Traverse léir ar an mbealach chun an deireadh, agus ansin tack ar. Mar sin, bheadh ​​a chiallaíonn go a chur isteach i ndeireadh an liosta Bheadh ​​bheith o de n oibriú, ag dul ar ais chun ár plé ar castacht ríomhaireachta. Ba mhaith sé a bheith ina o oibriú n, i gcás ina mar an liosta a fuair níos mó, agus níos mó, agus níos mó, beidh sé a bheith níos mó agus níos deacra rud éigin a tack ar ag an deireadh. Ach tá sé i gcónaí i ndáiríre éasca a rud éigin ar tack ag an tús, tá tú i gcónaí ag an tús. 

Agus beidh orainn a fheiceáil ar amhairc an arís. Agus ansin nuair a bhíonn déanta againn, uair amháin tá muid isteach an nód nua, ba mhaith linn a thabhairt ar ais ár n-pointeoir le an ceann nua de liosta nasctha, a ós rud é tá muid ag chur isteach ag an ag tosú a bheidh, a iarbhír pointeoir leis an nód a cruthaíodh againn ach. A ligean ar a shamhlú seo, mar gheall ar mo thuairimse, beidh sé cabhrú leat. 

Mar sin, tá anseo ar ár liosta, tá sé de ceithre ghné, nód ina bhfuil 15, a dhíríonn ar nód ina bhfuil 9, a pointí a nód ina bhfuil 13, a dhíríonn ar nód ina bhfuil 10, a bhfuil an null pointeoir mar a pointeoir seo chugainn ionas go bhfuil an deireadh an liosta. Mar sin, ba mhaith linn a chur isteach nód nua leis an luach 12 ag tús an liosta, cad a dhéanaimid? Bhuel, ar an gcéad táimid ag malloc spás le haghaidh na nód, agus ansin chuir muid 12 i ann. 

Mar sin, anois tá muid bainte amach pointe chinneadh, ceart? Ní mór dúinn cúpla go leideanna d'fhéadfadh muid bogadh, ba chóir a ceann muid ag bogadh ar dtús? Ar chóir dúinn a dhéanamh 12 pointe an ceann nua ar an list-- nó leithscéal dom, ba chóir dúinn a dhéanamh 12 pointe ar an ceann d'aois ar an liosta? Nó ba chóir dúinn a rá go bhfuil an liosta Tosaíonn anois ag 12. Níl idirdhealú ann, agus beidh muid ag breathnú ar an méid a tharlaíonn leis an dá sa dara. 

Ach a thugann sé sin ábhar mór do sidebar, atá bhfuil ceann de na rudaí trickiest le liostaí nasctha Tá a shocrú na leideanna san ord ceart. Má rudaí a bhogann tú as ord, Is féidir leat suas go deireadh thaisme orphaning an chuid eile den liosta. Agus anseo sampla de sin. Mar sin, a ligean ar dul leis an smaoineamh of-- go maith, tá muid a cruthaíodh ach 12. Tá a fhios againn go 12 ag dul a bheith an ceann nua ar an liosta, agus mar sin cén fáth nach bogadh againn ach an liosta pointeoir a chur in iúl ann. 

OK, mar sin go maith. Mar sin, anois i gcás ina ndéanann 12 pointe eile? Ciallaíonn mé, amhairc féidir linn a fheiceáil go mbeidh sé in iúl go 15, mar dhaoine tá sé i ndáiríre soiléir a chur chugainn. Cén chaoi a bhfuil a fhios an ríomhaire? Ní chuirimid bhfuil aon rud ag cur in iúl go 15 níos mó, ceart? 

Táimid tar éis a cailleadh aon cumas chun tagairt a dhéanamh 15. Ní féidir linn a rá arrow nua ionann chugainn rud éigin, níl aon rud ann. Go deimhin, tá muid dílleachtaí an chuid eile den liosta ag déanamh amhlaidh, tá muid briste thaisme an slabhra. Agus muid cinnte nach bhfuil ag iarraidh a dhéanamh sin. 

Mar sin, a ligean ar dul ar ais agus iarracht seo arís. B'fhéidir an rud ceart a dhéanamh Is a shocrú 12 s pointeoir seo chugainn go dtí an ceann d'aois ar an chéad liosta, ansin is féidir linn bogadh an liosta os a chionn. Agus go deimhin, is é sin an ord ceart go ndéanaimid Ní mór a leanúint nuair a bhíonn muid ag obair le liosta a nasctha ina n-aonar. Ba mhaith linn i gcónaí a cheangal ar an Gné nua isteach ar an liosta, sula chur orainn chineál sin de céim thábhachtach a athrú áit a bhfuil an ceann an liosta nasctha. Arís, tá go leithéid de rud bunúsach, nach bhfuil muid ag iarraidh súil a choinneáil ar é a chailleadh. 

Mar sin, ba mhaith linn a dhéanamh cinnte go tá gach rud chained le chéile, sula bogadh go pointeoir. Agus mar sin go mbeadh sé seo a bheith ar an ord ceart, a bhfuil a nascadh 12 ar an liosta, ansin a rá go dtosaíonn an liosta a 12. Má dúirt táimid ag thosaíonn an liosta ag 12 agus ansin iarracht chun nascadh 12 ar an liosta, táimid ag feiceáil cheana féin cad a tharlaíonn. Caillfidh muid an liosta de dhearmad. 

OK, mar sin rud amháin níos mó chun labhairt faoi. Cad más mian linn a fháil haitheantas coibhneasta de liosta ar fad nasctha ag an am céanna? Arís, tá muid ag mallocing go léir an spás, agus mar sin againn Ní mór go saor in aisce é nuair a bhíonn muid ag déanamh. Mar sin, anois ba mhaith linn a scriosadh ar an liosta nasctha ar fad. Bhuel, cad ba mhaith linn a dhéanamh? 

Má tá muid bainte amach an pointeoir null, táimid ag ag iarraidh a stopadh, ar shlí eile, ach a scriosadh an chuid eile den liosta agus ansin saor mé. Scrios an chuid eile den liosta, agus ansin saor in aisce ar an nód atá ann faoi láthair. Cad a dhéanann go bhfuil fuaim cosúil le, cén teicníc mór labhair muid dhéanann thart roimhe sin fhuaim mhaith? Scrios gach duine eile, ansin teacht ar ais agus a scriosadh dom. 

Sin athchúrsáil, atá déanta againn ar an fadhb le beagán níos lú, táimid ag rá a scriosadh gach duine eile, ansin is féidir leat a scriosadh dom. Agus níos faide síos an bóthar, nód sin Beidh rá, a scriosadh gach duine eile. Ach sa deireadh beidh orainn a fháil chun an pointe ina bhfuil an liosta null, agus go bhfuil ár gcás bonn. 

Mar sin, a ligean ar ghlacadh le breathnú ar seo, agus conas a d'fhéadfadh an obair seo. Mar sin, tá anseo ar ár liosta, tá sé mar an gcéanna liosta a bhí muid ag caint díreach faoi, agus níl na céimeanna. Níl a lán de téacs anseo, ach tá súil againn go mbeidh an léirshamhlú cabhrú. 

Mar sin, táimid have-- agus tharraing mé freisin suas ár frámaí Stack léiriú as ár físeán ar cruacha glaoch, agus táthar ag súil seo ar fad a thaispeáint le chéile agat cad atá ar siúl. Mar sin, tá anseo ar ár cód pseudocode. Má shroicheann muid null pointeoir, stad, ar shlí eile, scriosadh an chuid eile den liosta, ansin saor in aisce ar an nód atá ann faoi láthair. Mar sin ceart anois, list-- an pointeoir go mbeimid dul isteach chun pointí a scrios go dtí 12. Ní 12 pointeoir null, mar sin tá muid ag dul go dtí scriosadh an chuid eile den liosta. 

Cad atá ag scriosadh an chuid eile againn i gceist? Bhuel, ciallaíonn sé ag déanamh glaoch a mhilleadh, ag rá go 15 is é an tús an chuid eile den liosta ba mhaith linn a mhilleadh. Agus mar sin an glaoch a mhilleadh 12 Tá de chineál ar ar a shealbhú. Tá sé seo reoite ann, ag fanacht leis an glaoch a mhilleadh 15, a chríochnú a post. 

Bhuel, nach bhfuil 15 pointeoir null, agus mar sin tá sé ag dul a rá, ceart go léir, go maith, a scriosadh an chuid eile den liosta. An chuid eile den liosta a thosaíonn ag 9, agus mar sin beidh muid díreach fanacht go dtí go scriosann tú go léir go rudaí mar sin, ansin teacht ar ais agus a scriosadh dom. Bhuel tá 9 ag dul a rá, go maith, Níl mé pointeoir null, mar sin a scriosadh an chuid eile ar an liosta ó anseo. Agus mar sin déan iarracht agus scrios 13. 13 deir, nach bhfuil mé pointeoir null, rud céanna, Gabhann sé an buck. Níl an 10 pointeoir null, 10 Tá pointeoir null, ach ní féin é 10 null pointeoir ceart anois, agus mar sin a théann sí an buck freisin. 

Agus liosta anois pointí ann, sé Bheadh ​​pointe i ndáiríre a some-- má bhí mé níos mó spáis sa íomhá, go mbeadh sé pointe ar roinnt spáis randamach nach bhfuil a fhios againn cad é. Tá sé an pointeoir null áfach, ar an liosta Tá literally leagtha anois tá sé luachanna null. Tá sé seo ag cur in iúl ceart taobh istigh go bosca dearg. Shroich muid pointeoir null, mar sin Is féidir linn a stopadh, agus táimid ag ag déanamh. 

Agus mar sin go bhfuil fráma corcra now-- ag an barr an stack-- gur ar an fráma gníomhach, ach tá sé déanta. Má tá muid bainte amach pointeoir null, stop. Ní chuirimid aon rud a dhéanamh, táimid ag Ní féidir saor in aisce ar pointeoir null, ní raibh muid ar aon malloc spás, agus mar sin táimid ag déanamh. Mar sin, go fráma fheidhm scriosta, agus táimid ag resume-- muid ag piocadh suas áit ad'fhág muid amach leis an chéad ceann is airde, a tá an fráma gorm dorcha anseo. Mar sin, táimid ag piocadh suas ceart nuair a d'fhág muid amach. Scriosadh muid an chuid eile de na liosta cheana, mar sin anois tá muid ag dul go dtí saor in aisce na nóid atá ann faoi láthair. Mar sin, anois is féidir linn saor in aisce seo a nód, agus anois tá muid bainte amach faoi dheireadh na feidhme. Agus mar sin go fráma fheidhm scriosta, agus táimid ag piocadh suas ag an gceann gorm éadrom. 

Mar sin, says-- sé Tá mé done-- cheana scriosadh an chuid eile den liosta, agus mar sin saor in aisce ar an nód atá ann faoi láthair. Agus anois tá an fráma buí ar ais ar bharr an chairn. Agus mar sin mar a fheiceann tú, tá muid anois milleadh an liosta ó ceart ar chlé. 

Cad a tharla, áfach, dá mbeadh déanta againn rudaí ar an mbealach mícheart? Díreach mar nuair a rinne muid a chur gné. Má messed muid suas an slabhra, más rud é ní raibh muid a nascadh na leideanna san ord ceart, má táimid ach freed an chéad eilimint, má freed againn ach an ceann an liosta, anois táimid ag nach bhfuil aon bhealach chun tagairt a dhéanamh an chuid eile den liosta. Agus mar sin ba mhaith linn a bheith gach rud dílleachtaí, ba mhaith linn go raibh cad atá ar a dtugtar sceitheadh ​​chuimhne. Má tá tú chun cuimhne as ár físeán ar leithdháileadh cuimhne dinimiciúil, ní go an rud an-mhaith. 

Mar sin, mar a dúirt mé, tá Tá roinnt oibríochtaí gur gá dúinn a úsáid a bheith ag obair liosta le nasctha go héifeachtach. Agus féadfaidh tú faoi deara ar lár mé amháin, scriosadh eilimint amháin ó nasctha liosta. An chúis a rinne mé go is tá sé i ndáiríre de chineál ar tricky smaoineamh ar conas a scriosadh eilimint amháin ina n-aonar ó liosta nasctha. Ní mór dúinn a bheith in ann a scipeáil thar rud éigin ar an liosta, a ciallaíonn fháil againn go dtí sin táimid point-- ag iarraidh seo a scriosadh node-- ach d'fhonn a dhéanamh air mar sin againn ní chailleann aon fhaisnéis, ní mór dúinn a nascadh seo nód thar anseo, anseo. 

Mar sin, rinne mé dócha go mícheart ó thaobh amhairc. Mar sin, tá muid ag tús na ár liosta, tá muid ag dul tríd, ba mhaith linn a scriosadh an nód. Má táimid scriosadh ach é, tá muid briste ar an slabhra. Seo nód dheis anseo Tagraíonn gach rud eile, go bhfuil ann an slabhra ó anseo ar amach. 

Mar sin, an méid is gá dúinn a dhéanamh i ndáiríre tar éis dúinn leis an bpointe seo, Is gá dúinn a céim siar amháin, agus nascadh an nód anonn go dtí an nód, ionas gur féidir linn a scriosadh ansin an ceann i lár. Ach ní liostaí nasctha ina n-aonar ar fáil dúinn ar bhealach chun dul ar gcúl. Mar sin, ní mór dúinn a choinneáil ar ceachtar dhá threo, agus iad a bhogadh saghas céim amach, ceann amháin taobh thiar de na eile de réir mar a théann muid, nó a fháil go pointe agus ansin a sheoladh pointeoir eile tríd. Agus mar is féidir leat a fheiceáil, é a Is féidir a fháil ar salach beag. Fortunately, ní mór dúinn ar bhealach eile a réiteach go, nuair a labhairt linn faoi liostaí nasctha doubly. 

Tá mé Doug Lloyd, is é seo CS50.