[Powered by Google Translate] I gcláir, is gá dúinn go minic chun ionadaíocht a dhéanamh ar liostaí na luachanna, cosúil leis an ainmneacha na mac léinn i rannóg nó a n-scóir ar an tráth na gceist is déanaí. 

Sa teanga C, a dhearbhú gur féidir arrays a úsáid chun liostaí a stóráil. Tá sé éasca a enumerate na gnéithe de liosta stóráil in eagar, agus más gá duit chun rochtain a nó a mhodhnú an ghné liosta sháith do roinnt innéacs treallach mé, is féidir a dhéanamh in am i gcónaí, ach eagair míbhuntáistí a bheith acu, freisin. 

Nuair a dhearbhú dóibh, táimid ag teastáil a rá suas chun tosaigh cé chomh mór atá siad, is é sin, cé mhéad gnéithe féidir iad a stóráil agus cé chomh mór na heilimintí seo iad, atá arna chinneadh ag a n-cineál. Mar shampla, slánuimhir Arr (10) Is féidir a stóráil 10 míreanna Tá go bhfuil an méid ina slánuimhir. 

Ní féidir linn a athrú le sraith ar mhéid tar éis dearbhú. Ní mór dúinn a dhéanamh ar raon nua más mian linn a stóráil eilimintí níos mó. Is é an chúis ann leis an teorainn go bhfuil ár clár stórálann an réimse iomlán mar smután tadhlach de chuimhne. Abair é seo an maolán i gcás stóráil againn in ár eagar. Fhéadfadh a bheith ann athróga eile suite ceart aice leis an eagar i gcuimhne, mar sin ní féidir linn ach a dhéanamh ar an eagar níos mó. 

Uaireanta ba mhaith linn a thrádáil ar an raon luas rochtana tapa sonraí le haghaidh solúbthachta beagán níos mó. Cuir isteach an liosta nasctha, struchtúr eile sonraí bunúsacha nach dtiocfadh leat a bheith chomh eolach. Ag leibhéal ard, Stórálann liosta nasctha sonraí i sraith de nóid atá nasctha le chéile le naisc, mar sin, an t-ainm 'liosta nasctha.' Mar beidh orainn a fheiceáil, an difríocht i ndearadh cúis le buntáistí éagsúla agus na míbhuntáistí a ná eagar. 

Seo roinnt cód C le haghaidh liosta an-simplí nasctha na slánuimhreacha. Is féidir leat a fheiceáil go bhfuil muid ionadaíocht gach nód ar an liosta mar struct ina bhfuil 2 rudaí, slánuimhir a stóráil ar a dtugtar 'val' agus nasc leis an nód seo chugainn ar an liosta a ionadaíocht againn mar pointeoir ar a dtugtar 'seo chugainn.' Sa tslí seo, is féidir linn a rian ar an liosta iomlán le pointeoir ach amháin leis an nód 1, agus ansin is féidir linn leanúint ar an leideanna romhainn leis an nód 2, leis an nód 3, leis an nód 4, agus mar sin de, go dtí go bhfaigheann muid go dtí an deireadh an liosta. 

D'fhéadfá a bheith in ann a fheiceáil 1 buntáiste aige seo thar an struchtúr sraith statach - le liosta nasctha, ní mór dúinn le smután mór de chuimhne ar fad. D'fhéadfaí an nód 1 ar an liosta beo ag an áit seo i gcuimhne, agus d'fhéadfadh a bheith ar an nód 2 léir ar an mbealach thar anseo. Is féidir linn a fháil do na nóid aon ábhar ina bhfuil siad i gcuimhne, mar gheall ag tosú ag an nód 1, gach nód ar pointeoir eile insíonn dúinn go díreach cá háit le dul amach romhainn. 

Ina theannta sin, ní féidir linn a rá suas chun tosaigh cé chomh mór a bheidh ar liosta nasc ar an mbealach a dhéanann muid le arrays statach, toisc gur féidir linn a choinneáil nóid cur le liosta chomh fada agus tá spás áit éigin i gcuimhne do nóid nua. Dá bhrí sin, tá liostaí nasctha éasca a athrú dinimiciúil. Abair, níos déanaí sa chlár is gá dúinn a chur nóid níos mó isteach inár liosta. A chur isteach i nód nua a thabhairt isteach ar ár liosta ar an eitilt, gach ní mór dúinn a dhéanamh ná a cuimhne a dháileadh le haghaidh an nód, plop i luach sonraí, agus ansin, áit é an áit ba mhaith linn a leasú trí na leideanna cuí. 

