11.1.1. Crearea unei liste simplu inlantuite

2020/02/21 in Programare in C

La crearea unei liste simpu inlantuite se realizeaza urmatoarele:

1. Se initializeaza pointerii prim si ultim cu valoarea zero, deoarece lista la inceput este vida.
2. Se rezerva zona de memorie in heap pentru nodul curent.
3. Se incarca nodul curent cu datele curente, daca exista si apoi se trece la pasul 4.
   Altfel, lista este creata si se revine din functie.
4. Se atribuie pointerului ultim -> urm adresa de memorie a nodului curent, daca lista nu este vida.
   Altfel, se atribuie lui prim aceasta adresa.
5. Se atribuie lui ultim adresa nodului curent.
6. ultim -> urm = 0
7. Procesul se reia de la punctul 2 pentru a adauga un nod nou in lista.

Pentru a incarca datele curente in nod (punctul 3) vom apela o functie care este specifica aplicatiei. Aceasta functie poate sa aiba un nume dinainte precizat sau sa fie transferata printr-un parametru la functia de creare a listei. Acest parametru va fi un pointer spre functia respectiva. Solutia cu parametru se alege de obicei cand programul prelucreaza mai multe liste. In cazul de fata, presupunem ca programul prelucreaza o singura lista si de aceea in loc sa utilizam un parametru pointer, vom considera ca datele se incarca prin functia de nume incnod. Ea returneaza una din urmatoarele trei valori: 0, 1 si -1 si anume:

De exemplu, daca functia incnod citeste datele pe care le incarca in nod dintr-un fisier, atunci ea va returna valoarea -1 la intalnirea EOF, (nu mai sunt date de incarcat in nod).

Functia incnod are un singur parametru si anume adresa din memoria heap rezervata nodului curent, deci acest parametru este un pointer spre tipul comun nodului si structurii, adica spre TNOD.

Din cele de mai sus rezulta ca functia incnod are prototipul:

int incnod(TNOD *p);

O alta functie specifica aplicatiei concrete si care se apeleaza la crearea listei este cea care elibereaza zona de memorie rezervata nodului curent. Vom numi elibnod aceasta functie. Ea are prototipul:

void elibnod(TNOD *p);

Aceasta functie se apeleaza dupa un apel al functiei incnod in care aceasta nu a incarcat date in nodul curent (s-a revenit din ea cu valoarea 0 sau -1). In acest caz exista o zona de memorie rezervata in memoria heap pentru nodul curent, dar la apelul functiei incnod nu s-au incarcat date ori s-au incarcat partial. De aceea, in acest caz, vom elibera zona de memorie rezervata apeland elibnod.

Functia pentru crearea listei simplu inlantuite o numim crelist. Ea returneaza una din valorile 0 sau -1 si anume:

Astfel, definim functia crelist:

int crelist (){
/* - creaza o lista simplu inlantuita; 
   - returneaza:
      -  0 - la eroare;
      - -1 - creare normala. */
  extern TNOD *prim, *ultim;
  int i, n;
  TNOD *p;

  n = sizeof(TNOD);
  prim = ultim = 0; /* initial lista este vida */

/* se rezerva n octeti pentru nod in memoria heap */
  for ( ; ; ) {
    if ((p = TNOD *)malloc(n) == 0)
      printf("memorie insuficienta la crearea listei\n");
      exit(1);
    }
/* se incarca date in nod */
    if ((i = incnod(p)) != 1) {
      elibnod(p); /* se elibereaza zona rezervata pentru nod, ptr ca nu s-au incarcat date */
      return i;
    }
/* se inlantuie nodul in lista */
    if (ultim != 0)
      /* lista nu este vida */
      ultim -> urm = p;
    else
      /* lista vida */
      prim = p;

  ultim = p;
  ultim -> urm = 0;
  }
}

O lista poate fi organizata pastrand elementele ei in memoria heap, iar adresele lor intr-o tabela de pointeri.

Mai jos este prezentata o varianta a functiei crelist care creeaza o lista dupa acest principiu. In acest caz, tabloul de pointeri va fi global si are un numar maxim de elemente.

Numim tpnod acest tablou si cu itpnod variabila globala care are ca valoare indicele primului element al tpnod care este liber. Cu alte cuvinte, tpnod[itpnod-1] este pointerul spre ultimul nod adaugat in lista. Initial, itpnod are valoarea zero.

Tipul nodurilor nu mai este necesar sa fie recursiv, deoarece in acest caz ordonarea se realizeaza prin indici:

• primul nod are indicele zero;
• al doilea nod are indicele 1;
...
• ultimul nod are indicele itpnod-1.

De aceea, in locul tipului TNOD, vom folosi tipul:

typedef struct {
    declaratii
} TTNOD;

Tabloul tpnod se declara astfel:

TTNOD *tpnod[MAX];

unde:

Variabila itpnod este de tip int:

int itpnod;

Mai jos este indicata functia pentru crearea listei cu utilizarea tabloului tpnod. Ea utilizeaza functiile incnod si elibnod ca in cazul functiei crelist, fiind analoaga cu aceasta:

int tpcrelist {
/* - creaza o lista folosind un tablou de pointeri
   care pastreaza adresele nodulrilor listei;
   - returneaza:
      -  0 - la eroare;
      - -1 - creare normala. */
	  
  extern TTNOD *tpnod[];
  extern int itpnod;
  int i, n;
  TTNOD *p;

  n = sizeof(TTNOD);
  for (itpnod = 0; itpnod < MAX; itpnod++) {
    if ((p = (TTNOD *)malloc(n)) == 0)
      printf("memorie insuficienta la crearea listei\n");
      exit(1);
    }
/* se incarca date in nod */
    if ((i = incnod(p)) != 1) {
      elibnod(p);
      return i;
    }
    tpnod[itpnod] = p; /* pastreaza adresa nodului in tabloul de pointeri */
  }
}

11.1.2. Accesul la un nod al unei liste simplu inlantuite