Listas doblemente enlazadas C++ UP

Presentacion de listas doblemente enlazadas por los estudiantes de la Universidad de Panama, Comercio electronico.

1. Estudiantes: Miguel Gómez Osvaldo Herrera Bryan Ruiz Sander Peguero Docente: Jenny Ríos Tema: Listas doblemente Enlazadas Universidad de Panamá Facultad de Informática Electrónica y comunicación Estructura de Datos

2. LISTAS DOBLEMENTE ENLAZADAS Las listas doblemente enlazadas son estructuras de datos semejantes a las Listas Enlazadas Simples. La asignación de memoria es hecha al momento de la ejecución. Una lista doblemente enlazada es una lista lineal en la que cada nodo tiene dos enlaces, uno al nodo siguiente, y otro al anterior. El nodo típico es el mismo que para construir las listas que hemos visto, salvo que tienen otro puntero al nodo anterior: struct nodo { int dato; struct nodo *siguiente; struct nodo *anterior; }; DEFINICION:

3. LISTAS DOBLEMENTE ENLAZADAS OPERACIONES SOBRE LA LISTA DOBLEMENTE ENLAZADA: A. Declaracion de tipo, para manejar listas doblemente enlazadas B. Inserción de un elemento en la lista 1. Inserción en una lista vacía 2 . Inserción al inicio de la lista 3. Inserción al final de la lista 4. Inserción antes de un elemento de la lista 5. Inserción después de un elemento de la lista C. Eliminación de un elemento de la lista 1. Eliminación en la posición 1 en una lista con un solo elemento 2. Eliminación en la posición 1 en una lista con varios elementos 3. Eliminación en la ultima posición (el ultimo elemento) 4. Eliminación en otra parte de la lista en cierta posición D. Visualización de la lista E. Destrucción de la lista

4. LISTAS DOBLEMENTE ENLAZADAS INSERCION DE UN ELEMENTO EN LA LISTA: INSERCION EN UNA LISTA VACIA Modelo de la función: int ins_en_lista_vacia ( dl_Lista *lista, char *dato); Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además el puntero que define la lista, que valdrá NULL: El proceso es muy simple, bastará con que: lista apunta a nodo. lista->siguiente y lista->anterior apunten a null .

5. LISTAS DOBLEMENTE ENLAZADAS INSERCION DE UN ELEMENTO EN LA LISTA: INSERCION AL INICIO DE LA LISTA Partimos de una lista no vacía. Para simplificar, consideraremos que lista apunta al primer elemento de la lista doblemente enlazada: Insertar en primera posición El proceso es el siguiente: nodo->siguiente debe apuntar a Lista. nodo->anterior apuntará a Lista->anterior. Lista->anterior debe apuntar a nodo. Nodo insertado en primera posición Recuerda que Lista no tiene por qué apuntar a ningún miembro concreto de una lista doblemente enlazada, cualquier miembro es igualmente válido como referencia.

6. LISTAS DOBLEMENTE ENLAZADAS #include<iostream> #define Ascendente 1 #define Descendente using namespace std; //************************** NODO *********************************// typedef struct Nodo { int dato ; struct Nodo * sgt ; struct Nodo *ant; } TNodo ; //*****************************************************************//

7. LISTAS DOBLEMENTE ENLAZADAS //************************ LISTA **********************************// typedef struct LE { TNodo * inicio ; }TLE; //*****************************************************************// //************************* CREA NODO *****************************// TNodo * crearNodo (int x) { TNodo * nodo = ( TNodo *)malloc( sizeof ( TNodo )); nodo -> dato = x; nodo -> sgt = NULL; nodo ->ant = NULL;

8. LISTAS DOBLEMENTE ENLAZADAS return nodo ; } //*****************************************************************// //************************ CREA LISTA *****************************// TLE * crearLista () { TLE * lista = (TLE*)malloc( sizeof (TLE)); lista -> inicio = NULL; return lista ; } //*****************************************************************//

9. LISTAS DOBLEMENTE ENLAZADAS //************************ INSERTAR *******************************// void Insertar (TLE * lista , int x) { TNodo * nodo = crearNodo (x); TNodo *p=NULL; if( lista -> inicio == NULL) { lista -> inicio = nodo ; nodo ->ant==NULL; } else { p = lista -> inicio ; while(p-> sgt != NULL)

10. LISTAS DOBLEMENTE ENLAZADAS p = p-> sgt ; p-> sgt = nodo ; nodo ->ant=p; } } //*****************************************************************// //*********************** ELIMINAR ********************************// void Eliminar (TLE * lista , int dato ) { TNodo *p = lista -> inicio ; TNodo *ant = NULL;

