EJEMPLO - CONSTRUCCIÓN DE PILAS Y COLAS BASADAS EN LISTAS ENLAZADAS.



Análisis del problema
El concepto de pila y de co la se deriva fácilmente del de lista enlazada. Según se ha podido observar, en una lista enlazada es posible añadir información de manera muy flexible. Concretamente, se puede añadir o eliminar información: Una pila es la estructura de datos que se obtiene al limitar la adición o eliminación de elementos a uno de los extremos de una lista enlazada. Esto es, en una pila sólo se admite añadir y eliminar información por el principio (se puede hacer por el final, pero es menos eficiente).
Una cola es la estructura de datos que se obtiene al limitar la adición y eliminación de información en una lista de tal modo que sólo se admite la adición al principio de la lista, y la eliminación al final de la lista.

Diseño del programa


El método empleado para construir este programa consiste en utilizar una lista enlazada, ya creada anteriormente, y reducir las opciones al mínimo necesario. Concretamente, las opciones necesarias para la pila van a ser: El programa de lista enlazada ofrece muchas opciones innecesarias. Comenzaremos, por tanto, por rehacer el menú mostrado al usuario. Este puede quedar en la forma siguiente: 
P)oner Q)uitar V)er B)orrar H)Ayuda S)alir

Teniendo en cuent la definición de una pila, vamos a recurrir a la adición y eliminación de elementos por el mismo extremo. Por eficiente, seleccionaremos la adición y elimintación por el principio, aunque sería equivalente efectuar la adición y eliminación por el final.

Dado que únicamente se necesitan las opcione 1, 4, 7 y 8, se descartan todas las demás. Por tanto, eliminamos tanto los prototipos como los cuerpos de función (en listaenlazada.h y listaenlazada.c ). Hacemos esto para reducir al mínimo el tamaño del programa, auqnue basta con descartar las opciones y funciones innecesarias en main.c (sin modificar listaenlazada.h ni listaenlazada.c ). El resultado final es el programa que puede verse en la sección siguiente.

Implementación
En este ejercicio se omiten los archivos utiles.h y utiles.c, sobradamente conocidos. Se incluyen, por tanto, los archivos siguientes:
listaenlazada.h 
#ifndef __LISTAENLAZADA__
#define __LISTAENLAZADA__
/*
 Esta declaración de nodo es la más sencilla posible.
 En una aplicación real el nodo contendrá muchos más campos,
 como corresponde a un registro de una base de datos.
*/

typedef struct Nodo {
 int valor;
 struct Nodo * sig;
} Nodo;

typedef struct Lista {
 Nodo * ppio;
 Nodo * fin;
} Lista;

void leer_nodo(Nodo *);
void escribir_nodo(Nodo *);

void insertar_ppio(Lista * pl);
void insertar_final(Lista * pl);
void insertar_ordenado(Lista * pl);
void borrar_principio(Lista * pl);
void borrar_final(Lista * pl);
void borrar_buscando(Lista * pl);
void ver_lista(Lista * pl);
void borrar_lista(Lista * pl);
void duplicar_lista(Lista * pl);

#endif
main.h 
#ifndef __PROGRAMAPRINCIPAL__
#define __PROGRAMAPRINCIPAL__

typedef struct Global {
 Lista * lista;
} Global;

typedef void (*pfuncion)(Global *);

void dispatcher( char * pm, char * ov[], struct Global * pg, pfuncion pf[]);
void iniciacion(Global * pg, int argc, char * argv[]);
void terminacion(Global * pg);
void ayuda(Global * pg);

void opcion_1(Global * pg);
void opcion_4(Global * pg);
void opcion_7(Global * pg);
void opcion_8(Global * pg);
void salir(Global * pg);
void volver(Global * pg);

#endif
main.c 
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
#include "utiles.h"
#include "listaenlazada.h"
#include  "main.h"

int main(int argc, char * argv[])
{
  Global * pg = (Global *)malloc(sizeof(Global));
  pfuncion pfun[] = {
            &opcion_1, /* Ojo : orden de funciones */
            &opcion_4, /*  igual a orden de opciones válidas */
            &opcion_7,
            &opcion_8,
            &ayuda, /* "H" */
            &salir, /* "S" */
            NULL
           };
 char * opcionesvalidas[] = {
                "1", /* Ojo al orden de opciones  */
                "4",
                "7",
                "8",
                "H",
                "S"
               };
 /* El menú de pila se reduce a cuatro opciones, más las
  ya habituales opciones de Ayuda y de Salida.
 */
 char * menu =  "PILAS\n\n\
 • 1.- Poner (push).\n\
 • 4.- Quitar (pop).\n\
 • 7.- Ver toda la pila.\n\
 • 8.- Borrar toda la pila.\n\
 • H.- Ayuda.\n\
 • S.- Salir.";

 iniciacion(pg, argc, argv);
  dispatcher( menu,
        opcionesvalidas,
        pg,
        pfun);
  terminacion(pg);
  puts("\n\nThat's all folks!\n");
  return 0;
}

