Liste

<<Pagina Materiale

Liste

Structuri recursive
Structura de date lista
Tehnici de insertie a nodurilor
Tehnici de suprimare a nodurilor
Traversarea unei liste
Aplicatii ale listelor
Exemplu
Exercitii

Structuri recursive

La capitolul privitor la recursivitate, aceasta a fost ilustrata ca o proprietate specifica algoritmilor. Sa revedem definitia recursivitatii:
Un obiect sau un fenomen se defineste in mod recursiv daca in definitia sa exista o referire la el insusi.
Se va prezenta in continuare extinderea acestei proprietati asupra tipurilor de date, in forma structurilor de date recursive.

Prin analogie cu algoritmii, prin structura recursiva se intelege o structura care are cel putin o componenta de acelasi tip cu structura insasi. Si in acest caz poate exista recursivitate directa sau indirecta.
Pentru evitarea structurilor infinite, in definitia recursiva trebuie sa existe o conditie de care depinde prezenta efectiva a componentei sau componentelor recursive.
Structurile recursive pot fi implementate in C numai in forma unor structuri dinamice, deoarece o structura nu poate avea un camp de acelasi tip structura, ci doar pointer la structura.. Deci definitia unei structurii recursive recursiva va deveni: o structura care are o componenta de tip pointer la structura insasi.
Limitarea structurilor recursive se realizeaza prin existenta valorii NULL pentru pointeri.

La modul general, o structura recursiva se defineste:

struct recursiva{ // reprezinta un nod al unui arbore generalizat
    tip1 camp1; // m campuri de tipuri oarecare
    tip2 camp2;
    ...
    tipm campm;
    struct recursiva *p1, *p2, ..., *pn;// L
    // n campuri de tip pointer la structura
}; Cu extensiile aduse de C++, cum numele unei structuri este nume de tip, linia L devine:

recursiva *p1, *p2, ..., *pn;

In continuare discutia se va referi la structurile recursive care au o singura componenta pointer la structura.

Structura de date lista

Lista este o structura dinamica, situata in memoria centrala, in care toate elementele sunt de acelasi tip; numarul de elemente este variabil, chiar nul.
De remarcat diferentele fata de definitia tabloului: tabloul este o structura statica, situata in memoria centrala, in care toate elementele sunt de acelasi tip; numarul de elemente este constant.

O alta definire a listei este:
O lista L este o secventa de zero sau mai multe elemente, numite noduri, toate fiind de acelasi tip de baza T.
L=a1,a2,...,an (n>=0)

Daca n>=1, a1 se spune ca este primul nod al listei, iar an, ultimul nod. Daca n=0, lista este vida.
Numarul de noduri se numeste lungimea listei.

Un nod al listei liniare care apare ca o structura recursiva, avand o componenta de tip pointer la structura, reprezentand legatura ( inlantuirea ) spre nodul urmator. Lista in care fiecare nod are o sinfura inlantuire se numeste lista simplu inlantuita.

    struct nod{
        TipCheie cheie;
        TipInfo info;
        struct Nod* urmator;
};
struct nod* inceput;

//pentru o scriere mai compacta se pot defini tipurile:
typedef struct nod Nod, *pNod;
pNod inceput;

Caracteristica unei astfel de structuri consta in prezenta unei singure inlantuiri. Campul cheieserveste la identificarea nodului, campul urmatore pointer de inlantuire la nodul urmator, iar cel infocontine informatia utila.

Variabilainceputindica spre primul nod al listei. In unele situatii in locul lui inceputse utilizeaza un nod fictiv, adica o variabila de tip struct Nod cu campurile cheie si info neprecizate, dar campul urmatorindicand spre primul nod al listei.

De asemenea uneori este util a se pastra pointerul spre ultimul nod al listei.

O varianta este a listelor circulare la care dispare notiunea de prim, ultim nod, lista fiind un pointer ce se plimba pe lista.

Tehnici de insertie a nodurilor

Insertia unui nod la inceputul listei

Daca inceputeste variabila pointer ce indica spre primul nod al listei, iarqo variabila auxiliara de tip pointer, secventa urmatoare realizeaza insertia la inceputul listei si actualizeaza pointerulinceput:

