Haz una pregunta »

Las filas en lenguaje C

Abril 2015


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 devuelve -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


Consulta este artículo sin tener que estar conectado, descárgalo gratis aquí en formato PDF:
Las-filas-en-lenguaje-c.pdf

Consulta también

En la misma categoría

Les files en langage C
Por lami20j el 7 de diciembre de 2007
As filas em linguagem C
Por pintuda el 26 de octubre de 2011
El artículo original fue escrito por lami20j. Traducido por Carlos-vialfa.
El documento « Las filas en lenguaje C » de Kioskea (es.kioskea.net) se encuentra disponible bajo una licencia Creative Commons. Puedes copiarlo o modificarlo bajo las condiciones señaladas por esta licencia. Deberás hacerla siempre visible y dar crédito a Kioskea.