[Powered by Google Translate] Nan pwogram, nou souvan bezwen reprezante lis valè yo, tankou non yo nan elèv ki nan yon seksyon oswa nòt yo sou egzamen an dènye. 

Nan lang C, te deklare ranje yo ka itilize nan magazen lis. Li fasil eksplike eleman ki nan yon lis ki estoke nan yon etalaj, epi si ou bezwen gen aksè a oswa modifye eleman nan lis on pou kèk endèks abitrè mwen menm, ki ka fè l 'nan tan konstan, men ranje gen dezavantaj, tou. 

Lè nou deklare yo, n ap oblije di moute devan ki jan gwo yo ye a, ki se, konbyen eleman yo ka magazen ak ki jan gwo eleman sa yo se, ki se detèmine pa tip yo. Pou egzanp, int ArR (10) ka magazen 10 atik ki se gwosè a nan yon int. 

Nou pa kapab chanje gwosè yon etalaj an apre li fin deklarasyon an. Nou dwe fè yon etalaj nouvo si nou vle nan magazen plis eleman. Rezon ki fè yo sa a limitasyon ki egziste se ke nou pwogram estoke etalaj nan tout antye kòm yon moso vwazen nan memwa. Di sa a se zòn de defans nan kote nou ki estoke nan etalaj nou an. Ke ka gen kèk lòt ki chita dwat akote etalaj la nan memwa, se konsa nou pa kapab jis fè etalaj la pi gran. 

Pafwa nou ta renmen komès vit etalaj la done vitès aksè pou yon ti kras fleksibilite plis. Antre nan lis la lye, yon lòt estrikti done debaz ou pa ta ka kòm abitye avèk yo. Nan yon nivo segondè yo, yon lis lye estoke done nan yon sekans nan nœuds ki gen rapò ak chak lòt ak lyen yo, pakonsekan 'lye lis la.' non an Kòm nou pral wè, diferans sa a nan konsepsyon mennen nan avantaj ak dezavantaj diferan pase yon etalaj. 

Isit la nan kèk kòd C pou yon lis trè senp lye nan nonm antye relatif. Ou ka wè ke nou te reprezante chak ne nan lis la kòm yon struct ki gen 2 bagay sa yo, yon nonb antye relatif nan magazen yo rele 'Val' ak yon ap mennen nan ne nan pwochen nan lis la ki nou reprezante kòm yon konsèy rele 'vini yo.' Fason sa a, nou ka swiv lis la tout antye ak jis konsèy yon sèl ne nan 1ye ane, ak Lè sa a, nou ka swiv endikasyon yo kap vini ne nan 2nd, ne nan 3yèm, ne nan 4yèm, yo ak sou sa, jouk nou jwenn nan nan fen lis la. 

Ou ta ka kapab wè 1 avantaj sa a gen sou estrikti nan etalaj estatik - ak yon lis lye, nou pa bezwen yon moso gwo nan memwa tout ansanm. Ne nan 1st nan lis la te kapab viv nan kote sa a nan memwa, ak ne nan 2nd ta kapab tout wout la sou isit la. Nou ka fè nan tout nœuds yo pa gen matyè kote nan memwa yo ye a, paske kòmanse nan ne an 1ye ane, pwochen konsèy chak ne a di nou egzakteman ki kote yo ale vini yo. 

Anplis de sa, nou pa dwe di ke moute devan ki jan gwo yon lis lye va menm jan an nou fè ak ranje estatik, depi nou ka kenbe ajoute nœuds nan yon lis osi lontan ke gen nan espas yon kote nan memwa pou nœuds nouvo. Se poutèt sa, bay lis lye yo fasil Rdimansyone dynamique. Di, pita nan pwogram nan nou bezwen ajoute plis nœuds nan lis nou an. Insert yon ne nouvo nan lis nou an sou vole a, tout sa nou dwe fè se asiyen memwa pou sa ne, plok nan valè done a, ak Lè sa a, mete l 'kote nou vle pa adaptation endikasyon ki apwopriye yo. 

