Os dejo el enunciado y mi solución que, como tantas veces he dicho, es una de las posibles pues siempre hay varias.
Una lista doblemente enlazada es una lista enlazada en la que cada nodo tiene dos punteros, uno que apunta al siguiente nodo de la lista y otro que apunta al nodo anterior. Además, las listas doblemente enlazadas tienen una referencia a la cabeza de la lista y a la cola (ver figura).
a) Implementar en el archivo Lista.h el tipo T_Lista que representa una lista doblemente enlazada, donde cada nodo almacena el valor de un número entero.
NOTA: T_Lista debe tener referencias a la cabeza y a la cola de la lista.
b) Implementar en el archivo Lista.c las operaciones especificadas en el archivo Lista.h:
void crear(T_Lista *lista)
Crea una lista doblemente enlazada vacía.
void destruir(T_Lista *lista)
Destruye completamente la estructura de la lista.
void insertar(T_Lista *lista, int valor)
Inserta un nodo con el valor especificado como parámetro de forma ordenada
ascendente, para ello se deberá recorrer la lista desde la cabeza y desde la cola con
punteros auxiliares, insertándolo en el sitio correcto desde el primer puntero que lo
encuentre.
int eliminar(T_Lista *lista, int valor)
Elimina un nodo con el valor especificado como parámetro, para ello se deberá recorrer
la lista desde la cabeza y desde la cola con punteros auxiliares, eliminándolo desde el
primer puntero que lo encuentre. En caso de que exista más de un nodo con ese valor se
eliminará el primero encontrado, si se encuentran a la vez por la cabeza o por la cola se
eliminará solamente uno de los dos. Si no existe en la lista el valor no se eliminará nada.
El valor devuelto por la función indica si se ha eliminado o no el valor.
void imprimir(T_Lista lista, int direccion)
Escribe por pantalla la lista ordenada de forma ascendente si direccion == 0 y de
forma descendente en caso contrario.
Lista.h
#ifndef LISTA_H_
#define LISTA_H_
typedef struct Lista T_Lista;
struct Lista {
struct TNodo * cabeza;
struct TNodo * cola;
};
struct TNodo{
int valor;
struct TNodo* sig;
struct TNodo* ant;
};
void crear(T_Lista *lista);//Crea una lista doblemente enlazada vacía.
void destruir(T_Lista *lista); //Destruye completamente la estructura de la lista.
void insertar(T_Lista *lista, int valor);
int eliminar(T_Lista *lista, int valor);
void imprimir(T_Lista lista, int direccion);
#endif /* LISTA_H_ */
Lista.c
#include <stdio.h>
#include <stdlib.h>
#include "Lista.h"
void crear(T_Lista *lista){
//Crea una lista doblemente enlazada vacía.
(*lista).cabeza = NULL;
(*lista).cola = NULL;
}
void destruir(T_Lista *lista){
//Destruye completamente la estructura de la lista.
struct TNodo* auxiliar;
while((*lista).cabeza != NULL){
auxiliar = (*lista).cabeza ->sig;
free((*lista).cabeza);
(*lista).cabeza = auxiliar;
}
(*lista).cola = NULL;
}
void insertar(T_Lista *lista, int valor){
int insertado = 0;
struct TNodo* auxcab = (*lista).cabeza;
struct TNodo* auxcola = (*lista).cola;
struct TNodo * nuevo = malloc(sizeof(struct TNodo));
nuevo ->valor = valor;
if((*lista).cabeza == NULL && (*lista).cola == NULL){
nuevo -> sig = NULL;
nuevo -> ant = NULL;
(*lista).cabeza = nuevo;
(*lista).cola = nuevo;
insertado = 1;
}
while(!insertado){
if(auxcab != NULL){
if(auxcab ->valor < valor){
auxcab = auxcab -> sig;
}else{ // lo tengo que insertar
if(auxcab ->ant == NULL){ // es el primero
nuevo -> sig = auxcab;
nuevo -> ant = NULL;
auxcab -> ant = nuevo;
(*lista).cabeza = nuevo;
}else{
nuevo -> sig = auxcab;
nuevo -> ant = auxcab->ant;
auxcab->ant -> sig =nuevo;
auxcab->ant = nuevo;
}
insertado = 1;
}
}
if(auxcola != NULL && !insertado){
if(auxcola ->valor > valor){
auxcola = auxcola -> ant;
}else{ // lo tengo que insertar
if(auxcola-> sig == NULL){ // es el ultimo
auxcola -> sig = nuevo;
nuevo -> sig = NULL;
nuevo -> ant = auxcola;
(*lista).cola = nuevo;
}else{
nuevo -> sig = auxcola -> sig;
auxcola -> sig -> ant = nuevo;
nuevo -> ant = auxcola;
auxcola -> sig = nuevo;
}
insertado = 1;
}
}
}
}
int eliminar(T_Lista *lista, int valor){
struct TNodo* auxcab = (*lista).cabeza;
struct TNodo* auxcola = (*lista).cola;
struct TNodo * aux;
while(auxcab != NULL || auxcola != NULL){
if(auxcab != NULL && auxcab -> valor == valor){ // lo tengo que eliminar
if(auxcab -> ant == NULL){ // es el primero
aux = (*lista).cabeza -> sig;
free((*lista).cabeza);
(*lista).cabeza = aux;
(*lista).cabeza -> ant = NULL;
if(aux == NULL){
(*lista).cola = NULL;
}
}else{
auxcab -> ant -> sig = auxcab -> sig;
auxcab -> sig -> ant = auxcab -> ant;
free(auxcab);
}
return 1;
}else if(auxcola != NULL && auxcola -> valor == valor){
if(auxcola -> sig == NULL){ // es el ultimo
aux = (*lista).cola -> ant;
free((*lista).cola);
(*lista).cola = aux;
(*lista).cola -> sig = NULL;
}else{
auxcola -> ant -> sig = auxcola -> sig;
auxcola -> sig -> ant = auxcola -> ant;
free(auxcola);
}
return 1;
}else{
if(auxcola != NULL) auxcola = auxcola -> ant;
if(auxcab != NULL)auxcab = auxcab -> sig;
}
}
return 0;
}
void imprimir(T_Lista lista, int direccion){
/*Escribe por pantalla la lista ordenada de forma ascendente si direccion == 0
y de forma descendente en caso contrario. */
struct TNodo * aux;
if(direccion == 0){
aux = lista.cabeza;
while(aux != NULL){
printf("%d, ", aux ->valor);
aux = aux -> sig;
}
printf("\n");
}else{
aux = lista.cola;
while(aux != NULL){
printf("%d, ", aux ->valor);
aux = aux ->ant;
}
printf("\n");
}
}
int main(void) {
T_Lista lista;
crear(&lista);
insertar(&lista, 1);
insertar(&lista, 2);
insertar(&lista, -1);
insertar(&lista, 0);
imprimir(lista, 0);
imprimir(lista, 1);
eliminar(&lista, 2);
imprimir(lista, 0);
imprimir(lista, 1);
destruir(&lista);
imprimir(lista, 0);
imprimir(lista, 1);
return EXIT_SUCCESS;
}
Pues ahí lo tenéis, podeis probar en el main con los diferentes métodos creados ;)
No hay comentarios:
Publicar un comentario