Son aquellas cuyos elementos están distribuidos en la memoria del ordenador (en el montículo) de forma no contigua. Para estas estructuras, malloc(), calloc(), realloc() y free() juegan un papel clave en su mantenimiento. Se suelen usar registros donde uno o varios de sus campos son punteros, sirviendo de enlace entre los elementos:

typedef struct mi_estruct
{
   tipo campo;
   mi_estruc *siguiente;
} Estructura1;

La abstracción es un mecanismo definido como la capacidad de manejar objetos y situaciones concentrándonos sólo en la esencia de los mismos. Los T.A.D. constituyen una forma de generalizar y encapsular los aspectos más importantes de la información que manejamos dentro del programa, olvidando hasta el momento de la implementación como se va a representar esa información dentro del ordenador.

El T.A.D. se puede ver como un conjunto de valores y operaciones que se definen independientes de su implementación, para la que se utilizará uno de los tipos de datos básicos (ya sean enlazados, simples, etc.). Los T.A.D. definen un nuevo modelo de dato independiente de su representación real en memoria, con sus operaciones relacionadas definidas, también, de forma abstracta. Esto permite que pueda ser reutilizado luego en otros programas.

• Un TAD es una secuencia de valores, así como las operaciones definidas sobre ellos.
• La definición de TAD puede dividirse en 2 niveles:
  • Un 1er nivel superficial donde se define el TAD y las operaciones sobre el con poco detalle.
  • Un 2o nivel donde se profundiza en la definición del TAD y en la implementación de sus operaciones.
  • Esta implementación suele estar oculta posteriormente, de modo que se ubicará en un módulo independiente.
  • A futuros programadores sólo hay que especificarle el nombre del TAD y de las operaciones definidas sobre él.

Ejemplo: Un TAD es una fecha (int[3]) y sus funciones de manipulación (Crear, Distancia, Dia…).

Los TAD se dividen en:

Son aquellas estructuras abstractas de datos en que cada elemento tiene como mucho dos elementos adyacentes (posterior y/o anterior), como las pilas, colas y listas. La relación entre cada elemento es pues anterior-posterior, y desde un elemento cualquiera sólo se puede acceder a uno de estos 2 como máximo.

Son aquellos cuyos elementos pueden tener más de 2 adyacentes, a los que pueden acceder directamente (no tiene sentido el concepto de anterior/siguiente), como los árboles o grafos.

Es un TAD que se caracteriza por el modo de acceso a sus elementos. En estas pilas, el último elemento en añadirse es el primero en liberarse. No existe un método de acceso directo a cualquier elemento de la pila, sino que para acceder a uno de ellos es necesario desapilar los anteriores (los que estén "por encima" de éste). Las pilas son estructuras de tipo LIFO (Last Input First Output). Llevan asociados una variable llamada cima que indica la posición del último elemento apilado.

      |        |
      |        |
      |        |
      |        |
      |        |
      |--------| <- CIMA
      |   23   |   Elem 2
      |--------|
      |   15   |   Elem 1
      |--------|
      |   99   |   Elem 0
      ----------

Ej: un montón de platos.

/*--- algunas definiciones ---*/
#define TipoDatoPila  int
#define MAX_PILA 100
 
/*--- estructura utilizada ---*/
typedef struct
{
   TipoDatoPila ElementoPila[MAX_PILA];
   int cima;
}  Pila;
 
 
/*--- inicialización: poner la cima a -1 (no hay datos) ---*/
void InicializaPila( Pila *pila )
{    pila->cima = -1;  }
 
 
/*--- pila vacia: chequea si la pila está vacía mirando la cima ---*/
int PilaVacia( Pila *pila )
{
    if ( pila->cima == -1 )  return(1);
   return(0);  
}
 
 
/*--- Apilar: si no hemos llegado al límite, aumentar la cima y dejar allí el elemeno nuevo ---*/
int Apilar( Pila *pila, TipoDatoPila elemento )
{
   if ( pila->cima == MAX_PILA-1 )  return(0);
   pila->cima = pila->cima+1;
   pila->ElementoPila[pila->cima] = elemento;
   return(1);
}
 
 
/*--- Desapilar: si la pila no está vacía, tomar el elemento de la cima y decrementar la cima ---*/
TipoDatoPila Desapilar( Pila *pila )
{
   TipoDatoPila x;
 
   if( PilaVacia( pila ) == 1 )  return(0);
   x = pila->ElementoPila[pila->cima]
   pila->cima = pila->cima-1;
   return( x );
}

