11.1.2. Accesul la un nod al unei liste simplu inlantuite

2020/02/22 in Programare in C

Putem avea acces la nodurile unei liste simplu inlantuite incepand cu nodul spre care pointeaza variabila globala prim si trecand apoi pe rand de la un nod la altul, folosind variabila urm.

Exista cazuri in care dorim acces la un nod anumit al listei. In acest caz, este necesar sa definim modul de identificare al nodului la care dorim sa avem acces. Un mod simplu este acela de a indica numarul de ordine al nodului la care se doreste acces, de exemplu, se doreste acces la al n-lea nod al listei. Cum lista este o multime dinamica, acest mod de a defini accesul la un nod al ei nu este totdeauna cel mai potrivit. O alta metoda este aceea de a avea o componenta a nodurilor, care sa aiba valori diferite pentru noduri diferite. In acest caz se poate defini accesul la nodul din lista pentru care data respectiva are o valoare data. O astfel de data, care este componenta a nodurilor unei liste si are valori distincte pentru noduri diferite se numeste cheie.

Cheia poate fi o dat de un tip oarecare.

In cazul de fata vom considera o cheie de tip int. Functia de mai jos poate fi modificata pentru a utiliza chei de tip: long, char, double, etc.

Functia returneaza pointerul spre nodul cautat sau zero in cazul in care lista nu contine un nod a carui cheie sa aiba valoarea indicata de parametrul ei.

Nodurile listei au tipul definit astfel:

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

Putem defini functia de cautare ca mai jos:

TNOD *cnci(int c)
/* - cauta un nod al listei pentru care cheie = c;
   - returneaza pointerul spre nodul determinat
   in acest fel sau 0 daca nu exista niciun nod 
   asa incat cheie = c */
{
   extern TNOD *prim;
   TNOD *p;

   p = prim;
/* cautarea incepe cu nodul spre care pointeaza variabila prim */
   while (p != 0) {
      if (p -> cheie == c)
         return p; /* s-a gasit un nod pentru care cheie = c */
      p = p -> urm; /* se trece la nodul urmator din lista */
   }
/* in acest punct se ajunge cand nu exista un nod in lista 
cu proprietatea cheie = c */
   return 0;
}

O functie similara se poate construi si pentru cazul in care la implementarea listei se utilizeaza tabloul de pointeri tpnod.

In acest caz, tipul nodurilor listei se declara astfel:

typedef struct {
   declaratii
   int cheie;
   declaratii
} TTNOD;

Ambele functii parcurg elementele listei, nod cu nod, fie pana la intalnirea nodului cautat, fie pana la sfarsitul listei daca nu exista in lista un nod a carui cheie sa aiba valoarea ceruta. Aceasta metoda de cautare se numeste cautare liniara. Ea este o metoda foarte simpla de cautare, dar nu este eficienta si de aceea se aplica numai la listecu un numar relativ mic de noduri.

O metoda mult mai eficienta este metoda cautarii binare. Aceasta metoda poate fi aplicata simplu la listele implementate cu ajutorul tabelului tpnod. In acest scop lista trebuie intai sortata, de exemplu crescator, in raport cu valorile cheii. Sortarea se poate realiza procedand ca in exercitiul 8.18. in care cuvintele citite de la intrarea standard se pastreaza in memoria heap si in paralel cu aceasta se defineste un tablou cu adresele la care sunt pastrate aceste cuvinte. Apoi se realizeaza sortarea lor (ordonarea in ordine alfabetica) folosind metoda bulelor.

Pentru o eficienta mai buna se poate utiliza o alta metoda de sortare:

11.1.3. Inserarea unui nod intr-o lista simplu inlantuita