[Powered by Google Translate] În programare, de multe ori am nevoie pentru a reprezenta liste de valori,
cum ar fi numele de elevi într-o secțiune
sau scorurile lor pe ultimul test.
>> În limbajul C, a declarat matrice poate fi folosit
pentru a stoca liste.
E ușor să enumerăm elementele unei liste
stocate într-o matrice, și în cazul în care aveți nevoie pentru a accesa
sau de a modifica lista de elementul-lea
pentru unele indicele arbitrare I,
care se poate face în timp constant,
dar tablouri au dezavantaje, de asemenea.
>> Când ne-am le declare, suntem necesar să spunem
în față cât de mare sunt,
că este, cât de multe elemente care pot stoca
și cât de mare aceste elemente sunt, care este determinat de tipul lor.
De exemplu, int arr (10)
poate stoca 10 articole
care sunt de dimensiunea unei int.
>> Noi nu putem schimba dimensiunea unei matrice, după declarația.
Avem de a face o nouă matrice, dacă vrem să stocați mai multe elemente.
Motivul acestei limitări este faptul că există noastră
Programul stochează întreaga gamă
ca o bucată de memorie contiguă.
Spun acest lucru este în cazul în care buffer-am depozitat în gama noastră.
S-ar putea să fie cu alte variabile
situat chiar lângă matrice
în memorie, astfel încât nu putem
doar asigurați-matrice mai mare.
>> Uneori am dori să comerțului matrice de rapid viteza de acces la date
pentru o flexibilitate pic mai mult.
Introduceți lista de legat, o altă structură de date de bază
ar putea să nu fie la fel de familiarizați cu.
La un nivel ridicat,
o listă legată stochează datele într-o secvență de noduri
care sunt conectate între ele cu link-uri,
prin urmare, numele de "lista legat."
După cum vom vedea, această diferență în proiectarea
conduce la diferite avantaje și dezavantaje
decât o matrice.
>> Iată unele cod C pentru o listă foarte simplu legat de numere întregi.
Puteti vedea ca am reprezentat fiecare nod
în listă ca o struct care conține 2 lucruri,
un întreg pentru a stoca numită "val"
precum și un link la nodul următor din listă
care ne reprezintă ca un indicator numit "viitoare."
În acest fel, putem urmări întreaga listă
cu doar un pointer la nodul unic prima,
și apoi putem să urmați indicii pentru următoarele
la nodul 2,
la nodul 3,
la nodul 4,
și așa mai departe, până când vom ajunge la sfârșitul listei.
>> S-ar putea fi capabil de a vedea un avantaj acest lucru are
peste structura de matrice statice - cu o listă legată,
nu avem nevoie de o bucată mare de memorie cu totul.
Nodul prima din lista ar putea trăi în acest loc în memorie,
și nodul două ar putea fi tot drumul până aici.
Putem ajunge la toate nodurile, indiferent unde în memorie sunt,
deoarece incepand de la nodul 1, indicatorul fiecare nod de pe lângă
ne spune exact unde să mergem.
>> În plus, nu avem de spus în față
cât de mare o listă legată va fi modul in care facem cu matrice statice,
deoarece putem păstra adăugarea noduri la o listă
atât timp cât nu există spațiu de undeva în memorie pentru noduri noi.
Prin urmare, listele legate sunt ușor pentru a redimensiona dinamic.
Spune, mai târziu, în programul de care avem nevoie pentru a adăuga mai multe noduri
în lista noastră.
Pentru a insera un nou nod în lista noastră de pe zbura,
tot ce trebuie să faceți este să aloce memorie pentru acel nod,
plop, în valoare de date,
și plasați-l, apoi în cazul în care ne dorim prin ajustarea corespunzătoare indicii.
>> De exemplu, dacă am vrut să plaseze un nod între
nodurile 2 și 3 ale listei,
noi nu ar trebui să se mute nodurile 2 sau 3, la toate.
Spune-ne inserarea acestui nod rosu.
Tot ce ar trebui să faceți este să setați indicatorul nod nou de pe lângă
pentru a indica nodul treia
și rewire apoi indicatorul nod doilea de pe lângă
pentru a indica noul nostru nod.
Deci, ne putem redimensiona listele noastre de pe zbor
deoarece calculatorul nostru nu se bazează pe indexare,
ci mai degrabă pe corelarea folosind indicii pentru a le stoca.
>> Lista de preturi cu toate acestea, un dezavantaj al legate de
este faptul că, spre deosebire de o matrice statice,
calculatorul nu poate sari doar la mijlocul listei.
Din moment ce computerul are de a vizita fiecare nod în listă legată
pentru a ajunge la următoarea,
se va lua mai mult timp pentru a găsi un anumit nod
decât ar fi într-o matrice.
Pentru a traversa întreaga listă nevoie de timp proporțională
la lungimea listei,
sau O (n) în notație asimptotică.
În medie, ajungând la orice nod
De asemenea, are nevoie de timp proporțională cu nr.
>> Acum, hai să scrie de fapt un cod
care funcționează cu liste legate.
Să spunem că doriți o listă legată de întregi.
Ne poate reprezenta un nod în lista noastră din nou
ca o struct cu 2 campuri,
o valoare întreagă numită "val"
și un pointer lângă urmatorul nod al listei.
Ei bine, se pare destul de simplu.
>> Să presupunem că vrem să scrie o funcție
care traversează lista și imprimă
valoarea stocată în ultimul nod al listei.
Ei bine, asta înseamnă că va trebui să traverseze toate nodurile din lista
pentru a găsi ultima, dar din moment ce nu suntem adăugarea de
sau ștergerea nimic, nu vrem să se schimbe
structura internă a pointerilor următoare în listă.
>> Deci, vom avea nevoie de un pointer special pentru traversarea
pe care o vom numi "pe șenile."
Acesta va accesa cu crawlere prin toate elementele listei
urmând lanțul de pointeri pentru următoarele.
Tot ce-am stocat este un pointer la nodul 1,
sau "capul" listei.
Puncte de cap la nodul primul.
Este de tip pointer-la-nod.
>> Pentru a obține efectiv primul nod în listă,
trebuie să dereference acest indicator,
dar înainte de a putem dereference, avem nevoie pentru a verifica
dacă indicatorul este nul primul.
Dacă e nul, lista este goală,
și ar trebui să imprima un mesaj care, pentru că lista este goală,
nu există nici un nod ultima.
Dar, hai să spunem lista nu este goală.
Dacă nu e, atunci ar trebui să se târască prin intreaga lista
până când vom ajunge la ultimul nod din lista,
și cum putem spune dacă ne uităm la ultimul nod din listă?
>> Ei bine, în cazul în care indicatorul de pe lângă un nod este nulă,
știm că suntem la sfârșitul
deoarece indicatorul ultima următoare ar avea nici un nod următor din lista de la punctul la.
E bună practică de a păstra întotdeauna indicatorul ultimul nod de pe lângă inițializat la nul
pentru a avea o proprietate standardizat care ne avertizează atunci când am ajuns la sfârșitul listei.
>> Deci, în cazul în care pe șenile → următoare este nulă,
amintiți-vă că săgeata de sintaxa este o comandă rapidă pentru dereferencing
un pointer la o structura, atunci accesarea
sa câmpul de lângă echivalentă cu incomode:
(* Pe șenile). Următor.
Odată ce am găsit ultimul nod,
vrem să le imprimați pe șenile → val,
valoarea din nodul curent
care știm că este ultima.
În caz contrar, dacă nu suntem încă la ultimul nod din lista,
avem pentru a trece la urmatorul nod din lista
și verificați dacă asta e ultima.
Pentru a face acest lucru, am stabilit doar indicatorul nostru pe șenile
să indice valoarea nodul curent de pe lângă,
că este, nodul următor din listă.
Acest lucru se face prin setarea
pe șenile crawler = → viitoare.
Apoi ne-am repeta acest proces, cu o buclă, de exemplu,
până când vom găsi ultimul nod.
Deci, de exemplu, în cazul în care a fost pe șenile îndreptat spre cap,
am setat pe șenile pentru a indica pe șenile → următoare,
care este aceeași ca și în câmpul următor al nodului primul.
Deci, acum crawlerul nostru este îndreptat la nodul 2,
și, din nou, vom repeta acest lucru cu o buclă,
până când am găsit ultimul nod, care este,
în cazul în care indicatorul de pe lângă nod este indică spre zero.
Și acolo îl avem,
am gasit ultimul nod din lista, pentru a imprima și valoarea sa,
vom folosi doar pe șenile → val.
>> Traversarea nu este așa de rău, dar ce despre introducerea?
Să spun că vrem să inserați un întreg în locul 4
într-o listă întreagă.
Aceasta este între nodurile curente 3 si 4.
Din nou, trebuie să traverseze lista doar pentru a
ajunge la elementul treia, cea pe care o ai dupa inserarea.
Deci, vom crea un pointer pe șenile din nou pentru a traversa pe lista,
verificați dacă indicatorul nostru central este nul,
si daca nu e, punctul nostru de indicatorul pe șenile de la nodul capului.
Deci, suntem la primul element.
Trebuie să mergem mai departe 2 mai multe elemente înainte de a putea insera,
astfel încât să putem folosi o buclă pentru
int i = 1; i <3; i + +
și în fiecare iterație a buclei,
avansa indicatorul nostru pe șenile înainte de 1 nod
prin verificarea dacă câmpul nodul curent de pe lângă este nul,
si daca nu e, mutați indicatorul crawlerului nostru la urmatorul nod
prin fixarea egală cu indicatorul de pe lângă nodul curent.
Deci, din moment bucla noastră pentru a face acest lucru spune
de două ori,
am ajuns la nodul 3,
și o dată indicatorul crawlerului nostru a ajuns la nodul după
pe care dorim să inserați noul nostru întreg,
cum facem de fapt introducerea?
>> Ei bine, întreg noul nostru trebuie să fie introdus în lista de
ca parte dintr-o structura de nod proprie,
deoarece aceasta este într-adevăr o secvență de noduri.
Deci, hai să facem un pointer la nodul nou
numit "new_node,"
și a stabilit la punctul în memorie pe care le aloca acum
pe heap pentru nodul în sine,
și cât de mult de memorie avem nevoie de a aloca?
Ei bine, de marimea unui nod,
și vrem să setați domeniul său la Val întreg care ne-o dorim pentru a insera.
Să spunem, 6.
Acum, nodul conține valoarea noastră întreagă.
Este, de asemenea, bune practici pentru a inițializa câmp noul nod de pe lângă
să indice null,
dar acum ce?
>> Avem de a schimba structura internă a listei
și indicii pentru următoarele cuprinse în lista existentă de
Nodurile 3 și 4.
Având în vedere că indicii următoarele determina ordinea listei,
și din moment ce ne introduce noul nostru nod
chiar în mijlocul listei,
acesta poate fi un pic dificil.
Acest lucru se datorează faptului că, amintiți-vă, calculatorul nostru
cunoaște doar amplasarea de noduri în listă
din cauza indicii următoarele stocate în nodurile precedente.
Deci, dacă ne-am pierdut vreodată cale de oricare dintre aceste locații,
spun prin schimbarea uneia dintre următoarele indicii din lista noastră,
de exemplu, să spunem ne-am schimbat
nod treilea domeniu de pe lângă
să indice o nod aici.
Ne-ar fi de noroc, pentru că nu ne-am
au nici o idee în cazul în care pentru a găsi restul listei,
și că este, evident, foarte rău.
Deci, trebuie să fim foarte atenți cu privire la comanda
în care ne manipula pointeri noastre pentru următoarele timpul inserției.
>> Deci, pentru a simplifica acest lucru, să spunem că
primele noastre 4 noduri
sunt numite A, B,, C, și D, cu săgeți care reprezintă lanțul de pointeri
care conectează nodurile.
Deci, avem nevoie de a introduce noul nostru nod
între nodurile C și D.
Este important să-l facă în ordinea corectă, și vă voi arăta de ce.
>> Să ne uităm la modul greșit de a face acest lucru mai întâi.
Hei, știm noul nod trebuie să vină imediat dupa C,
așa că hai să setați indicatorul următor lui C
să indice new_node.
În regulă, pare ok, trebuie doar să termin până acum de către
punct de luare nod nou indicatorul de lângă D,
dar așteptați, cum putem face asta?
Singurul lucru care ne-ar putea spune unde D a fost,
a fost următoarea indicatorul anterior stocate în C,
dar am rescris doar că indicatorul
pentru a indica nou nod,
astfel încât nu mai avem nici o idee unde D este în memorie,
și am pierdut restul listei.
Nu e bine deloc.
>> Deci, cum facem acest drept?
În primul rând, punctul indicatorul noul nod de pe lângă la D.
Acum, atât noul nod lui și a lui C pentru următoarele indicii
sunt orientate către același nod, D,
dar asta e bine.
Acum putem indica indicatorul următor C, la nod nou.
Deci, am făcut acest lucru fără a pierde date.
În cod, C este nodul curent
că indicatorul traversare pe șenile este orientată spre,
și D este reprezentat de nodul indicat de către câmpul nodul curent de pe lângă,
sau pe șenile → următoare.
Deci, ne-am stabilit prima indicatorul nod nou de pe lângă
să indice pe șenile → următoare,
fel cum am spus indicatorul următor new_node ar trebui să
indică D în ilustrație.
Apoi, putem seta indicatorul nodul curent de pe lângă
la nodul noul nostru,
la fel cum am fost nevoiți să așteptăm de la punctul C la new_node în desen.
Acum totul e în ordine, și nu ne-am pierdut
evidența tuturor datelor, și noi am fost capabil să pur și simplu
lipi nod noul nostru în mijlocul listei
fără reconstrucția totul sau schimbarea chiar orice elemente
modul în care ne-ar fi trebuit să o matrice de lungime fixă.
>> Deci, listele sunt legate de o bază, dar importantă, dinamică structură de date
care au atât avantaje, cât și dezavantaje
comparativ cu matrice și alte structuri de date,
și așa cum este adesea cazul în informatică,
este important să știi când să utilizeze fiecare instrument,
astfel încât să puteți alege instrumentul potrivit pentru postul potrivit.
>> Pentru mai multă practică, încearcă să scrii funcțiile pentru a
șterge nodurile dintr-o listă legată -
amintiți-vă să fie atent cu privire ordinea în care ați rearanja
de indicii pentru următoarele pentru a se asigura că nu pierdeți o bucată din lista ta -
sau o funcție pentru a număra nodurile dintr-o listă legată,
sau o distracție, de a inversa ordinea de toate nodurile dintr-o listă legată.
>> Numele meu este Michael Jackson Steinkamp, ​​acest lucru este CS50.