pNod inceput, q;

q=(pNod)malloc(sizeof(Nod)); //creaza spatiu pentru un nou nod
q->urmator=inceput;
//asignarea campurilor cheie si info
inceput=q;

Secventa este corecta si pentru insertia intr-o lista vida, caz in care valoarea lui inceput esteNULL.

Insertia unui nod la sfarsitul listei

Devine mai simpla daca se pastreaza o variabilasfarsit indicand spre ultimul nod al listei:

pNod inceput, sfarsit, q;

q=(pNod)malloc(sizeof(Nod)); //creaza spatiu pentru nou nod ultim
sfarsit->urmator=q;
q->urmator=NULL;
//asignarea campurilor cheie si info
sfarsit=q;

Pentru insertia la sfarsitul listei este necesara existenta a cel putin unui nod, care se creaza prin secventa de la paragraful anterior.

Insertia unui nod dupa unul indicat

Este simpla pentru ca se cunoaste pointerul spre nodul anterior si spre cel urmator celui care se insereaza (pointerul spre nodul urmator este valoarea campului urmator al nodului indicat).

Insertia unui nod in fata unui nod indicat

Printr-un artificiu, se reduce acest caz la cel anterior: se insereaza un nod dupa cel indicat, cheia si informatia din nodul indicat fiind atribuite noului nod inserat si fiind inlocuite cu valorile nodului care trebuia inserat.

Tehnici de suprimare a nodurilor

Pentru suprimarea nodului urmator celui indicat de o variabila pointerq, prin atribuirea:

q->urmator=q->urmator->urmator;

se exclud din lista legaturile la si de la nodul de suprimat.

Pentru suprimarea nodului anterior unuia precizat, se aduce nodul precizat in cel de suprimat. Apoi se suprima succesorul lui, deci cel indicat initial de variabila pointer q:
*q=*q->urmator;/* pentru expresia din dreapta, operatorul de selectie indirecta -> este mai prioritar decat cel de indirectare *, deci nu sunt necesare parantezele */

Traversarea unei liste

Daca nodul de inceput al listei este indicat de variabila inceput, o variabila auxiliara q, care parcurge toate nodurile listei pana cand valoarea ei devine NULL, permite accesul la fiecare nod si efectuarea operatiei specifice traversarii:

for(q=inceput;q!=NULL;q=q->urmator)
//prelucrarea nodului indicat de q

Daca lista are doua noduri fictive, unul de inceput si unul de sfarsit, secventa de traversare devine:

for(q=inceput->urmator;q!=sfarsit;q=q->urmator)
//prelucrarea nodului indicat de q

Aplicatii ale listelor

Liste ordonate si reorganizarea listelor

a)Cautarea intr-o lista neordonata; tehnica fanionului

Se considera o lista simplu inlantuita, cu nodurile de tip Nod. Daca inceput indica spre primul nod al listei, iar ordinea cheilor in lista este aleatoare, cautarea unei chei implica traversarea listei. Functia booleana gasit returneaza valoarea pointerului spre nodul cu cheia egala cu cea cautata, daca un astfel de nod exista si valoarea NULL in caz contrar:

pNod gasit(TipCheie val){
          pNod poz;
          poz=inceput;
          while (poz!=NULL)
               if (poz->cheie==val)
                   return poz;
               else
                   poz=poz->urmator;
          return poz;// cu valoarea NULL

Cautarea se poate perfectiona prin utilizarea metodei fanionului, lista prelungindu-se cu un nod fictiv numit fanion, la creare lista continand acest unic nod. In functia gasit, inainte de baleierea listei, informatia cautata se introduce in cheia nodului fanion, astfel incat va exista cel putin un nod cu cheia cautata:

pNod fanion;
pNod gasit(TipCheie val){
          pNod poz;
          for(poz=inceput,fanion->cheie=val;poz->cheie!=val;
              poz=poz->urmator);
          if(poz==fanion)
                return NULL;
          return poz;

b)Crearea unei liste ordonate; tehnica celor doi pointeri

In continuare se prezinta o metoda foarte simpla pentru crearea unei liste ordonate, tipurile pNod si Nod fiind cele definite anterior. Lista se initializeaza cu doua noduri fictive pointate de doua variabile pointer, inceput sifanion:

pNod inceput, fanion;

void init(void);
     inceput=(pNod)malloc(sizeof(Nod));
     fanion=(pNod)malloc(sizeof(Nod));
     inceput->urmator=fanion;
}

