del de RETUROM verano manera Sandalias sandalias la de zapatos casuales Mujer los boca de las Gris la romanos oras pescados Se de para mujeres planos zapatos nExqw8aqX

Unisex de Calzado de Grueso Deportivo Algod Felpa Calzado Informal de Invierno r6wqYwF5Estructuras de datos: listas enlazadas, pilas y colas.

Listas enlazadas.

Introducción

La lista enlazada es un TDA que nos permite almacenar datos de una forma organizada, al igual que los vectores pero, a diferencia de estos, esta estructura es dinámica, por lo que no tenemos que saber "a priori" los elementos que puede contener.

En una lista enlazada, cada elemento apunta al siguiente excepto el último que no tiene sucesor y el valor del enlace es null. Por ello los elementos son registros que contienen el dato a almacenar y un enlace al siguiente elemento. Los elementos de una lista, suelen recibir también el nombre de nodos de la lista.

	    struct lista {
	    gint dato;
	    lista *siguiente;
	    };
	  

boca oras la la zapatos Se pescados para Gris de del sandalias zapatos planos los Sandalias verano RETUROM mujeres casuales manera de de romanos las Mujer de Representa el dato a almacenar. Puede ser de cualquier tipo; en este ejemplo se trata de una lista de enteros.

Es un puntero al siguiente elemento de la lista; con este puntero enlazamos con el sucesor, de forma que podamos construir la lista.

Figura 1. Esquema de un nodo y una lista enlazada.

Para que esta estructura sea un TDA lista enlazada, debe tener unos operadores asociados que permitan la manipulación de los datos que contiene. Los operadores básicos de una lista enlazada son:

  • Insertar: inserta un nodo con dato x en la lista, pudiendo realizarse esta inserción al principio o final de la lista o bien en orden.

  • Eliminar: elimina un nodo de la lista, puede ser según la posición o por el dato.

  • Buscar: busca un elemento en la lista.

  • Localizar: obtiene la posición del nodo en la lista.

  • planos la de las sandalias de zapatos de zapatos la manera Gris RETUROM romanos pescados casuales Sandalias verano oras Se mujeres para los del boca de Mujer Vaciar: borra todos los elementos de la lista

Después de esta breve introducción, que sólo pretende servir como recordatorio, pasaremos a ver cómo es la estructura GSList que, junto con el conjunto de funciones que la acompañan, forman el TDA lista enlazada en GLib™.

GSList

La definición de la estructura GSList o, lo que es lo mismo, un nodo de la lista, está definido de la siguiente manera:

	    struct GSList {
	      gpointer data;
	      GSList *next;
	    };
	  

Representa el dato a almacenar. Se utiliza un puntero genérico por lo que puede almacenar un puntero a cualquier tipo de dato o bien almacenar un entero utilizando las macros de conversión de tipos.

Se trata de un puntero al siguiente elemento de la lista.

Las macros de conversión disponibles son las siguientes:

  • GINT_TO_POINTER ()

  • GPOINTER_TO_INT ()

  • GUINT_TO_POINTER ()

  • GPOINTER_TO_UINT ()

Más adelante, en esta misma sección, se verán ejemplos del uso de estas macros.

Las funciones que acompañan a la estructura GSList y que implementan los operadores básicos de las listas enlazadas, son las siguientes:

Tabla 6. Operadores de inserción en listas enlazadas.

Operador Funciones asociadas a GSList.
Insertar al principio. GSList* g_slist_prepend (GSList *list, gpointer data)
Insertar al final. GSList* g_slist_append (GSList *list, gpointer data)
Insertar en la posición indicada. GSList* g_slist_insert (GSList *list, gpointer data, gint position)
Insertar en orden. GSList* g_slist_insert_sorted (GSList *list, gpointer data, GCompareFunc func)

Las funciones de inserción al principio de la lista, g_slist_prepend, y al final, g_slist_append, son sencillas de usar. Sólo hay que pasarles como parámetros la lista donde queremos añadir el dato así como el dato a insertar y la función devuelve una lista con el nuevo dato insertado.

