Se alocă în heap memorie pentru noul nod, adresa fiind în pTemp.Liste
Lista este o multimulţime dinamică, adică este o colecţie cu un număr variabil de elemente, care se pot repeta. Elementele au acelaşi tip. În general, tipul elementelor unei liste este un tip utilizator. Elementele unei liste se numesc noduri.
Dacă între nodurile unei liste există o singură relaţie de ordine, atunci lista se numeşte simplu înlănţuită.
Dacă între nodurile unei liste există două relaţii de ordine, atunci lista se numeşte dublu înlănţuită.
În general vom spune că o listă este n-înlănţuită dacă între nodurile ei sunt definite n relaţii de ordine.
În legătură cu listele se au în vedere unele operaţii de interes general:
crearea unei liste;
accesul la un nod oarecare al listei;
inserarea unui nod într-o listă;
ştergerea unui nod dintr-o listă;
ştergerea unei liste.
Liste simplu înlănţuite
Între nodurile unei liste simplu înlănţuite este definită o singură relaţie de ordine, totală. De obicei această relaţie este cea de succesor, adică fiecare nod conţine un pointer a cărui valoare reprezintă adresa nodului următor din listă. Asemănător, se poate defini relaţia de precedent. În cele ce urmează ne vom mărgini numai la liste simplu înlănţuite pentru care nodurile satisfac relaţia succesor. O asemenea listă se caracterizează prin aceea că există totdeauna un nod şi numai unul care nu are următor (succesor, fiu), precum şi un nod, unic, care nu este următorul (succesorul) nici unui alt nod. Aceste noduri formează capetele listei simplu înlănţuite. Pentru a gestiona nodurile unei liste simplu înlănţuite, vom utiliza doi pointeri spre cele două capete ale listei. Notăm pointerul spre nodul care nu este următorul (succesorul) nici unui alt nod al listei (adică primul nod al listei) cu pInceputLista şi cu pSfarsitLista pointerul spre nodul care nu are succesor în listă. Aceşti pointeri vor fi utilizaţi în toate exemplele pe care le vom avea în vedere în prelucrarea listelor simplu înlănţuite. Ei pot fi definiţi fie ca variabile globale, fie ca parametri pentru funcţiile de prelucrare a listei, fie ca date membru ale unui obiect.
Tipul unui nod într-o listă simplu înlănţuită se poate defini folosind o declaraţie de forma (C/C++):
typedef struct _tagNod {
//declaraţii;
int nCodUnic;
struct _tagNod *pElementUrmator;
} MPI_Nod;
Pointerul pElementUrmator va conţine adresa spre următorul nod al listei, adică defineşte relaţia succesor pentru nodurile listei. Nodul spre care pointează variabila pSfarsitLista va avea drept valoare NULL pentru pElementUrmator (pElementUrmator = NULL;).
Pointerii pInceputLista şi pSfarsitLista se declară în afara oricărei funcţii (de obicei înaintea definirii funcţiei main a programului principal, deci variabile globale) prin:
MPI_Nod *pInceputLista, *pSfarsitLista;
Ne vom mărgini la a descrie ordinea operaţiilor ce trebuie respectată în lucrul cu diverse structuri. Menţionăm de la început că nu urmărim o optimizare a codului, ci o înţelegere corectă a operaţiilor ce trebuie efectuate şi o claritate a codului scris
Crearea unei liste simplu înlănţuite
Operaţiile ce trebuiesc efectuate la crearea unei liste simplu înlănţuite sunt:
Se iniţializează pointerii pInceputLista şi pSfarsitLista cu valoarea NULL, deoarece la început lista este vidă.
Se rezervă zonă de memorie în memoria heap pentru nodul curent.
Se încarcă nodul curent cu informaţiile suplimentare.
Se atribuie pointerului pSfarsitLista->pElementUrmator adresa din memoria heap a nodului curent, dacă lista nu este vidă. Altfel se atribuie lui pInceputLista această adresă.
Se atribuie pointerului pSfarsitLista adresa nodului curent.
pSfarsitLista->pElementUrmator = NULL;
Procesul se reia de la pasul 2 de mai sus pentru a adăuga un nod nou la listă.
Pentru claritate, acţiunea de creare a unei liste ar trebui tratată în modul următor:
- Lista este vidă şi trebuie creat primul nod al listei.
- Lista nu este vidă şi se adaugă un nou nod la sfârşitul listei.
Pentru cazul unu, ordinea operaţiilor este următoarea:
Se iniţializează pointerii pInceputLista şi pSfarsitLista cu valoarea NULL, deoarece la început lista este vidă.
pInceputLista = NULL;
pSfarsitLista = NULL;
Se rezervă zonă de memorie în memoria heap pentru nodul curent.
Se încarcă nodul curent cu informaţiile suplimentare.
Se atribuie pointerului pInceputLista şi pSfarsitLista adresa din memoria heap a nodului curent (pointerii pInceputLista şi pSfarsitLista au aceeaşi valoare când lista este vidă (valoarea NULL) sau lista are un singur element.
Se atribuie valoarea NULL pointerului pElementUrmator.
Codul ar putea arăta astfel:
...
// C1.1.
pInceputLista = NULL;
pSfarsitLista = NULL;
// C1.2.
pTemp = (MPI_Nod*)malloc(sizeof(MPI_Nod));
if (pTemp == NULL)
{
printf (“Memorie insuficienta la crearea listei\n”);
exit(1);
}
// C1.3.
// acţiuni specifice de iniţializare a datelor membru din nodul listei
// C1.4.
pInceputLista = pTemp;
pSfarsitLista = pTemp;
// C1.5.
pSfarsitLista->pElementUrmator = NULL;
Pentru al doilea caz ordinea operaţiilor este următoarea:
Se rezervă zonă de memorie în memoria heap pentru nodul curent.
Se încarcă nodul curent cu informaţiile suplimentare.
Se atribuie pointerului pSfarsitLista->pElementUrmator adresa din memoria heap a nodului creat.
Se atribuie pointerului pSfarsitLista adresa din memoria heap a nodului creat.
Se atribuie valoarea NULL pointerului pSfarsitLista->pElementUrmator.
Codul ar putea fi următorul:
// C2.1.
pTemp = (MPI_Nod*)malloc(sizeof(MPI_Nod));
if (pTemp == NULL) {
printf (“Memorie insuficienta la crearea listei\n”);
exit(1);
}
// C2.2.
// operaţii specifice de iniţializare a nodului
// C2.3. Se face legătura dintre ultimul nod al listei cu noul nod creat
pSfarsitLista->pElementUrmator = pTemp;
// C2.4. Noul nod creat va deveni ultimul nod al listei
pSfarsitLista = pTemp;
//C2.5. Acum pSfarsitLista pointează spre noul nod creat care nu are succesori
pSfaristLista->pElementUrmator = NULL;
Se alocă în heap memorie pentru noul nod, adresa fiind în pTemp.
Ordinea operaţiilor care urmează este strictă:
- realizarea legăturii noului nod cu ultimul nod al listei;
- noul nod devine ultimul nod al listei;
- pElementUrmator din ultimul nod adăugat ia valoarea NULL.