[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.