Liste dinamice 1

Listele Linked - o structură de date compusă din noduri, fiecare dintre care conține atât datele reale și una sau două link-ul ( „link-ul“) la nodul următor și / sau anterior din listă. Există mai multe tipuri de liste, aici sunt unele dintre ele: pur și simplu conectate unidirecțional, pur și simplu conectat la purtător inel dublu legat, inel dublu legat.

Lista unidirecțional legate individual.

Prin lista de implicite aranjament pur și simplu conectate unidirecțional serie de elemente de implementare stabilite. Începând cu un anumit nod, noi credem că este primul din acest site are link-uri la alta, și așa mai departe. În cele mai multe cazuri, primul nod ca gol, pentru că atunci este mai ușor de a lucra cu lista. Într-o listă legată, fiecare nod are o referire numai la elementul următor, adică, nu putem trece la sfârșitul listei, înainte de a începe. Lista unidirecțională se termină cu o referință NULL.

Să ne gândim la ce funcții am putea avea nevoie pentru a lucra cu lista. Poate că acest lucru - organizarea listei, lista de ieșire sortare, introducerea unui element nou într-o listă sortată. Deci, trebuie mai întâi să aranjeze nodul în sine, din totalitatea care va forma lista.

Acum, avem nevoie pentru a începe să creeze o variabilă de tip listă, care va indica primul element
listă.

Lista * de start = o nouă listă; // aloca memorie pentru primul element
Start-> următor = NULL; // în acest moment primul element este în același timp, iar ultima este următoarea se referă la NULL

Așa cum am aloca memorie pentru primul element, trebuie doar să facă, și pentru toate cele ulterioare.
Acum, ia în considerare parte a codului, care va genera o listă.

Lista * p_list = începe;
pentru (int i = 0; i<20; i+=2)
Lista * tmp = listă nouă; // Alocați memorie pentru
tmp-> item = i; // aici totul este clar
tmp-> următor = NULL; // vom insera un nod în partea de jos a listei și așa următoare = NULL
p_list-> next = tmp; // acum p_list-> pentru următoarele puncte de la nodul creat
p_list = p_list-> următor; // Mutați cursorul la ultimul element.
>

Aici vom folosi un indicator de lucru pentru a nu schimba început, care indică întotdeauna la primul nod din listă. După executarea acestui cod de lista noastră arată astfel:

Să ne derive lista consola creată. Pentru a face acest lucru, a scrie o funcție separată:

spectacol void (lista * start) // setarea - pe partea de sus a listei indicatorul.
Lista * p_list; // lucrător pointer
p_list = Start-> următor; // la început, el se referă la al doilea nod din listă.






în timp ce (p_list! = NULL)
cout <articol < p_list = p_list-> următor; // mutați cursorul la un singur nod.
>
>

Lista * tmp = listă nouă; // Aloca memorie pentru noul nod
tmp-> item = el;
tmp-> next = p_list-> următor;
p_list-> next = tmp; // Inserare nod după nodul indicat de p_list
pauză;
>
p_list = p_list-> următor; // muta cursorul la elementul următor.
if (p_list-> următor == NULL el> = p_list-> Element) // Verificare nu este necesar să se introducă un nod al listei.
Lista * tmp = listă nouă;
tmp-> item = el;
tmp-> următor = NULL; // Din moment ce introduce un nod la sfârșitul listei elementul următor trebuie să se refere la o NULL
p_list-> următor = tmp; // inserați nod din listă.
pauză;
>

Încercați să atragă o diagramă a elementului de inserție în listă. Aceasta este temele)
Acum scrie o funcție care va sorta lista. Vom folosi una dintre cele mai simple algoritmi de sortare - sortare cu bule.

sortare void (lista * start) // setarea - pe partea de sus a listei indicatorul.
Lista * p_list; // pointer la exterior pentru tsykla
Lista * pp_list; // pentru interior
pentru (p_list = Start-> următor ;! p_list = NULL; p_list = p_list-> următor) // trece printr-o listă a tuturor nodurilor
pentru (pp_list = Start-> următor ;! pp_list-> următor = NULL; pp_list = pp_list-> următor) // dar aici numai la nodul, următor care indică NULL
// schimbul valorilor normale
în cazul în care (pp_list-> Element> pp_list-> rivalului> Element)
tmp int;
tmp = pp_list-> element; //
pp_list-> Element = pp_list-> rivalului> element;
pp_list-> rivalului> item = tmp;
>

Și ultima funcție - îndepărtarea unui element din listă:

void dell (lista * de start, int el) // pointer la partea de sus a listei, iar valoarea pe care o căutăm în listă, dacă vom găsi mijloacele pentru a șterge.
Lista * p_list = Start-> următor; // lucrător pointer, care va fi folosit pentru a rula prin listă.
Lista * prev = pornire; // pointer care va indica întotdeauna la elementul anterior p_list.
în timp ce (p_list! = NULL) // ruleaza Full-Lista
// verifica - dacă eliminarea necesității de a
în cazul în care (p_list-> Element == el)
// nod timesign, care se va înregistra valoarea nodului care urmează să fie șters.
Lista * tmp = listă nouă;
* Tmp = * p_list;
// acum avem nevoie pentru a face astfel încât următorul element al nodului precedent indică spre un nod care este după p_list, adică p_list-> următor
prev-> next = p_list-> următor;
șterge tmp;
>
prev = p_list; // muta cursorul anterioare pe un element
p_list = p_list-> următor; // muta doar următor.
>
>

Iată cum arată în jurul valorii de:

Avantajele liste dinamice este că putem destul de ușor pentru a insera un element sau scoateți-l din listă. Matricea este ceva mai complicat. Un alt avantaj este faptul că dimensiunea listei poate fi schimbată în orice moment în timpul programului.

Dar lista are dezavantajele sale. Una dintre cele mai importante este că nu putem avea acces la nodul k precum și o matrice, listele trebuie să mergem prin toate elementele care merg la k. De asemenea, nodurile din lista nu sunt plasate consecutiv în memorie și programul rulează un pic mai lent decât ar fi cu o matrice, în cazul în care toate elementele sunt aranjate în serie.

Asta e tot) dacă cineva este interesat de acest subiect, ar fi continuat mai târziu) Descrieți lucrarea cu lista circulară, pur și simplu conectat conectat de două ori, de două ori inelul conectat.
Posibila eroare gramaticală) română nu este limba mea maternă) este gata să asculte toate observațiile).