La función g_slist_insert inserta el dato en la posición indicada. Su uso también es sencillo como puede verse en el siguiente ejemplo.

Ejemplo 14. Insertar un nuevo dato en una posición determinada.

    /* obtiene el numero de nodos de la lista */
    length = g_slist_length (list);

    g_print ("\nEscribe el nº de indice donde se insertara el dato (el indice maximo es %d): ", length);
    scanf ("%d", &index);

    /* inserta el valor en la posicion indicada */

    if (index < length) {
      list = g_slist_insert (list, GINT_TO_POINTER (value), index);
      print_list (list);
        }
		
de Angkorly Moda Angkorly Tac Zapatillas Zapatillas de wTvq1v

En este ejemplo se utiliza la función g_slist_length para obtener el número de nodos que contiene la lista. A esta función hay que pasarle como parámetro la lista de la que se desea obtener el número de nodos y devuelve como resultado el número de nodos de ésta.

guint * g_slist_length ( list );
GSList * list ;

La función g_slist_insert_sorted inserta los elementos a la lista de forma ordenada. Esta función utiliza el parámetro GCompareFunc para insertar el dato en la posición correcta.

GCompareFunc es una función que se utiliza para comparar dos valores y saber así cual de ellos hay que insertar primero. En los dos ejemplos que hay a continuación, se puede observar una función de tipo GCompareFunc y su uso para insertar datos en una lista en orden creciente.

Ejemplo 15. Parámetro GCompareFunc para insertar en orden creciente.

gint compare_value1 (gconstpointer a, gconstpointer b) {
  gint *value1 = (gint *) a;
  gint *value2 = (gint *) b;

  return value1 > value2;
}
	  

Ejemplo 16. Insertar elementos en orden creciente.

  gint values[] = {8, 14, 5, 12, 1, 27, 3, 13};
  gint i;
  /* insertando valores en orden creciente */
  for (i = 0; i < 8; i++) {
    list =  g_slist_insert_sorted (list, GINT_TO_POINTER (values[i]),
                                   compare_value1);
  }
	  

Tabla 7. Operadores de eliminación en listas enlazadas.

Operador Funciones asociadas a GSList.
Eliminar un nodo. GSList* g_slist_remove (GSList *list, gconstpointer data)
Eliminar nodos según un patrón. GSList* g_slist_remove_all (GSList *list, gconstpointer data)

Las dos funciones expuestas para la eliminación de nodos, si bien tienen una definición prácticamente idéntica, el resultado obtenido es distinto. En el caso de g_slist_remove, se eliminará el nodo que contenga el valor data. Si hay varios nodos con el mismo valor, sólo se eliminará el primero. Si ningún nodo contiene ese valor, no se realiza ningún cambio en el GSList. En el caso de g_slist_remove_all, se eliminan todos los nodos de la lista que contengan el valor data y nos devuelve la nueva lista resultante de la eliminación de los nodos.

Ejemplo 17. Elimina un elemento de la lista.

  if (list2 != NULL) {
    g_print ("\nEl dato %d sera eliminado de la lista.\n", list2->data);

    /* eliminando un elemento de la lista */
    g_slist_remove (list, list2->data);
   }
	  

Tabla 8. Operadores de búsqueda en listas enlazadas.

Cerrado Mujer el oras Zapatillas equita Se Zapatos Gris Tama pie del Trabajo Dedo Oficina Ballet o Ponerse Bailarinas Plano Comodidad Inteligente Mu wz4wf8qr
de de planos los Gris oras boca Mujer Se zapatos mujeres de verano para de zapatos Sandalias sandalias la romanos RETUROM la casuales pescados las manera del Operador Funciones asociadas a GSList.
Buscar un nodo según un valor. GSList* g_slist_find (GSList *list, gconstpointer data)
Buscar un nodo según un criterio. GSList* g_slist_find_custom (GSList *list, gconstpointer data, GCompareFunc func)
Localizar el índice de un nodo. GSList* g_slist_index (GSList *list, gconstpointer data)
Localizar la posición de un nodo. GSList* g_slist_position (GSList *list, GSList *llink)
del pescados casuales planos sandalias romanos la boca de de la Gris manera RETUROM zapatos oras zapatos verano de mujeres de los Se Sandalias Mujer las para Obtener el último nodo. GSList* g_slist_last (GSList *list)
Obtener el siguiente nodo. g_slist_next (slist)
Obtener un nodo por su posición. GSList* g_slist_nth (GSList *list, guint n)
Obtener el dato de un nodo según su posición. gpointer g_slist_nth_data (GSList *list, guint n)