/*
 Todas las opciones residen en listaenlazada.c
*/
void dispatcher( char * pm, char * ov[], Global * pg, pfuncion pf[])
{
  char * temp = NULL;     /* Para leer la instrucción */
  int instruccion;           /* dada por el usuario                      */
  int num_opciones = 0;
  int i;

  /* Recuento de opciones */
  while(pf[num_opciones] != NULL)
   num_opciones++;
  /* Bucle principal de ejecución */
  do
   {
      printf("%s ", pm);
   temp = sgets();
   instruccion = -1;
   /*
    Ahora se busca la instrucción dada entre las posibles instrucciones
    válidas. De este modo se halla el número de instrucción solicitado,
    que servirá como índice de función. Si no se encuentra la instrucción,
    el índice no es válido y se llama a volver, que no hace nada,
    y siempre es la última opción.
   */
   for(i=0;i<num_opciones;i++)/* Ojo a las instrucciones vacías */
    if(0==strcasecmp(ov[i],temp))
     {
      instruccion = i;
      break;
     }
   system(BORRAR);
     if (-1 != instruccion)
      pf[instruccion](pg);
     else
      printf("%c", 7);
   free(temp);
   temp = NULL;
    }
    while (&salir != pf[instruccion]);

} /* Fin de dispatcher() */
void iniciacion(Global * pg, int argc, char * argv[])
{
  pg->lista = malloc(sizeof(Lista));
  pg->lista->ppio = NULL; /* Al comenzar NO hay nodos */
  pg->lista->fin = NULL;   /* Al comenzar NO hay nodos */
}

void terminacion(Global * pg)
{
  borrar_lista(pg->lista); /* Aunque no es preciso, liberamos todos los nodos
           de la lista. En una base de datos, sería preciso
           ofrecer la opción de guardar la información
           en disco.
         */
}

void volver(struct Global * pg)
{
 return;
}
void ayuda(Global * pg)
{
 /* Vamos a mostrar los valores y direcciones de todas
 las variables (y nodos) del programa.*/
 Nodo * temp;
 Lista * pl = pg->lista;
 printf("\n\nProceso de ayuda.\n\n");
 printf("\n\npg vale        : $%p\n", pg);
 printf("pl->ppio vale  : $%p\n", pl->ppio);
 printf("pl->fin vale   : $%p\n", pl->fin);
 if (NULL == pl->ppio)
  {
   /* La lista está vacía */
   printf("\n\nLa lista está vacía.\n\n");
  }
 else
  {
   printf("\n\nContenido de la lista (izquierda primero).\n\n");
   temp = pl->ppio;
   do {
    printf("Dir. nodo: $%p - Valor almacenado: %d - Dir. nodo siguiente: $%p\n",
     temp, temp->valor,temp->sig);
    temp = temp->sig;
   } while (temp); /* En el último elemento, el campo sig es cero */
   printf("\n\n");
  }
}
void salir(Global * pg)
{

 /* Si hubiera cambios que guardar, este sería el lugar */
 return;
}
void opcion_1(Global * pg)
{
 insertar_ppio(pg->lista);
}

void opcion_4(Global * pg)
{
 borrar_principio(pg->lista);
}

void opcion_7(Global * pg)
{
 ver_lista(pg->lista);
}

void opcion_8(Global * pg)
{
 borrar_lista(pg->lista);
}
listaenlazada.c 
#include <stdlib.h>
#include "utiles.h"
#include "listaenlazada.h"