/*--- algunas definiciones ---*/
#define TipoDatoPila  int
 
typedef struct DatoPila
{
   TipoDatoPila dato;
   struct DatoPila *anterior;
}  ElementoPila;
 
typedef struct
{
   ElementoPila *cima;
} Pila;
 
/*--- inicialización: poner la cima a NULL (no hay datos) ---*/
void InicializaPila( Pila *pila )
{    pila->cima = NULL;  }
 
/*--- pila vacia: chequea si la pila está vacía mirando la cima ---*/
int PilaVacia( Pila *pila )
{
    if ( pila->cima == NULL )  return(1);
   return(0);  
}
 
/*--- Apilar: pedir memoria para un nuevo elemento y ponerlo en la cima ---*/
int Apilar( Pila *pila, TipoDatoPila elemento )
{
   ElementoPila *nuevo;
   nuevo = (ElementoPila *) malloc(sizeof(ElementoPila));
   if( nuevo == NULL ) Error();
 
   nuevo->dato = elemento;
   nuevo->anterior = pila->cima;
   pila->cima = nuevo;
}
 
/*--- Desapilar: si la pila no está vacía, tomar el elemento,
     enlazar la cima con el anterior y liberar mem ---*/
TipoDatoPila Desapilar( Pila *pila )
{
   ElementoPila *borrar;
   TipoDatoPila x;
 
   if( PilaVacia( pila ) == 1 )  return(0);
   borrar = cima->pila;
   x =pila->cima->dato;
   pila->cima = pila->cima->anterior;
   free( borrar );
   return( x );
}

• El gestor de programas del S.O. utiliza la pila para guardar momentáneamente los parámetros y dirección de retorno de la función que se está procesando actualmente.

• La pila también puede utilizarse para la resolución de expresiones algebráicas, pasando las expresiones a notación infija y evaluándolas de este modo, mucho más sencillo.

Son un TAD formados por una sencuencia de elementos, caracterizados porque sus elementos se insertan por un extremo y se extraen por el extremo opuesto (el primer elemento en insertarse es el primero en extraerse, o FIFO).

        -------------------------------
 <-     | 23 | 21 | 31 | 12 | 99 | 02 |  <-
        -------------------------------
    Cabeza                                 COLA
(lugar de extraccion)             (Lugar de insercion)

#define TipoDatoCola  int
#define MAX_COLA 100
 
typedef struct
{
   TipoDatoCola ElementoCola[MAX_COLA];
   int inicio, final;
}  Cola;
 
void InicializaCola( Cola *cola )
{    cola->inicio = cola->final = -1;  }
 
int ColaVacia( Cola *cola )
{
    if ( cola->inicio == cola->final)  return(1);
   return(0);  
}
 
int Encolar( Cola *cola, TipoDatoCola elemento )
{
   if ( cola->final == MAX_COLA-1 )  ErrorColaLlena();
   cola->final=cola->final+1;
   cola->ElementoCola[cola->final] = elemento;
}
 
TipoDatoCola Desencolar( Cola *cola )
{
   TipoDatoCola x;
   if( ColaVacia( cola ) == 1 )  ErrorColaVacia();
   cola->inicio = cola->inicio+1;
   x = cola->ElementoCola[cola->inicio]
   return( x );
}

Tras varias operaciones de inserción sobre la cola llegará un punto en que final llegará a MAX_COLA-1 y obtendremos mensajes de cola llena, así como cuando eliminemos elementos (donde aumentaremos el inicio de la cola), no pudiendo reaprovechar el espacio libre. Para evitar esto se usan las COLAS CIRCULARES, un tipo especial de cola que actúa como si el vector fuese una estructura circular (es decir, cuando no existen más casillas libres del vector a la derecha, sigue insertando elementos al principio). Las funciones Encolar y Desencolar quedan:

