Algoritmi pentru prelucrarea listelor

          După modul cum este definită relaţia de ordine în listă, rezultă şi accesul la nodurile listei. Pentru a găsi un nod al listei va trebui să parcurgem lista de la început şi apoi trecem de la un nod la altul folosind pointerul pElementUrmator. Pentru a găsi un anumit nod al listei va trebui să definim criterii de identificare pentru acesta (de exemplu numărul de ordine al nodului, nodul care conţine o anumită informaţie, etc.).

Parcurgerea toatală a listei pentru a afişa (a efectua anumite operaţii) poate fi redată cu următorul cod:

...

MPI_Nod    *pTemp;

pTemp = pInceputLista;

while (pTemp != NULL)

{

          // Calcule. Adresa nodului curent este în pTemp.

          ...

          // Trec la următorul nod al listei

          pTemp = pTemp->pElementUrmator;

}

...

Dacă definim drept criteriu de căutare după o anumită valoare a datei membru nCodUnic al structurii MPI_Nod, atunci determinarea nodului respectiv se va face parcurgând lista de la început şi comparând valoarea datei membru nCodUnic cu valoarea memorată într-o variabilă locală (în general preluată de la tastatură sau rezultată în urma unor calcule anterioare). Presupunem că valoarea este păstrată în variabila m_nCodUnic. Codul poate arăta astfel (în cadrul unei funcţii):

...

MPI_Nod    *pTemp;

int     m_nCodUnic;

...

pTemp = pInceputLista;

while (pTemp != NULL)

{

if (pTemp->nCodUnic == m_nCodUnic)

          return pTemp; // în pTemp avem adresa nodului căutat

pTemp = pTemp->pElementUrmator;

}

return NULL;       //nu există un asemenea nod

...

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

          Inserarea unui nod într-o listă simplu înlănţuită se poate face în mai multe moduri:

inserarea înaintea primului nod;

inserarea înaintea unui nod precizat printr-o cheie;

inserarea după un nod precizat printr-o cheie;

inserarea după ultimul nod al listei – aceasta coincide cu operaţia de adăugare la sfârşitul listei, descrisă mai înainte.

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

Adresa primului nod al listei (dacă nu este vidă) este păstrată în pointerul pInceputLista. Operaţiile care trebuiesc efectuate precum şi ordinea acestora este descrisă în continuare:

- alocare de memorie pentru noul nod, adresa se obţine de exemplu în pTemp (dacă operaţia s-a desfăşurat cu succes se continuă cu (2) altfel se renunţă la inserare);

- pointerul pTemp->pElementUrmator va păstra adresa următorului nod care este în fapt fostul prim nod al listei, deci valoarea lui pInceputLista;

pTemp->pElementUrmator = pInceputLista;

pointerul pInceputLista va primi ca valoare adresa noului nod creat

pInceputLista = pTemp;

Observaţie. Dacă se inversează etapele 2) cu 3) atunci am pierdut lista. Pointerul pSfarsitLista va puncta spre ultimul element al listei, pointerul pInceputLista va puncta spre noul nod creat iar pInceputLista->pElementUrmator va puncta tot spre noul nod creat. O încercare de a parcurge lista în acest moment va duce la buclarea programului.

          Dacă lista este vidă această operaţie coincide cu cea de creare a primului nod al listei.

          Inserarea unui nod într-o listă simplu înlănţuită înaintea unui nod precizat printr-o cheie

Presupunem că valoarea cheii memorată în nod este în data membru nCodUnic. Să reprezentăm grafic ce ar trebui să facem în această situaţie. Prin nod curent înţelegem nodul din listă care satisface condiţia nCodUnic = m_nCodUnic.

          Ordinea operaţiilor care trebuie făcute este următoarea (presupunând că toate operaţiile se efectuează cu succes):

- alocarea memoriei pentru nodul de inserat; adresa va fi păstrată în variabila pTemp;

- păstrarea adresei nodului anterior în variabila  pNodAnterior;

- păstrarea adresei nodului care satisface condiţia (nodul curent) în variabila pNodCurent;