void leer_nodo(Nodo * pn)
{
  char  * temp;
  temp = pedir("\n\nEscriba el número entero que se\
almacenará en este nodo:\n\n");
  pn->valor = strtol(temp,0,10);
  /*
    Liberamos temp para que no haya fugas de memoria
  */
  free(temp);
  pn->sig = NULL; /* Por seguridad */
  printf("\n");
}
void escribir_nodo(Nodo * pn)
{
  printf("%6d", pn->valor);
}
/*  • 1.- Insertar nodo al principio. */
void insertar_ppio(Lista * pl)
{
  Nodo * temp;
  temp = (Nodo *)malloc(sizeof(Nodo));
  if (temp!=NULL) /* Hay espacio para el nodo nuevo */
    {
      printf("\n\nAdición de un nodo al principio de la lista.\n\n");
      leer_nodo(temp);
      if (NULL == pl->ppio)
        {
          /*
            La lista estaba vacía y pasa a tener un solo nodo.
            Tanto ppio como fin apuntan a ese nodo.
            El elemento siguiente no existe, luego se da al
            puntero sig el valor NULL.
          */
          pl->ppio = temp;
          pl->fin = temp;
          pl->ppio->sig = NULL;
        }
      else
        {
          /* La lista no está vacía. El nodo recién creado pasa
          a ocupar la primera posición. Si hay un sólo nodo,
          pasamos a tener dos, y el puntero de fin ya
          tiene valor correcto. Si había dos o más nodos,
          pasamos a tener tres o más nodos, y el puntero de fin
          también tiene valor correcto. */
          temp->sig = pl->ppio;
          pl->ppio = temp; /* El nodo pasa a ser la nueva ppio*/
        }
    }
  else
    printf("\n\nSALIENDO- No hay espacio para añadir un nodo al principio.\n\n");
}
/*  • 2.- Insertar nodo al final. */
void insertar_final(Lista * pl)
{
  Nodo * temp;
  temp = (Nodo *)malloc(sizeof(Nodo));
  if (temp!=NULL)
    {
      printf("\n\nAdición de un nodo al final de la lista.\n\n");
      leer_nodo(temp);
      if (NULL == pl->ppio)
        {
          /*
            La lista estaba vacía y pasa a tener un solo nodo.
            Tanto ppio como fin apuntan a ese nodo.
            El elemento siguiente no existe, luego se da al
            puntero sig el valor 0.
          */
          pl->ppio = temp;
          pl->fin = temp;
          pl->ppio->sig = NULL;
        }
      else
        {
          /* La lista no está vacía. El nodo recién creado pasa
          a ocupar la última posición */
          pl->fin->sig = temp;
          pl->fin = temp; /* El nodo pasa a ser el nuevo fin*/
          temp->sig = NULL; /* No hay un siguiente del último elemento */
        }
    }
  else
    printf("\n\nSALIENDO- No hay espacio para añadir un nodo al final.");
}
/*  • 3.- Insertar nodo buscando su posición. */
void insertar_ordenado(Lista * pl)
{
  Nodo * temp, *anterior, *posterior;
  temp = (Nodo *)malloc(sizeof(Nodo));
  if (temp)
    {
      printf("\n\nInserción de un nodo buscando su posición.\n\n");
      leer_nodo(temp);
      if (NULL == pl->ppio)
        {
          /*
            La lista estaba vacía y pasa a tener un solo nodo.
            Tanto ppio como fin apuntan a ese nodo.
            El elemento siguiente no existe, luego se da al
            puntero sig el valor 0.
          */
          pl->ppio = temp;
          pl->fin = temp;
          pl->ppio->sig = 0;
        }
      else
        {
          /* La lista no está vacía. El nodo recién creado debe
          ocupar una posición dada por su valor. Suponemos que
          la lista está ordenada de modo ascendente (el nodo de
          valor más pequeño está a la izquierda del todo).
          Por tanto, primero se verifica si el valor del nodo
          recién leído es anterior al valor situado en la ppio;
          de ser así, se pone nuestro nodo como ppio.
          Si nuestro nodo no es anterior a la ppio, quizá esté
          por detrás de la fin (a la derecha del todo). Si es
          así, se pone al final del todo.
          Por último, si no está ni antes que la ppio ni después
          de la fin, ocupa una posición intermedia. Esa posición
          se busca, y se inserta el nodo adecuadamente. */
          /* Veamos si está antes del principio */
          if (temp->valor <= pl->ppio->valor)
            {
              temp->sig = pl->ppio;
              pl->ppio = temp;
            }
          else
          /* Veamos si está despues del final */
            if (temp->valor >= pl->fin->valor)
              {
                pl->fin->sig = temp;
                pl->fin = temp;
                pl->fin->sig = NULL;
              }
            else
          /* Busquemos su posición-como mínimo hay dos nodos en la lista */
              {
                /* Para que el nodo esté en posición correcta, su valor
                debe ser mayor o igual que el del nodo de su izquierda,
                (anterior)y menor o igual que el valor del nodo de su
                derecha (posterior)*/
                anterior = pl->ppio;
                posterior = pl->ppio->sig;
                while(!(temp->valor >= anterior->valor && temp->valor <= posterior->valor))
                  {
                    anterior = posterior;
                    posterior = posterior->sig;
                  }
                /* Al llegar aquí, hay que insertar temp entre anterior y posterior */
                temp->sig = posterior;
                anterior->sig = temp;
              }
        }
    }
  else
    printf("\n\nSALIENDO- No hay espacio para añadir un nodo al principio.");
}
/*  • 4.- Borrar nodo al principio. */
void borrar_principio(Lista * pl)
{
  Nodo * temp;
  if (NULL == pl->ppio)
    printf("\n\nLa lista está vacía.\n\n");
  else
    {
      if (NULL != pl->ppio->sig) /* No es el único nodo */
        {
          temp = pl->ppio;
          pl->ppio = pl->ppio->sig;
          free(temp);
        }
      else /* Es el último nodo */
        {
          free(pl->ppio);
          pl->ppio = NULL;
          pl->fin = NULL;
        }
    }
  printf("\n\nNodo inicial borrado.\n\n");
}
/*  • 5.- Borrar nodo al final. */
void borrar_final(Lista * pl)
{
  Nodo * temp;
  if (NULL == pl->ppio)
    printf("\n\nLa lista está vacía.\n\n");
  else
    {
      if (NULL == pl->ppio->sig) /* Hay un solo nodo */
        {
          printf("\n\nEl valor del nodo borrado es: ");
          escribir_nodo(pl->ppio);
          free(pl->ppio);
          pl->ppio = NULL;
          pl->fin = NULL;
        }
      else
        {
          /* Hay que buscar el nodo anterior al final */
          temp = pl->ppio;
          while (temp->sig != pl->fin)
            {
              temp = temp->sig;
            }
          /* Al llegar aquí, temp apunta al nodo anterior a fin */
          printf("\n\nEl valor del nodo borrado es: ");
          escribir_nodo(pl->fin);
          printf("\n");
          free(pl->fin);
          pl->fin = temp;
          temp->sig = NULL;
        }
    }
  printf("\n\nNodo final borrado.\n\n");
}
/*  • 6.- Borrar un nodo tras buscarlo. */
void borrar_buscando(Lista * pl)
{
  /* Se trata de tomar un valor y buscarlo en la lista. Si
  se encuentra en algún nodo, se elimina ese nodo. Si no
  se encuentra en ningún nodo, se advierte al usuario.
  Este sería el mecanismo necesario para quitar una tarea
  de una cola, por ejemplo la de impresión. */
  int buscado;
  Nodo *temp, *indice, *anterior;
  if (NULL == pl->ppio)
    {
      printf("\n\nPerdón, la lista está vacía.\n\n");
      return;
    }
  printf("\n\nEscriba el valor que quiere borrar: ");
  scanf("%d%*c", &buscado);

  if (pl->ppio == pl->fin) /* Hay un solo nodo */
    {
      if (buscado == pl->ppio->valor)
        {
          free(pl->ppio);
          pl->ppio = NULL;
          pl->fin = NULL;
        }
      else
        printf("No se encontró el valor.");
    }
  else /*Hay dos nodos o más */
    {
      if (buscado == pl->ppio->valor)
        {
          temp = pl->ppio;
          pl->ppio = pl->ppio->sig;
          free(temp);
        }
      else
        if (buscado == pl->fin->valor)
          {
            indice = pl->ppio;
            while(indice->sig != pl->fin)
              {
                indice = indice->sig;
              }
            free(pl->fin);
            pl->fin = indice;
            pl->fin->sig=NULL;
          }
        else /*Puede estar en posición intermedia; no es el primero ni el último */
          {
            anterior = pl->ppio;
            for(indice=anterior->sig;indice!=pl->fin;indice=indice->sig)
              {
                if (buscado == indice->valor)
                  {
                    anterior->sig = indice->sig;
                    free(indice);
                    return;
                  }
                anterior = anterior->sig;
              }
            if (indice == pl->fin)
              printf("No se encontró el valor.");
          }
    }
}
/*  • 7.- Ver toda la lista. */
 void ver_lista(Lista * pl)
{
  Nodo * temp;
  if (NULL == pl->ppio)
    {
      /* La lista está vacía */
      printf("\n\nPerdón, la lista está vacía.\n\n");
    }
  else
    {
      printf("\n\nContenido de la lista (izquierda primero).\n\n");
      temp = pl->ppio;
      do {
        escribir_nodo(temp);
        temp = temp->sig;
      } while (NULL != temp); /* En el último elemento, el campo sig es cero */
      printf("\n\n");
    }
}
/*  • 8.- Borrar toda la lista. */
void borrar_lista(Lista * pl)
{
  /* No hay otro remedio que ir hasta el penúltimo elemento,
  borrarlo, y repetir el proceso de ir al penúltimo elemento
  hasta que no queden nodos. Si construyésemos una lista
  formada por nodos con dos enlaces, uno hacia la derecha
  y otro hacia la izquierda... (véanse las listas
  doblemente enlazadas) */
  Nodo *temp, *penultimo;
  if (NULL == pl->ppio)
    {
      /* La lista está vacía */
      printf("\n\nPerdón, la lista está vacía.\n\n");
    }
  else
    {
      if(NULL == pl->ppio->sig)
        {
          /* Hay un solo elemento */
          free(pl->ppio);
          pl->ppio = 0;
          pl->fin = 0;
        }
      else
        {
          do
            {
              penultimo = pl->ppio;
              temp = pl->ppio->sig;
              while(NULL != temp->sig)
                {
                  penultimo = temp;
                  temp = temp->sig;
                }
              free(temp);
              penultimo->sig = NULL;
            } while (penultimo != pl->ppio);
            free(pl->ppio);
            pl->ppio = NULL;
            pl->fin = NULL;
        }
      printf("\n\nLa lista se ha borrado.\n\n");
    }
}
/*  • 9.- Duplicar una lista. */
void duplicar_lista(Lista * pl)
{
  Lista * lista_local; /* Para manejar la otra lista */
  Nodo * tg,*tl;
  if (NULL == pl->ppio)
    {
      printf("\n\nImposible duplicar - lista vacía.\n\n");
    }
  else
    {
      lista_local = malloc(sizeof(Lista));
      tg = pl->ppio;
      tl = (Nodo *)malloc(sizeof(Nodo));
      tl->valor = tg->valor;
      tl->sig = NULL;
      lista_local->ppio = tl;
      lista_local->fin = tl;
      tg = tg->sig;
      while (tg)
        {
          tl = (Nodo *)malloc(sizeof(Nodo));
          tl->valor = tg->valor;
          tl->sig = 0;
          lista_local->fin->sig = tl;
          lista_local->fin = tl;
          tg=tg->sig;
        }
      /* Ya tenemos toda la lista copiada.
      Vamos a verificarlo llamando a una de las opciones y pasándole
      el nuevo parámetro (local)*/
      printf("\n\nLISTA LOCAL - ");
      ver_lista(lista_local);
      /* Y después borramos la lista */
      borrar_lista(lista_local);
      free(lista_local);
    }
}
makefile 
OBJECTS = main.o utiles.o listaenlazada.o
pila: $(OBJECTS)
 cc $(OBJECTS) -o pila