Mar shampla, má bhíomar ag iarraidh chun áit a nód i idir an nóid 2ú agus 3ú an liosta,  ní ba mhaith linn a bhogadh na nóid 2 nó 3 ar chor ar bith. Abair táimid isteach an nód dearg. Gach ba mhaith linn a dhéanamh ná a leagtar ar an nód nua pointeoir seo chugainn a chur in iúl leis an nód 3 agus rewire ansin an nód 2 ar pointeoir eile a chur in iúl ar ár nód nua. Mar sin, is féidir linn a Athraigh ár liostaí ar an eitilt ós rud é nach bhfuil ar ár ríomhaire ag brath ar innéacsú, ach ar nascadh leideanna a úsáid chun iad a stóráil. 

Liostaí sin féin, faoi mhíbhuntáiste de nasctha is é sin, murab ionann agus sraith statach, ní féidir leis an ríomhaire a léim díreach go dtí an lár an liosta. Ós rud é go bhfuil an ríomhaire chun cuairt a thabhairt gach nód sa liosta nasctha a fháil chun an céad ceann eile, tá sé ag dul a ghlacadh níos faide a fháil nód ar leith ná mar a bheadh ​​sé i sraith. Chun lean Bíonn an liosta iomlán ama comhréireach le fad an liosta, nó O (n) i nodaireacht asymptotic. Ar an meán, a bhaint amach ar aon nód freisin Tógann am i gcomhréir leis n. 

Anois, a ligean ar scríobh iarbhír roinnt cód go n-oibríonn le liostaí nasctha. Ligean le rá ba mhaith linn liosta nasctha de slánuimhreacha. Is féidir linn ionadaíocht a dhéanamh ar nód i ár liosta arís mar struct le 2 réimsí, luach slánuimhir a dtugtar 'val' agus pointeoir in aice leis an nód eile den liosta. Bhuel is cosúil, simplí go leor. 

Ligean le rá ba mhaith linn a scríobh le feidhm a thrasnaíonn an liosta agus priontaí amach na luach atá stóráilte sa nód deiridh den liosta. Bhuel, ciallaíonn sé go beidh orainn a Traverse na nóid ar an liosta chun teacht ar an ceann deireanach, ach ós rud é nach bhfuil muid ag cur nó a scriosadh rud ar bith, nach bhfuil muid ag iarraidh a athrú struchtúr inmheánach na leideanna eile ar an liosta. 

Mar sin, beidh orainn gá pointeoir go sonrach le haghaidh traversal a beidh muid ag glaoch 'crawler.' Beidh sé crawl trí gach gné den liosta trí na slabhra leideanna seo chugainn. Tá gach ní mór dúinn a stóráil ar pointeoir leis an nód 1, nó 'ceann' an liosta. Pointí Ceann leis an nód 1. Tá sé de chineál pointeoir-go-nód. 

Chun a fháil ar iarbhír an 1ú nód ar an liosta, ní mór dúinn a téigh i pointeoir seo, ach sular féidir linn téigh é, ní mór dúinn a sheiceáil má tá an biorán nialasach ar dtús. Má tá sé null, tá an liosta folamh, agus ba chóir dúinn a phriontáil amach teachtaireacht, toisc go bhfuil an liosta folamh, níl aon nód seo caite. Ach, a rá a ligean ar nach bhfuil an liosta folamh. Más rud é nach bhfuil sé, ansin ba chóir dúinn crawl tríd an liosta iomlán go dtí go bhfaigheann muid go dtí an nód deiridh an liosta, agus conas is féidir linn a insint má tá muid ag breathnú ar an nód deiridh sa liosta? 

Bhuel, má tá nód ar pointeoir eile faoin margadh saothair, tá a fhios againn táimid ag an deireadh ós rud é go mbeadh an pointeoir deiridh eile nach bhfuil aon nód seo chugainn ar an liosta a chur in iúl go. Tá dea-chleachtas é a choinneáil i gcónaí ar an nód seo caite pointeoir eile initialized nialasach go bhfuil maoin caighdeánaithe a foláirimh dúinn nuair atá bainte amach againn an deireadh an liosta. 