int Encolar( Cola *cola, TipoDatoCola elemento )
{
  int sigfinal;
   sigfinal = (cola->final+1) % MAX_COLA;
   if ( sigfinal == cola->inicio  )  ErrorColaLlena();
   cola->final=sigfinal;
   cola->ElementoCola[sigfinal] = elemento;
}
 
TipoDatoCola Desencolar( Cola *cola )
{
   TipoDatoCola x;
   if( ColaVacia( cola ) == 1 )  ErrorColaVacia();
   cola->inicio = (cola->inicio+1) % MAX_COLA;
   x = cola->ElementoCola[cola->inicio]
   return( x );
}

Mediante el operador módulo (%), obtenemos los equivalentes en el inicio y final de la cola.

#define TipoDatoCola int
 
typedef struct DatoCola
{
   TipoDatoCola dato;
   struct DatoCola *siguiente;
}  ElementoCola;
 
typedef struct
{
   ElementoCola *inicio, *final;
} Cola;
 
/*--- inicialización de la cola poniendo inicio y final a NULL 
           y chequeo de si está vacia o no--- ---------------------*/
void InicializaCola( Cola *cola )
{   cola->inicio = cola->final = NULL; }
 
int ColaVacia( Cola *cola )
{    if ( cola->inicio == NULL )  return(1);  else   return(0);   }
 
 
/*--- Encolar: consiste en pedir memoria para un nuevo elemento, copiando
          en él los datos, y poniendo siguiente a NULL (es el último de la cola). 
         Después se hace que el último elemento de la cola apunte al nuevo, 
           así como el final de la cola - --------------------------*/
int Encolar( Cola *cola, TipoDatoCola elemento )
{  
   ElementoCola *nuevo;
 
   nuevo = (ElementoCola *) malloc( sizeof(ElementoCola ));
   if( nuevo == (ElementoCola *) NULL ) ErrorObtMemoria();
 
   nuevo->dato = elemento;
   nuevo->siguiente = NULL;
 
   if( ColaVacia(cola) )   cola->inicio = cola->final = nuevo;
   else
   {
       (cola->final)->siguiente = nuevo;
       cola->final = nuevo;
   }
}
 
/*--- Desencolar: Coger el inicio de la cola, hacer que su siguiente
           sea el nuevo inicio, y liberar su mem asignada--------------*/
TipoDatoCola Desencolar( Cola *cola )
{
   ElementoCola *borrar;
   TipoDatoCola elemento;
   if( ColaVacia( cola ) == 1 )  return(0);
 
   borrar = cola->inicio;
   elemento = borrar->dato;
 
   cola->inicio = (cola->inicio)->siguiente;
   free(borrar);
   return(elemento);
}

Las colas se suelen utilizar en los sistemas operativos para controlar las Prioridades de los Procesos (Colas de…), o en las impresoras (cola de impresión donde se almacenan las peticiones de impresión de documentos que van llegando).

Son TAD en las que los elementos están organizados siguiendo un orden secuencial. Cada elemento tiene un anterior y un siguiente en la lista. En las listas genéricas (no así en colas o pilas, que son casos especiales de listas) no existe una restricción en la localización de los elementos insertados o extraídos. Son estructuras mucho más flexibles, donde tanto la inserción como eliminación pueden darse en cualquier posición de la lista.

  Inicio                                 Final (apunta a NULL)
     ------    ------    ------    --------
     | 23 |--->| 12 |--->| 11 |--->| 99 |\|
     ------    ------    ------    --------

Si la lista de implementara de manera estática, la eliminación o inserción de un elemento supondría la reorganización (movimiento) del resto de elementos del vector. La implementación enlazada es mucho más eficiente, y mediante ella podemos construir Listas Simplemente Enlazadas (cada elemento tiene acceso al siguiente), Listas Doblemente Enlazadas (cada elemento tiene acceso al anterior y al siguiente) o Listas Circulares (el último elemento tiene acceso al inicio de la lista).