utiles.o: utiles.c utiles.h
 cc -c utiles.c -o utiles.o

main.o: main.c utiles.h main.h
 cc -c main.c

listaenlazada.o: listaenlazada.c listaenlazada.h
 cc -c listaenlazada.c

clean:
 rm -f utiles.o
 rm -f *.o
 rm -f pila


Implementación de una cola


Como puede observarse en el programa anterior, el diseño de la lista enlazada y el diseño del programa principal están acoplados. Esto dificulta el uso de listaenlazada.c como biblioteca independiente, que es nuestro objetivo. Por tanto, vamos a rediseñar listaenlazada.c (básicamente se trata de cambiar los nombres de sus opciones) y main.c (haciendo que opcion_i sea una función intermedia que llama a los elementos necesarios de listaenlazada.c ). De este modo listaenlazada.c se desacopla por completo de main.c , y el programa núcleo se hace más flexible. Estamos facilitando de este modo el uso de bibliotecas.

Los ficheros que vamos a mostrar son los siguientes: Véase a continuación la implementación de la cola.
makefile 
OBJECTS = main.o utiles.o listaenlazada.o
cola: $(OBJECTS)
	cc $(OBJECTS) -o cola

utiles.o: utiles.c utiles.h
	cc -c utiles.c -o utiles.o

