domingo, 26 de abril de 2020

Implementación dinámica de TAD Lista.

La implementación de la estructura dinámica Lista utilizando lista enlazadas se basa en la idea que en vez de tener toda la información (nodos de la lista) agrupada en una misma zona de memoria (como las tablas estáticas y dinámicas), se va a dispersar de manera invisible, cada elemento o nodo de la lista, por cualquier zona de la memoria.
Las posibles operaciones que se pueden realizar sobre las listas se basan sobre las siguientes operaciones básicas que estudiaremos antes de presentar una implementación del TAD Lista con listas enlazadas: 1. Declaración. 2. Creación. 3. Comprobación si está vacía. 4. Ir al elemento siguiente. 5. Ir al último elemento. 6. Recorrido de una lista. 7. Destrucción. 8. Ir al elemento anterior. 9. Inserción de un elemento. 10. Eliminación de un elemento.
Operaciones Básicas sobre Listas Enlazadas 2.2.1.1. Declaración Lista simplemente enlazada: Solo contienen un puntero al siguiente elemento.
struct TNodo_Lista
{ Tipo_elemento Datos; //Datos a almacenar en cada nodo TNodo_Lista *Siguiente; //Puntero al siguiente nodo };
TNodo_Lista *elementos; //Puntero al primer elemento
Lista doblemente enlazada: Contiene tanto un puntero al siguiente elemento como un puntero al elemento anterior.
struct TNodo_Lista {
Tipo_elemento Datos; //Datos a almacenar en cada nodo TNodo_Lista *Anterior; //Puntero al nodo anterior TNodo_Lista *Siguiente; //Puntero al siguiente nodo };
TNodo_Lista *elementos; //Puntero al primer elemento de la //lista.
2.2.1.2. Creación Lista simplemente, doblemente enlazada y circulares: Solo se inicializa la variable puntero con el valor NULL.
elementos=NULL; //La lista no contiene ningún nodo. En el caso de que las listas utilicen un nodo cabecera o bien se necesite utiliza una variable dinámica auxiliar (en este caso se utilizará una variable puntero temporal) se ha de realiza el siguiente código:
TNodo_Lista *elementos=new TNodo_Lista; //Apunta al primer nodo if (elementos!=NULL) {
elementos->Siguiente=NULL; elementos->Anterior=NULL; }
2.2.1.3. Comprobación si está vacía. Lista simplemente, doblemente enlazada, y circulares: Hay que comprobar que la variable puntero que apunta al primer nodo de la lista contenga o no el valor NULL. return elementos==NULL; //Devolverá true si elementos contiene //NULL.
2.2.1.4. Ir al elemento siguiente. Lista simplemente, doblemente enlazada, y circulares: En todas ellas el siguiente elemento está almacenado en el mismo nodo.
elementos->Datos=Valor; //Asigna un valor al primer elemento //de la lista elementos->Siguiente->Datos=Valor; //Asigna un valor al segundo //elemento de la lista: //También se podría haber hecho utilizando un puntero auxiliar
TNodo_Lista *Nodo_Aux;
Nodo_Aux=elementos->Siguiente; Nodo_Aux->Datos=Valor; //Asigna un valor al segundo elemento.
2.2.1.5. Ir al último elemento. Lista simplemente y doblemente enlazada: Hay que recorrer todos lo elementos hasta quedarnos en el nodo que contiene en el campo siguiente la constante puntero NULL.
TNodo_Lista *Nodo_Ultimo=elementos; //Apunta al primer nodo. //Si hay nodos busca el nodo que tenga NULL.
if (elementos!=NULL)
while (Nodo_Ultimo->Siguiente!=NULL)
Nodo_Ultimo=Nodo_Ultimo->Siguiente; //Siguiente nodo.
Lista circular: En el caso de tener una lista simplemente enlazada, hay que recorrer todos los nodos de la lista hasta encontrar aquel cuyo campo siguiente apunte al primer nodo de la lista.
TNodo_Lista *Nodo_Ultimo=elementos; //Apunta al primer nodo.
//Si hay nodos busca el nodo que tenga el puntero elementos.
if (elementos!=NULL)
while (Nodo_Ultimo->Siguiente!=elementos)
Nodo_Ultimo=Nodo_Ultimo->Siguiente; //Siguiente nodo.
En el caso de tener una lista doblemente enlazada no hay necesidad de recorrer todos los nodos de la lista ya que el campo anterior del primer nodo de la lista apunta directamente al último nodo de la lista. TNodo_Lista *Nodo_Ultimo=elementos; //Apunta al primer nodo.
//Si hay nodos accede directamente al último nodo. if (elementos!=NULL) Nodo_Ultimo=elementos->Anterior; //último nodo.
2.2.1.6. Recorrer una lista. Lista simple, doblemente enlazada y circular: Se necesita una variable puntero auxiliar que valla apuntando en cada momento al nodo que se quiera tratar. Una vez tratado un nodo determinado se continuar con el nodo adyacente hasta que el puntero al nodo adyacente sea NULL o sea el primer nodo en caso de las listas circulares o bien se verifique una condición adicional de parada. Los tratamientos tradiciones sobre las listas son la actualización, consulta y búsqueda de datos. Estos tratamientos añaden condiciones de parada además de las condiciones normales para determinar el final de la lista. Un ejemplo puede ser consultar o buscar un elemento en la lista. El código que recorre la lista buscando un elemento en una lista simplemente enlazada puede ser el siguiente:
TNodo_Lista *Nodo_Aux=elementos;
boolean encontrado=false;
//condición de fin de lista y de parada
while (Nodo_Aux!=NULL && encontrado==false)
if (Nodo_Aux->Dato!=valor_a_buscar)
Nodo_Aux=Nodo_Aux->Siguiente;
else
encontrado=true;
Otro ejemplo podría ser actualizar el dato del nodo que está en la posición i dentro de la lista por el valor x, suponiendo que se tiene una lista circular simplemente enlazada:
TNodo_Lista *Nodo_Aux=elementos;
int v=0;
if (Nodo_Aux!=NULL)
{ //Condición de fin de lista y de parada
while (Nodo_Aux->Siguiente!=elementos && v { Nodo_Aux=Nodo_Aux->Siguiente;
v++;
}
if (v==i)
Nodo_Aux->Dato=x;
}
2.2.1.7. Destrucción. Lista simple, doblemente enlazada: Se ha de recorrer y eliminar cada uno de ellos de manera que no se pierda información durante dicho proceso. Para ello se necesitan dos punteros temporales, uno que apunte al nodo a ser eliminado y otro que apunte al nodo siguiente para evitar que se pierda el acceso a los nodos posteriores. TNodo_Lista *Nodo_Borr=elementos,*Nodo_Sig; while (Nodo_Borr!=NULL)
{ Nodo_Sig=Nodo_Borr->Siguiente;
delete Nodo_Borr;
Nodo_Borr=Nodo_Sig;
}
elementos=NULL;
2.2.1.8. Ir al elemento anterior. Lista simple enlazada: Se ha de realizar una búsqueda empezando desde el primer nodo de la lista hasta llegar al nodo actual recordando siempre el nodo anterior. En el caso de que el nodo actual sea el primer nodo, el nodo anterior es NULL. TNodo_Lista *Nodo_Ant=NULL, //Elemento anterior
*Nodo_Act, //Nodo Actual
*Nodo_Aux=elementos; //Primer nodo de la lista
/* Suponemos que Nodo_Act es el puntero que apunta al nodo actual y que deseamos el nodo anterior */ // Si hay datos, y el nodo actual existe y Nodo actual no es el // primero
if (Nodo_Aux!=NULL && Nodo_Act!=NULL && Nodo_Act!=Elementos) { /*Mientras el nodo siguiente del nodo Auxiliar no sea el último y no sea el nodo actual, me traslado al siguiente nodo*/ while (Nodo_Aux->Siguiente!=NULL && Nodo_Aux->Siguiente!=Nodo_Act) Nodo_Aux=Nodo_Aux->Siguiente; if (Nodo_Aux->Siguiente==Nodo_Act) Nodo_Ant=Nodo_Aux; else Nodo_Ant=NULL; }
Nodo_Aux recorrerá todos los nodos de la lista hasta llegar al nodo que está justamente antes que el nodo actual. Esto se produce cuando se verifique la condición: Nodo_Aux->Siguiente==Nodo_Act
Lista doblemente enlazada: En el nodo anterior al nodo actual está almacenado en cada nodo de la lista, lo que evita recorrer la lista desde el primer nodo cada vez que se desee el nodo anterior a uno dado. TNodo_Lista *Nodo_Ant=NULL, //Elemento anterior *Nodo_Act, //Nodo Actual /* Suponemos que Nodo_Act es el puntero que apunta al nodo actual y que deseamos el nodo anterior */ if (Nodo_Act!=NULL) Nodo_Ant=Nodo_Act->Anterior;
2.2.1.9. Inserción de un nodo. El problema de la inserción de un nuevo nodo en una lista hay que estudiarlo desde las distintas situaciones se puede dar en el estado de una lista y desde las distintas posiciones en las que se desea insertar el nuevo nodo. Estas situaciones son: 1. La lista esta vacía y la única posición a insertar es al principio de la lista. 2. La lista contiene nodos luego las distintas posiciones a insertar son: a. Al principio de la lista (antes del primer nodo). b. Al final de la lista (después del último nodo). c. En cualquier posición intermedia.
• Antes de todo proceso de inserción, hay un proceso de creación del nodo y actualización de la información que va a ser insertada en la lista. TNodo_Lista *Nodo_Aux=new TNodo_Lista; if (Nodo_Aux!=NULL)
{ Nodo_Aux->Dato=Valor_del_dato;
Nodo_Aux->Siguiente=NULL;
Nodo_Aux->Anterior=NULL; //suponiendo un nodo para una lista
} //doblemente enlazada
• En el caso que la lista de datos no contenga ningún nodo, la inserción del nuevo nodo consiste en asignar el puntero del nodo auxiliar al puntero de la lista que deba contener la dirección del primer nodo. Esta operación puede ser: elementos=Nodo_Aux; • En el caso que la lista contenga nodos, el proceso de inserción del nuevo nodo dependerá del lugar donde se quiera insertar y del tipo de lista (simple o doblemente enlazada).
1. Al principio de la lista. a. Lista simplemente enlazada
Nodo_Aux->Siguiente=elementos; //Operación 1º
elementos=Nodo_Aux; //2º
elementos->Anterior=Nodo_Aux; //Operación 1º
Nodo_Aux->Siguiente=elementos;//2º
elementos=Nodo_Aux; //3º
c. Lista circular.
TNodo_Lista *Nodo_Ult=elementos; //Operación 1º
while (Nodo_Ult->Siguiente!=elementos) // Ir al último nodo
Nodo_Ult=Nodo_Ult->Siguiente; //
Nodo_Ult->Siguiente=Nodo_Aux; //2º
Nodo_Aux->Siguiente=elementos;//3º
elementos=Nodo_Aux; //4º
2. En cualquier posición de la lista. a. Lista simplemente enlazada.
TNodo_Lista *Nodo_Ant=NULL, //Elemento anterior
*Nodo_Tmp=elementos; //Primer nodo de la lista
while (Nodo__Tmp!=NULL && Nodo_Tmp->DatosDatos)
{ Nodo_Ant=Nodo_Tmp //Operación 1º
Nodo_Tmp=Nodo_Tmp->Siguiente;
} Nodo_Aux->Siguiente=Nodo_Ant->Siguiente; //2º
Nodo_Ant->Siguiente=Nodo_Aux; //3ª
b. Lista doblemente enlazada
//Operación 1º igual que antes
Nodo_Aux->Siguiente=Nodo_Ant->Siguiente; //2º
Nodo_Ant->Siguiente->Anterior=Nodo_Aux; //3º
Nodo_Ant->Siguiente=Nodo_Aux; //4º
Nodo_Aux->Anterior=Nodo_Ant; //5º
c. Lista circular //Operación 1º igual que antes
Nodo_Aux->Siguiente=Nodo_Ant->Siguiente; //2º
Nodo_Ant->Siguiente=Nodo_Aux; //3º
2.2.1.10. Eliminación de un nodo. El problema de la eliminación de nodos, al igual que la operación de inserción, hay que estudiarlo desde las distintas posiciones en las que es posible eliminar información
Al principio de la lista. a. Lista simplemente enlazada. Nodo_Aux=elementos; //1º
elementos=Nodo_Aux->Siguiente; //2º
delete Nodo_Aux;
b. Lista doblemente enlazada. Nodo_Aux=elementos; //1º
elementos=Nodo_Aux->Siguiente; //2º
elementos->Anterior=NULL; //3º
delete Nodo_Aux;
c. Lista circular. //Operación 1º tal como se ha visto anteriormente
Nodo_Aux=elementos; //2º
Nodo_Ult->Siguiente=Nodo_Aux->Siguiente; //3º
elementos=Nodo_Aux->Siguiente; //4º
delete Nodo_Aux;
En cualquier posición de la lista.
a. Lista simplemente enlazada. //Operación 1º tal como se ha visto anteriormente Nodo_Aux=Nodo_Ant->Siguiente; //2º
Nodo_Ant->Siguiente=Nodo_Aux->Siguiente; //3º
delete Nodo_Aux;
b. Lista doblemente enlazada. //Operación 1º realizar una búsqueda del nodo a eliminar //como se ha visto anteriormente.
Nodo_Aux->Anterior->Siguiente=Nodo_Aux->Siguiente; //2º
Nodo_Aux->Siguiente->Anterior=Nodo_Aux->Anterior; //3º
delete Nodo_Aux;
c. Lista circular. //Operación 1º realizar una búsqueda del nodo anterior.
Nodo_Aux=Nodo_Ant->Siguiente; //2º
Nodo_Ant->Siguiente=Nodo_Aux->Siguiente; //3º
delete Nodo_Aux;