Cómo programar filas en lenguaje C

Cómo programar filas en lenguaje C

El objetivo de este artículo es que el lector comprenda el empleo de las filas en lenguaje C. Para explicar el algoritmo hemos optado por utilizar una lista enlazada simple.

¿Cuáles son los requisitos previos?

  1. Conocer los tipos de datos.
  2. Las estructuras.
  3. El uso de typedef.
  4. Los punteros.
  5. Las funciones del usuario.
  6. Las listas simplemente enlazadas.
  7. Las listas doblemente enlazadas.

¿Cuál es la definición de una fila?

La fila es una estructura de datos que permite almacenar datos en el orden FIFO (First In First Out). La recuperación de los datos se realiza en el orden en el que son insertados.

Para la implementación hemos elegido una lista enlazada simple. La inserción en la fila se hará en el orden normal, el primer elemento de la fila será el primer elemento ingresado, por lo tanto su posición será al inicio de la fila:

¿Cómo se construye el modelo de un elemento de la fila?

Para definir un elemento de la fila será utilizado el tipo struct.

El elemento de la fila contendrá un campo dato y un puntero siguiente.

El puntero siguiente debe de ser del mismo tipo que el elemento, de lo contrario no podrá apuntar hacia él.

El puntero siguiente permitirá el acceso al próximo elemento:

typedef struct ElementoLista {
    char *dato;
    struct ElementoLista *siguiente;
}Elemento;

Para tener el control de la fila, es preferible guardar ciertos elementos: el primer elemento, el último elemento y el número de elementos.

Para ello será utilizada otra estructura (no es obligatorio, pueden ser utilizadas variables):

typedef struct ListaUbicación{
  Elemento *inicio;
  Elemento *fin;
  int tamaño;
} Fila;

¿Cuáles son las operaciones sobre las filas?

Inicialización

Modelo de la función:

void initialisation (Fila * serie);

Esta operación debe ser hecha antes de cualquier otra operación sobre la fila. Esta inicializa el puntero inicio y el puntero fin con el puntero NULL y el tamaño con el valor 0.

La función:

void inicialización (Fila * serie){
  serie->inicio = NULL;
  serie->fin = NULL;
  serie->tamaño = 0;
}

Inserción

A continuación el algoritmo de inserción y registro de los elementos:

  • Declaración del elemento a insertar.
  • Asignación de la memoria para el nuevo elemento.
  • Rellenar el contenido del campo de datos.
  • Actualizar el puntero inicio hacia el 1er elemento (el inicio de la fila).
  • Actualizar el puntero fin (esto nos servirá para la inserción hacia el final de la fila).
  • Actualizar el tamaño de la pila.

Modelo de la función:

int insertar (Fila * serie, Elemento * actual, char *dato);

La primera imagen muestra el inicio de la inserción, por lo que el tamaño de la lista es 1 después de esta:

En la fila, el elemento a recuperar es el primero en entrar. Por ello, la inserción se hará siempre al final de la fila. Es el orden normal de la inserción (primero, segundo, tercero, etc.):

La función:

int insertar (Fila * serie, Elemento * actual, char *dato){
  Elemento *nuevo_elemento;
  if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento))) == NULL)
    return -1;
  if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof (char)))
      == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);
  if(actual == NULL){
    if(serie->tamaño == 0)
      serie->fin = nuevo_elemento;
    nuevo_elemento->siguiente = serie->inicio;
    serie->inicio = nuevo_elemento;
  }else {
    if(actual->siguiente == NULL)
      serie->fin = nuevo_elemento;
    nuevo_elemento->siguiente = actual->siguiente;
    actual->siguiente = nuevo_elemento;
  }
  serie->tamaño++;
  return 0;
}

Eliminar un elemento de la fila

Para eliminar un elemento de la fila simplemente hay que eliminar el elemento hacia el cual apunta el puntero inicio. Esta operación no permite recuperar el dato al inicio de la fila (el primer dato), solo eliminarlo.

Modelo de la función:

int eliminar (Fila * serie);

La función tiene como resultado -1 en caso de error, si no devuelve 0.

Las etapas:

  • El puntero sup_elemento contendrá la dirección del primer elemento.
  • El puntero inicio apuntará hacia el segundo elemento (después de la eliminación del primero, el segundo estará al inicio de la fila).
  • El tamaño de la fila disminuirá un elemento.

La función:

int eliminar (Fila * serie){
  Elemento *sup_elemento;
  if (serie->tamaño == 0)
    return -1;
  sup_elemento = serie->inicio;
  serie->inicio = serie->inicio->siguiente;
  free (sup_elemento->dato);
  free (sup_elemento);
  serie->tamaño--;
  return 0;
}

Visualización de la fila

Para mostrar la fila entera es necesario posicionarse al inicio de la fila (el puntero inicio lo permitirá). A continuación, utilizando el puntero siguiente de cada elemento, la fila es recorrida del primer hacia el último elemento. La condición para detenerse es dada por el tamaño de la fila.

