11.1. Lista simplu inlantuita

2020/02/21 in Programare in C

Asa cum s-a aratat mai sus, intre nodurile unei liste simplu inlantuite este definita o singura relatie de ordonare. De obicei aceasta relatie este cea de succesor, adica fiecare nod contine un pointer a carui valoare este adresa nodului urmator din lista. In mod analor se poate defini relatia de precedent. In cele ce urmeaza, ne vom margini la liste simplu inlantuite pentru care nodurile satisfac relatia de succesor.

Intr-o astfel de lista exista totdeauna un nod si numai unul care nu mai are ca urmator (succesor), precum si un nod care nu este urmatorul (succesorul) niciunui alt nod. Aceste noduri formeaza capetele listei simplu inlantuite.

Pentru a gestiona nodurile unei liste simplu inlantuite vom utiliza doi pointeri spre cele doua capete. Numim prim pointerul spre nodul care nu este urmatorul niciunui nod al listei si ultim pointerul spre nodul care nu are succesor in lista. Acesti pointeri vor fi utilizati in taoate functiile pentru prelucararea listelor simplu inlantuite. Ei pot fi definiti fie ca variabile globale, fie ca parametri pentru functiile de prelucrare a listei. Se alege alternativa cu variabile globale in cazul in care nu se gestioneaza mai multe liste simplu inlantuite in acelasi program. Dimpotriva, pointerii respectivi se vor transfera prin parametri in cazul in care programul gestioneaza mai multe liste simplu inlantuite.

In cele ce urmeaza vom considera cazul in care pointerii prim si ultim sunt variabile globale.

Tipul unui nod intr-o lista simplu inlantuita se poate defini folosind o declaratie de forma:

typedef struct tnod {
    declaratii
    struct tnod *urm;
} TNOD;

Pointerii prim si ultim se declara in afara oricarei functii prin:

TNOD *prim, *ultim;

De obicei, ei vor fi declarati inaintea functiei main a programului.

Pointerul urm defineste relatia de succesor pentru nodurile listei. Pentru fiecare nod, el are ca valoare adresa nodului urmator din lista. Exceptie de la aceasta regula o constituie nodul spre care pointeaza variabila ultim. In acest caz, urm are valoarea 0 (pointerul nul).

In continuare vom construi functii care sa realizeze operatii pentru liste simplu inlantuite.

11.1.1. Crearea unei liste simplu inlantuite