Listas simplemente encadenada

Publicado por rogikato / en 23:39 / /

En una lista simplemente encadenada, cada elemento posee apenas información de quien es su sucesor.
Es necesario también almacenar la información del primer elemento de la lista.
Principales problemas:
_Imposibilidad de regresar al elemento anterior.
_Necesidad de guardar información del elemento anterior a fin de realizar algunas operaciones.


Implementación (Estática)


Para simplificar se considerará que los elementos almacenados serán números enteros. Los elementos serán insertados de forma ordenada.
El esquema gráfico abajo muestra el proceso de inserción de un nuevo elemento en una lista encadenada estática. El nuevo elemento será insertado entre el elemento actual y el elemento anterior.

Especificación:
1. LE *Inicia_Lista(int N)         // Crea una nueva lista con N elementos
2. void Inserta_Elemento(LE *L, int A)    //Inserta un nuevo elemento A en la posicion correcta de la lista L
3. int Elimina_Elemento(LE *L, int A)      //Elimina el elemento A de la lista L. Si el elemento no existe o la lista está vacía, retorna -1.
4. void Imprime_Lista (LE *L)
5. LE *Vacia_Lista(LE *L)


Código:

#include<iostream.h> #include<stdlib.h> #include<stdio.h> typedef struct lista LE; typedef struct nodo_lista NO; typedef struct vacio VC; struct vacio { int ultimo; /* guarda a última posición ocupada del vector pos_vac */ int *pos_vac; }; struct nodo_lista { int elem; int prox; /* guarda la posición del próximo elemento en la lista */ }; struct lista { int head ; /* marca la posición del primer elemento de la lista */ VC *vac ; /* guarda posiciones vacías */ NO *nodo ; }; LE *Inicia_Lista(int N) { LE *temp; int i ; if ((temp = (LE *) malloc(sizeof(LE))) != NULL) { if ((temp->nodo = (NO *) malloc(N*sizeof(NO))) != NULL) { if ((temp->vac = (VC *) malloc(N*sizeof(VC))) != NULL) { if ((temp->vac->pos_vac = (int *) malloc(N*sizeof(int))) != NULL) { temp->vac->ultimo = N-1; for (i = 1; i <= N; i++) temp->vac->pos_vac[i-1] = N-i; temp->head = -1; /* lista vacia */ return(temp); } else exit(0); } else exit(0); } else exit(0); } else exit(0); } void Inserta_Elemento(LE *L, int A) { int i,ant; /* Ejercicio: realizar prueba para ver si todavía existe espacio */ if (L->head == -1) /* Lista esta vacía */ { L->head = 0; L->nodo[0].elem = A; L->nodo[0].prox = -1; (L->vac->ultimo)--; } else { i = L->head; ant = -1; while ((i != -1) && (L->nodo[i].elem <= A)) { ant = i; /* guarda la posicion del anterior */ i = L->nodo[i].prox; } L->nodo[L->vac->pos_vac[L->vac->ultimo]].elem = A; if (ant == -1) /* incluir al inicio de la lista */ { L->nodo[L->vac->pos_vac[L->vac->ultimo]].prox = L->head; L->head = L->vac->pos_vac[L->vac->ultimo]; } else { L->nodo[L->vac->pos_vac[L->vac->ultimo]].prox = L->nodo[ant].prox; L->nodo[ant].prox = L->vac->pos_vac[L->vac->ultimo]; } (L->vac->ultimo)--; } return; } void Imprime_Lista(LE *l) { int i; i = l->head; cout<<"\n Elementos "; while (i != -1) { cout<<l->nodo[i].elem<<" "; i = l->nodo[i].prox; } } /* Ejercicios: Implementar las funciones que faltan */ int Elimina_Elemento(LE *L, int A){ int i,ant; if (L->head == -1){ return -1; } else { i = L->head; if (L->nodo[i].elem == A) { L->head = L->nodo[i].prox; (L->vac->ultimo)++; return 1; } while(i != -1){ if(L->nodo[i].elem==A){ L->nodo[ant].prox=L->nodo[i].prox; L->nodo[i].prox=NULL; (L->vac->ultimo)++; return 1; } else{ ant=i; i=L->nodo[i].prox; } } return -1; } } main() { LE *l; int N,aux_l,x=0; char opc; cout<<"Ingrese el num. max. elem. en la lista\n"; cin>>N; l = (LE *) Inicia_Lista(N); while (1) { cout<<"\n Insertar(i) Eliminar(e) Imprimir(p) Salir(s) "; cin>>opc; if (opc == 'i') { cout<<"\n Ingrese el nuevo número entero "; cin>>x; Inserta_Elemento(l,x); } if (opc == 'e') { printf("\n Ingrese el núm. entero a buscar "); scanf("%d",&x); aux_l = Elimina_Elemento(l,x); if (aux_l == -1) printf("Numero no encontrado\n"); } if (opc == 'p') Imprime_Lista(l); if (opc == 's') { /* l = (LE *) Vacia_Lista(l); */ exit(0); } } }