Mar sin, má tá crawler → chugainn faoin margadh saothair, cuimhnigh go bhfuil an chomhréir arrow aicearra chun dereferencing ar pointeoir go struct, rochtain a fháil ar ansin dá réimse eile coibhéiseach leis an awkward: (* Crawler). Seo chugainn. Nuair atá againn fuair an nód deiridh, ba mhaith linn a phriontáil crawler → Val, an luach sa nód reatha Tá a fhios againn an ceann deireanach. Seachas sin, más rud é nach bhfuil muid go fóill ag an nód deiridh sa liosta, ní mór dúinn a bhogadh ar aghaidh go dtí an nód seo chugainn ar an liosta agus seiceáil más rud é go an ceann deireanach. Chun seo a dhéanamh, a leag muid ach ár pointeoir crawler a chur in iúl leis an nód reatha luach seo chugainn, is é sin, an nód seo chugainn ar an liosta. Déantar é seo trí leagan crawler = crawler → seo chugainn. Ansin againn arís an próiseas seo, le lúb mar shampla, go dtí go bhfaighidh muid ag an nód deiridh. Mar sin, mar shampla, má bhí crawler dírithe ar cheann, a leag muid crawler a chur in iúl do crawler → seo chugainn, Is é atá mar an gcéanna leis an réimse eile den nód 1. Mar sin, tá anois ar ár crawler dírithe ar an nód 2, agus, arís, arís muid seo le lúb, go dtí go atá déanta againn go raibh an nód deiridh, is é sin, ina bhfuil an nód ar pointeoir eile atá dírithe ar nialasach. Agus ní mór dúinn é, tá muid fuair an nód deiridh sa liosta, agus a phriontáil a luach, linn a úsáid ach crawler → Val. 

Ní thrasnaíonn olc sin, ach cad faoi chur isteach? Let a rá ba mhaith linn a chur isteach slánuimhir isteach sa suíomh 4 i liosta slánuimhir. Is é sin idir na nóid atá ann faoi láthair 3 agus 4. Arís, ní mór dúinn an liosta lean ach a fháil chun an ghné 3, an ceann táimid ag chur isteach i ndiaidh. Mar sin, ní mór dúinn a chruthú pointeoir crawler arís chun Traverse an liosta, seiceáil an bhfuil ár n-pointeoir nialasach ceann, agus más rud é nach bhfuil sé, pointe ár pointeoir crawler ag an nód ceann. Mar sin, táimid ag an eilimint 1. Ní mór dúinn dul ar aghaidh 2 heilimintí níos mó sular féidir linn a chur isteach, ionas gur féidir linn a úsáid le haghaidh lúb slánuimhir i = 1; i <3; i + + agus i ngach leagan den lúb, chun cinn ár n-pointeoir crawler ar aghaidh ag 1 nód ag seiceáil má tá an nód reatha réimse eile faoin margadh saothair, agus más rud é nach bhfuil sé, ár pointeoir crawler a bhogadh chuig an nód seo chugainn ag leagan síos comhionann é leis an nód reatha pointeoir seo chugainn. Mar sin, a deir ós rud é ár lúb le haghaidh a dhéanamh go faoi ​​dhó, tá muid bainte amach an nód 3, agus tá ár n-pointeoir crawler sroichte ach amháin nuair an nód tar éis a ba mhaith linn a chur isteach ar ár slánuimhir nua, conas is féidir linn i ndáiríre a dhéanamh ar an chur isteach? 

Bhuel, tá ár slánuimhir nua a chur isteach ar an liosta mar chuid dá struct nód féin, ós rud é seo i ndáiríre sraith de nóid. Mar sin, a ligean ar a pointeoir nua a dhéanamh ar nód ar a dtugtar 'new_node,' agus leag sé a chur in iúl chun cuimhne go bhfuil muid a leithdháileadh anois ar an gcarn le haghaidh an nód féin, agus cé mhéid a chuimhne is gá dúinn a leithroinnt? Bhuel, an méid nód, agus ba mhaith linn dá réimse Val leagtar dtí an tslánuimhir is go ba mhaith linn a chur isteach. Ligean le rá, 6. Anois, tá an nód dár luach slánuimhir. Tá sé freisin dea-chleachtas a thúsú an nód nua réimse seo chugainn a chur in iúl nialasach, ach anois cad é? 