Pentru introducerea unei noi chei in lista, pastrand ordonarea, se va scrie o functie gasit, care daca gaseste cheia in lista returneaza valoarea 1 si pointerii p1 spre nodul gasit si p2 spre cel anterior, respectiv in cazul negasirii cheii, valoarea 0 si pointerii p1 si p2 spre nodurile intre care trebuie facuta insertia:

int gasit(TipCheie val, pNod* p1, pNod* p2){
          for(*p2=inceput,*p1=(*p2)->urmator,fanion->cheie=val;
              (*p1)->cheie<=val;p2=p1,*p1=(*p1)->urmator);
          return *p1!=fanion && (*p1)->cheie==val;

Fragmentul de program care insereaza o noua cheie este:

    pNod p1,p2,p3;
    TipCheie val;
          ...
    if (!gasit(val,&p1,&p2)){
            p3=(pNod)malloc(sizeof(Nod));//creare nod nou
            p2->urmator=p3; //legatura de la nodul anterior la cel nou
            p3->cheie=val;
                                 //completare p3->info
            p3->urmator=p1;//legatura de la noul nod la cel urmator
    }

Pentru tiparirea cheilor dintr-o lista ordonata astfel creata, pointerul care parcurge nodurile trebuie sa fie initializat cu valoarea pointerului spre primul nod efectiv al listei, urmator celui inceput, iar parcurgerea listei se face pana la intilnirea nodului fanion:

    pNod p;
    for(p=inceput->urmator;p!=fanion;p=p->urmator)
      //prelucrarea nodului indicat de p

Exemplu

Sa se realizeze un program care raspunde la urmatoarele comenzi:
   'a' - Citeste o linie de forma
                  identificator , numar ;
unde numar este un numar intreg si retine in evidenta identificatorul impreuna cu numarul asociat lui.
   't' - Citeste o linie care contine un identificator. Daca acesta se gaseste in evidenta se tipareste valoarea asociata lui , in caz contrar se tipareste un mesaj de eroare.
   's' - Citeste o linie ce contine un identificator si il sterge din evidenta.
   'l' - Tipareste in ordine alfabetica identificatorii din evidenta impreuna cu valorile asociate lor
   '+' - Citeste doua linii , fiecare continand un identificator. In cazul in care ambii se afla in evidenta , se tipareste suma lor. In caz ca unul sau ambii identificatori lipsesc din evidenta se tipareste un mesaj de eroare.
   '-' - Citeste doua linii , fiecare continind un identificator. In cazul in care ambii se afla in evidenta , se tipareste diferenta lor. In caz ca unul sau ambii identificatori lipsesc din evidenta se tipareste un mesaj de eroare.
   '*' - Citeste doua linii , fiecare continand un identificator. In cazul in care ambii se afla in evidenta , se tipareste produsul lor. In caz ca unul sau ambii identificatori lipsesc din evidenta se tipareste un mesaj de eroare.
   '/' - Citeste doua linii , fiecare continind un identificator. In cazul in care ambii se afla in evidenta , se tipareste rezultatul impartirii lor. In caz ca unul sau ambii identificatori lipsesc din evidenta se tipareste un mesaj de eroare.
   'f' - Se termina programul
In lista identificatorii sunt pastrati in mod ordonat.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define Max 10

typedef struct elem{
           char *id;
           int valoare;
           struct elem *urm;
} Nod,*pNod;

void listare( void );
pNod cauta( char* );
void sterge( char* );
void introdu( char*, int );

nod *radacina = NULL;

pNod ccauta( pNod lista , char *s )
{
pNnod q1 ;

         for( q1 = lista ; q1 != NULL && strcmp( q1->id,s ) < 0 ;
              q1 = q1->urm );
         if ( q1 != NULL && strcmp( q1->id,s ) == 0 )
                   return q1;
         return NULL;
      }

void clist( pNod lista )
{
pNod q;

for( q = lista ; q != NULL ; q = q->urm )
printf(" identificator:%s, valoare:%d\n",q->id,q->valoare);

}

pNod csterge( pNod lista, char *s )
{

pNod q1 , q2;

         for( q1 = q2 = lista ; q1 != NULL && strcmp( q1->id,s ) < 0;
           q2 = q1, q1 = q1->urm);
          if( q1 != NULL && strcmp( q1->id,s ) == 0 )
              if( q1 != q2 )
                {
                    q2->urm = q1->urm;
                    return lista ;
                }
                else return lista->urm;
           else
             {
              printf("Eroare:identificatorul %s nu apare in lista\n",s);
              return lista;
             }
       }

pNod cintrodu( pNod lista , char *s ,int v)
{
pNod q1 , q2 , aux;

          if( ( aux = (pNod)malloc(sizeof(Nod))) == NULL ||
              ( aux->id = (char *) malloc(strlen(s) +1)) == NULL )
               {
                 printf(" Eroare: memorie insuficienta\n");
                 exit( 1 );
               }
           else
           {
             strcpy( aux->id,s );
             aux->valoare = v;
           }
         for( q1 = q2 = lista ; q1 != NULL && strcmp( q1->id,s ) < 0;
           q2 = q1, q1 = q1->urm);
         if( q1 != NULL && strcmp( q1->id,s ) == 0 )
          {
                 printf(" Eroare : %s apare in lista\n",s);
                 return lista;
          }
          else
              if( q1 != q2 )
                {
                    q2->urm = aux ;
                    aux->urm = q1;
                    return lista ;
                }
                else
                {
                    aux->urm = lista;
                    return aux;
                 }
       }

void listare(void)
       {
         clist( radacina );
       }

pNod cauta( char *s )
       {
         return ccauta( radacina , s );
       }

void sterge( char *s )
       {
         radacina = csterge ( radacina, s );
       }

void introdu( char *s, int v)
       {
         radacina = cintrodu( radacina, s, v );
       }

void getlin( char *s , int *val )
       {
        int i = 0, j;
        char temp[ Max ];

        gets( temp );
        s[ i ] = '\0' ; *val = 0;
        while( temp[ i ] != '\0' )
          if( isalpha( temp[ i ] ))
           {
             j = 0;
             while( isalnum( temp[ i ])) s[ j++ ] = temp[ i++ ];
             s[ j ] = '\0';
           }
           else
             if( isdigit( temp[i] ))
               while( isdigit( temp[i] ))
               {
                 *val = *val * 10 + temp[i] - '0' ;
                 i++;
               }
               else i++;
       }

void ad( void )
      {
       int val;
       char s[ Max ];

       getlin( s , &val );
       if( strlen( s ) != 0 ) introdu( s , val );
        else printf(" Eroare : linie incorecta \n");
      }

void ti( void )
      {
        char s[ Max ];
        nod *p;
        int val;

        getlin( s , &val );
        if( strlen( s ) != 0 )
         {
           if( ( p = cauta( s )) != NULL )
             printf("identificator:%s,valoare :%d \n",p->id,p->valoare);
           else printf(" Eroare: identificator nedefinit \n");
        }
         else printf(" Eroare: linie incorecta \n");
      }

void st( void )
      {
        char s[ Max ];
        int val;

          getlin(s , &val );
          if( strlen( s ) != 0 ) sterge( s );
           else printf(" Eroare: linie incorecta \n");

}

void oper( char c )
       {
        char s1[ Max ] , s2[ Max ];
        int val;
        nod *p1 , *p2;

getlin(s1 , &val);
getlin(s2, &val);

        if(( strlen( s1 ) != 0 ) && ( strlen( s2 ) != 0))
          if((( p1 = cauta( s1 )) != NULL) &&
             (( p2 = cauta( s2 )) != NULL ))
          {
            switch( c )
            {
              case '+' : val = p1->valoare + p2->valoare ; break;
              case '-' : val = p1->valoare - p2->valoare ; break;
              case '*' : val = p1->valoare * p2->valoare ; break;
              case '/' : if( p2-> valoare != 0 )
                                val = p1->valoare / p2->valoare ;
                           else printf(" Eroare: Impartire la 0\n") ;
                           break;
            }
            printf(" Rezultatul operatiei e %d \n", val);
          }
           else printf(" Eroare: linie eronata \n ");
      }

void meniu(void)
{
char o;

         while( 1 )
         {
          clrscr();
          printf(" a .... adauga in evidenta un id si val asociata \n");
          printf(" t .... tipareste valoarea asociata unui id \n");
          printf(" s .... sterge un id \n");
          printf(" l .... listeaza id-rii si valorile asociate \n");
          printf(" + .... calculeaza suma pt. 2 id \n");
          printf(" - .... calculeaza diferenta pt. 2 id \n");
          printf(" * .... calculeaza produsul pt. 2 id \n");
          printf(" / .... calculeaza impartirea pt. 2 id \n");
          printf(" f .... termina programul \n");
          printf("\n Introduceti optiune :"); o = getchar(); getchar();
          switch(tolower(o))
          {
            case 'a': ad();break;
            case 't': ti();break;
            case 's': st();break;
            case 'l': listare();break;
            case '+': case '-' : case '*' : case '/' : oper(o); break;
            case 'f' : return;
            default : printf(" Eroare : Comanda inexistenta \n");
         }
         getchar();
        }
       }

void main( void )
       {
        meniu();
       }

Functiaccauta cauta un identificator in lista returnand pointerul nodului in care s-a gasit identificatorul. Functia clistafiseaza continutul listei. csterge elimina un nod din lista, iar cintrodu va introduce un nod in lista. Aceste functii au ca si parametru formal pointerul de inceput al listei prelucrate.
Folosind aceste functii se definesc cauta, sterge si introdu cu rolul de cautare , stergere si introducere a unui identificator, precum si functia listare , care va lista identificatorii din lista.
Functia meniuafiseaza meniul programului , preia un caracter , reprezentand o comanda , care se va prelucra prin apelul functiei asociate.
Functia operare ca si parametru operatorul de executat .Functia citeste doi identificatori gaseste in lista valorile asociate lor, dupa care executa si afiseaza rezultatul operatiei.

Exercitii

1.Informatiile despre abonatii telefonici (nume, adresa, numar de telefon) se pastreaza intr-o lista ordonata alfabetic dupa numele abonatilor. Sa se realizeze un program interactiv care realizeaza operatiile:

adaugarea unui nou abonat
scoaterea din evidenta a unui abonat
afisarea numarului de telefon al unui abonat
afisarea datelor unui abonat cu un numar dat
afisarea intregii liste.

2.Se prelucreaza un fisier text oarecare, contorizand pentru fiecare identificator, numarul de aparitii. Se vor crea doua liste, in variantele:

lista neordonata, cu nod fanion si insertie la inceputul listei
lista ordonata avand doua noduri fictive.

3.Sa se implementeze un set de functii care realizeaza urmatoarele operatii:

adauga( t, id ) : introduce identificatorul id in lista t
prezent( t, id ): returneaza 1 sau 0 dupa cum identificatorul id este sau nu prezent in lista t
sterge( t, id ) : elimina identificatorul id din lista t
reuneste( t1,t2,t ) : lista t va contine toti identificatorii din t1 sau t2
intersectie( t1,t2,t ) : lista t va contine toti identificatorii care sint prezenti in t1 si t2
scadere( t1,t2,t ) : lista t va contine identificatorii care sunt prezenti in t1 si absenti in t2
tipareste( t ) : tipareste in ordine alfabetica identificatorii din t

Folosind functiile de mai sus, sa se realizeze un program care citeste doua secvente de text consecutive , care se termina fiecare cu o marca EOF. Dupa citirea textelor se cere sa se tipareasca in ordine alfabetica identificatorii prezenti in primul text , apoi cei din al doilea text. In final se vor tipari in ordine alfabetica identificatorii care sunt prezenti atat in primul cat si in al doilea text.

<<Pagina Materiale