main.o: main.c utiles.h main.h
	cc -c main.c

listaenlazada.o: listaenlazada.c listaenlazada.h
	cc -c listaenlazada.c

clean:
	rm -f utiles.o
	rm -f *.o
	rm -f cola
listaenlazada.h 
#ifndef __LISTAENLAZADA__
#define __LISTAENLAZADA__
/*
	Esta declaración de nodo es la más sencilla posible.
	En una aplicación real el nodo contendrá muchos más campos,
	como corresponde a un registro de una base de datos.
*/

typedef struct Nodo {
	int valor;
	struct Nodo * sig;
} Nodo;

typedef struct Lista {
	Nodo * ppio;
	Nodo * fin;
} Lista;

void leer_nodo(Nodo *);
void escribir_nodo(Nodo *);

void insertar_ppio(Lista * pl);
void insertar_final(Lista * pl);
void insertar_ordenado(Lista * pl);
void borrar_principio(Lista * pl);
void borrar_final(Lista * pl);
void borrar_buscando(Lista * pl);
void ver_lista(Lista * pl);
void borrar_lista(Lista * pl);
void duplicar_lista(Lista * pl);

#endif
listaenlazada.c 
#include <stdlib.h>
#include "utiles.h"
#include "listaenlazada.h"

void leer_nodo(Nodo * pn)
{
  char  * temp;
  temp = pedir("\n\nEscriba el número entero que se\
almacenará en este nodo:\n\n");
  pn->valor = strtol(temp,0,10);
  /*
    Liberamos temp para que no haya fugas de memoria
  */
  free(temp);
  pn->sig = NULL; /* Por seguridad */
  printf("\n");
}
void escribir_nodo(Nodo * pn)
{
  printf("%6d", pn->valor);
}
/*  • 1.- Insertar nodo al principio. */
void insertar_ppio(Lista * pl)
{
  Nodo * temp;
  temp = (Nodo *)malloc(sizeof(Nodo));
  if (temp!=NULL) /* Hay espacio para el nodo nuevo */
    {
      printf("\n\nAdición de un nodo al principio de la lista.\n\n");
      leer_nodo(temp);
      if (NULL == pl->ppio)
        {
          /*
            La lista estaba vacía y pasa a tener un solo nodo.
            Tanto ppio como fin apuntan a ese nodo.
            El elemento siguiente no existe, luego se da al
            puntero sig el valor NULL.
          */
          pl->ppio = temp;
          pl->fin = temp;
          pl->ppio->sig = NULL;
        }
      else
        {
          /* La lista no está vacía. El nodo recién creado pasa
          a ocupar la primera posición. Si hay un sólo nodo,
          pasamos a tener dos, y el puntero de fin ya
          tiene valor correcto. Si había dos o más nodos,
          pasamos a tener tres o más nodos, y el puntero de fin
          también tiene valor correcto. */
          temp->sig = pl->ppio;
          pl->ppio = temp; /* El nodo pasa a ser la nueva ppio*/
        }
    }
  else
    printf("\n\nSALIENDO- No hay espacio para añadir un nodo al principio.\n\n");
}
/*  • 2.- Insertar nodo al final. */
void insertar_final(Lista * pl)
{
  Nodo * temp;
  temp = (Nodo *)malloc(sizeof(Nodo));
  if (temp!=NULL)
    {
      printf("\n\nAdición de un nodo al final de la lista.\n\n");
      leer_nodo(temp);
      if (NULL == pl->ppio)
        {
          /*
            La lista estaba vacía y pasa a tener un solo nodo.
            Tanto ppio como fin apuntan a ese nodo.
            El elemento siguiente no existe, luego se da al
            puntero sig el valor 0.
          */
          pl->ppio = temp;
          pl->fin = temp;
          pl->ppio->sig = NULL;
        }
      else
        {
          /* La lista no está vacía. El nodo recién creado pasa
          a ocupar la última posición */
          pl->fin->sig = temp;
          pl->fin = temp; /* El nodo pasa a ser el nuevo fin*/
          temp->sig = NULL; /* No hay un siguiente del último elemento */
        }
    }
  else
    printf("\n\nSALIENDO- No hay espacio para añadir un nodo al final.");
}
/*  • 3.- Insertar nodo buscando su posición. */
void insertar_ordenado(Lista * pl)
{
  Nodo * temp, *anterior, *posterior;
  temp = (Nodo *)malloc(sizeof(Nodo));
  if (temp)
    {
      printf("\n\nInserción de un nodo buscando su posición.\n\n");
      leer_nodo(temp);
      if (NULL == pl->ppio)
        {
          /*
            La lista estaba vacía y pasa a tener un solo nodo.
            Tanto ppio como fin apuntan a ese nodo.
            El elemento siguiente no existe, luego se da al
            puntero sig el valor 0.
          */
          pl->ppio = temp;
          pl->fin = temp;
          pl->ppio->sig = 0;
        }
      else
        {
          /* La lista no está vacía. El nodo recién creado debe
          ocupar una posición dada por su valor. Suponemos que
          la lista está ordenada de modo ascendente (el nodo de
          valor más pequeño está a la izquierda del todo).
          Por tanto, primero se verifica si el valor del nodo
          recién leído es anterior al valor situado en la ppio;
          de ser así, se pone nuestro nodo como ppio.
          Si nuestro nodo no es anterior a la ppio, quizá esté
          por detrás de la fin (a la derecha del todo). Si es
          así, se pone al final del todo.
          Por último, si no está ni antes que la ppio ni después
          de la fin, ocupa una posición intermedia. Esa posición
          se busca, y se inserta el nodo adecuadamente. */
          /* Veamos si está antes del principio */
          if (temp->valor <= pl->ppio->valor)
            {
              temp->sig = pl->ppio;
              pl->ppio = temp;
            }
          else
          /* Veamos si está despues del final */
            if (temp->valor >= pl->fin->valor)
              {
                pl->fin->sig = temp;
                pl->fin = temp;
                pl->fin->sig = NULL;
              }
            else
          /* Busquemos su posición-como mínimo hay dos nodos en la lista */
              {
                /* Para que el nodo esté en posición correcta, su valor
                debe ser mayor o igual que el del nodo de su izquierda,
                (anterior)y menor o igual que el valor del nodo de su
                derecha (posterior)*/
                anterior = pl->ppio;
                posterior = pl->ppio->sig;
                while(!(temp->valor >= anterior->valor && temp->valor <= posterior->valor))
                  {
                    anterior = posterior;
                    posterior = posterior->sig;
                  }
                /* Al llegar aquí, hay que insertar temp entre anterior y posterior */
                temp->sig = posterior;
                anterior->sig = temp;
              }
        }
    }
  else
    printf("\n\nSALIENDO- No hay espacio para añadir un nodo al principio.");
}
/*  • 4.- Borrar nodo al principio. */
void borrar_principio(Lista * pl)
{
  Nodo * temp;
  if (NULL == pl->ppio)
    printf("\n\nLa lista está vacía.\n\n");
  else
    {
      if (NULL != pl->ppio->sig) /* No es el único nodo */
        {
          temp = pl->ppio;
          pl->ppio = pl->ppio->sig;
          free(temp);
        }
      else /* Es el último nodo */
        {
          free(pl->ppio);
          pl->ppio = NULL;
          pl->fin = NULL;
        }
    }
  printf("\n\nNodo inicial borrado.\n\n");
}
/*  • 5.- Borrar nodo al final. */
void borrar_final(Lista * pl)
{
  Nodo * temp;
  if (NULL == pl->ppio)
    printf("\n\nLa lista está vacía.\n\n");
  else
    {
      if (NULL == pl->ppio->sig) /* Hay un solo nodo */
        {
          printf("\n\nEl valor del nodo borrado es: ");
          escribir_nodo(pl->ppio);
          free(pl->ppio);
          pl->ppio = NULL;
          pl->fin = NULL;
        }
      else
        {
          /* Hay que buscar el nodo anterior al final */
          temp = pl->ppio;
          while (temp->sig != pl->fin)
            {
              temp = temp->sig;
            }
          /* Al llegar aquí, temp apunta al nodo anterior a fin */
          printf("\n\nEl valor del nodo borrado es: ");
          escribir_nodo(pl->fin);
          printf("\n");
          free(pl->fin);
          pl->fin = temp;
          temp->sig = NULL;
        }
    }
  printf("\n\nNodo final borrado.\n\n");
}
/*  • 6.- Borrar un nodo tras buscarlo. */
void borrar_buscando(Lista * pl)
{
  /* Se trata de tomar un valor y buscarlo en la lista. Si
  se encuentra en algún nodo, se elimina ese nodo. Si no
  se encuentra en ningún nodo, se advierte al usuario.
  Este sería el mecanismo necesario para quitar una tarea
  de una cola, por ejemplo la de impresión. */
  int buscado;
  Nodo *temp, *indice, *anterior;
  if (NULL == pl->ppio)
    {
      printf("\n\nPerdón, la lista está vacía.\n\n");
      return;
    }
  printf("\n\nEscriba el valor que quiere borrar: ");
  scanf("%d%*c", &buscado);

  if (pl->ppio == pl->fin) /* Hay un solo nodo */
    {
      if (buscado == pl->ppio->valor)
        {
          free(pl->ppio);
          pl->ppio = NULL;
          pl->fin = NULL;
        }
      else
        printf("No se encontró el valor.");
    }
  else /*Hay dos nodos o más */
    {
      if (buscado == pl->ppio->valor)
        {
          temp = pl->ppio;
          pl->ppio = pl->ppio->sig;
          free(temp);
        }
      else
        if (buscado == pl->fin->valor)
          {
            indice = pl->ppio;
            while(indice->sig != pl->fin)
              {
                indice = indice->sig;
              }
            free(pl->fin);
            pl->fin = indice;
            pl->fin->sig=NULL;
          }
        else /*Puede estar en posición intermedia; no es el primero ni el último */
          {
            anterior = pl->ppio;
            for(indice=anterior->sig;indice!=pl->fin;indice=indice->sig)
              {
                if (buscado == indice->valor)
                  {
                    anterior->sig = indice->sig;
                    free(indice);
                    return;
                  }
                anterior = anterior->sig;
              }
            if (indice == pl->fin)
              printf("No se encontró el valor.");
          }
    }
}
/*  • 7.- Ver toda la lista. */
 void ver_lista(Lista * pl)
{
  Nodo * temp;
  if (NULL == pl->ppio)
    {
      /* La lista está vacía */
      printf("\n\nPerdón, la lista está vacía.\n\n");
    }
  else
    {
      printf("\n\nContenido de la lista (izquierda primero).\n\n");
      temp = pl->ppio;
      do {
        escribir_nodo(temp);
        temp = temp->sig;
      } while (NULL != temp); /* En el último elemento, el campo sig es cero */
      printf("\n\n");
    }
}
/*  • 8.- Borrar toda la lista. */
void borrar_lista(Lista * pl)
{
  /* No hay otro remedio que ir hasta el penúltimo elemento,
  borrarlo, y repetir el proceso de ir al penúltimo elemento
  hasta que no queden nodos. Si construyésemos una lista
  formada por nodos con dos enlaces, uno hacia la derecha
  y otro hacia la izquierda... (véanse las listas
  doblemente enlazadas) */
  Nodo *temp, *penultimo;
  if (NULL == pl->ppio)
    {
      /* La lista está vacía */
      printf("\n\nPerdón, la lista está vacía.\n\n");
    }
  else
    {
      if(NULL == pl->ppio->sig)
        {
          /* Hay un solo elemento */
          free(pl->ppio);
          pl->ppio = 0;
          pl->fin = 0;
        }
      else
        {
          do
            {
              penultimo = pl->ppio;
              temp = pl->ppio->sig;
              while(NULL != temp->sig)
                {
                  penultimo = temp;
                  temp = temp->sig;
                }
              free(temp);
              penultimo->sig = NULL;
            } while (penultimo != pl->ppio);
            free(pl->ppio);
            pl->ppio = NULL;
            pl->fin = NULL;
        }
      printf("\n\nLa lista se ha borrado.\n\n");
    }
}
/*  • 9.- Duplicar una lista. */
void duplicar_lista(Lista * pl)
{
  Lista * lista_local; /* Para manejar la otra lista */
  Nodo * tg,*tl;
  if (NULL == pl->ppio)
    {
      printf("\n\nImposible duplicar - lista vacía.\n\n");
    }
  else
    {
      lista_local = malloc(sizeof(Lista));
      tg = pl->ppio;
      tl = (Nodo *)malloc(sizeof(Nodo));
      tl->valor = tg->valor;
      tl->sig = NULL;
      lista_local->ppio = tl;
      lista_local->fin = tl;
      tg = tg->sig;
      while (tg)
        {
          tl = (Nodo *)malloc(sizeof(Nodo));
          tl->valor = tg->valor;
          tl->sig = 0;
          lista_local->fin->sig = tl;
          lista_local->fin = tl;
          tg=tg->sig;
        }
      /* Ya tenemos toda la lista copiada.
      Vamos a verificarlo llamando a una de las opciones y pasándole
      el nuevo parámetro (local)*/
      printf("\n\nLISTA LOCAL - ");
      ver_lista(lista_local);
      /* Y después borramos la lista */
      borrar_lista(lista_local);
      free(lista_local);
    }
}
main.h 
#ifndef __PROGRAMAPRINCIPAL__
#define __PROGRAMAPRINCIPAL__

