Los tipos de datos son los enteros, reales, valores booleanos y todos los objetos. Un tipo de datos es abstracto cuando los programadores pueden trabajar con él conociendo sólo sus operaciones. Uno puede abstraerse de su implementación y utilizarlos exitosamente.
La abstracción es importante para poder disminuir la complejidad de los problemas que se enfrentan. Sin embargo, también es útil conocer aspectos de la implementación de los tipos de datos con los que se trabaja y por ello estudiamos como se representaban los números reales. Esto nos permite entender mejor sus limitaciones.
Una lista enlazada es una estructura de datos que se visualiza como una cadena de eslabones que termina con una referencia nula. Cada eslabón se representa por medio de las siguiente estructura:
struct Eslabon
{
...
struct Eslabon *prox;
};
Lo que caracteriza al eslabón como una estructura de datos recursiva es que entre las variables se encuentra una referencia a un objeto del mismo tipo.
Junto con poseer una referencia del próximo eslabón en la cadena, se colocan variables en la estructura para almacenar datos concerniente al problema que se pretende resolver. Por ejemplo:
struct Eslabon
{
char s[10];
struct Eslabon *prox;
};
struct Eslabon *primero; /* Referencia global al primero de la lista */
Si por ejemplo queremos saber cuantos eslabones tiene la lista, la única forma es recorriendola completamente:
int cuenta()
{
struct Eslabon e= primero;
int cont=0;
while (e!=NULL)
{
e = e->prox;
cont++;
}
return cont;
}
En el nuevo eslabón se coloca el string que se agrega a la lista. Esto no es trivial porque la estructura no contiene ningún puntero hacia el final. Por lo tanto hay que recorrerla hasta encontrar el último eslabón:
void agregaalfinal(char s[])
{
if (primero==NULL)
{
/* SE CREA UN NUEVO ESLABON */
primero= (struct Eslabon *) malloc (sizeof(struct Eslabon));
/* Y SE COPIA EL CONTENIDO */
strcpy(primero->s,s);
}
else
{
struct Eslabon *e= primero;
/* LA RECORREMOS HASTA CASI EL FINAL */
while (e->prox!=NULL) e= e->prox;
/* SE CREA UN NUEVO ESLABON */
e->prox= (struct Eslabon *) malloc (sizeof(struct Eslabon));
/* Y SE COPIA EL CONTENIDO */
strcpy(e->prox->s,s);
}
}
Observe que el caso en que la cola está vacía es un caso de borde, porque en ese caso el eslabón debe ser referenciado por la variable primero.
Propuesto:¿Cómo se agrega al principio de una lista?
Hay que tener en cuenta la condición de si se elimina el primer eslabón o se elimina cualquiera de los otros, para eliminar el primer eslabón se necesita un tratamiento especial.
void eliminar(char key[])
{
if (strcmp(primero->s,key)==0) /* Se elimina el primero */
{
primero = primero->prox;
}
else
{
struct Eslabon e=primero;
/* SE UTILIZA UNA MODIFICACION DE RECORRER LA LISTA */
while (e->prox != NULL && strcmp(e->prox->s,key)!=0) e = e->prox;
/* ESTAMOS O AL FINAL O JUSTO ANTES DEL ESLABON BUSCADO */
/* SI ESTAMOS AL FINAL SALIMOS */
if (e->prox == NULL) return;
/* SINO, SACAMOS EL ESLABON */
e->prox = e->prox->prox;
}
}
Propuesto: ¿Cómo eliminar la condición de borde al insertar al principio?
Estos son los patrones de programación utilizados en Listas Enlazadas:
Problema Resuelto:
El tipo de dato arreglo asociativo de strings con llaves enteras es un tipo de dato parecido al arreglo de strings, sólo que en vez de “numerar” las celdas de 0 a n-1 para recuperar los datos podemos asignarle a cada string una “llave”, para así buscar y recuperar más rápidamente.
La solución a esta estructura de datos la llamaremos MAP y su implementación será mediante listas enlazadas. En la figura se observa la estructura de una arreglo asociativo que posee las asociaciones (2, "hola"), (5, "que") y (3, "tal").
Pregunta:
¿Para qué es el
eslabón falso?
Observe que el orden en que se organiza la lista enlazada es irrelevante. El eslabón que contiene la llave 2 podría haber quedado perfectamente después del eslabón de la llave 5 sin alterar el contenido formal del arreglo asociativo. El orden en que quedarán almacenadas las llaves depende únicamente del orden en que se hagan las asociaciones.
Por lo tanto, la estructura de representación de la estructura EslabónM y su referencia primero será:
struct EslabonM
{
int llave;
char val[10];
struct EslabonM *sgte;
}
struct eslabonM *primero;
Para implementar la operación get se usa el patrón de recorrido de la lista enlazada. Al hacer la búsqueda de la llave no se necesita visitar el eslabón falso por lo tanto el recorrido de los eslabones comienza por el segundo eslabón:
char *getString(int llave)
{
struct EslabonM *e= primero->sgte;
while (e!=null)
{
if (e->llave==llave) return e->val;
e= e->sgte;
}
return NULL; /* NO ESTA LA LLAVE */
}
La búsqueda termina cuando se encuentra la llave especifica o cuando se acaba la lista enlazada. En este último caso el programa entrega NULL. También se necesita hacer este mismo recorrido con la operación put. Si la llave existe se modifica el valor en el mismo eslabón. Si la llave no existía previamente en la lista enlazada, se crea un nuevo eslabón para esa llave y se agrega por conveniencia justo después del eslabón falso:
void put(int llave, char val[])
{
struct EslabonM *e= primero->sgte;
while (e!=null)
{
if (e.llave==llave) /* La llave existe */
{
strcpy(e->val,val);
return;
}
e= e->sgte;
}
/*
La llave no existía previamente
Creamos un nuevo eslabon y lo agregamos entre el eslabon
falso y el segundo eslabon, es decir, insertamos “al principio”
*/
e = (struct EslabonM *) malloc (sizeof (struct Eslabon));
strcpy(e->val,val);
e->llave=llave;
e->sgte=primero->sgte;
primero->sgte= e;
}
La siguiente figura muestra el caso en que la llave ya existía previamente en el arreglo asociativo:
Propuesto: Verifique que las dos operaciones funcionan correctamente cuando el arreglo asociativo se encuentra vacío (cuando la lista enlazada sólo contiene el eslabón falso).
La operación remove elimina una asociación en el arreglo asociativo. Esto equivale a eliminar el eslabón que contiene la llave especificada.
El primer intento de implementación que viene a la mente consiste en usar el patrón de recorrido de los eslabones para buscar la llave que se desea eliminar. Sin embargo, este patrón no sirve porque cuando se encuentre la llave, la variable sgte que hay que modificar se encuentra en el eslabón visitado en la iteración anterior. Pero este eslabón ya se visitó y no es posible volverlo a recorrer si comenzar por el primer eslabón.
Para resolver el problema, modificamos ligeramente el patrón de recorrido de modo de mantener en la variable anterior el eslabón visitado en la iteración anterior. La siguiente figura muestra cómo realizar la eliminación del eslabón utilizando la variable anterior:
El código para eliminar una llave del arreglo asociativo es entonces:
void remove(int llave)
{
struct EslabonM *anterior= primero;
struct EslabonM *proximo= primer->sgte;
while (proximo!=null && proximo->llave!=llave)
{
anterior= proximo;
proximo= proximo->sgte;
}
if (proximo==null) /* la llave no existe en el arreglo asociativo */
return;
/*
La llave si existe, por lo que se elimina el eslabon
referenciado por proximo
*/
anterior.sgte= proximo.sgte;
}
La eliminación es una operación frecuente con las listas enlazadas, por lo que este trozo de código constituye un patrón de programación. Estúdielo cuidadosamente.