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