Pou egzanp, si nou te vle mete yon ne nan ant nœuds yo 2 zyèm ak 3 nan lis la,  nou pa ta gen pou avanse pou nœuds yo 2yèm oswa 3yèm nan tout. Di nou ap mete sa a ne wouj. Tout sa nou ta dwe fè se mete pwochen konsèy ne nan nouvo nan nan pwen ne nan 3yèm ak Lè sa a, rewire pwochen konsèy ne nan 2nd nan nan pwen ne nouvo nou an. Se konsa,, nou ka Rdimansyone lis nou an sou vole a depi òdinatè nou yo pa konte sou Indexing, men pito sou ki lye ak lè l sèvi avèk endikasyon nan magazen yo. 

Sepandan, yon dezavantaj ki genyen nan lye lis se ke yo, kontrèman ak yon etalaj estatik, òdinatè a pa ka jis Ale nan mitan an nan lis la. Depi òdinatè a gen ale nan chak ne nan lis la lye pou li ale nan youn nan pwochen, li pral pran plis tan sa yo jwenn yon ne patikilye pase sa li ta nan yon etalaj. Traverse lis la tout antye pran tan pwopòsyonèl longè nan lis la, oswa O (n) nan asenptotik notasyon. Nan mwayèn, rive kote nenpòt ne tou pran tan pwopòsyonèl avèk n. 

Koulye a, kite a aktyèlman ekri kèk kòd ki travay ak lye lis. Se pou nou di nou vle yon lis lye nan nonm antye relatif. Nou ka reprezante yon ne nan lis nou an ankò kòm yon struct ak 2 chan sa yo, yon valè nonb antye relatif rele 'Val' ak yon konsèy akote ne nan pwochen nan lis la. Oke, sanble senp ase. 

Se pou nou di nou vle ekri yon fonksyon ki travèrs lis la ak simagri soti nan valè ki estoke nan ne an dènye nan lis la. Bon, ki vle di nou pral bezwen Traverse tout nœuds yo ki nan lis la jwenn youn nan sot pase yo, men depi nou pa ap ajoute oswa efase anyen, nou pa vle chanje estrikti nan entèn nan pwent yo pwochen nan lis la. 

Se konsa, nou pral bezwen yon konsèy espesyalman pou parcourt ki n ap rele 'krole. Li pral rale atravè tout eleman ki nan lis la nan suiv chèn nan pwent kap vini an. Tout sa nou te sere a se yon konsèy ne nan 1ye ane, 'oswa' tèt 'nan lis la. Head pwen ne la 1st. Li nan nan kalite konsèy-a-ne. 

Pou jwenn vrè 1ye ne a nan lis la, nou dwe dèreferans sa a konsèy, men nou avan nou kapab dèreferans li, nou bezwen yo tcheke si konsèy la se nil an premye. Si li la nil, lis la se vid, e nou ta dwe enprime soti yon mesaj ke, paske lis la se vid, pa gen okenn ne dènye. Men, kite a di lis la se pa vid. Si li pa, lè sa a nou ta dwe rale nan lis la tout antye jiskaske nou jwenn yo ne an dènye nan lis la, ak ki jan nou ka di si nou ap chèche nan ne an dènye nan lis la? 

Byen, si konsèy pwochen yon ne a se nil, nou konnen nou se nan fen a depi dènye konsèy nan pwochen pa ta gen okenn ne pwochen nan lis la nan pwen yo. Li nan bon pratik toujou kenbe pwochen konsèy ne an dènye a inisyalizèd nil gen yon pwopriyete ofisyèl ki AVÈTISMAN nou lè nou te rive nan fen an de lis la. 

