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