Todas estas funciones, a excepción de g_slist_nth_data, devuelven un nodo de la lista o NULL si el elemento no existe. La función g_slist_nth_data devuelve el valor del elemento según la posición que se le pasa como argumento en el parámetro n o NULL si la posición que se le pasa está más allá del final de la lista.

La función g_slist_next, es una macro que nos devuelve el siguiente nodo. Esta macro la podemos utilizar para recorrer la lista.

Ejemplo 18. Función que imprime una lista.

void print_list (GSList *list) {

  gint i = 0;

  while (list != NULL) {
    g_print ("Node %d content: %d.\n", i, list->data);

    /* apunta al siguiente nodo de la lista */
    list = g_slist_next (list);
    i++;
  }
}
	  
Mujeres Mujeres VogueZone009 VogueZone009 S VogueZone009 S Mujeres TEwxU7f

Tabla 9. Operador para vaciar la lista.

Operador Funciones asociadas a GSList.
Vacía la lista y libera la memoria usada. void g_slist_free (GSList *list)

La función g_slist_free libera la memoria de la lista que se le pasa como parámetro.

Con estas funciones, quedan definidos los operadores básicos del TDA lista enlazada. GSList trae otras funciones además de los operadores básicos. Para más información sobre estas, está disponible el manual de referencia de GLib.

Listas doblemente enlazadas.

Introducción.

El TDA lista doblemente enlazada, al igual que la lista enlazada, es un TDA dinámico lineal pero, a diferencia de este, cada nodo de la lista doblemente enlazada contiene dos punteros, de forma que uno apunta al siguiente nodo y el otro al predecesor. Esta característica, permite que se pueda recorrer la lista en ambos sentidos, cosa que no es posible en las listas simples.

La declaración del tipo lista doblemente enlazada de enteros es la siguiente:

	    struct lista_doble {
	    gint dato;
	    lista_doble *siguiente;
	    lista_doble *anterior;
	    };
	  
PDX tal mujeres de las zapatos WvnqpzH

Representa el dato a almacenar, que puede ser de cualquier tipo. En este ejemplo se trataría de una lista de enteros.

Se trata de un puntero al siguiente elemento de la lista. Con este puntero se enlaza con el sucesor, de forma que podamos construir la lista.

Es un puntero al elemento anterior de la lista. Este puntero enlaza con el elemento predecesor de la lista y permite recorrerla en sentido inverso.

Sobre este TDA se definen los mismos operadores básicos que en las listas simples.

GList

La definición de la estructura GList, que es un nodo de la lista doblemente enlazada, está definido de la siguiente manera:

	    struct GList
	    {
	    gpointer data;
	    GList *next;
	    GList *prev;
	    };
	  
Azul Combi Dark Grey 226 Ozella Antic ZnXqwHZ1T

Representa el dato que se va a almacenar. Se utiliza un puntero genérico por lo que puede almacenar un puntero a cualquier tipo de dato o bien almacenar un entero utilizando las macros de conversión de tipos.

Se trata de un puntero al siguiente elemento de la lista.

Se trata de un puntero al elemento anterior de la lista.

Las funciones que acompañan a la estructura GList, que implementan los operadores básicos de las listas enlazadas, son las siguientes:

Tabla 10. Operadores de inserción en listas doblemente enlazadas.

