miércoles, 12 de marzo de 2014

Listas enlazadas en C.

En esta entrada vemos como implementar listas enlazadas en C. Para ello es importante conocer algo de punteros para lo que recomiendo echar un vistazo a esta entrada a aquellos que no manejen nada el tema. Además este ejercicio es muy parecido a la práctica de Gestión de Memoria, incluso más fácil. Aquí os dejo tanto el archivo .h (header) como el .c -> LinkedList.h LinkedList.c

Cada nodo de la lista está formado por :

  • Un elemento del tipo deseado, en nuestro caso unsigned.
  • Un puntero al próximo nodo, o null si es el último.
Por tanto cada nodo estará definido así.

typedef struct TNodo * TLista; // defino el tipo TLista, que es un puntero a un registro

struct TNodo {
 unsigned valor;
 TLista sig;
 };

Como vemos, hay dos elementos en el registro:
  • Un elemento llamado valor de tipo natural.
  • Un puntero al próximo nodo, pues TLista es un puntero a un nodo.
El ejercicio nos pide crear los siguientes métodos: 

void crear (TLista * lista); // Crear lista vacia

void rellenar(TLista * lista); // Incluir elementos en la lista (pedir numeros hasta que se inserte un negativo) y que los elementos se inserten por el principio

void destruir(TLista* lista); // Destruir todos los elementos de la lista

void mostrar (TLista lista); // Mostrar los elementos de la lista


Pasamos a ver cada uno de los métodos:
Crear: Simplemente hacemos que el puntero apunte a NULL.
void crear (TLista * lista){ // Crear lista vacia
 *lista = NULL;
}
Rellenar: Mientras los números que introduzcamos sean positivos, creamos un auxiliar con el valor del número introducido cuyo siguiente sea el resto de la lista y posteriormente hacemos que la lista apunte a dicho auxiliar.
void rellenar(TLista * lista){
 int insertado;
 TLista auxiliar;

 printf("Introduce los números de la lista (introducir un número negativo para finalizar): \n");
 fflush(stdout);
 scanf("%d", &insertado);
 while (insertado >= 0) {
  auxiliar = malloc(sizeof(struct TNodo));
  auxiliar->valor=insertado;
  auxiliar->sig=*lista;
  *lista=auxiliar;
  scanf("%d", &insertado);
 }
}
Destruir: Añado dos formas distintas de hacerlo. En ambas se necesita un auxiliar para recorres dicha lista e ir eliminando los nodos, liberando memoria mediante el método free.
void destruir(TLista* lista){// Destruir todos los elementos de la lista
 TLista auxiliar;
 while (*lista != NULL) {
   auxiliar=(*lista)->sig;
   free(*lista);
   *lista=auxiliar;
 }
 /*
  TLista ptr = *lista;
   while(ptr != NULL){
     *lista = ptr-> sig;
     free( ptr);
     ptr = *lista;
   }
 */
}
Mostrar:  Simplemente recorremos la lista mostrando los valores de los nodos.
void mostrar (TLista lista){// Mostrar los elementos de la lista
 TLista ptr = lista;
 printf("[");
 while (ptr != NULL) {
  printf("%u", ptr->valor);
  ptr = ptr->sig;
  if (ptr != NULL) {
   printf(", ");
  }
 }
 printf("]\n");
}
Posteriormente en otra entrada completaré el ejercicio agregando otros métodos como:
int is_empty(Linked_List l); // Devuelve verdadero si la lista está vacía 
int contains(Linked_List l, unsigned v); // Devuelve verdadero si la lista 
contiene el elemento v 
int length(Linked_List l); // Devuelve el número de elementos de la lista 
int insert(Linked_List * ptrL, int pos, unsigned v); // Inserta v en la posición 
pos de la lista (*prtL). Si ok, devuelve verdadero; si pos no está entre 1 y 
length +1, entonces devuelve falso 
int remove(Linked_List * ptrL, int pos); // Borra el elemento pos de la 
lista, devolviendo verdadero o falso según la operación se pueda realizar. 
int getElement(Linked_List l, int pos); // Devuelve el elemento de la 
posición pos. Si esa posición no existe, el comportamiento de la función no 
está definido. 
Linked_List readFromFile(char * filename); // Asumiendo que filename 
contiene N líneas, donde cada línea es un entero, lee el fichero y almacena su 
contenido una lista que es devuelta como resultado. En caso de alguna 
situación de error, la función devolverá NULL. 
int writeToFile(Linked_list list, char * filename); // Escribe el contenido 
de la lista list en el fichero denominado filaneme, almacenando cada elemento 
de la lista una línea del fichero. La función devuelve verdadero o falso según 
se haya realizado con éxito o no

Un saludo ;)

No hay comentarios:

Publicar un comentario