- atribuirea pointerului pNodAnterior->pElementUrmator a adresei nodului ce trebuie jnserat, păstrat în variabila pTemp;

- atribuirea pointerului pTemp->pElementUrmator a adresei nodului curent pNodCurent;

- iniţializarea datelor pentru noul nod.

Observaţie. Trebuie avută în vedere posibilitatea că şi primul nod al listei poate îndeplini condiţia de căutare. În acest caz avem de inserat un nod la începutul listei.

În continuare, s-ar părea că nu este necesară o altă prelucrare deoarece pNodCurent = pNodAnterior->pElementUrmator. Să nu uităm însă că valoarea cheii ne ajută la obţinerea nodului curent.

Codul ar putea fi următorul (inserăm acest cod în cadrul unei funcţii care returnează 0 în caz de succes sau 1 în caz contrar):

...

MPI_Nod    *pTemp, *pNodCurent, *pNodAnterior;

int     m_nCodUnic;

...

pTemp = pInceputLista;

pNodAnterior = pInceputLista;

pNodCurent = NULL;            

while (pTemp != NULL){// Caut nodul ce satisface condiţia...

          if (pTemp->nCodUnic == m_nCodUnic)

{

pNodCurent = pTemp;

break;

}

          pNodAnterior = pTemp;

          pTemp = pTemp->pElementUrmator;

}

if (pNodCurent == NULL) {

          printf(“Nu exista cheia %d Lista nemodificata...”, m_nCodUnic);

          return –1;

}

if (pNodCurent == pInceputLista)

