Principais operações em Listas
TPA - 2009-2
Listas Simples
Inserção no Final
1. void insereNofinalDaLista(Lista *l, Elemento e){
2.
Lista paux,p;
3.
p =malloc(sizeof(struct nodo));
4.
p->prox=NULL;
5.
p->e=e;
6.
if (*l == NULL) {
7.
*l =p;
8.
}
9.
else {
10.
paux = *l;
11.
while(paux->prox){
12.
paux=paux->prox;
13.
}
14.
paux->prox=p;
15.
}
16.
17. }
Insere no final da lista Recursivamente
1. void insereNofinalDaListaRec(Lista *l,
Elemento e){
2.
if (*l == NULL) {
3.
*l = malloc(sizeof(struct nodo));
4.
(*l)->e=e;
5.
(*l)->prox = NULL;
6.
}
7.
else
8.
insereNofinalDaLista( &((*l)->prox), e);
9. }
10.
Inserção Ordenada –
1. void insereListaOrdenada(Lista *l, Elemento e){
2.
Lista paux,pant,p;
3.
p = malloc(sizeof(struct nodo));
4.
p->e=e;
5.
p->prox = NULL;
6.
7.
if (*l == NULL) {
8.
*l=p;
9.
}
10.
else{
11.
pant=*l;
12.
paux = pant->prox;
13.
while(paux!=NULL){
14.
if((paux)->e.codigo>=e.codigo){
15.
break;
16.
}
17.
pant=paux;
18.
paux=paux->prox;
19.
}
20.
p->prox=paux;
21.
pant->prox = p;
22.
}
23. }
Remove da Lista um elemento arbitrário
1. Elemento removeDaLista(Lista *l, int codigo){
2.
Lista paux;
3.
Elemento e;
4.
if(*l==NULL){
5.
return e;
6.
}
7.
if((*l)->e.codigo== codigo){
8.
paux = *l;
9.
*l=(*l)->prox;
10.
e = paux->e;
11.
free(paux);
12.
return e;
13.
}
14. else {
15.
return removeDaLista(&((*l)->prox),codigo);
16.
}
17. }
Lista Circular
Inserção
1. void insereaDireita(Lista *l, Elemento e){
2. Lista p;
3. p = malloc(sizeof(struct nodo));
4. p->e = e;
5. if (*l==NULL){ /* Lista vazia */
6.
p->prox = p;
7.
*l = p;
8. }
9. else {
10.
p->prox = (*l)->prox;
11.
(*l)->prox = p;
12. }
13. }
Remoção
1. int removeaDireita(Lista *l, Elemento *ret){
2.
Lista paux;
3.
if (*l == NULL){
4.
return 0;
5.
}
6.
else {
7.
paux = (*l)->prox;
8.
*ret = paux->e;
9.
if (*l==paux){ /* Lista com apenas um nó */
10.
*l = NULL;
11.
}
12.
else{
13.
(*l)->prox = paux->prox;
14.
}
15.
free(paux);
16.
return 1;
17. }
18. }
Remoção de elemento arbitrário
1.
Elemento removeElemento(Lista *l, int codigo){
2.
Lista paux1,paux2;
3.
Elemento e;
4.
if(*l==NULL){
5.
return e;
6.
}
7.
paux1=*l;
8.
paux2=paux1->prox;
9.
do{
10.
if (paux2->e.codigo==codigo){
11.
break;
12.
}
13.
paux1=paux2;
14.
paux2=paux2->prox;
15.
}while(paux2!=*l);
16.
if(paux2->e.codigo!=codigo){
17.
// elemento não encontrado
18.
return e; //retorna e vazio;
19.
}
20.
paux1->prox = paux2->prox;
21.
e = paux2->e;
22.
if(*l==paux2){ /* se o nodo procurado é o apontado por l*/
23.
if(paux1!=paux2){ /* lista com mais de um nodo */
24.
*l=paux1;
25.
}
26.
else { /* lista com um so nodo */
27.
*l=NULL;
28.
}
29.
}
30.
free(paux2);
31.
return e;
32.
}
Lista duplamente encadeada
1. void insereNaLista(Lista *l, Elemento e){
2.
Lista p;
3.
p = malloc(sizeof(struct nodo));
4.
p->e = e;
5.
6.
if (*l==NULL){ /* Lista vazia */
7.
p->prox = p;
8.
p->ant=p;
9.
*l = p;
10. }
11. else {
12.
(*l)->ant->prox=p;
13.
p->prox=(*l);
14.
p->ant=(*l)->ant;
15.
(*l)->ant=p;
16.
(*l)=p;
17. }
18. }
Remoção
1. Elemento removeDaLista(Lista *l){
2. Elemento e;
3. Lista anterior, proximo;
4.
if(*l==NULL){ // lista vazia
5.
return e;
6.
}
7.
if(*l==(*l)->ant) { // lista de um nodo somente
8.
e=(*l)->e;
9.
free(*l);
10.
*l=NULL;
11.
return e;
12.
}
13.
anterior=(*l)->ant;
14.
proximo = (*l)->prox;
15.
anterior->prox=proximo;
16.
proximo->ant=anterior;
17.
e=(*l)->e;
18.
free(*l);
19.
*l=proximo;
20.
return e;
21. }
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
Removendo elemento arbitrário.
Elemento removeElemento(Lista *l, int codigo){
Lista aeliminar, proximo,anterior;
Elemento e;
if(*l==NULL){ // 1.lista vazia
return e;
}
aeliminar = *l;
do {
if(aeliminar->e.codigo==codigo)
break;
aeliminar=aeliminar->prox;
}while(aeliminar!=*l);
if (aeliminar->e.codigo!=codigo){ // 2.elemento nao existe
return e;
}
if ((*l)->ant==(*l)){ // 3. so um elemento na lista
*l=NULL;
return e;
}
else{
anterior = aeliminar->ant;
proximo = aeliminar->prox;
anterior->prox=proximo;
proximo->ant=anterior;
if(aeliminar==*l){ // 4. se eliminar o elemento apontado por l atualizo l
*l=proximo;
}
}
e = aeliminar->e;
free(aeliminar);
return e;
}