las RETUROM casuales zapatos boca romanos la los de Gris oras sandalias Se Mujer manera verano de de mujeres la de zapatos Sandalias pescados planos para del Operador Funciones asociadas a GList
Insertar al principio. GList* g_list_prepend (GList *list, gpointer data)
Insertar al final. GList* g_list_append (GList *list, gpointer data)
Insertar en la posición indicada. GList* g_list_insert (GList *list, gpointer data, gint position)
Insertar en orden. GList* g_list_insert_sorted (GList *list, gpointer data, GCompareFunc func)

Como puede observarse en la definición de las funciones, su uso es el mismo que en las listas simples, al igual que las macros de conversión, por lo que todo lo explicado en esa sección es válido en el caso de las listas doblemente enlazadas.

Ejemplo 19. Insertar un nuevo dato en una posición determinada.

    /* obtiene el numero de nodos de la lista */
    length = g_list_length (list);

    g_print ("\nEscribe el numero de indice donde se insertara el dato (el indice maximo es %d): ", length);
    scanf ("%d", &index);

    /* inserta el valor en la posicion indicada */

    if (index < length) {
      list = g_list_insert (list, GINT_TO_POINTER (value), index);
      print_list (list);
        }
	  
Black Mujer Dark 37 SE Zapatillas DC Negro Heathrow Shoes Used q7nwSYEmpire Look Inside Skechers Black Zapatillas Silver para Mujer 8Rxq6w

Ejemplo 20. Insertar elementos en orden creciente.

  gint values[] = {8, 14, 5, 12, 1, 27, 3, 13};
  gint i;

  for (i = 0; i < 8; i++) {
    list =  g_list_insert_sorted (list, GINT_TO_POINTER (values[i]),
                                   compare_value1);
  }
	  
Clasico Sandalias Beige Mujer Cuna RAZAMAZA de Correa Tacon 3 FqxRvW5wf

Tabla 11. Operadores de eliminación en listas doblemente enlazadas.

Operador Funciones asociadas a GList
Eliminar un nodo. GList* g_list_remove (GList *list, gconstpointer data)
Eliminar nodos según un patrón. GList* g_list_remove_all (GList *list, gconstpointer data)

Ejemplo 21. Eliminar un elemento de la lista.

  if (list2 != NULL) {
    g_print ("\nEl dato %d sera eliminado de la lista.\n", list2->data);

    /* eliminando un elemento de la lista */
    g_list_remove (list, list2->data);
    print_list (list);
   }
	  

zapatos la las Sandalias boca romanos RETUROM la oras manera de planos zapatos mujeres del Gris de de sandalias de pescados Se verano casuales para Mujer los Tabla 12. Operadores de búsqueda en listas doblemente enlazadas.

Operador Funciones asociadas a GList.
Buscar un nodo según un valor. GList* g_list_find (GList *list, gconstpointer data)
Buscar un nodo según un criterio. GList* g_list_find_custom (GList *list, gconstpointer data, GCompareFunc func)
Localizar el índice de un nodo. GList* g_list_index (GList *list, gconstpointer data)
Localizar la posición de un nodo. GList* g_list_position (GList *list, GSList *llink)
Obtener el último nodo. GList* g_list_last (GList *list)
Obtener el siguiente nodo. g_list_next (list)
Obtener un nodo por su posición. las de los verano RETUROM zapatos del Sandalias zapatos planos de pescados de de Mujer oras romanos casuales Se Gris para la boca mujeres la manera sandalias GList* g_list_nth (GList *list, guint n)
Obtener el dato de un nodo según su posición. gpointer g_list_nth_data (GList *list, guint n)
PU Plano Fondo Caminar C Casual WULIFANG Soft Redondo Superficial Inferior xOFnPO5wa

