tda list ă
DESCRIPTION
TDA list ă. Structuri de date şi algoritmi - laborator - s.l . dr. ing Ciprian-Bogdan Chiril ă Universitatea Politehnica Timi ş oara 2014. Cuprins. Definiţii şi operaţii asupra listelor Tehnici de implementare a listelor Implementarea listelor cu ajutorul tipului tablou - PowerPoint PPT PresentationTRANSCRIPT
TDA listă
Structuri de date şi algoritmi-laborator-
s.l. dr. ing Ciprian-Bogdan ChirilăUniversitatea Politehnica Timişoara
2014
Cuprins Definiţii şi operaţii asupra listelor Tehnici de implementare a listelor
Implementarea listelor cu ajutorul tipului tablou
Implementarea listelor cu ajutorul tipului pointer; structuri recursive de tip listă
Implementarea listelor cu ajutorul cursorilor
Definiţia listei
O lista L e o secvenţă de zero sau mai multe elemente, numite noduri, toate fiind de acelasi tip de bază T.
L=a1, a2, ... ,an (n>=0)
Operaţii asupra listelor Insereaza(L,x,p) Cauta(x,L) Furnizeaza(p,L) Suprima(p,L) Urmator(p,L) Anterior(p,L) Initializare(L) Primul(L) TiparesteLista(L)
Implementarea listelor cu ajutorul tipului tablou – structura de date
#define N 100
typedef struct{int tab[N];int pozUltim;
} Lista;
Iniţializare, inserare început listăvoid initializeaza(Lista *pl){
pl->pozUltim=-1;}
void insereaza_inceput(Lista *pl,int x){
int i;
pl->pozUltim++;
for(i=pl->pozUltim;i>0;i--){
pl->tab[i]=pl->tab[i-1];}
pl->tab[0]=x;}
Inserare interior/sfârşit listăvoid insereaza(Lista *pl,int x,int p){
int i;
pl->pozUltim++;
for(i=pl->pozUltim;i>p;i--){
pl->tab[i]=pl->tab[i-1];}
pl->tab[p]=x;}
void insereaza_sfarsit(Lista *pl, int x){
pl->pozUltim++;pl->tab[pl->pozUltim]=x;
}
Tipărire conţinut listăvoid tipareste_lista(Lista l){
int i;for(i=0;i<=l.pozUltim;i++){
printf("%d ",l.tab[i]);}printf("\n");
}
Exemplu de utilizarevoid main(){
Lista l1;initializeaza(&l1);insereaza_inceput(&l1,10);insereaza_inceput(&l1,12);insereaza_inceput(&l1,14);insereaza_inceput(&l1,15);insereaza_inceput(&l1,16);insereaza_sfarsit(&l1,20);insereaza_sfarsit(&l1,22);insereaza_sfarsit(&l1,23);insereaza_sfarsit(&l1,25);insereaza(&l1,7,2);tipareste_lista(l1);
}
Implementarea listelor cu ajutorul tipului pointer – structura de date
typedef struct Nod{
int cheie;int info;Nod* urm;
} Nod;
typedef struct{
Nod* prim;Nod* ultim;
} Lista;
Iniţializare listăvoid initializeaza_lista(Lista *pl){
pl->prim=NULL;pl->ultim=NULL;
}
Inserare început listăvoid insereaza_inceput(Lista *pl,Nod *p){
if(pl->prim==NULL){
pl->prim=p;pl->ultim=p;
}else{
p->urm=pl->prim;pl->prim=p;
}}
Inserare sfârşit listăvoid insereaza_sfarsit(Lista *pl,Nod *p){
if(pl->prim==NULL){
pl->prim=p;pl->ultim=p;
}else{
pl->ultim->urm=p;pl->ultim=p;
}}
Inserare înainte de nod (1)void insereaza_inainte_nod(Lista *pl,int cheie,Nod *p){
if(pl->prim==NULL){
pl->prim=p;pl->ultim=p;
}else
Inserare înainte de nod (2){
Nod *q,*r;if(pl->prim->cheie==cheie){
insereaza_inceput(pl,p);}else{
for(q=r=pl->prim;q!=NULL;r=q,q=q->urm){
if(q->cheie==cheie){
r->urm=p;p->urm=q;break;
}}
}}
}
Inserare după nod (1)void insereaza_dupa_nod(Lista *pl,int cheie,Nod *p){
if(pl->prim==NULL){
pl->prim=p;pl->ultim=p;
}else
Inserare după nod (2){
Nod *q;if(pl->ultim->cheie==cheie){
insereaza_sfarsit(pl,p);}else{
for(q=pl->prim;q!=NULL;q=q->urm){
if(q->cheie==cheie){
p->urm=q->urm;q->urm=p;break;
}}
}}
}
Tipărire conţinut listăvoid tipareste_lista(Lista l){
Nod* p;for(p=l.prim;p!=NULL;p=p->urm){
printf("%d ",p->info);}printf("\n");
}
Ştergere listăvoid sterge_lista(Lista *pl){
Nod *p,*q;
for(p=pl->prim;p!=NULL;){
q=p->urm;printf("Sterg nodul de la adresa: %p.\n",p);free(p);p=q;
}}
Exemplu de utilizareLista l1;initializeaza_lista(&l1);Nod *pnod1=(Nod*)malloc(sizeof(Nod));pnod1->cheie=1;pnod1->info=110;pnod1->urm=NULL;…Nod *pnod6=(Nod*)malloc(sizeof(Nod));pnod6->cheie=6;pnod6->info=160;pnod6->urm=NULL;insereaza_inceput(&l1,pnod2);insereaza_inceput(&l1,pnod1);insereaza_sfarsit(&l1,pnod3);insereaza_sfarsit(&l1,pnod4);insereaza_inainte_nod(&l1,3,pnod5);insereaza_dupa_nod(&l1,3,pnod6);tipareste_lista(l1);sterge_lista(&l1);
Implementarea listelor cu ajutorul cursorilor – structura de date
#define N 100
typedef struct{
int info;int urm;
} Nod;
typedef struct {
Nod tab[N];int prim, disponibil;
} Lista;
Iniţializare listăvoid initializeaza(Lista *pl){
pl->prim=-1;pl->disponibil=0;
}
Inserare început listăvoid insereaza_inceput(Lista *pl,int x){
pl->tab[pl->disponibil].info=x;pl->tab[pl->disponibil].urm=pl->prim;pl->prim=pl->disponibil;pl->disponibil++;
}
Inserare sfârşit listăvoid insereaza_sfarsit(Lista *pl, int x){
int c,c2;for(c=pl->prim;c!=-1;c2=c,c=pl->tab[c].urm){
;}pl->tab[c2].urm=pl->disponibil;pl->tab[pl->disponibil].info=x;pl->tab[pl->disponibil].urm=-1;pl->disponibil++;
}
Tipărire conţinut listăvoid tipareste_lista(Lista l){
int c;for(c=l.prim;c!=-1;c=l.tab[c].urm){
printf("%d ",l.tab[c].info);}printf("\n");
}
Exemplu de utilizarevoid main(){
Lista l1;initializeaza(&l1);insereaza_inceput(&l1,10);insereaza_inceput(&l1,20);insereaza_inceput(&l1,30);insereaza_inceput(&l1,40);insereaza_sfarsit(&l1,50);insereaza_sfarsit(&l1,60);insereaza_sfarsit(&l1,70);insereaza_sfarsit(&l1,80);tipareste_lista(l1);
}