Tá a athrú ar an struchtúr inmheánach an liosta agus na leideanna seo chugainn atá ar an liosta ar ann cheana féin Nóid 3 agus 4. Ós rud é na leideanna seo chugainn an t-ord an liosta, agus ós rud é tá muid isteach ar ár nód nua ceart i lár an liosta, Is féidir é a bheith ina giotán tricky. Tá sé seo toisc, cuimhnigh, is é ár ríomhaire ach amháin a fhios ag an suíomh na nóid ar an liosta mar gheall ar an leideanna romhainn atá stóráilte sa an nóid roimhe sin. Mar sin, má chaill muid riamh rian ar bith de na suímh seo, a rá trí athrú a dhéanamh ar cheann de na leideanna eile i ár liosta, mar shampla, a rá athraigh muid an nód 3 ar réimse eile a chur in iúl ar roinnt nód thar anseo. Ba mhaith linn a bheith as luck, toisc nach mbeadh orainn bhfuil aon smaoineamh nuair a aimsiú ar an gcuid eile den liosta, agus tá go léir go dona. Mar sin, ní mór dúinn a bheith cúramach i ndáiríre faoi an t-ordú ina bhfuilimid ag ionramháil ár leideanna seo chugainn le linn chur isteach. 

Mar sin, seo a shimpliú, a ligean ar rá go ár gcéad 4 nóid Tugtar A, B, C, agus D, agus na saigheada a ionadaíonn do na slabhra leideanna a nascadh leis an nóid. Mar sin, is gá dúinn a chur isteach ar ár nód nua i idir nóid C agus D. Tá sé ríthábhachtach é a dhéanamh san ord ceart, agus beidh mé léiríonn tú cén fáth. 

Ligean ar breathnú ar an bealach mícheart a dhéanamh ar dtús. Hey, tá a fhios againn go bhfuil an nód nua atá le teacht ceart tar éis C, sin a ligean leagtha pointeoir seo chugainn C a chur in iúl go new_node. Gach ceart is cosúil, maith go leor, ní mór dúinn ach a chríochnú suas anois ag a dhéanamh ar an nód nua pointe pointeoir in aice le D, ach fan, conas is féidir linn a dhéanamh? An rud amháin a d'fhéadfadh a insint dúinn nuair a bhí D, Bhí an pointeoir eile atá stóráilte cheana i C, ach rewrote againn ach go pointeoir a chur in iúl leis an nód nua, mar sin againn a thuilleadh go mbeadh aon leid nuair atá D i gcuimhne, agus tá muid chaill an chuid eile den liosta. Ní maith ar chor ar. 

Mar sin, conas a dhéanann muid an ceart? Gcéad dul síos, pointe an nód nua pointeoir chugainn ag D. Anois, leideanna araon an nód ar nua agus C chugainn Tá dírithe ar an nód céanna, D, ach sin fíneáil. Anois is féidir linn pointe pointeoir seo chugainn C ag an nód nua. Mar sin, tá muid é seo gan aon chailliúint sonraí. I cód, gurb é C an nód atá ann faoi láthair go bhfuil an pointeoir traversal crawler dírithe, agus tá D ionadú ag an nód aird ar an nód reatha réimse seo chugainn, nó crawler → seo chugainn. Mar sin, a leag muid ar dtús leis an nód nua pointeoir seo chugainn a chur in iúl do crawler → seo chugainn, ar an mbealach céanna a dúirt muid ba chóir pointeoir seo chugainn new_node ar pointe go D sa léaráid. Ansin, is féidir linn a leagtar ar an nód reatha pointeoir eile chun ár nód nua, díreach mar a bhí againn chun fanacht le pointe C new_node sa líníocht. Anois tá gach rud in ord, agus nach raibh againn a chailleadh rianú aon sonraí, agus bhí muid in ann ach bata ár nód nua i lár an liosta gan atógáil an rud ar fad nó fiú aistriú aon ghnéithe ar an mbealach ba mhaith linn a bhí acu a le sraith seasta fad. 

Mar sin, tá liostaí nasctha le, bunúsach, ach tábhachtach dinimiciúil sonraí struchtúr a bhfuil an dá buntáistí agus míbhuntáistí i gcomparáid le arrays agus struchtúir sonraí eile, agus is minic an cás san eolaíocht ríomhaireachta, tá sé tábhachtach go mbeadh a fhios nuair a úsáid gach uirlis, ionas gur féidir leat a roghnú an uirlis ceart don phost ceart. 

Le haghaidh cleachtas níos mó, déan iarracht feidhmeanna scríobh chuig scriosadh nóid ó liosta nasctha - cuimhnigh a bheith cúramach faoi an t-ordú ina bhfuil tú rearrange do leideanna seo chugainn chun a chinntiú nach gcailleann tú le smután de do liosta - nó feidhm ag comhaireamh an nóid i liosta nasctha, nó ceann spraoi, a athrú an t-ordú gach ceann de na nóid i liosta nasctha. 

Is é mo ainm Jackson STEINKAMP, is é seo CS50.