La función:

void muestra(Fila *serie){
  Elemento *actual;
  int i;
  actual = serie->inicio;
  for(i=0;i<serie->tamaño;++i){
    printf(" %s ", actual->dato);
    actual = actual->siguiente;
  }
}

Recuperación del dato al inicio de la fila

Para recuperar el dato al inicio de la fila sin eliminarlo, utilizaremos una macro. Esta lee los datos al inicio de la fila utilizando el puntero inicio.

#define fila_dato(serie) serie->inicio->dato

¿Cuál es un ejemplo completo?

fila.h

/*      fila.h       */
typedef struct ElementoLista{  
char *dato;  struct ElementoLista *siguiente
;} Elemento;
typedef struct ListaUbicación{  
Elemento *inicio;  Elemento *fin;  int tamaño;
} Fila;

/* inicialización */
void inicialización (Fila * serie);

/* Insertar*/
int insertar (Fila * serie, Elemento * actual, char *dato);

/* Eliminar*/
int eliminar (Fila * serie);

/* FirstInFirstOut */
#define fila_dato(serie) 
serie->inicio->dato

/* Muestra la Fila */
void muestra(Fila *serie);

fila_function.h

/*      fila_function.h       */
void inicialización (Fila * serie){  
serie->inicio = NULL;  
serie->fin = NULL;  
serie->tamaño = 0;}

/* insertar (añadir) un elemento en la Fila */
int insertar (Fila * serie, Elemento * actual, char *dato){  
Elemento *nuevo_elemento;  
if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento))) == NULL)    return -1; 
if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof (char)))      == NULL)    return -1;  strcpy (nuevo_elemento->dato, dato);  
if(actual == NULL){    
if(serie->tamaño == 0)      serie->fin = nuevo_elemento;    
nuevo_elemento->siguiente = serie->inicio;    
serie->inicio = nuevo_elemento;  
}
else 
{    
if(actual->siguiente == NULL)      serie->fin = nuevo_elemento;    
nuevo_elemento->siguiente = actual->siguiente;    
actual->siguiente = nuevo_elemento;  }  
serie->tamaño<gras>;  
return 0;
}

/* eliminar (quitar) un elemento de la Fila */
int eliminar (Fila * serie){ 
Elemento *sup_elemento;  
if (serie->tamaño == 0)    return -1;  
sup_elemento = serie->inicio;  
serie->inicio = serie->inicio->siguiente;  
free (sup_elemento->dato);  
free (sup_elementoo);  
serie->tamaño--; 
return 0;
}

/* visualización de la Fila */
void muestra(Fila *serie){  
Elemento *actual; 
int i;  
actual = serie->inicio;  
for(i=0;i<serie->tamaño;++i){    
printf(" %s ", actual->dato);    
actual = actual->siguiente; 
}
}

fila.c

/*      fila.c       */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "fila.h"
#include "fila_function.h"
int main (){  
Fila *serie;  
char *nom;  
if ((serie = (Fila *) malloc (sizeof (Fila))) == NULL)    return -1;  
if ((nom = (char *) malloc (50 * sizeof (char))) == NULL)    return -1;  
inicialización (serie);  
printf ("Ingrese una palabra: ");  
scanf ("%s", nom);  
insertar (serie, serie->fin, nom);  
printf ("La fila (%de elementos)\n",serie->tamaño);  
printf("\nInicio de la FILA [ ");  
muestra (serie);    
  
/*el primero en entrar será mostrado */  
printf(" ] Fin de la FILA\n\n");  
printf ("Ingrese una palabra: ");  
scanf ("%s", nom);  
insertar (serie, serie->fin, nom);  
printf ("La fila (%de elementos)\n",serie->tamaño);  
printf("\nInicio de la FILA [ ");  
muestra (serie); 
     
/*el primer elemento será mostrado */  
printf(" ] Fin de la FILA\n\n");  
printf ("Ingrese una palabra: ");  
scanf ("%s", nom);  
insertar (serie, serie->fin, nom);  
printf ("La fila (%de elementos)\n",serie->tamaño);  
printf("\nInicio de la FILA [ ");  
muestra (serie);     
 
/*el primero en entrar será mostrado */  
printf(" ] Fin de la FILA\n\n");  
printf ("\nEl primero en entrar (FirstInFirstOut) [ %s ] será eliminado",                    fila_dato(serie));  
printf ("\nEl primer en entrar es eliminado\n");  
eliminar (serie);     
        
 /* eliminación del primer elemento ingresado */  
printf ("La fila (%de elementos): \n",serie->tamaño);  
printf("\nInicio de la FILA [ ");  
muestra (serie);  
printf(" ] Fin de la FILA\n\n");  
return 0;
}
Alrededor del mismo tema

Lenguajes