11. LISTAS DOBLEMENTE ENLAZADAS { if(p-> dato == dato ) encontrado =1; else { ant = p; p = p-> sgt ; } } if(p!=NULL) { if (ant==NULL)

12. LISTAS DOBLEMENTE ENLAZADAS lista -> inicio =( lista -> inicio )-> sgt ; else { ant-> sgt =p-> sgt ; p-> sgt ->ant=ant; } free(p); } } //*****************************************************************// //************************ BORRAR *********************************// void Borrar (TLE * lista ) { TNodo *p = NULL; while( lista -> inicio != NULL)

13. LISTAS DOBLEMENTE ENLAZADAS { p = lista->inicio; lista->inicio = p->sgt; p->sgt->ant==NULL; free(p); } } //*****************************************************************// //********************** REPORTAR ********************************// void Reportar(TLE *lista , int Orden ) {

14. LISTAS DOBLEMENTE ENLAZADAS TNodo *p = lista->inicio; if( Orden == Ascendente) { cout<<" lista -> "; while(p!=NULL) { cout<<p->dato<<" <-> "; p = p->sgt; } cout<<"NULL";

15. LISTAS DOBLEMENTE ENLAZADAS } else { cout <<" NULL "; while(p-> sgt !=NULL) p = p-> sgt ; while(p!=NULL) { cout <<" <-> "<<p-> dato ; p = p->ant; } cout <<" <- Lista";

16. LISTAS DOBLEMENTE ENLAZADAS } cout<<endl<<endl; system("pause"); cout<<endl; } //*****************************************************************// //*********************** ESTA VACIA ******************************// void Vacia(TLE *lista) { if(lista->inicio == NULL) cout<<endl<<" - La Lista Esta Vacia !!! "<<endl; else

17. LISTAS DOBLEMENTE ENLAZADAS cout<<endl<<" - La Lista No Esta Vacia !!! "; cout<<endl<<endl; system("pause"); cout<<endl; } //*****************************************************************// //*****************************************************************// //*****************************************************************// int main() { system("color f3"); TLE *L=crearLista();

18. LISTAS DOBLEMENTE ENLAZADAS int N,E,i =0; int opcion ; cout << endl <<"\t----------------------------------------------------------------- "; cout << endl <<"\t| LISTAS ENLAZADAS DOBLES |"; cout << endl <<"\t| - [ UNIVERSIDAD NACIONAL DE PANAMA ] - |"; cout << endl <<"\t----------------------------------------------------------------- "<< endl ; cout << endl << endl ; cout <<" MENU LISTAS DOBLES"<< endl ; cout <<" ------------------ "; while(1) { cout << endl << endl ; cout <<" -------------------------------- "<< endl ; cout <<" | 1. Insertar |"<< endl ; cout <<" | 2. Eliminar Elemento |"<< endl ; cout <<" | 3. Borrar Lista |"<< endl ; cout <<" | 4. Mostrar Lista Ascendente |"<< endl ; cout <<" | 5. Mostrar Lista Descendente |"<< endl ; cout <<" | 6. Lista Esta Vacia |"<< endl ; cout <<" | 7. Salir |"<< endl ; cout <<" --------------------------------"<< endl ;

19. LISTAS DOBLEMENTE ENLAZADAS do { cout << endl << endl <<" -> Ingrese Opcion "<< endl ; cout <<" ---------------> "; cin >> opcion ; } while( opcion < 1 || opcion > 7); switch( opcion ) { case 1: i ++; cout<<endl<<" - Ingrese ["<<i<<"] elemento: "; cin>>N; Insertar(L,N); break;

20. LISTAS DOBLEMENTE ENLAZADAS case 2: cout << endl <<" - Ingrese Elemento a Eliminar : "; cin >>E; Eliminar (L,E); break; case 3: Borrar (L); cout << endl << endl ; cout <<" - Se Elimino La Lista Correctamente ... "; cout << endl << endl ; system("pause"); cout << endl ; break;

21. LISTAS DOBLEMENTE ENLAZADAS case 4: cout << endl ; Reportar ( L,Ascendente ); cout << endl ; break; case 5: cout << endl ; Reportar ( L,Descendente ); cout << endl ; break;

22. LISTAS DOBLEMENTE ENLAZADAS case 6: Vacia (L); break; case 7: exit(1); default: cout << endl << endl ; cout <<" La Opcion No es Valida !!!!!!!!!:"; } } cout << endl << endl ; system("PAUSE"); return EXIT_SUCCESS; } //*****************************************************************//