typedef struct Global {
  Lista * lista;
} Global;

typedef void (*pfuncion)(Global *);

void dispatcher( char * pm, char * ov[], struct Global * pg, pfuncion pf[]);
void iniciacion(Global * pg, int argc, char * argv[]);
void terminacion(Global * pg);
void ayuda(Global * pg);

void salir(Global * pg);
void volver(Global * pg);
/*
  No necesitamos las opciones 2, 3, 4, 6 y 9
*/
void opcion_1(Global * pg);
/*
void opcion_2(Global * pg);
void opcion_3(Global * pg);
void opcion_4(Global * pg);
*/
void opcion_5(Global * pg);
/*
void opcion_6(Global * pg);
*/
void opcion_7(Global * pg);
void opcion_8(Global * pg);
/*
void opcion_9(Global * pg);
*/
#endif
main.c 
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
#include  "utiles.h"
#include "listaenlazada.h"
#include "main.h"
/*
  Implementación de una cola basada en una lista
  simplemente enlazada
*/
int main(int argc, char * argv[])
{
  Global * pg = (Global *)malloc(sizeof(Global));
  pfuncion pfun[] = {
                      &opcion_1,  /* Ojo: el orden de funciones tiene que ser */
                      &opcion_5,  /* igual al orden de opciones válidas */
                      &opcion_7,
                      &opcion_8,
                      &ayuda, /* "H" */
                      &salir, /* "S" */
                      NULL
                    };
  char * opcionesvalidas[] = {
                                "1", /* Ojo: el orden de opciones tiene que   */
                                "5",  /* ser igual al orden de funciones */
                                "7",
                                "8",
                                "H",
                                "S"
                              };

  char * menu =   "Cola basada en una lista enlazada\n\n\
  • 1.- Poner en cola (enqueue).\n\
  • 5.- Quitar de cola (dequeue).\n\
  • 7.- Ver toda la cola.\n\
  • 8.- Borrar toda la cola.\n\
  • H.- Ayuda.\n\
  • S.- Salir.";

  iniciacion(pg, argc, argv);
  dispatcher( menu,
              opcionesvalidas,
              pg,
              pfun);
  terminacion(pg);
  puts("\n\nThat's all folks!\n");
  return 0;
}