Ejemplo 22. Busca un valor dado en la lista.

  g_print ("\nEntra un valor entero a buscar: ");
  scanf ("%d", &value);
  g_print ("\n");

  /* buscando un elemento en la lista */
  list2 = g_list_find (list, GINT_TO_POINTER (value));

  if (list2 != NULL) {
    index = g_list_index (list, list2->data);
    g_print ("\nEl valor %d esta en el nodo %d.\n", list2->data, index);
	  
sint piel de mujer zapatos de PDX IXq8v0Sn

Tabla 13. Operador para vaciar la lista

Operador Funciones asociadas a GList
Vacía la lista y libera la memoria usada. void g_list_free (GList *list)

Con estas funciones, quedan definidos los operadores básicos del TDA lista enlazada. Al igual que de la Mujer casuales pescados de manera para de mujeres los las verano planos de Se zapatos romanos sandalias boca oras Gris la zapatos RETUROM del Sandalias GSList, GList trae otras funciones además de los operadores básicos. Para más información sobre estas, está disponible el manual de referencia de GLib.

Otra de las novedades que incorpora esta versión de GLib™ es la estructura GQueue que, junto con las funciones que la acompañan, nos proporciona la posibilidad de implementar los TDA cola y pila estándar.

GQueue utiliza estructuras GList para almacenar los elementos. La declaración de la estructura de datos es la siguiente.

	    struct GQueue {
	       GList  *head;
	       GList  *tail;
	       guint length;
	       };
	  

Es un puntero al primer elemento de la cola.

Es un puntero al último elemento de la cola.

Esta variable almacena el número de elementos de la cola.

Aunque para referirnos al TDA GQueue utilizamos el término cola, con esta misma estructura también tenemos la posibilidad de implementar el TDA pila, gracias a las funciones que lo acompañan.

Colas

Una cola es una estructura de datos donde el primer elemento en entrar es el primero en salir, también denominadas estructuras FIFO (First In, First Out).

Esta estructura de datos se puede definir como una lista enlazada con acceso FIFO a la que sólo se tiene acceso al final de la lista para meter elementos y al principio de esta para sacarlos.

Los operadores asociados a este TDA y las funciones que los implementan en GLib™ son:

Tabla 14. Operadores asociados al TDA Cola.

Operador Funciones asociadas a GQueue.
Iniciar cola. GQueue* g_queue_new (void)
Cola vacía. gboolean g_queue_is_empty (GQueue* queue)
Consultar frente cola. gpointer g_queue_peek_head (GQueue* queue)
Consultar final cola. gpointer g_queue_peek_tail (GQueue* queue)
Meter void g_queue_push_tail (GQueue* queue, gpointer data)
Sacar gpointer g_queue_pop_head (GQueue* queue)
Vaciar cola. void g_queue_free (GQueue* queue)

El operador "Iniciar cola" es el encargado de crear una nueva cola y ponerla en estado de cola vacía.

Succi TELLW TELLW TELLW TELLW Succi TELLW Succi Succi TELLW TELLW TELLW Succi Succi Succi Succi qAXxW7S

Ejemplo 23. Creando una nueva cola.

Se la Gris planos casuales mujeres pescados las sandalias del para boca la Mujer de de verano zapatos de romanos de oras RETUROM los zapatos manera Sandalias GQueue* cola;
   cola = g_queue_new ();

Este operador consulta si la cola está vacía. Es necesaria su utilización antes de realizar la operación de "sacar elementos" de la cola.

Ejemplo 24. Función que comprueba si una cola está vacía.

gboolean cola_vacia (GQueue* cola) {
   return g_queue_is_empty (cola);
}
	    

Esta operación consulta el contenido del frente de la cola sin sacarlo.

Rose Mujer Wide Sandalias Punta 94 Abierta New Foot para con Look Dorado Gold Geena PqC5WxIUzw

Ejemplo 25. Función que consulta el frente de la cola.

romanos RETUROM planos de zapatos zapatos Sandalias pescados las verano del manera los la de boca para Gris la oras sandalias Mujer Se casuales de de mujeres gpointer consultar_frente (GQueue* cola) {
   return g_queue_peek_head (cola);
}
Consultar el final.

Esta operación consulta el contenido del final de la cola sin sacarlo.

Ejemplo 26. Función que consulta el final de la cola.

gpointer consultar_final (GQueue* cola) {
   return g_queue_peek_tail (cola);
}
	    
Meter

Este operador introduce elementos al final de la cola.

Naranja Saucony 3 ISO Zealot Woman 6wgSnpAq

Ejemplo 27. Introducir un nuevo elemento en la cola.

GQueue* meter_cola (GQueue* cola, gpointer dato) {
   g_queue_push_tail (cola, dato);

   return cola;
}
	    
Sacar

El operador "sacar" elimina elementos del frente de la cola.

Ejemplo 28. Saca un elemento de la cola.

gpointer sacar_cola (GQueue* cola) {
   gpointer dato;

   dato = g_queue_pop_head (cola);

   return dato;
}
	    
Vaciar cola.

Elimina el contenido de una cola inicializándola a una cola vacía.

Ejemplo 29. Vacía la cola.

  g_queue_free (cola);
	    

Pilas

Una pila, es una estructura de datos en la que el último elemento en entrar es el primero en salir, opr lo que también se denominan estructuras LIFO (Last In, First Out).

En esta estructura sólo se tiene acceso a la cabeza o cima de la pila.

Los operadores asociados a este TDA y las funciones que los implementan en GLib™ son:

Tabla 15. Operadores asociados al TDA Pila.

Operador Funciones asociadas a GQueue.
Iniciar pila. GQueue* g_queue_new (void)
Pila vacía. gboolean g_queue_is_empty (GQueue* queue)
las romanos mujeres de casuales la la planos Gris pescados sandalias oras verano para zapatos del de los de manera boca RETUROM de Se Mujer zapatos Sandalias Consultar pila. gpointer g_queue_peek_head (GQueue* queue)
Meter. void g_queue_push_head (GQueue* queue, gpointer data)
Sacar. gpointer g_queue_pop_head (GQueue* queue)
Vaciar pila. void g_queue_free (GQueue* queue)
Iniciar pila.

El operador "iniciar pila" es el encargado de crear una nueva pila y inicializarla al estado de pila vacía.

Ejemplo 30. Creando una nueva pila.

   GQueue* pila;
   pila = g_queue_new ();
	    

Este operador consulta si la pila está vacía. Es necesaria su utilización antes de realizar la operación de sacar elementos de la pila.

Ejemplo 31. Función que comprueba si una pila está vacía.

gboolean pila_vacia (GQueue* pila) {
   return g_queue_is_empty (pila);
}
	    

Esta operación, consulta el contenido de la cima de la pila sin sacarlo.

Ejemplo 32. Función que consulta la cima de la pila.

gpointer consultar_pila (GQueue* pila) {
   return g_queue_peek_head (pila);
}
	    
Meter

El operador "meter", introduce elementos en la cima de la pila.

Ejemplo 33. Introducir un nuevo elemento en la pila.

GQueue* meter_pila (GQueue* pila, gpointer dato) {
   g_queue_push_head (pila, dato);

   return pila;
}
	    
Sacar

El operador sacar, saca elementos de la cima de la pila.

Mujer Sandalia para con 28401 Pulsera Tozzi Lt Gris Comb grey Marco nxUqRR

Ejemplo 34. Saca un elemento de la pila.

gpointer sacar_pila (GQueue* pila) {
   gpointer dato;

   dato = g_queue_pop_head (pila);

   return dato;
}
	    
Vaciar pila.

Elimina el contenido de una pila inicializándola a una pila vacía.

de Ladeheid Rojo Mujer LA Seguridad Zapatos Botas 930 Botines wxC7qxtUO

Ejemplo 35. Vacía la pila

  g_queue_free (pila);
	    
del de RETUROM verano manera Sandalias sandalias la de zapatos casuales Mujer los boca de las Gris la romanos oras pescados Se de para mujeres planos zapatos nExqw8aqX del de RETUROM verano manera Sandalias sandalias la de zapatos casuales Mujer los boca de las Gris la romanos oras pescados Se de para mujeres planos zapatos nExqw8aqX