{// Nodul se inserează la începutul listei. Se va apela funcţia care tratează acest caz. }

else

{ //  aloc memorie pentru noul nod

pTemp =  (MPI_Nod*)malloc(sizeof(MPI_Nod));

if (pTemp == NULL) {

          printf(“Nu pot aloca memorie pentru noul nod\n”;

          return –1; // Se întoarce un cod de eroare

          }

pNodAnterior->pElementUrmator = pTemp;

pTemp->pElementUrmator = pNodCurent;

// Urmează iniţializări pentru nodul inserat

return 0; // Operaţie încheiată cu succes

          Inserarea unui nod într-o listă simplu înlănţuită după un nod precizat printr-o cheie

Ca mai sus, prin nod curent înţelegem nodul din listă care satisface condiţia nCodUnic = m_nCodUnic. În acest caz avem nevoie de adresa nodului următor, adresă care este păstrată în pElementUrmator al nodului curent. Codul pentru determinarea nodului curent este următorul:

MPI_Nod    *pTemp;

int     m_nCodUnic;

...

pTemp = pInceputLista;

while (pTemp != NULL)

{

if (pTemp->nCodUnic == m_nCodUnic)

          return pTemp;

pTemp = pTemp->pElementUrmator;

}

// Dacă nu există un asemenea nod se întoarce valoarea NULL

return NULL;

Ordinea operaţiilor este:

- se determină nodul curent, adresa păstrându-se în pNodCurent;

- dacă există nod curent, se alocă memorie pentru nodul ce se va adăuga (presupunem că operaţia s-a efectuat cu succes); adresa se păstrează în pTemp;

adresa nodului următor (dacă există), se salvează într-o variabilă temporară, pTempUrmator;

- se actualizează valoarea pointerului pElementUrmator din nodul curent, cu adresa noului nod : pNodCurent->pElementUrmator = pTemp;

- se realizează legătura dintre noul nod şi următoarele, pTemp->pElemntUrmator = pTempUrmator;

- dacă pTempUrmator este NULL (necompletat) atunci înseamnă că inserarea se face la sfârşitul listei şi atunci trebuie actualizată valoarea pointerului pSfarsitLista cu adresa nodului adăugat, care se găseşte în pTemp; deci pSfarsitLista = pTemp.

Observaţie. Codul poate fi scris imediat traducând strict etapele descrise mai sus.

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

Ştergerea se poate realiza în mai multe moduri. În cele ce urmează avem în vedere următoarele cazuri:

- ştergerea primului nod al unei liste simplu înlănţuite;

- ştergerea unui nod precizat printr-o cheie;

- ştergerea ultimului nod al unei liste simplu înlănţuite.

Vom analiza fiecare situaţie în parte punând în evidenţă operaţiile care trebuie efectuate precum şi ordinea acestora. Operaţia comună tuturor cazurilor luate în considerare este cea a eliberării memoriei alocate. Pentru fiecare funcţie (operator) din C/C++ de alocare de memorie din memoria heap există definită şi funcţia (operatorul) corespunzătoare de eliberare a memoriei ocupate.

          Ştergerea primului nod al unei liste simplu înlănţuite

Ştergerea primului nod presupune reactualizarea valorii pointerului pInceputLista cu valoarea pointerului pInceputLista->pElementUrmator. Ordinea operaţiilor este următoarea:

- dacă valoarea pointerului pInceputLista este NULL atunci lista este vidă şi nu avem ce şterge (operaţie terminată);

- dacă pInceputLista = pSfarsitLista atunci lista are un singur nod şi vom elibera memoria ocupată de acel nod după care vom asigna valorea NULL pentru pointerii pInceputLista şi pSfarsitLista (operaţie terminată), în caz contrar se trece la (3);

- păstrăm adresa de început a listei într-o variabilă temporară, pTemp;

- asignăm pointerului pInceputLista valoarea pointerului

 pInceputLista->pElementUrmator;

eliberăm zona de memorie a cărei adresă se află în pTemp.

Se observă că dacă se execută direct (4) se pierde adresa zonei de memorie ce trebuie eliberată.

          Ştergerea unui nod precizat printr-o cheie

Ştergerea unui nod precizat printr-o cheie (se presupune că nodul care trebuie şters are succesor) presupune refacerea legăturilor dintre nodul precedent şi succesorul nodului şters, precum şi eliberarea zonei de memorie alocate. Presupunem că lucrăm cu următoarele variabile de memorie:

pNodAnterior ce conţine adresa nodului precedent celui ce trebuie şters;

pNodCurent ce conţine adresa nodului ce trebuie şters;

pNodUrmator ce conţine adresa nodului succesor celui ce trebuie şters care se obţine astfel:

pNodUrmator = pNodCurent->pElementUrmator;

Cu aceste notaţii ordinea operaţiilor este următoarea:

- se actualizează valoarea pointerului pNodAnterior->pElementUrmator cu valoarea pointerului pNodUrmator;

- se eliberează zona de memorie dată de pNodCurent.

Determinarea nodului curent se va face cu ajutorul unui cod asemănator celui descris la căutarea unui nod folosind o cheie.

Observaţie. Dacă nodul ce trebuie şters este primul nod al listei (pNodCurent = pInceputLista) atunci se aplică soluţia indicată în paragraful anterior.

          Ştergerea ultimului nod al unei liste simplu înlănţuite

Această operaţie presupune următoarele acţiuni:

- dacă lista este vidă atunci nu avem ce şterge, operaţia fiind  terminată;

- determinarea penultimului nod al listei, a cărui adresă o vom păstra în variabila pTemp;

- eliberarea zonei de memorie a cărei adresă se află în pSfarsitLista;

- actualizarea valorii pointerului pSfarsitLista cu valoarea variabilei pTemp;

- setarea pe NULL a pointerului pSfaristLista->pElementUrmator.

Observaţie. Aplicarea efectivă necesită de fiecare dată parcurgerea listei în totalitatea ei, ceea ce pentru liste mari operaţia este consumatoare de timp.

Etapele de mai sus nu tratează cazul când lista are exact un singur nod. În această situaţie, înainte de etapa (2) ar trebui testat dacă pInceputLista = pSfarsitLista. În caz afirmativ, se execută etapele descrise la ştergerea primului nod al listei. De asemenea trebuie testat mereu dacă lista nu este vidă.

          Ştergerea unei liste simplu înlănţuite

Ştergerea unei liste simplu înlănţuite se poate face prin aplicarea repetată a acţiunii de ştergere a primului nod din listă. Se repetă acest procedeu până când valoarea pointerului pInceputLista devine NULL.