/*
  Hacemos uso de la biblioteca listaenlazada.c
*/
void dispatcher( char * pm, char * ov[], Global * pg, pfuncion pf[])
{
  char * temp = NULL;         /* Para leer la instrucción */
  int instruccion;           /* dada por el usuario                      */
  int num_opciones = 0;
  int i;

  /* Recuento de opciones */
  while(pf[num_opciones] != NULL)
    num_opciones++;
  /* Bucle principal de ejecución */
  do
    {
      printf("%s ", pm);
      temp = sgets();
      instruccion = -1;
      /*
        Ahora se busca la instrucción dada entre las posibles instrucciones
        válidas. De este modo se halla el número de instrucción solicitado,
        que servirá como índice de función. Si no se encuentra la instrucción,
        el índice no es válido y se llama a volver, que no hace nada,
        y siempre es la última opción.
      */
      for(i=0;i<num_opciones;i++)/* Ojo a las instrucciones vacías */
        if(0==strcasecmp(ov[i],temp))
          {
            instruccion = i;
            break;
          }
      system(BORRAR);
      if (-1 != instruccion)
        pf[instruccion](pg);
      else
        printf("%c", 7);
      free(temp);
      temp = NULL;
    }
    while (&salir != pf[instruccion]);

} /* Fin de dispatcher() */

