/* ------------------------------------------------------------ */ /* IMPLEMENTACION DE FUNCIONES BASICAS SOBRE LISTAS ENCADENADAS */ /* ------------------------------------------------------------ */ #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; /* ----------------------------------------------------- */ /* Funciones de Manejo de Múltiples Listas encadenadas */ /* ----------------------------------------------------- */ /* Cuando podemos modificar la posición inicial de la lista señalada por Base, debemos pasar un puntero a Base, PBase == & Base O lo que es lo mismo *PBase == Base */ /* ------------------------------------------------------ */ void Crear (Elemento **PBase); boolean Vacia (Elemento *Base); TipoDato Primero (Elemento *Base); TipoDato Ultimo (Elemento *Base); boolean PonAlFinal (Elemento **PBase, TipoDato Dato); boolean PonAlPrincipio (Elemento **PBase, TipoDato Dato); boolean BorrarAlFinal (Elemento **PBase); boolean BorrarAlPrincipio (Elemento **PBase); boolean InsertarEnOrden (Elemento **PBase, TipoDato Dato ); boolean BorrarElemento (Elemento **PBase, TipoDato Dato ); void VerLista (Elemento *Base ); void VaciarLista (Elemento **PBase ); /*----------------------------------------------------------------*/ /* Inicializa el puntero de la Lista */ void Crear(Elemento **PBase) { *PBase = NULL; } /*----------------------------------------------------------------*/ /* Indica si esta o no vacia */ boolean Vacia(Elemento *Base) { return ( Base == NULL)?TRUE:FALSE; } /*----------------------------------------------------------------*/ /* evuelve el valor almacenado en el primer elemento de la Lista */ TipoDato Primero(Elemento *Base) { return Base->valor; } /*----------------------------------------------------------------*/ /* Devuelve el valor almacenado en el último elemento de la Lista */ TipoDato Ultimo(Elemento *Base) { 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 (Elemento **PBase,TipoDato Dato) { Elemento *pnuevo; boolean resu; resu = FALSE; pnuevo = malloc( sizeof(Elemento) ); if ( pnuevo != NULL ) { pnuevo->sig = *PBase; pnuevo->valor = Dato; *PBase = pnuevo; resu = TRUE; } return resu; } /*----------------------------------------------------------------*/ /* Crea un nuevo elemento al final de la lista */ boolean PonAlFinal (Elemento **PBase, TipoDato Dato) { Elemento *paux,*pnuevo; /* Creo el elemento nuevo */ pnuevo = malloc( sizeof(Elemento)); if ( pnuevo == NULL ) { /* Si 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 ( *PBase != NULL ) { paux = *PBase; 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 */ *PBase = pnuevo; } return TRUE; } /*----------------------------------------------------------------*/ /* Elimina el primer elemento de la lista */ boolean BorrarAlPrincipio (Elemento **PBase ) { Elemento *paux; paux = *PBase; if ( !Vacia(*PBase) ) { /* Señala al siguiente y libero memoria */ *PBase = (*PBase)->sig; free(paux); return TRUE; } return FALSE; } /*----------------------------------------------------------------*/ /* Borra el último elemento de la lista */ boolean BorrarAlFinal(Elemento **PBase) { Elemento *paux1,*paux2; if ( Vacia(*PBase) ) { return FALSE; } else { /* Si solo hay uno */ if ( (*PBase)->sig == NULL ) { free(*PBase); *PBase = NULL; } else { paux1 = *PBase; /* Primer elemento */ paux2 = (*PBase)->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(Elemento **PBase, TipoDato Dato ) { Elemento *paux1, *paux2, *pnuevo; pnuevo = malloc (sizeof (Elemento) ); if ( pnuevo == NULL ) { return FALSE; } pnuevo->valor = Dato; /* Si está vacia */ if ( *PBase == NULL ) { *PBase = pnuevo; pnuevo->sig = NULL; } else { /* Si está antes del primero */ if ( (*PBase)->valor > pnuevo->valor ) { pnuevo->sig = *PBase; *PBase = pnuevo; } else { paux1 = *PBase; /* Primero */ paux2 = (*PBase)->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 (Elemento **PBase, TipoDato Dato ) { Elemento *paux1,*paux2; /* Si no hay elementos */ if ( *PBase == NULL ) { return FALSE; } /* Si es el primero */ if ( (*PBase)->valor == Dato ) { paux1 = *PBase; *PBase = (*PBase)->sig; free(paux1); } else { /* Busco el elemento */ paux1 = *PBase; paux2 = (*PBase)->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 (Elemento *Base ) { 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 (Elemento **PBase ) { Elemento *paux; while ( *PBase != NULL ) { paux = *PBase; *PBase = (*PBase)->sig; free(paux); } } /*----------------------------------------------------------------*/ /*----------------------------------------------------------------*/ /* Prueba de Funciones */ void main() { Elemento *Lista1, *Lista2; Crear(&Lista1); Crear(&Lista2); if ( Vacia (Lista1) ) puts ("Lista1 vacia"); if ( Vacia (Lista2) ) puts ("Lista2 vacia"); PonAlPrincipio(&Lista1,100); PonAlPrincipio(&Lista1,10); PonAlPrincipio(&Lista1,1); PonAlPrincipio(&Lista2,200); PonAlPrincipio(&Lista2,20); PonAlPrincipio(&Lista2,2); if (! Vacia (Lista1) ) VerLista (Lista1) ; if (! Vacia (Lista2) ) VerLista (Lista2) ; getchar(); PonAlFinal(&Lista1,1000); PonAlFinal(&Lista2,2000); VerLista(Lista1); VerLista(Lista2); getchar(); printf(" El primero de la lista 1 es :%d \n", Primero(Lista1)); printf(" El primero de la lista 2 es :%d \n", Primero(Lista2)); printf(" El último de la lista 1 es :%d \n", Ultimo(Lista1) ); printf(" El último de la lista 2 es :%d \n", Ultimo(Lista2) ); BorrarAlPrincipio(&Lista1); BorrarAlFinal(&Lista1); VerLista(Lista1); BorrarAlPrincipio(&Lista2); BorrarAlFinal(&Lista2); VerLista(Lista2); getchar(); InsertarEnOrden(&Lista1,5); InsertarEnOrden(&Lista2,2); InsertarEnOrden(&Lista1,110); InsertarEnOrden(&Lista2,220); VerLista(Lista1); VerLista(Lista2); getchar(); if ( !BorrarElemento(&Lista1,88) ) puts("No puedo borrar el elemento 88 de lista 1"); BorrarElemento(&Lista1,100); BorrarElemento(&Lista2,200); VerLista(Lista1); VerLista(Lista2); getchar(); VaciarLista(&Lista1); VerLista(Lista1); VaciarLista(&Lista2); VerLista(Lista2); getchar(); }