[Powered by Google Translate] En programado, ni ofte bezonas por reprezenti listoj de valoroj,
kiel la nomoj de studentoj en sekcio
aŭ liaj partituroj al la lasta kvizo.
>> En la lingvo C, deklaris tabeloj povas esti uzata
stoki lertaj.
Estas facile numeri la eroj de listo
stokita en tabelo, kaj se vi bezonas aliron
aŭ modifi la th,-a listo elemento
por iuj arbitraj indekso mi,
kiu povas esti farita en konstanta tempo,
sed arrays havas malavantaĝojn, ankaŭ.
>> Kiam ni deklari ilin, ni postulas por diri
ĉe fronto kiom granda estas,
tio estas, kiom da elementoj ne povas stoki
kaj kiel grandan tiuj elementoj estas, kiu estas difinita per sia tipo.
Ekzemple, int Arr (10)
povas stoki 10 artikoloj
kiuj estas la grandeco de int.
>> Ni ne povas ŝanĝi tabelo de grandeco post deklaro.
Ni devas fari novan tabelo se ni volas konservi pli elementoj.
La kialo ĉi tiu limigo ekzistas estas ke nia
programo stokas la tutan tabelo
kiel bela eron de memoro.
Diru ĉi tiu estas la bufro kie ni gardas en nia tabelo.
Povas esti aliaj variabloj
lokita tuj apud la tabelo
en memoro, do ni ne povas
nur fari la tabelo pli granda.
>> Kelkfoje ni ŝatus komerci la tabelo de rapida datumoj aliro rapido
por iom pli fleksebleco.
Entajpu la ligitaj listo, alia baza datumstrukturo
vi eble ne estos tiel familiara kun.
Je alta nivelo,
kunligita listo stokas datumojn en vico de verticoj
ke estas konektitaj inter aliaj kun ligoj,
tie la nomo 'ligitaj listo.'
Kiel ni vidos, tiu diferenco en dezajno
kondukas al malsamaj avantaĝoj kaj malavantaĝoj
ol tabelo.
>> Jen kelkaj C-kodo por tre simplaj ligitaj listo de entjeroj.
Vi povas vidi ke ni reprezentis ĉiu nodo
en la listo kiel struct kiuj enhavas 2 aferojn,
entjero stoki nomita 'val'
kaj ligon al la sekva nodo en la listo
kiuj ni reprezentas kiel puntero nomita 'sekva'.
Tiel, ni povas spuri la tutan liston
kun nur unu sagon al la 1-a nodo,
kaj poste ni povas sekvi la sekvanta punteros
al la 2a nodo,
al la 3a nodo,
al la 4a nodo,
kaj tiel plu, ĝis ni atingos la finon de la listo.
>> Vi eble povos vidi 1 avantaĝon ĉi tiu havas
super la statika tabelo strukturo - kun ligitaj listo,
ni ne bezonas grandan eron de memoro aro.
La 1-a nodo de la listo povus vivi en tiu loko en la memoro,
kaj la 2-a vertico povus esti la tuta vojo super tie.
Ni povas alveni al ĉiuj nodoj negrave kie en memoro estas,
ĉar ekde la 1a nodo, ĉiu nodo La sekva puntero
diras ni precize kien iri proksima.
>> Aldone, ni ne devas diri supren fronto
kiom granda estas ligitaj listo estos la maniero ni faras kun statika arrays,
ĉar ni povas subteni aldonante nodoj al listo
tiel longe, kiel ekzistas spaco ie en memoro por novaj nodoj.
Sekve, kunligita lertaj estas facilaj regrandigi dinamike.
Diru, poste en la programo necesas aldoni pli nodoj
en nian liston.
Por enmeti novan nodon en nia listo de la muŝo,
ĉiuj ni devas fari estas rezervi memoron por tiu nodo,
plop en la datumoj valoro,
kaj poste meti ĝin kie volas modifu la taŭgajn punteros.
>> Ekzemple, se ni volis meti nodo en inter
la 2-a kaj 3-a nodoj de la listo,
ni ne devus movi la 2-a aŭ 3-a nodoj ajn.
Diru ni enmeto ĉi ruĝa nodo.
Ĉiuj ni devus fari estas metita la nova vertico La sekva puntero
atentigi al la 3a nodo
kaj tiam ReWire la 2-a nodo La sekva puntero
atentigi al nia nova nodo.
Do, ni povas regrandigi niaj listoj en la muŝo
ekde nia komputilo ne fidi indeksado,
sed prefere en ligas uzante punteros stoki ilin.
>> Tamen, malavantaĝo de ligitaj listoj
estas ke, kontraste kun statika tabelo,
la komputilo ne povas ĝuste salti al la mezo de la listo.
Ekde la komputilo devas viziti ĉiu vertico en la ligitaj listo
alveni ĝis la sekva,
ĝi tuj preni plu trovi apartan nodon
ol would en tabelo.
Tra la tuta listo prenas tempon proporcia
al la longo de la listo,
aŭ O (n) en asimptota skribmaniero.
Averaĝe, atingante ajna nodo
ankaŭ prenas tempon proporcia al n.
>> Nun, ni reale skribi iom da kodo
kiu funkcias kun ligitaj listoj.
Supozu ke ni volas ligitaj listo de entjeroj.
Ni povas reprezenti nodo en nia listo denove
kiel struct kun 2 kampoj,
entjera valoro nomita 'val'
kaj proksima sagon al la sekva nodo de la listo.
Nu, ŝajnas sufiĉe simpla.
>> Supozu ke ni volas skribi funkcio
kiu trairas la listo kaj gravuraĵoj el la
valoro stokita en la lasta nodo de la listo.
Nu, tio signifas ke ni bezonos tra ĉiuj nodoj en la listo
trovi la lasta, sed ekde ni ne aldonante
aŭ forigi ion, ni ne volas ŝanĝi
la interna strukturo de la sekvanta punteros en la listo.
>> Do, ni bezonas puntero specife por traversal
kiuj ni vokos 'crawler.'
Ĝi rampas tra ĉiuj eroj de la listo
sekvante la ĉeno de la proksima punteros.
Ĉiuj ni stokis estas sagon al la 1-a nodo,
aŭ 'kapo' de la listo.
Kapo poentojn al la 1-a vertico.
Estas de tipo puntero-al-nodo.
>> Por ricevi la reala 1er nodo en la listo,
ni devas dereference ĉi pointer,
sed antaŭ ol ni povas dereference ĝin, ni devas kontroli
se la puntero estas nula unua.
Se estas nula, la listo estas malplena,
kaj ni devus presi mesaĝon ke, ĉar la listo estas malplena,
ne estas lasta nodo.
Sed, diru la listo ne estas malplena.
Se ĝi ne estas, tiam ni devus rampi tra la tutan liston
ĝis ni atingos la lastan nodon de la listo,
kaj kiel ni povas diri se ni rigardas la lastan nodon en la listo?
>> Nu, se vertico La sekva puntero estas nula,
ni scias ni fine
ekde la pasinta sekva puntero ne havus sekva nodo en la listo atentigi al.
Ĝi estas bona praktiko ĉiam subteni la lastan nodon La sekva puntero inicializado al nula
havi normigita propraĵo kiu alarmas nin kiam ni atingis la finon de la listo.
>> Do, se crawler → sekva estas nula,
memoru ke la sago sintakso estas simbola ligilo por dereferencing
puntero al struct, tiam alirante
lia proksima kampo ekvivalento al la mallerta:
(* Crawler). Proksima.
Iam ni trovis la lasta nodo,
ni volas presi crawler → val,
la valoron en la nuna nodo
kiuj ni scias estas la lasta.
Alie, ĉu ni ankoraŭ ne en la lasta nodo en la listo,
ni devas movi al la venonta vertico en la listo
kaj kontrolu ĉu tio estas la lasta.
Por fari tion, ni simple metis niajn crawler puntero
atentigi al la nuna nodo La sekva valoro,
tio estas, la sekvanta nodo en la listo.
Ĉi tiu estas farita per opcio
crawler = crawler → proksima.
Tiam ni ripetu ĉi tiun procezon, kun buklo ekzemple,
ĝis ni trovos la lastan nodon.
Do, ekzemple, se crawler estis indikante kapon,
ni aro crawler atentigi al crawler → proksima,
kiu estas la sama kiel la proksima kampo de la 1-a vertico.
Do, nun nia crawler notas al la 2a nodo,
kaj, denove, ni ripetu ĉi kun buklo,
ĝis ni trovis la lasta nodo, tio estas,
kie la nodo la sekva puntero notas al nula.
Kaj tie ni havas,
ni trovis la lasta nodo en la listo, kaj presi lian valoron,
ni simple uzu crawler → val.
>> Lauxiris ne estas tiel malbona, sed kio pri enmeto?
Lasas ke ni volas enmeti entjero en la 4a pozicio
en entjera listo.
Kiu estas inter la aktuala 3a kaj 4a nodoj.
Denove, ni devas trairi la listo nur por
alveni al la 3a ero, la ni enmeto poste.
Do, ni krei crawler puntero denove tra la listo,
kontroli se nia kapo puntero estas nula,
kaj se ĝi ne estas, atentigi niajn crawler puntero ĉe la kapo nodo.
Do, ni estas en la 1-a elemento.
Ni devas iri antaŭen 2 pli elementoj antaŭ ol ni povas enigi,
do ni povas uzi por buklo
int i = 1; i <3; i + +
kaj en ĉiu ripeto de la ciklo,
antaŭi nia crawler puntero antaŭen per 1 nodo
kontrolante se la nuna nodo La sekva kampo estas nula,
kaj se ĝi ne estas, movi niajn crawler sagon al la sekva nodo
per opcio ĝi egala al la nuna nodo La sekva puntero.
Do, ekde nia por buklo diras fari tion
dufoje,
ni atingis la 3-a nodo,
kaj unu fojon nia crawler puntero atingis la nodo post
kion ni volas enmeti nia nova entjero,
how do ni efektive ne la enmeto?
>> Nu, nia nova entjero devas esti enmetita en la listo
kiel parto de lia propra vertico struct,
ekde ĉi tiu estas vere vico de nodoj.
Do, ni faru novan puntero al nodo
nomita 'new_node:
kaj starigis gxin rekte al la memoro, ke ni nun atribui
sur la havaĵon por la nodo mem,
kaj kiom memoro Kion ni bezonas atribui?
Nu, la grandeco de nodo,
kaj ni volas establi lia val kampo al la entjera ke ni volas enmeti.
Diru, 6.
Nun, la nodo enhavas niajn entjera valoro.
Estas ankaŭ bona praktiko por pravalorizi la nova vertico La sekva kampo
atentigi al nula,
sed nun, kion?
>> Ni devas ŝanĝi la interna strukturo de la listo
kaj la sekvan punteros enhavita en la listo de ekzistantaj
3-a kaj 4-a nodoj.
Ekde la venonta punteros determini la ordon de la listo,
kaj pro tio ni enmeto nia nova nodo
rekte en la mezo de la listo,
ĝi povas esti iom malfacila.
Ĉi tio estas ĉar, memoru, nia komputilo
nur konas la situon de nodoj en la listo
pro la sekva punteros stokita en la antaŭa nodoj.
Do, se ni iam miskalkulis iu el tiuj lokoj,
diru ŝanĝante unu el la sekvaj indikoj en nia listo,
ekzemple, supozu ke ni ŝanĝis
la 3-a nodo La sekva kampo
atentigi al iu nodo super tie.
Ni ŝatus el sorton, ĉar ni ne volis
havi neniun ideon kie trovi la resto de la listo,
kaj tio evidente vere malbona.
Do, ni devas esti vere zorgema pri la ordo
en kiu ni manipuli nian proksiman punteros dum inserción.
>> Do, por simpligi ĉi tion, diru ke
nia unua 4 nodoj
nomas A, B, C, kaj D, kun la sagoj reprezentas la ĉeno de punteros
kiuj konektas la nodoj.
Do, ni bezonas enmeti nia nova nodo
en inter nodoj C kaj D.
Estas kritika fari ĝin en la rajton ordo, kaj mi montros al vi kial.
>> Ni rigardu la malĝusta vojo al fari ĝin unue.
Hej, ni scias la nova vertico devas veni tuj post C,
do ni starigis C La sekva puntero
atentigi al new_node.
Bone, ŝajnas bone, ni nur devas fini nun per
farante la nova vertico La sekva puntero punkto al D,
sed atendas, kiel ni povas fari?
La sola afero, kiu povus diri al ni kie D estis,
estis la sekva puntero antaŭe stokitaj en C,
sed ni nur reverkis ke puntero
atentigi al la nova nodo,
do ni ne plu havas neniun postsignon kie D estas en memoro,
kaj ni perdis la resto de la listo.
Ne bona ajn.
>> Do, kiel ni faru tiun rajton?
Unue, notas la novan nodon La sekva puntero en D.
Nun, tiel la nova nodo kaj C la sekva punteros
estas montrante la sama nodo, D,
sed tio estas bone.
Nun ni povas noti C La sekva puntero ĉe la nova nodo.
Do, ni faris tion sen perdi neniun datumon.
En kodo, C estas la nuna nodo
ke la traversal puntero crawler estas indikante,
kaj D estas reprezentita de la nodo montradis per la nuna nodo La sekva kampo,
aŭ crawler → proksima.
Do, ni unue starigis la nova vertico La sekva puntero
atentigi al crawler → proksima,
la sama maniero ni diris new_node La sekva puntero should
noti al D en la ilustraĵo.
Tiam, oni povas agordi la nuna nodo La sekva puntero
al nia nova nodo,
kiel ni devis atendi al punkto C al new_node en la desegno.
Nun ĉiu estas en ordo, kaj ni ne perdu
spuri de ajna datumoj, kaj ni povis nur
batos nia nova nodo en la mezo de la listo
sen rekonstruado la tuta afero aŭ eĉ ŝanĝante ajna elementoj
la vojo ni estus devinta kun fiksa longeco tabelo.
>> Do, kunligita lertaj estas baza, sed grava, dinamika datumstrukturo
kiuj havas ambaŭ avantaĝojn kaj malavantaĝojn
kompare kun tabeloj kaj aliaj datumstrukturoj,
kaj kiel ofte okazas en komputiko,
ĝi estas grave scii kiam uzi ĉiu ilo,
tiel vi povos repreni la dekstra ilo por la rajto laboron.
>> Por pli oportuna, provu skribi funkciojn al
forviŝi nodoj de ligitaj listo -
memori esti zorgema pri la ordo en kiu vi reordigi
via venonta punteros por certigi ke vi ne perdu eron de via listo -
aŭ funkcio por rakonti la nodoj en ligitaj listo,
aŭ amuza unu, por inversigi la ordon de ĉiuj el la nodoj en ligitaj listo.
>> Mia nomo estas Jackson Steinkamp, ​​ĉi tiu estas CS50.