void iniciacion(Global * pg, int argc, char * argv[])
{
    pg->lista = malloc(sizeof(Lista));
    pg->lista->ppio = NULL; /* Al comenzar NO hay nodos */
    pg->lista->fin = NULL;   /* Al comenzar NO hay nodos */
}

void terminacion(Global * pg)
{
    borrar_lista(pg->lista); /* Aunque no es preciso, liberamos todos los nodos
                     de la lista. En una base de datos, sería preciso
                     ofrecer la opción de guardar la información
                     en disco.
                  */
}

void volver(struct Global * pg)
{
  return;
}
void ayuda(Global * pg)
{
  /* Vamos a mostrar los valores y direcciones de todas
  las variables (y nodos) del programa.*/
  Nodo * temp;
  Lista * pl = pg->lista;
  printf("\n\nProceso de ayuda.\n\n");
  printf("\n\npg vale        : $%p\n", pg);
  printf("pl->ppio vale  : $%p\n", pl->ppio);
  printf("pl->fin vale   : $%p\n", pl->fin);
  if (NULL == pl->ppio)
    {
      /* La lista está vacía */
      printf("\n\nLa cola está vacía.\n\n");
    }
  else
    {
      printf("\n\nContenido de la cola (izquierda primero).\n\n");
      temp = pl->ppio;
      do {
        printf("Dir. nodo: $%p - Valor almacenado: %d - Dir. nodo siguiente: $%p\n",
          temp, temp->valor,temp->sig);
        temp = temp->sig;
      } while (temp); /* En el último elemento, el campo sig es cero */
      printf("\n\n");
    }
}
void salir(Global * pg)
{

  /* Si hubiera cambios que guardar, este sería el lugar */
  return;
}

/*
  Solo necesitamos las opciones 1, 5, 7, 8, Ayuda y Salir
*/
void opcion_1(Global * pg)
{
  insertar_ppio(pg->lista);
}

void opcion_5(Global * pg)
{
  borrar_final(pg->lista);
}

void opcion_7(Global * pg)
{
  ver_lista(pg->lista);
}

void opcion_8(Global * pg)
{
  borrar_lista(pg->lista);
}
Comentarios finales


Esta última versión del listaenlazada.c es un ejemplo de lo que deben ser las bibliotecas construidas por el programador con vistas a su reutilización posterior. Las funciones y estructuras de datos construidas son independientes del exterior (salvo el uso de utiles.c ). En particular, listaenlazada.c es independiente de esta versión del programa núcleo, y se puede utilizar en cualquier otro programa sin más dificultad que modificar la estructura de datos Nodo , y las funciones leer_nodo() y escribir_nodo() . Sería sencillo añadir un iterador llamado pasivar() y otro llamado activar() , que grabarían y leerían, respectivamente, toda la lista en disco. De este modo tenemos una herramienta flexible para el almacenamiento de cantidades casi arbitrarias de información.