O listă înlănţuită este o structură de date constituită dintr-o succesiune de elemente denumite noduri. Fiecare nod din listă conţine două părţi: o parte de informaţie (în care sunt memorate informaţiile corespunzătoare nodului, specifice problemei) şi o parte de legătură (în care este memorată adresa următorului element din listă).
                Pentru simplitate vom considera, fără a restrânge generalitatea, ca informaţiile memorate în nodurile listei sunt numere întregi. Declaraţia structurii care reprezintă un nod din listă va fi:

Struct Nod {
                int inf;
                struct Nod *urm;
};

                Se obeservă că adresa fiecărui nod din listă este conţinută într-un alt nod, cu o singură excepţie: primul nod al listei. Prin urmare, pentru a identifica o listă simplu înlănţuită este suficient să reţinem adresa primului element al listei.
Definim tipul de date Lista, care este adresa unui nod din listă:

typedef struct Nod * Lista;

                Exceptând primul nod (a cărui adresă nu este conţiuntă de nici un nod al listei), într-o listă simplu înlănţuită mai există un nod special: ultimul nod. După acest nod nu mai urmează nici un alt nod al listei, deci ultimul nod va conţine în partea de legătură pointerul NULL.
Operaţiile fundamentale sunt:

1. Inserarea unui nod în listă;
2. Ştergerea unui nod din listă;
3. Parcurgerea unei liste.

 

 

Inserarea unui nod într-o listă simplu înlănţuită

                Pentru inserare vom implementa o funcţie denumită Insert cu trei parametri.

1. Prim – pointer care conţine adresa primului nod din listă în care se face inserarea; acest parametru va fi transmis prin referinţă, deoarece în urma inserării începutul listei se poate modifica;
2. p – pointer care conţine adresa nodului din listă după care se face inserarea; daca p este NULL, deducem că inserarea noului nod se va face la începtul listei;
3. x – informaţia nodului care urmează să fie inserat în listă.

Vom aloca dinamic memorie pentru un nou nod, a cărui adresă o vom reţine în variabila pointer
q . În zona de informaţii vom memora valoarea x (q->inf=x).
La inserare apar două cazuri distincte. Dacă p==NULL noul nod va fi inserat la începutul listei; dacă p!=NULL inserarea se face în interiorul listei.

void Insert (Lista &Prim, Lista p, int x){
  Lista q=new Nod;
  q->inf=x;
      if(!p) {q->urm=Prim; Prim=q;}
        else {q->urm=p->urm; p->urm=q;}
}

                Observaţii:

1. Crearea unei liste se realizează prin inserări succesive de elemente.
2. Funcţia de inserare creată este generală, functionează pentru toate cazurile posibile (inserare la începutul listei, inserare în interiorul listei şi inserare la sfârşitul listei)

Ştergerea unui nod dintr-o listă simplu înlănţuită

Pentru ştergere vom implementa o funcţie denumită Delete cu doi parametri:

1. Prim – pointer care conţine adresa primului nod al listei din care se face ştergerea; acest parametru va fi transmis prin referinţă, deoarece în urma ştergerii, începutul listei se poate modifica;
2. p – pointer care conţine adresa nodului din listă care precedă nodul ce urmează a fi şters (se transmite adresa nodului precedent şi nu adresa nodului de şters pentru a putea restaura corect legăturile în listă); dacă p este NULL deducem că va fi şters primul nod din listă.

Şi la ştergere apar două cazuri distincte. Dacă p==NULL va fi şters primul nod din listă; dacă
p!=NULL va fi şters un nod din interiorul listei.

void Delete (Lista &Prim, Lista p){
  Lista q;
  If(p) {q=p->urm;
       if(q) {p->urm=q->urm; delete q}
       }
       else {q=Prim;
         if(q) {Prim=Prim->urm; delete q;}
     }
}
Parcurgerea unei liste

                A parcurge o listă presupune a vizita fiecare nod din listă, în scopul prelucrării informaţiilor asociate nodurilor.
În acest scop vom utiliza un pointer p căruia îi vom atribui iniţial adresa primului element din listă. Cât timp lista nu s-a terminat (p!=NULL), se vizitează nodul curent, apoi se trece la nodul următor (p=p->urm). Funcţia următoare realizează parcurgerea unei liste simplu înlănţuite cu afişarea informaţiilor din noduri:

void Afisare (Lista Prim){
  Lista p;
    for (p=Prim; p; p=p->urm)
      cout << p->inf<<’   ’;
   cout<<endl;
}

Up Home Structura Site

A. Ceva

Up Home Structura Site

 

B. Ceva

Up Home Structura Site

 

C. Ceva

Up Home Structura Site

 

D. Ceva

Up Home Structura Site

 

E. Ceva

Up Home Structura Site

 

F. Ceva

Up Home Structura Site