Se konsa, si krole → pwochen se nil, sonje ke sentaks la flèch se yon chemen kout pou dereferencing yon konsèy nan yon struct, lè sa a gen aksè nan jaden pwochen li yo ekivalan a gòch la: (* Krole). Vini yo. Yon fwa nou te jwenn ne an dènye, nou vle enprime krole → Val, valè a nan ne aktyèl la ki nou konnen se youn nan dènye. Sinon, si nou pa ankò nan ne an dènye nan lis la, nou gen pou avanse pou sou ne nan pwochen nan lis la epi tcheke si se yon sèl an dènye. Pou fè sa, nou jis mete konsèy krole nou nan pwen nan valè pwochen ne yo ye a, ki se, ne nan pwochen nan lis la. Sa a se fè pa mete krole = krole → kap vini an. Lè sa a, nou repete pwosesis sa a, ak yon riban pou egzanp, jiskaske nou jwenn ne an dènye. Se konsa, pou egzanp, si krole te lonje dwèt nan tèt, nou mete krole nan pwen krole pwochen →, ki se menm bagay la tou kòm jaden nan pwochen nan ne an 1st. Se konsa, kounye a krole nou an, ap lonje dwèt ne a 2yèm, , epi, ankò, nou repete sa a ak yon riban, jiskaske nou te jwenn ne an dènye, se sa ki, kote pwochen konsèy ne la se lonje dwèt nil. Se la nou genyen li, nou te jwenn ne an dènye nan lis la, ak nan enprime valè li yo, nou jis itilize krole → Val. 

Travelers se pa konsa pou sa move, men sa ki sou yo mete? Pèmèt di nou vle insert yon nonb antye relatif nan pozisyon an 4yèm nan yon lis antye ki pè. Sa a se ant nœuds yo genyen kounye a 3yèm ak 4yèm. Yon fwa ankò, nou dwe Traverse lis la jis jwenn yo eleman nan 3yèm, youn nan nou ap mete apre. Se konsa, nou kreye yon konsèy krole ankò nan Traverse lis la, tcheke si konsèy tèt nou an, se nil, ak si li pa, montre konsèy krole nou an nan ne an tèt. Se konsa, nou ap nan eleman nan 1st. Nou gen yo ale pou pi devan 2 plis eleman, anvan nou ka insert, pou nou ka sèvi ak yon riban pou int mwen = 1; mwen <3; mwen + + ak nan chak iterasyon nan riban an, avanse konsèy krole nou devan pa 1 ne lè w tcheke si jaden pwochen ne yo ye a se nil, ak si li pa, deplase konsèy krole nou yo ne nan pwochen pa mete li egal a konsèy pwochen ne yo ye a. Se konsa, depi riban pou nou di fè sa de fwa, nou te rive jwenn ne nan 3yèm, epi yon fwa te konsèy krole nou te rive jwenn ne la apre ki nou vle insert nonb antye relatif nouvo nou an, ki jan nou aktyèlman mete la? 

Oke, nonb antye relatif nouvo nou an ki gen yo dwe mete nan lis la kòm yon pati nan struct pwòp ne li yo, depi sa a se reyèlman yon sekans nan nœuds. Se konsa, kite a fè yon konsèy ki nouvo nan ne rele 'new_node,' yo mete l 'nan pwen memwa ke nou kounye a asiyen sou pil wòch la pou ne nan tèt li, ak konbyen memwa nou bezwen asiyen? Oke, gwosè a nan yon ne, e nou vle mete jaden Val li nan nonb antye relatif a ke nou vle insert. Se pou nou di, 6. Koulye a, ne an gen valè nonb antye relatif nou an. Li la tou bon pratik inisyalize pwochen jaden ne nan nouvo nan nan pwen nil, Men, koulye a ki sa? 

Nou dwe chanje estrikti nan entèn nan lis la ak pwent yo pwochen genyen nan yo nan ki deja egziste a lis la nan 3yèm ak 4yèm nœuds. Depi pwent yo pwochen detèmine lòd la lis la, epi depi nou ap mete ne nou nouvo dwa rantre nan mitan lis la, li ka yon ti jan difisil. Sa a se paske, sonje, konpitè nou an sèlman konnen ki kote nœuds nan lis la paske nan pwent yo pwochen ki estoke nan ne yo anvan yo. Se konsa, si nou janm pèdi tras nan nenpòt nan anplasman sa yo, di pa chanje youn nan pwent yo pwochen nan lis nou an, pou egzanp, di nou chanje pwochen jaden ne nan 3yèm a nan pwen nan kèk ne sou isit la. Nou ta dwe soti nan chans, paske nou pa t 'vle gen okenn lide kote yo jwenn rès la nan lis la, ak sa a, se evidamman reyèlman move. Se konsa, nou gen yo dwe reyèlman atansyon sou lòd la nan ki nou manipile endikasyon pwochen nou an pandan ensèsyon. 

