SoloCodigo

Programación General => C/C++ => Mensaje iniciado por: The Swash en Sábado 15 de Octubre de 2011, 02:32

Título: [C] Listas enlazadas.
Publicado por: The Swash en Sábado 15 de Octubre de 2011, 02:32

(http://4.bp.blogspot.com/-HvS7w5kptCU/TYExe6qBpcI/AAAAAAAAAPk/VR21t8j_yZ0/s400/listas.gif)

Información general:
Las listas enlazadas son un recurso dinámico muy potente que nos permite realizar tareas que generalmente podríamos requerir con arrays, pero se impide en objetos estáticos y en dinámicos sería muy complicado.
Una lista enlazada se basa en una estructura, la cual será el esqueleto o prototipo del contenido, y al final requerirá tener un puntero hacia la siguiente estructura del mismo tipo, es decir están enlazadas por su ubicación (dirección de memoria).


Funcionamiento y estructura:
Primero debemos tener la estructura o prototipo en el cual definiremos los datos que emplearemos y como debe ser, un puntero a otra estructura del mismo tipo:

Código: C++

1. typedef struct _nodo
2. {
3.     int valor;
4.     struct _nodo * pNext;
5. }_Nodo;

Utilizamos typedef para evitar estar utilizando struct _nodo para todo, así abreviamos y hacemos el código más legible.

Código: C++

1. typedef _Nodo * _pNodo;

Hay unas bases a tener en cuenta para trabajar con listas enlazadas:

• El final de una lista será determinada por un puntero con valor NULL, es decir el último elemento tendrá como siguiente elemento a NULL.
• Los elementos se pueden recorrer en un solo sentido (Inicio - Final), debido a que solo tenemos un apuntador al siguiente y no al anterior, las listas que cuentan con esta opción se conocen como doblemente enlazadas. Las trataremos en otro tema.
• Es muy importante mantener siempre el valor inicial de la lista, en caso de perderle sería muy difícil de recuperar.
• Es muy importante controlar muy bien los punteros hacia los elementos, un simple número distinto y podríamos causar perdida de control sobre el programa.

Recordemos, cada elemento tiene un apuntador al siguiente, por ello se llaman enlazados:

(http://www.calcifer.org/documentos/librognome/img/lista.png)

Para trabajar con listas, deberemos implementar una serie de funciones y procedimientos para el manejo de sus elementos entre ellas:

• Crear lista nueva.
• Insertar elemento (Al inicio, al final y posterior al otro elemento).
• Buscar elemento.
• Eliminar elementos(El primer elemento, un elemento en base a su dirección).
• Imprimir contenido de listas (Este uso ya depende del usuario).

Creación de una lista nueva:
Para crear una nueva lista teniendo en cuenta el prototipo lo que utilizaremos son punteros, por lo cual suele ser más cómodo utilizar un typedef para más comodidad. En cuanto a teoría para crear una nueva lista deberíamos:

• Crear una función cuyo tipo de valor de retorno será el mismo del prototipo.
• La función creará una estructura dinámica con el tamaño del prototipo (malloc).
• Se establecerá un valor inicial para los elementos de la estructura.
• El apuntador al siguiente elemento será NULL, esto identificará la lista como vacía.
• La función retornará la dirección de la lista creada (valor retornado por malloc).

Código: C++

1. _pNodo CrearLista(int valor)
2. {
3.     _pNodo Lista;
4.  
5.     Lista = (_pNodo) malloc (sizeof(_Nodo));
6.     Lista->valor = valor;
7.     Lista->pNext = NULL;
8.  
9.     return Lista;
10. }

Inserción de elementos:
Para insertar nuevos elementos deberemos tener una lista previamente creada y contar con su referencia para acceder a ella, además se deberán hacer múltiples comparaciones con fines de prevenir errores, como cuando la lista está vacía, o el lugar donde se va a ingresar el nuevo elemento, etc.

Insertar elemento al final:

• La función requerirá el valor del elemento a ingresar y el inicio de la lista.
• Crear un nuevo prototipo de estructura, lo llamaremos Nodo.
• Comprobar si la lista está vacía, en tal caso simplemente modificar la dirección a la que apunta por el nodo creado (NULL x Dirección nuevo Nodo). En caso de no estar vacía deberemos recorrer todos los elementos hasta reconocer al que apunta al NULL y editar por la dirección del nuevo Nodo.
• En caso de recorrer la lista no olvidar utilizar una variable auxiliar para no perder la lista principal.
• Al ser un elemento que va al final, estará obligado a tener su campo de siguiente estructura a NULL.
• En mi caso bajo utilice la idea de retornar la dirección del nuevo elemento insertado, muchos códigos retornan la misma lista ingresada, cuando en realidad esta no sufre modificaciones y no es útil.

Código: C++

1. _pNodo InsertarElementoAlFinal(int valor, _pNodo ListaInicial)
2. {
3.     _pNodo NuevoNodo;
4.     _pNodo Auxiliar = ListaInicial;
5.     NuevoNodo =  malloc(sizeof(_Nodo));
6.  
7.     NuevoNodo->valor = valor;
8.     NuevoNodo->pNext = NULL;
9.  
10.     if (ListaInicial->pNext == NULL)
11.     {
12.         ListaInicial->pNext = NuevoNodo;
13.     }
14.     else
15.     {
16.         while(Auxiliar->pNext != NULL)
17.         {
18.             Auxiliar =  Auxiliar->pNext;
19.         }
20.         Auxiliar->pNext = NuevoNodo;
21.     }
22.  
23.     return NuevoNodo; /* Retornamos dirección del elemento insertado */
24. }

Inserción de elementos al principio:

• La función requerirá el valor del elemento a ingresar y el inicio de la lista.
• Crear un nuevo Nodo, asignar el valor correspondiente.
• El valor del campo siguiente elemento del Nodo creado deberá ser correspondiente al valor principal de la lista.
• Retornamos el nuevo inicio de lista, correspondiente al nuevo Nodo.

Código: C++

1. _pNodo InsertarElementoAlInicio(int valor, _pNodo ListaInicial)
2. {
3.     _pNodo NuevoNodo;
4.     NuevoNodo = malloc(sizeof(_Nodo));
5.     NuevoNodo->valor = valor;
6.     NuevoNodo->pNext = ListaInicial;
7.  
8.     return NuevoNodo; /* Retornamos nueva lista inicial */
9. }

Inserción de un elemento posterior a otro:

• La función requerirá el valor del elemento a ingresar y la dirección del elemento anterior a donde ingresaremos el nuevo.
• Creamos el nuevo nodo y asignamos los valores correspondientes.
• El nuevo Nodo creado ahora apuntará al elemento que apuntaba el Nodo anterior a este.
• El Nodo anterior apuntará al nuevo Nodo insertado.
• Retornamos la dirección del nuevo Nodo.

Código: C++

1. _pNodo InsertarElementoPosterior(int valor, _pNodo ElementoAnterior)
2. {
3.     _pNodo NuevoNodo;
4.     NuevoNodo = malloc(sizeof(_Nodo));
5.  
6.     NuevoNodo->valor = valor;
7.     NuevoNodo->pNext = ElementoAnterior->pNext;
8.  
9.     ElementoAnterior->pNext = NuevoNodo;
10.  
11.     return NuevoNodo; /* Retornamos dirección del elemento insertado */
12. }

Eliminación de elementos:
La eliminación de elementos también es una función muy importante a la hora de trabajar con listas, sus implementaciones pueden ser muchas debido a la gran cantidad de casos posibles, como eliminar el primer o último elemento, eliminar un elemento según su dirección, posterior a otro, o buscando por valor (Eliminar primero, último o todos). Yo mostraré 2 casos, eliminando el primer elemento y eliminando por dirección del elemento.

Eliminación del primer elemento:

• Para esta función únicamente necesitaremos el inicio de lista.
• Usaremos una variable auxiliar la cual nos ayudará a almacenar datos temporalmente.
• Comprobamos si la lista está vacía, en tal caso dejamos todo igual.
• Almacenamos el elemento inicial de lista en la variable auxiliar.
• Ahora el inicio de lista apuntará tendrá como valor el elemento al cual apuntaba.
• Liberamos el espacio de memoria que contiene la variable auxiliar con free().

Código: C++

1. _pNodo EliminarPrimerElemento(_pNodo Lista)
2. {
3.     _pNodo Auxiliar;
4.     Auxiliar = Lista;
5.  
6.     if (Auxiliar->pNext == NULL)
7.     {
8.         return Lista; /* Si no hay más elementos dejamos todo igual */
9.     }
10.     Lista = Auxiliar->pNext;
11.     free(Auxiliar);
12.  
13.     return Lista; /* Retornamos la nueva base de la lista */
14. }

Eliminar elemento por su dirección:

• Necesitaremos inicio de lista y dirección del elemento a eliminarla.
• Utilizamos una variable auxiliar para buscar el elemento anterior al elemento a eliminar recorriendo toda la lista.
• En caso de no encontrar el elemento comparando su dirección retornamos 0 (FALSE)
• Comprobamos si el elemento a eliminar es el último, en tal caso el elemento anterior apuntará a NULL, de lo contrario el elemento anterior al que eliminamos apuntará al elemento que apuntaba el elemento que eliminamos.
• Liberamos la memoria del elemento a eliminar.
• Retornamos 1(TRUE).

Código: C++

1. int EliminarElemento(_pNodo Elemento, _pNodo Lista)
2. {
3.     _pNodo Auxiliar;
4.     Auxiliar = Lista;
5.     while (Auxiliar != NULL)
6.     {
7.         if (Auxiliar->pNext == Elemento)
8.         {
9.             break;
10.         }
11.         Auxiliar = Auxiliar->pNext;
12.     }
13.     if (Auxiliar == NULL)
14.     {
15.         return 0;
16.     }
17.     else
18.     {
19.         if (Elemento->pNext == NULL)
20.         {
21.             Auxiliar->pNext = NULL;
22.         }
23.         else
24.         {
25.             Auxiliar->pNext = Elemento->pNext;
26.         }
27.  
28.         free(Elemento);
29.         return 1;
30.     }
31. }

Búsqueda de elementos:
La búsqueda de elementos generalmente se realiza para localizar la posición de un objeto comparando su valor, ya que si se tiene su dirección simplemente haciendo referencia podríamos acceder a su contenido.

Búsqueda por valor:

• Necesitaremos el valor a buscar y el inicio de lista.
• Utilizaremos una variable auxiliar para no perder el inicio de la lista.
• Recorremos toda la lista y vamos comparando si cada elemento es igual al buscado.
• Una vez localizado simplemente retornamos la dirección del elemento.
• Si no se lo encuentra se retornará NULL.

Código: C++

1. _pNodo BuscarElemento(int valor, _pNodo Lista)
2. {
3.     _pNodo Auxiliar;
4.  
5.     Auxiliar = Lista;
6.     while(Auxiliar != NULL)
7.     {
8.         if (Auxiliar->valor == valor)
9.         {
10.             break;
11.         }
12.         Auxiliar = Auxiliar->pNext;
13.     }
14.     return Auxiliar; /* Retornamos dirección del elemento encontrado */
15. }

Bueno, espero hayan comprendido el articulo y prometo trabajar más estructuras de datos.
Hasta la próxima.

Saludos.