typedef struct DatoLista
{
   TipoDatoLista dato;
   struct DatoLista *siguiente;
}  ElementoLista;
 
typedef struct
{
   ElementoLista *inicio;
} Lista;
 
 
void InicializaLista( Lista *lista )
{    lista->inicio = NULL;  }
 
int ListaVacia( Lista *lista )
{
   if ( lista->inicio == NULL )    return(1);
   return(0);
}
 
ElementoLista *LocalizarNodoEnLista( Lista *lista, TipoDatoLista x )
{
   ElementoLista *aux;
 
   aux = lista->inicio;                  /* nos ponemos al inicio de la lista */
   while( aux!=NULL )                    /* mientras no lleguemos al final... */
   {
      if( aux->dato == x )               /* comprobamos si el dato coincide con el actual */
            return( aux );               /* si, lo devolvemos */
      aux = aux->siguiente;              /* no, vamos al siguiente elemento */
   }
   return(NULL);                         /* si llega aqui es que no lo encontró */
}
 
ElementoLista* LocalizarNodoEnListaOrdenada( Lista *lista, TipoDatoLista x )
{
   ElementoLista *aux, *anterior=NULL;
 
   aux = lista->inicio;
 
   /* buscar hasta el final o hasta encontrar uno > que el buscado */
 
   while( aux!=NULL &amp;&amp; aux->dato<=x)
   {
      anterior = aux;
      aux = aux->siguiente;
   }
 
   /* si es distinto de NULL y es igual al buscado -> encontrado */
 
   if( aux!= NULL &amp;&amp; aux->dato == x )
     return(aux);
 
   /* si no, hemos encontrado el hueco donde deberia estar este dato */
  else
     return(anterior);
}
 
 
/*--------------------------------------------------------------*/
int InsertarEnLista( Lista *lista, TipoDatoLista dato,  ElementoLista *donde )
{
   ElementoLista *nuevo;
 
   nuevo = (ElementoLista *) malloc( sizeof(ElementoLista) );
   if( nuevo == NULL ) ErrorMemoria();
 
   /* copiamos los datos deseados al campo clave del nuevo nodo */
   nuevo->dato = dato;
 
   /* si la lista esta vacia o va al principio de la misma -> */
   if( ListaVacia(lista) || donde == NULL )
   {
      nuevo->siguiente = lista->inicio;
      lista->inicio = nuevo;
   }
   else
   {
      nuevo->siguiente = donde->siguiente;
      donde->siguiente = nuevo;
   }
   return(1);
}
 
 
/*--------------------------------------------------------------*/
ElementoLista *InsertarEnListaOrdenada( Lista *lista, TipoDatoLista dato )
{
   ElementoLista *donde;
 
    donde = LocalizarHuecoParaNodoEnListaOrdenada( lista, dato.nombre );
    InsertarEnLista( lista, dato, donde );
    return( donde );
}
 
 
/*--------------------------------------------------------------*/
int EliminarNodoLista( Lista *lista, ElementoLista *nodo )
{
   ElementoLista *aux;
   if( ListaVacia( lista ) || nodo == NULL )
      return(0);
 
  /* comprobamos si nodo es el inicio de la lista */
   if( nodo == lista->inicio )
   {
 
      /* si lo es, lo eliminamos y ponemos inicio=siguiente) */
      lista->inicio = (lista->inicio)->siguiente;
      free( nodo );
   }
 
  /* en caso normal, localizamos el elemento anterior y borramos */
  else
   {
      aux = lista->inicio;
      while( aux->siguiente != nodo  &amp;&amp;  aux->siguiente!= NULL)
         aux = aux->siguiente;
 
      /* si no encontramos el elemn anterior, devolver error() */
      if( aux->siguiente==NULL )
         return(2);
 
     /* eliminar el nodo especificado */
      aux->siguiente = nodo->siguiente;
      free(nodo);
   }
   return(1);
}

<Volver a la sección de Tutoriales de Programación>