Implementación de Listas Enlazadas Simples en C
Las listas enlazadas son una estructura de datos fundamental en informática. Permiten almacenar una colección de elementos de forma dinámica, donde cada elemento apunta al siguiente elemento de la lista. A continuación, se presenta un ejemplo de implementación de listas enlazadas simples en C.
«`c #include #include
typedef struct _nodo { int valor; struct _nodo *siguiente; } tipoNodo;
typedef tipoNodo *pNodo; typedef tipoNodo *Lista;
/* Funciones con listas: */ void Insertar(Lista *l, int v); void Borrar(Lista *l, int v); int ListaVacia(Lista l); void BorrarLista(Lista *l); void MostrarLista(Lista l);
int main() { Lista lista = NULL; pNodo p;
Insertar(&lista, 20); Insertar(&lista, 10); Insertar(&lista, 40); Insertar(&lista, 30);
MostrarLista(lista);
Borrar(&lista, 10); Borrar(&lista, 15); Borrar(&lista, 45); Borrar(&lista, 30); Borrar(&lista, 40);
MostrarLista(lista);
BorrarLista(&lista);
system(«PAUSE»); return 0; }
void Insertar(Lista *lista, int v) { pNodo nuevo, anterior;
/* Crear un nodo nuevo */ nuevo = (pNodo)malloc(sizeof(tipoNodo)); nuevo->valor = v;
/* Si la lista está vacía */ if (ListaVacia(*lista) || (*lista)->valor > v) { /* Añadimos la lista a continuación del nuevo nodo */ nuevo->siguiente = *lista; /* Ahora, el comienzo de nuestra lista es en nuevo nodo */ *lista = nuevo; } else { /* Buscar el nodo de valor menor a v */ anterior = *lista; /* Avanzamos hasta el último elemento o hasta que el siguiente tenga un valor mayor que v */ while (anterior->siguiente && anterior->siguiente->valor <= v) { anterior = anterior->siguiente; } /* Insertamos el nuevo nodo después del nodo anterior */ nuevo->siguiente = anterior->siguiente; anterior->siguiente = nuevo; } }
void Borrar(Lista *lista, int v) { pNodo anterior, nodo;
nodo = *lista; anterior = NULL; while (nodo && nodo->valor < v) { anterior = nodo; nodo = nodo->siguiente; } if (!nodo || nodo->valor != v) return; else { /* Borrar el nodo */ if (!anterior) /* Primer elemento */ *lista = nodo->siguiente; else /* un elemento cualquiera */ anterior->siguiente = nodo->siguiente; free(nodo); } }
int ListaVacia(Lista lista) { return (lista == NULL); }
void BorrarLista(Lista *lista) { pNodo nodo;
while (*lista) { nodo = *lista; *lista = nodo->siguiente; free(nodo); } }
void MostrarLista(Lista lista) { pNodo nodo = lista;
if (ListaVacia(lista)) printf(«Lista vacía\n»); else { while (nodo) { printf(«%d -> «, nodo->valor); nodo = nodo->siguiente; } printf(«\n»); } } «`
Implementación de Listas Doblemente Enlazadas en C
Las listas doblemente enlazadas son una variante de las listas enlazadas simples, donde cada nodo apunta tanto al siguiente elemento como al anterior. Esto permite recorrer la lista en ambas direcciones. A continuación, se presenta un ejemplo de implementación de listas doblemente enlazadas en C.
«`c #include #include
#define ASCENDENTE 1 #define DESCENDENTE 0
typedef struct _nodo { int valor; struct _nodo *siguiente; struct _nodo *anterior; } tipoNodo;
typedef tipoNodo *pNodo; typedef tipoNodo *Lista;
/* Funciones con listas: */ void Insertar(Lista *l, int v); void Borrar(Lista *l, int v); void BorrarLista(Lista *l); void MostrarLista(Lista l, int orden);
int main() { Lista lista = NULL; pNodo p;
Insertar(&lista, 20); Insertar(&lista, 10); Insertar(&lista, 40); Insertar(&lista, 30);
MostrarLista(lista, ASCENDENTE); MostrarLista(lista, DESCENDENTE);
Borrar(&lista, 10); Borrar(&lista, 15); Borrar(&lista, 45); Borrar(&lista, 30);
MostrarLista(lista, ASCENDENTE); MostrarLista(lista, DESCENDENTE);
BorrarLista(&lista);
system(«PAUSE»); return 0; }
void Insertar(Lista *lista, int v) { pNodo nuevo, actual;
/* Crear un nodo nuevo */ nuevo = (pNodo)malloc(sizeof(tipoNodo)); nuevo->valor = v;
/* Colocamos actual en la primera posición de la lista */ actual = *lista; if (actual) while (actual->anterior) actual = actual->anterior; /* Si la lista está vacía o el primer miembro es mayor que el nuevo*/ if (!actual || actual->valor > v) { /* Añadimos la lista a continuación del nuevo nodo */ nuevo->siguiente = actual; nuevo->anterior = NULL; if (actual) actual->anterior = nuevo; if (!*lista) *lista = nuevo; } else { /* Avanzamos hasta el último elemento o hasta que el siguiente tenga un valor mayor que v */ while (actual->siguiente && actual->siguiente->valor <= v) { actual = actual->siguiente; } /* Insertamos el nuevo nodo después del nodo anterior */ nuevo->siguiente = actual->siguiente; actual->siguiente = nuevo; nuevo->anterior = actual; if (nuevo->siguiente) nuevo->siguiente->anterior = nuevo; } }
void Borrar(Lista *lista, int v) { pNodo nodo;
/* Buscar el nodo de valor v */ nodo = *lista; while (nodo && nodo->valor < v) nodo = nodo->siguiente; while (nodo && nodo->valor > v) nodo = nodo->anterior;
/* El valor v no está en la lista */ if (!nodo || nodo->valor != v) return;
/* Borrar el nodo */ /* Si lista apunta al nodo que queremos borrar, apuntar a otro */ if (nodo == *lista) if (nodo->anterior) *lista = nodo->anterior; else *lista = nodo->siguiente;
if (nodo->anterior) /* no es el primer elemento */ nodo->anterior->siguiente = nodo->siguiente; if (nodo->siguiente) /* no es el último nodo */ nodo->siguiente->anterior = nodo->anterior; free(nodo); }
void BorrarLista(Lista *lista) { pNodo nodo, actual;
actual = *lista; while (actual->anterior) actual = actual->anterior;
while (actual) { nodo = actual; actual = actual->siguiente; free(nodo); } *lista = NULL; }
void MostrarLista(Lista lista, int orden) { pNodo nodo = lista;
if (!lista) { printf(«Lista vacía»); return; }
if (orden == ASCENDENTE) { while (nodo->anterior) nodo = nodo->anterior; printf(«Orden ascendente: «); while (nodo) { printf(«%d -> «, nodo->valor); nodo = nodo->siguiente; } } else { while (nodo->siguiente) nodo = nodo->siguiente; printf(«Orden descendente: «); while (nodo) { printf(«%d -> «, nodo->valor); nodo = nodo->anterior; } }
printf(«\n»); } «`
Implementación de una Pila en C con Registros de Empleados
Una pila es una estructura de datos que sigue el principio LIFO (Last In, First Out), es decir, el último elemento en entrar es el primero en salir. A continuación, se presenta un ejemplo de implementación de una pila en C que almacena registros de empleados, incluyendo nombre, sueldo y número de hijos.
«`c #include #include #include
typedef struct nodo { char nombre[30]; float sueldo; int nhijos; struct nodo *sig; } tipoNodo;
struct datos { char nom[30]; float suel; int hijos; } auxi;
typedef tipoNodo *pNodo; typedef tipoNodo *Pila;
void push(char n[30], float s, int h, Pila *pila) { pNodo nuevo; nuevo = (pNodo)malloc(sizeof(tipoNodo)); strcpy(nuevo->nombre, n); nuevo->sueldo = s; nuevo->nhijos = h; nuevo->sig = *pila; *pila = nuevo; }
struct datos pop(Pila *pila) { pNodo nodo; nodo = *pila; if (!nodo) { return auxi; } else { *pila = nodo->sig; strcpy(auxi.nom, nodo->nombre); auxi.suel = nodo->sueldo; auxi.hijos = nodo->nhijos; free(nodo); return auxi; } }
int main() { Pila *pila2 = NULL; // Inicializar la pila a NULL int r, i, hij; struct datos ret; char nom[30]; float sue; printf(«Cuantos trabajadores desea ingresar?\n»); scanf(«%d», &r); for (i = 0; i < r; i++) { // Corregir la condición del bucle printf(«\nIngrese nombre: «); fflush(stdin); gets(nom); printf(«\nIngrese sueldo: «); scanf(«%f», &sue); printf(«\nIngrese cantidad de hijos: «); scanf(«%d», &hij); push(nom, sue, hij, pila2); } printf(«Trabajadores con dos o mas hijos: \n»); for (i = 0; i < r; i++) { // Corregir la condición del bucle ret = pop(pila2); if (ret.hijos >= 2) { printf(«\nNombre: %s «, ret.nom); printf(«\nSueldo: %.2f «, ret.suel); // Mostrar el sueldo con dos decimales printf(«\nCantidad de Hijos: %d \n\n\n», ret.hijos); } } system(«PAUSE»); return 0; } «`
En este ejemplo, la función push agrega un nuevo empleado a la pila y la función pop extrae el último empleado agregado. El programa principal solicita al usuario la cantidad de trabajadores a ingresar y luego muestra los datos de los trabajadores con dos o más hijos.