/* ------------------------------------------------------------ */ /* IMPLEMENTACION DE FUNCIONES BASICAS UNA LISTA ENCADENADA */ /* ------------------------------------------------------------ */ #include #include typedef enum {FALSE=0,TRUE=1} boolean; /* Tipo de dato que almacena cada elemento de la lista */ typedef int TipoDato; /* Estructura autoreferenciada */ struct SEle{ TipoDato valor; struct SEle *sig; }; typedef struct SEle Elemento; /* Variable global Puntero de Inicio de la Lista */ Elemento *Base; /* ------------------------------------------------- */ /* Funciones de Manejo de UNA lista encadenada */ /* ------------------------------------------------- */ void Crear (void); boolean Vacia (void); TipoDato Primero (void); TipoDato Ultimo (void); boolean PonAlFinal (TipoDato Dato); boolean PonAlPrincipio (TipoDato Dato); boolean BorrarAlFinal (void); boolean BorrarAlPrincipio (void); boolean InsertarEnOrden (TipoDato Dato ); boolean BorrarElemento (TipoDato Dato ); void VerLista (void); void VaciarLista (void); /*----------------------------------------------------------------*/ /* Inicializa el puntero de la Lista */ void Crear(void) { Base = NULL; } /*----------------------------------------------------------------*/ /* Indica si esta o no vacia */ boolean Vacia(void) { return ( Base == NULL)?TRUE:FALSE; } /*----------------------------------------------------------------*/ /* evuelve el valor almacenado en el primer elemento de la Lista */ TipoDato Primero(void) { return Base->valor; } /*----------------------------------------------------------------*/ /* Devuelve el valor almacenado en el último elemento de la Lista */ TipoDato Ultimo(void) { Elemento *paux; paux = Base; while ( paux->sig != NULL ) { paux = paux->sig; } return paux->valor; } /*----------------------------------------------------------------*/ /* Crea un nuevo elemento al principio de la Lista */ boolean PonAlPrincipio ( TipoDato Dato) { Elemento *pnuevo; boolean resu; resu = FALSE; pnuevo = (Elemento *) malloc( sizeof(Elemento) ); if ( pnuevo != NULL ) { pnuevo->sig = Base; pnuevo->valor = Dato; Base = pnuevo; resu = TRUE; } return resu; } /*----------------------------------------------------------------*/ /* Crea un nuevo elemento al final de la lista */ boolean PonAlFinal ( TipoDato Dato) { Elemento *paux,*pnuevo; /* Creo el elemento nuevo */ pnuevo = (Elemento *) malloc( sizeof(Elemento)); if ( pnuevo == NULL ) { /* Si no pude crear el elemento termina la función */ return FALSE; } /* Relleno el nuevo elemento */ pnuevo->valor = Dato; pnuevo->sig = NULL; /* Va a ser el último */ /* Si no está vacia recorro la lista hasta alcanzar el último elemento */ if ( Base != NULL ) { paux = Base; while ( paux->sig != NULL ) { paux = paux->sig; } /* El puntero siguiente del último elemento señala al nuevo */ paux->sig = pnuevo; } else { /* La lista está vacia */ /* Base señala al nuevo elemento */ Base = pnuevo; } return TRUE; } /*----------------------------------------------------------------*/ /* Elimina el primer elemento de la lista */ boolean BorrarAlPrincipio (void) { Elemento *paux; paux = Base; if ( !Vacia() ) { /* Señala al siguiente y libero memoria */ Base = Base->sig; free(paux); return TRUE; } return FALSE; } /*----------------------------------------------------------------*/ /* Borra el último elemento de la lista */ boolean BorrarAlFinal(void) { Elemento *paux1,*paux2; if ( Vacia() ) { return FALSE; } else { /* Si solo hay uno */ if ( Base->sig == NULL ) { free(Base); Base = NULL; } else { paux1 = Base; /* Primer elemento */ paux2 = Base->sig; /* Segundo elemento */ while ( paux2->sig != NULL ) { paux1 = paux2; paux2 = paux2->sig; } /* Pon el puntero siguiente del elemento anterior a NULL */ paux1->sig = NULL; /* Libero el espacio del último elemento */ free(paux2); } return TRUE; } } /*----------------------------------------------------------------*/ /* Coloca un elemento en la lista insertando en orden creciente */ boolean InsertarEnOrden( TipoDato Dato ) { Elemento *paux1, *paux2, *pnuevo; pnuevo = (Elemento *) malloc (sizeof (Elemento) ); if ( pnuevo == NULL ) { return FALSE; } pnuevo->valor = Dato; /* Si está vacia */ if ( Base == NULL ) { Base = pnuevo; pnuevo->sig = NULL; } else { /* Si está antes del primero */ if ( Base->valor > pnuevo->valor ) { pnuevo->sig = Base; Base = pnuevo; } else { paux1 = Base; /* Primero */ paux2 = Base->sig; /* Segundo */ while ( paux2 != NULL ) { if ( paux2->valor > pnuevo->valor ) { break; } paux1 = paux2; paux2 = paux2->sig; } // Inserto paux1->sig = pnuevo; pnuevo->sig = paux2; } } return TRUE; } /*----------------------------------------------------------------*/ /* Borra un elemento determinado */ boolean BorrarElemento ( TipoDato Dato ) { Elemento *paux1,*paux2; /* Si no hay elementos */ if ( Base == NULL ) { return FALSE; } /* Si es el primero */ if ( Base->valor == Dato ) { paux1 = Base; Base = Base->sig; free(paux1); } else { /* Busco el elemento */ paux1 = Base; paux2 = Base->sig; while ( paux2 != NULL ) { if ( paux2->valor == Dato ) { break; } paux1 = paux2; paux2 = paux2->sig; } if ( paux2 == NULL ) { /* No está */ return FALSE; } else { paux1->sig = paux2->sig; free(paux2); } } return TRUE; } /*----------------------------------------------------------------*/ /* Muestra el contenido de la lista */ void VerLista ( void ) { Elemento *paux; printf("\n LISTA: ["); paux = Base; while ( paux != NULL ) { printf("->%d ",paux->valor); paux = paux->sig; } printf("]\n"); } /*----------------------------------------------------------------*/ /* Borrar todos los elemento de la lista */ void VaciarLista(void) { Elemento *paux; while ( Base != NULL ) { paux = Base; Base = Base->sig; free(paux); } } /*----------------------------------------------------------------*/ /*----------------------------------------------------------------*/ /* Prueba de Funciones */ int main() { Crear(); if ( Vacia () ) puts ("Lista vacia"); PonAlPrincipio(30); PonAlPrincipio(20); PonAlPrincipio(10); if (! Vacia () ) VerLista () ; getchar(); PonAlFinal(100); PonAlFinal(200); PonAlFinal(300); VerLista(); getchar(); printf(" El primero es :%d \n", Primero()); printf(" El último es :%d \n", Ultimo() ); BorrarAlPrincipio(); BorrarAlFinal(); VerLista(); printf(" El primero es :%d \n", Primero()); printf(" El último es :%d \n", Ultimo() ); getchar(); InsertarEnOrden(5); InsertarEnOrden(15); InsertarEnOrden(150); InsertarEnOrden(1500); VerLista(); getchar(); if ( !BorrarElemento(88) ) puts("No puedo borrar el elemento 88 "); BorrarElemento(200); BorrarElemento(20); VerLista(); getchar(); VaciarLista(); VerLista(); getchar(); }