[Powered by Google Translate] A la programació, sovint necessitem per representar llistes de valors,
com ara els noms dels estudiants d'una secció
o classificacions en l'última prova.
>> En el llenguatge C, va declarar matrius poden utilitzar
per emmagatzemar llistes.
És fàcil enumerar els elements d'una llista
emmagatzemats en una matriu, i si vostè necessita per accedir a
o modificar l'element de la llista ITH
per algun índex arbitrari I,
que es pot fer en un temps constant,
però les matrius tenen desavantatges, també.
>> Quan els declare, estem obligats a dir
des del principi el grans que són,
és a dir, quants elements es poden emmagatzemar
i el gran que aquests elements són, que es determina pel seu tipus.
Per exemple, arranjament de int (10)
Pot emmagatzemar 10 elements
que tenen la mida d'un int.
>> No podem canviar la mida d'una matriu després de la declaració.
Hem de fer una nova matriu si volem emmagatzemar més elements.
La raó d'aquesta limitació que existeix és que el nostre
programa emmagatzema tota la matriu
com un tros contigu de memòria.
Dir això és el buffer on s'emmagatzema en la nostra matriu.
Hi pot haver altres variables
situat just al costat de la matriu
a la memòria, de manera que no pot
només que la matriu més gran.
>> De vegades ens agradaria que el comerç de la matriu ràpida velocitat d'accés a dades
per una mica més de flexibilitat.
Introduïu la llista enllaçada, una altra estructura de dades bàsiques
vostè podria no ser tan familiaritzats.
En un nivell alt,
una llista enllaçada emmagatzema les dades en una seqüència de nodes
que estan connectats entre si amb enllaços,
per tant "llista enllaçada. 'el nom
Com veurem, aquesta diferència en el disseny
condueix a diferents avantatges i desavantatges
d'una matriu.
>> Aquí hi ha un codi C per a una llista molt simple enllaçada de nombres enters.
Es pot veure que hem representat a cada node
a la llista com una estructura que conté dues coses,
un enter per emmagatzemar anomenat 'val'
i un enllaç per al node següent a la llista
que representem com un punter anomenat 'next'.
D'aquesta manera, podem seguir la llista sencera
amb només un únic punter al node primer,
i després podem seguir els següents consells
per al segon node,
al node tercer,
per al quart node,
i així successivament, fins arribar a la final de la llista.
>> Vostè pot ser capaç de veure un avantatge que això té
sobre l'estructura matriu estàtica - amb una llista enllaçada,
no necessitem una gran part de la memòria del tot.
El node 1 de la llista podria viure en aquest lloc en la memòria,
i el segon node podria ser tot el camí fins aquí.
Podem arribar a tots els nodes no importa on en la memòria són,
perquè a partir de la primera node, el punter següent de cada node
ens diu exactament on anar després.
>> A més, no has de dir per avançat
el gran que una llista enllaçada és el camí que fem amb arrays estàtics,
ja que podem seguir afegint nodes a una llista
sempre que no hi ha espai en algun lloc de la memòria dels nous nodes.
Per tant, les llistes enllaçades són fàcils de canviar la mida de forma dinàmica.
Diguem, més tard en el programa hem d'afegir més nodes
a la nostra llista.
Per inserir un nou node a la llista sobre la marxa,
tot el que hem de fer és assignar memòria per a aquest node,
plop en el valor de les dades,
i després col · locar on vulguem amb la configuració dels indicadors apropiats.
>> Per exemple, si volguéssim posar un node en el medi
els nodes 2 i 3 de la llista,
no hauríem de moure els nodes segon o tercer en absolut.
Diguem que vas a inserir aquest node vermell.
Tot el que hauria de fer és configurar punter següent del nou node
perquè apunti al node 3
i després tornar a col · locar el punter següent node de segon
perquè apunti al nostre nou node.
Per tant, podem canviar la mida de les nostres llistes sobre la marxa
ja que el nostre equip no depèn de la indexació,
sinó més aviat en vincular l'ús de punters per emmagatzemar-los.
>> Llistes Però un desavantatge de vinculats
és que, a diferència d'una matriu estàtica,
l'ordinador no només pot saltar a la meitat de la llista.
Atès que l'equip ha de visitar cada node en la llista enllaçada
per arribar a la següent,
que prendrà més temps per trobar un node particular
el que ho faria en una matriu.
Per recórrer tota la llista pren temps proporcional
a la longitud de la llista,
o O (n) en notació asimptòtica.
De mitjana, arribant qualsevol node
També es necessita temps proporcional a n.
>> Ara, anem a realment escriure codi
que treballa amb llistes enllaçades.
Diguem que volem una llista enllaçada d'enters.
Podem representar un node en la llista de nou
com una estructura amb dos camps,
un valor enter anomenat 'val'
i un punter proper al següent node de la llista.
Bé, sembla bastant simple.
>> Suposem que volem escriure una funció
que recorre la llista i imprimeix el
valor emmagatzemat en l'últim node de la llista.
Bé, això vol dir que haurem de recórrer tots els nodes de la llista
per trobar l'última, però ja no estem afegint
o esborrar res, no volem canviar
l'estructura interna dels punters següents a la llista.
>> Per tant, anem a necessitar un punter específicament per traversal
que anomenarem "crawler".
Es arrosseguen a través de tots els elements de la llista
seguint la cadena de punters propers.
Tots hem emmagatzemat és un punter al node primer,
o "cap" de la llista.
Punts del cap a la primera node.
És de tipus punter a node.
>> Per obtenir l'actual primera node a la llista,
hem d'eliminar la referència aquest indicador,
però abans de poder deferenciarlo, hem de comprovar
si el punter és nul en primer lloc.
Si és nul, la llista és buida,
i hem imprimir un missatge que, pel fet que la llista és buida,
no hi ha últim node.
Però, suposem que la llista no és buida.
Si no és així, llavors hem de gatejar per tota la llista
fins arribar a l'últim node de la llista,
i com podem saber si estem davant l'últim node a la llista?
>> Bé, si el punter següent d'un node és nul,
sabem que estem al final
des del següent punter darrera no tindria cap node següent a la llista per apuntar.
És una bona pràctica per mantenir sempre punter següent de l'últim node de s'inicialitzen a null
tenir una propietat estàndard que ens avisa quan hem arribat al final de la llista.
>> Per tant, si crawler → següent és nul,
recordar que la sintaxi de fletxa és un accés directe per eliminar la referència
un punter a una estructura, a continuació, accedir a
seu següent camp equivalent al maldestre:
(* Crawler). Següent.
Una vegada que hagis trobat l'últim node,
volem imprimir crawler → val,
el valor en el node actual
que sabem que és l'última.
En cas contrari, si no estem encara en l'últim node de la llista,
hem de passar a la següent node a la llista
i comprovar si aquest és l'últim.
Per això, s'acaba d'establir nostre punter sobre erugues
per apuntar al següent valor del node actual,
és a dir, el node següent a la llista.
Això es fa mitjançant l'establiment
crawler = crawler → següent.
Després repetim aquest procés, amb un llaç per exemple,
fins a trobar l'últim node.
Així, per exemple, si rastrejador estava apuntant al capdavant,
ens vam proposar rastrejador perquè apunti a erugues → següent,
que és el mateix que el camp proper de la primera node.
Així que, ara que el nostre rastrejador està apuntant al node 2,
i, de nou, es repeteix això amb un bucle,
fins que hàgim trobat l'últim node, és a dir,
on punter següent del node apunta null.
I aquí el tenim,
hem trobat l'últim node de la llista, i la impressió del seu valor,
només ha d'utilitzar crawler → val.
>> Travessant no és tan dolent, però què passa amb la inserció?
Diguem que volem inserir un nombre sencer en la 4 ª posició
en una llista de nombres enters.
Que està entre els nodes actuals tercer i quart.
Un cop més, hem de recórrer la llista només per
arribar a la tercera part, la qual estem inserint després.
Així, vam crear un punter rastrejador de nou per recórrer la llista,
comprovar si el nostre cap punter és nul,
i si no ho és, apuntar amb el punter sobre erugues en el node principal.
Per tant, estem en l'element primer.
Hem d'anar cap endavant 2 elements més abans de poder inserir,
pel que podem utilitzar un bucle for
int i = 1; i <3; i + +
i en cada iteració del bucle,
avançar en el punter sobre erugues presentades per un node
comprovant si el camp proper del node actual és nul · la,
i si no és així, moure el nostre rastrejador punter al següent node
fixant igual al següent punter del node actual.
Per tant, des del nostre bucle per fer això, diu
dues vegades,
hem arribat al node 3,
i una vegada que el nostre punter rastrejador ha arribat al node després de
que volem inserir el nostre nou sencer,
Com és en realitat la inserció?
>> Doncs bé, el nostre nou sencer ha de ser inserit en la llista
com a part de la seva pròpia estructura de node,
ja que això és realment una seqüència de nodes.
Per tant, farem un nou punter al node
anomenat 'new_node,'
i configurar-lo perquè apunti a la memòria que ara assignar
a la pila per al node en si,
i la quantitat de memòria hem d'assignar?
Doncs bé, la mida d'un node,
i volem establir el seu camp val l'enter que volem inserir.
Diguem, 6.
Ara, el node conté el nostre valor sencer.
També és una bona pràctica per inicialitzar camp proper del nou node
per apuntar a null,
però ara què?
>> Cal canviar l'estructura interna de la llista
i els indicadors continguts en els següents de la llista
Els nodes 3 i 4.
Atès que els punters propers determinar l'ordre de la llista,
i ja que estem introduint el nostre nou node
a la dreta en el mitjà de la llista,
que pot ser una mica complicat.
Això és perquè, recordi, el nostre equip
només coneix la ubicació dels nodes a la llista
perquè dels punters propers emmagatzemats en els nodes anteriors.
Per tant, si mai perdut el rastre de cap d'aquests llocs,
diuen que en canviar un dels punters següents a la llista,
Per exemple, diguem que canviem
camp següent node de la tercera de
perquè apunti a algun node per aquí.
Ens agradaria estar fora de sort, ja que no ho faria
Té alguna idea d'on trobar la resta de la llista,
i això és, òbviament, molt malament.
Per tant, hem de tenir molta cura per tal de
en el qual manipulem nostres punters propers durant la inserció.
>> Així que, per simplificar això, direm que
nostres primers 4 nodes
es denominen A, B, C, i D, amb les fletxes que representen la cadena de punters
que connecten els nodes.
Per tant, hem d'inserir el nostre nou node
entre els nodes C i D.
És molt important fer-ho en l'ordre correcte, i jo et mostraré per què.
>> Fem una ullada a la forma incorrecta de fer-ho en primer lloc.
Hey, sabem que el nou node ha de venir a la dreta després de C,
així que anem a establir el punter pròxim C
perquè apunti a new_node.
D'acord, sembla estar bé, només hem d'acabar ara per
fer punt del nou node punter prop de D,
però espera, com podem fer això?
L'única cosa que ens pot dir on D és,
va ser el següent punter emmagatzemat prèviament en C,
però ens va tornar a escriure aquest punter
perquè apunti al nou node,
de manera que ja no tenim ni idea d'on D és en la memòria,
i hem perdut la resta de la llista.
No és bo en absolut.
>> Així que, com podem fer això bé?
En primer lloc, assenyalar punter següent del nou node al Sr
Ara, tant el nou node i la de C pròxims punters
apunten cap al mateix node, D,
però això està bé.
Ara podem assenyalar següent punter de C en el nou node.
Per tant, hem fet això sense perdre cap dada.
En el codi, C és el node actual
que el recorregut punter rastrejador fa referència,
i D està representat pel node al qual apunta el camp següent node actual,
o rastrejador → següent.
Així, en primer lloc establir el punter següent del nou node
perquè apunti a erugues → següent,
de la mateixa manera que vam dir punter proper new_node han de tenir per
apuntar a D a la il · lustració.
Llavors, podem establir el punter següent del node actual
al nostre nou node,
la mateixa manera que va haver d'esperar al punt C new_node en el dibuix.
Ara tot està en ordre, i no va perdre
fer un seguiment de les dades, i vam ser capaços de simplement
enganxar nostre nou node al mig de la llista
sense reconstruir tota la cosa, o fins i tot canviant els elements
la forma en què s'han hagut de amb una matriu de longitud fixa.
>> Per tant, les llistes enllaçades són un bàsic, però important, l'estructura de dades dinàmica
que tenen avantatges i desavantatges
en comparació amb les matrius i altres estructures de dades,
i com és sovint el cas en informàtica,
és important saber quan utilitzar cada eina,
perquè pugui triar l'eina adequada per al treball correcte.
>> Per practicar més, intenti escriure funcions per
eliminar nodes d'una llista enllaçada -
recordi anar amb compte amb l'ordre en què es reorganitzen
els punters següents per assegurar-se que no perdi una bona part de la seva llista -
o una funció per comptar els nodes en una llista enllaçada,
o una diversió, per invertir l'ordre de tots els nodes d'una llista enllaçada.
>> El meu nom és Jackson Steinkamp, ​​això és CS50.