Se konsa,, nan senplifye sa a, se pou yo di ke premye nou 4 nœuds yo rele yo A, B, C, ak D, ak flèch ki reprezante chenn a endikasyon ki konekte nœuds yo. Se konsa,, nou bezwen insert ne nou nouvo nan ant nœuds C ak D. Li nan kritik fè li nan lòd ki dwat, ak mwen pral montre w pou ki rezon. 

Se pou yo gade nan fason a mal fè li an premye. Hey, nou konnen ne nan nouvo gen vini dwa apre C, kidonk kite a mete pwochen konsèy C a nan pwen new_node. Tout dwa, sanble oke, nou jis gen nan fini kounye a pa fè pwochen pwen ne nan nouvo nan konsèy nan D, Men, tann, ki jan nou ka fè sa? Bagay la sèlman ki te ka di nou kote D a te, te konsèy nan pwochen te deja ki estoke nan C, Men nou jis reekri ki konsèy nan pwen ne nan nouvo, pou nou pa gen nenpòt ki endikasyon ki kote D se nan memwa, e nou te pèdi rès la nan lis la. Pa bon nan tout. 

Se konsa, ki jan nou fè sa dwa? Premyèman, pwen pwochen konsèy ne nan nouvo a nan D. Koulye a, tou de nouvo ne la a ak nan C endikasyon pwochen yo lonje dwèt ne a menm, D, men sa a amann. Koulye a, nou ka pwente pwochen konsèy C a nan ne nan nouvo. Se konsa, nou te fè sa a san yo pa pèdi nenpòt done. Nan kòd, C se ne aktyèl la ki parcourt konsèy krole la ap lonje dwèt a, ak D a reprezante ne la pwente ke jaden pwochen ne yo ye a, oswa krole → kap vini an. Se konsa, nou premye mete pwochen konsèy ne nan nouvo nan nan pwen krole pwochen →, menm jan nou te di pwochen konsèy new_node a ta dwe lonje dwèt sou D nan ilistrasyon an. Lè sa a,, nou ka mete pwochen konsèy ne yo ye a sou nouvo ne nou an, menm jan nou menm te rete nan pwen C rive nan new_node nan desen an. Koulye a, tout bagay ap nan lòd, epi nou pa t 'pèdi swiv nan nenpòt ki done yo, epi nou yo te kapab jis bwa ne nou nouvo nan mitan an nan lis la san rebati tout bagay la oswa menm déplacement nenpòt eleman wout la nou ta yo te oblije ak yon etalaj fiks longè. 

Se konsa,, lis lye se yon debaz, men ki enpòtan yo, dinamik done estrikti ki gen tou de avantaj ak dezavantaj konpare ak ranje ak done lòt estrikti, epi kòm se souvan ka a nan syans konpitè, li enpòtan yo konnen ki lè yo sèvi ak chak zouti, pou ou kapab chwazi zouti an dwa pou travay la dwat. 

Pou plis pratik, eseye ekri fonksyon efase nœuds nan yon lis lye - sonje yo dwe pran prekosyon pou nan ki lòd ou ordonne endikasyon pwochèn ou an asire ke ou pa pèdi yon ti moso nan lis ou a - oswa yon fonksyon nan konte nœuds yo nan yon lis lye, oswa yon plezi yon sèl, nan ranvèse lòd la nan tout nan nœuds yo nan yon lis lye. 

Non mwen se Jackson Steinkamp, ​​sa a se CS50.