Implementación (Dinámica)

Por simplicidad los elementos almacenados serán números enteros. Los elementos serán insertados de forma ordenada.
El esquema gráfico abajo muestra el proceso de inserción de un nuevo elemento en una lista encadenada dinámica. el nuevo elemento será insertado entre el elemento actual y el elemento anterior.



Las operaciones ilustradas pueden ser descritas como:
nuevo->prox = actual;
anterior->prox = nuevo;

Especificación:

1. LE *Inicia_Lista()                                 //Crea una nueva lista
2. void Inserta_Elemento(LE *L, int A)    //Inserta un nuevo elemento A en la posición correcta de la lista L
3. int Elimina_Elemento(LE *L, int A)       //Elimina el elemento A de la lista L. Si el elemento no existe o la lista está vacía retorna -1.
4. void Imprime_Lista (LE *L)
5. LE *Vacia_Lista(LE *L)

Código:
#include<iostream.h> #include<conio.h> #include<stdlib.h> typedef struct lista LE; typedef struct nodo_lista NO; struct nodo_lista { int elem; NO *prox; /* guarda la posicion del proximo elemento en la lista */ }; struct lista { NO *head,*pa,*imp; /* guarda la direccion del primer elemento de la lista */ }; LE *Inicia_Lista(void) { LE *temp; if ((temp = (LE *) malloc(sizeof(LE))) != NULL) { temp->head = NULL; return(temp); } else exit(0); } void Inserta_Elemento(LE *L, int A) { NO *aux,*ant,*atu; if ((aux = (NO *) malloc(sizeof(NO))) != NULL) { aux->elem = A; if (L->head == NULL) { aux->prox = NULL; L->head = aux; } else { atu = L->head; ant = NULL; while ((atu != NULL) && (atu->elem <= A)) { ant = atu; atu = atu->prox; } if (ant == NULL) /* insertar en la primera posición de la lista */ { aux->prox = L->head; L->head = aux; } else { aux->prox = ant->prox; ant->prox = aux; } } } else exit(0); return; } int Eliminar_Elemento(LE *L,int A){ NO *aux,*ant,*atu; if ((aux = (NO *) malloc(sizeof(NO))) != NULL) { if(L->head == NULL){ return -1; } else{ atu=L->head; if(atu->elem==A){ L->head = atu-> prox; return 1; } while (atu != NULL) { if(atu->elem==A){ ant->prox=atu->prox; atu->prox=NULL; return 1; } else{ ant=atu; atu=atu->prox; } } return -1; } } } void Invertir_Lista(LE *L){ NO *aux,*ant,*atu; if ((aux = (NO *) malloc(sizeof(NO))) != NULL) { atu = L->head; ant = NULL; while (atu!= NULL) { L->head=atu->prox; atu->prox=ant; ant=atu; atu=L->head; } while (ant != NULL) { cout<<ant->elem<<" "; ant = ant->prox; } } } void InPar_Lista(LE *L){ NO *atu,*par,*impar; if ((par = (NO *) malloc(sizeof(NO))) != NULL) { atu = L->head; par = NULL; impar = NULL; while (atu != NULL) { if(atu->elem%2==0) { if(par==NULL) {L->pa=atu; par=atu; } else{ par->prox=atu; par=atu; }} else { if(impar==NULL) {L->imp=atu; impar=atu; } else{ impar -> prox = atu; impar=atu; }} atu = atu->prox; if(atu==NULL) {if(par!=NULL)par->prox=NULL; if(impar!=NULL)impar->prox=NULL; } } par=L->pa; impar=L->imp; while(par!=NULL) { cout<<par->elem<<" "; par = par->prox; } cout<<endl; while(impar!=NULL) { cout<<impar->elem<<" "; impar = impar->prox; } } } void Imprime_Lista(LE *L){ NO *aux,*atu; int tam=0; if ((aux = (NO *) malloc(sizeof(NO))) != NULL) { atu = L->head; while (atu != NULL) { tam++; cout<<atu->elem<<" "; atu = atu->prox; } cout<<" de tama\xa4o "<<tam; } } /* Ejercicios: Implementar las funciones que faltan */ main() { int aux_l; LE *l; int x=0; char opc; l = (LE *) Inicia_Lista(); while (1) { cout<<"\nInsertar (i) Eliminar (e) Imprimir (p) Invertir (v) Inpar Par (d) Sair s) "; cin>>opc; if (opc == 'i') { cout<<"\n Ingrese el nuevo elemento entero "; cin>>x; Inserta_Elemento(l,x); } if (opc == 'e') { cout<<"\n Ingrese el número entero a buscar "; cin>>x; aux_l = Eliminar_Elemento(l,x); if (aux_l == -1) cout<<"Numero no encontrado\n"; } if(opc=='v') Invertir_Lista(l); if(opc=='d') InPar_Lista(l); if (opc == 'p') Imprime_Lista(l); if (opc == 's') { //l = (LE *) Vacia_Lista(l); exit(0); } } }