Menu

Las filas en lenguaje C

ESFRBR
Haz una pregunta

las filas – Primero en Entrar, Primero en salir




Requisitos

Los tipos de datos
Las estructuras
El uso de typedef
Los punteros
Las funciones de usuario

Las listas simplemente enlazadas
Las listas doblemente enlazadas

I. Introducción

El objetivo de este articulo es que el lector comprenda el empleo de las filas.
Para explicar el algoritmo he elegido utilizar una lista enlazada simple. Por lo que la comprensión de las listas enlazadas es necesaria.

II. Definición

La fila es una estructura de datos que permite almacenar datos en el orden FIFO (First In First Out) en español, Primero en Entrar, Primero en Salir).
La recuperación de los datos es hecha en el orden en que son insertados.

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

III. La construcción del 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 ser del mismo tipo que el elemento, de lo contrario no podrá apuntar hacia el elemento.
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, 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;

IV. Operaciones sobre las filas

A. 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;
}

B. 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 la inserción.


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 (1ro, 2do, 3ro, 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;
}

C. 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 1er elemento
  • el puntero inicio apuntará hacia el 2do elemento (después de la eliminación del 1er elemento, el 2do elemento 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;
}

D. Visualización de la fila

Para mostrar la fila entera, es necesario posicionarse al inicio de la fila (el puntero inicio lo permitirá).
Luego, utilizando el puntero siguiente de cada elemento, la fila es recorrida del 1er hacia el ultimo 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;
  }
}

E. Recuperación del dato al inicio de la fila

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

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

V. 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;}

Ver también

Jean-François Pillou

Jean-François Pillou - Fundador de CCM
Mejor conocido como Jeff, Jean-François Pillou es el fundador de CommentCaMarche.net. También es CEO de CCM Benchmark y director digital en el Grupo Figaro.

Más información sobre el equipo de CCM

Consulta también